هوش مصنوعی (فصل سوم: عامل های حل مسئله)

هوش مصنوعی (فصل سوم: عامل های حل مسئله)

اسلاید 1: فصل سومعامل هاي حل مسئلهAlireza yousefpouryousefpour@shomal.ac.ir

اسلاید 2: فصل سوم: حل مسئلهعامل هاي حل مسئلهProblem Solving Agentروشهاي حل مسئله يا تکنيک هاي مختلف در هوش مصنوعي جهت ساخت لايه:4. استفاده از دانش 2. تقليل مسئله1. جستجوي فضاي حالتState Space SearchProblem ReductionKnowledge Base3. با ارضاي محدوديتConstraint Satisfaction Problem

اسلاید 3: فصل سوم: جستجوجستجو (Search) :فرآيند اول: فرموله سازي هدف (Goal Function)هدف براي عامل کاملاً مشخص مي شود و به عبارت ديگر اهدافي که عامل سعي در رسيدن به آنها را دارد محدود و مشخص مي شوندفرآيند دوم: فرموله سازي مسئله (Problem Formulation)فرآيندي که تصميم مي گيرد چه عملياتي جهت رسيدن به هدف در نظر گرفته شود

اسلاید 4: فصل سوم: جستجوپس از مشخص نمودن اين دو فرآيند، عامل دنباله اي از اعمال را براي رسيدن به هدف مي يابد که به اين پروسه Search گفته مي شودمسير جستجويعني فرآيند جستجو را مي توان مانند يک درخت جستجو در نظر گرفت ريشه درخت يک گره است که با حالت اوليه مسئله مطابقت دارد. استراتژي جستجو گره اي را از درخت به منظور گسترش انتخاب مي کند که اين کار تا رسيدن به هدف ادامه مي يابد و بدين صورت درخت جستجو تشکيل مي گرددعامل حل مسئله داراي مراحل << فرموله سازي – جستجو – اجرا >> مي باشد

اسلاید 5: فصل سوم: جستجوي فضاي حالت1. جستجو در فضاي حالتState Space Searchبراي حل مسئله p به روش جستجو از طريق فضاي حالت بايد پارامترهاي زير مشخص شوند: وضعيت ابتدايي مسئله (Initial State) عملگرها (Operators) – تابع مابعدشامل تعريف مسئله ، واقعيتها ، فرضيات و دانسته هاستمجموعه اي از عمليات که براي عامل قابل دسترسي باشد – عامل توليد فضاي جستجو  فرموله سازي مسئله

اسلاید 6: فصل سوم: جستجوي فضاي حالت (ادامه ... ) وضعيت هدف g (Goal State – Goal Test) تابع هزينه مسير (Path-cost Function)شامل بخشي از مسئله است که نتيجه و پاسخ در آنجا مشخص است  فرموله سازي هدفتابعي که براي هر مسير هزينه اي را در نظر مي گيرد که مجموع هزينه ها در طول مسير از مبداء تا گره جاري

اسلاید 7: فصل سوم: جستجوي فضاي حالت - مثال اولمثال 1 :مسئله: مرتب سازي يک آرايه سه عنصري A[1..3]={0 , 2 , 1} به صورت صعودي وضعيت ابتدايي وضعيت هدف g تابع هزينه مسير عملگرها آرايه A[ ] = {0 , 2 , 1}جابجايي دو عنصر وضعيتي که در آن به ازاي هر دو عنصر مجاور در آرايه عنصر سمت چپ از عنصر سمت راست کوچکتر يا مساوي باشد هر عمل ارزش يک داردSwap( A1 , A2 ) , Swap( A1 , A3 )Swap( A2 , A1 ) , Swap( A2 , A3 )Swap( A3 , A1 ) , Swap( A3 , A2 )

اسلاید 8: فصل سوم: جستجوي فضاي حالت - مثال اول021201120012201210012وضعيت هدفالگوريتم جستجو همين جا متوقف مي شود و راه حل (مسير جواب) را ارائه مي دهدمتناظر با يک عملگروضعيتي از مسئله- درخت جستجو

اسلاید 9: فصل سوم: جستجوي فضاي حالت- روش تشکيل درخت جستجوجستجوي در فضاي حالت از وضعيت ابتدايي شروع کرده و اقدام به توليد فضاي جستجو (درخت جستجو) مي نمائيم بدين صورت که عملگرها را به وضعيت ابتدايي اعمال کرده و وضعيت هاي جديد مسئله توليد مي شود و وضعيت جديد مسئله نيز مجدداً تحت تاثير عملگر قرار مي گيرد. توليد درخت جستجو تا آنجايي ادامه پيدا مي کند که : شرح کلي اين روش: 2.درخت جستجو کاملا توليد شده ولي هدف در آن ديده نمي شود در اين صورت مسئله پاسخ ندارد. 1. به وضعيتي برسيم که هدف است در اين صورت راه حل ارئه مي شود

اسلاید 10: فصل سوم: جستجوي فضاي حالت – ساختار درخت جستجوساختمان داده براي درخت جستجو :يگ گره به عنوان ساختار داده: وضعيتي که گره در فضاي حالت داراست گره والد عملگري که براي توليد گره بکار رفته است عمق گره هزينه مسير ( از حالت اوليه تا گره )

اسلاید 11: فصل سوم: جستجوي فضاي حالت – مثال دوممثال 2 :مسئله: دنياي جارو برقي با دو خانه مجاور وضعيت ابتدايي وضعيت هدف g تابع هزينه مسير عملگرها يکي از 8 حالت ممکن 1. حرکت به سمت چپ  Lوضعيتي از مسئله که در آن هيچ يک از چهار خانه ها خاکي نداشته باشدفرض هر عمل ارزش يک داشته باشد 3. عمل مکش  S 2. حرکت به سمت راست  R

اسلاید 12: فصل سوم: جستجوي فضاي حالت – مثال دوم8 وضعيت ممکن مسئله :

اسلاید 13: فصل سوم: جستجوي فضاي حالت – مثال دومگراف کامل: دنياي جاوبرقيبا سه عملگرفضاي حالت

اسلاید 14: فرض: در مثال دنياي جاروبرقيوضعيت ابتداييLLSRRS حالت تکراريحالت تکراري وضعيت هدففصل سوم: جستجوي فضاي حالت – درخت جستجو مثال دوم

اسلاید 15: فصل سوم: جستجوي فضاي حالت – درخت جستجو مثال دومفرض: در مثال دنياي جاروبرقيLLSRRS حالت تکراريحالت تکراري وضعيت هدفمسير پاسخ يا راه حل مسئله

اسلاید 16: فصل سوم: جستجوي فضاي حالت – مثال سوممثال3- معماي 8Start StateGoal State وضعيت ابتدايي وضعيت هدف g تابع هزينه مسير عملگرها هر قدم ارزش 1 دارد، بنابراين هزينه مسير همان طول مسير است.وضعيتي از مسئله که با ساختار هدف مطابقت مي‌کند. هر حالتي را ميتوان به عنوان حالت اوليه در نظر گرفت- اگر سمت چپ خانه i خالي باشد حرکت به سمت چپ- اگر سمت راست خانه i خالي باشد حرکت به سمت راست- اگر سمت بالا خانه i خالي باشد حرکت به سمت بالا- اگر سمت پايين خانه i خالي باشد حرکت به سمت پايين

اسلاید 17: مثال3- معماي 8Start StateGoal State وضعيت ابتدايي وضعيت هدف g تابع هزينه مسير عملگرها هر قدم ارزش 1 دارد، بنابراين هزينه مسير همان طول مسير است.وضعيتي از مسئله که با ساختار هدف مطابقت مي‌کند. هر حالتي را ميتوان به عنوان حالت اوليه در نظر گرفت- اگر سمت چپ خانه i خالي باشد حرکت به سمت چپ- اگر سمت راست خانه i خالي باشد حرکت به سمت راست- اگر سمت بالا خانه i خالي باشد حرکت به سمت بالا- اگر سمت پايين خانه i خالي باشد حرکت به سمت پايينبه ازاي هر i مي تواند اعداد 1 تا 8 قرار گيرد پس جمعاً 32 عملگر داريم آيا مي توان عملگر ها را محدود کنيم ولي همان درخت جستجو را داشته باشيم؟1- اگر سمت چپ خانه خالي ، عدد باشد حرکت خانه خالي به سمت چپ2- اگر سمت راست خانه خالي ، عدد باشد حرکت خانه خالي به سمت راست3- اگر سمت بالا خانه خالي ، عدد باشد حرکت خانه خالي به سمت بالا4- اگر سمت پايين خانه خالي ، عدد باشد حرکت خانه خالي به سمت پايينفصل سوم: جستجوي فضاي حالت – مثال سوم

اسلاید 18: فصل سوم: استراتژي هاي جستجو در فضاي حالتاستراتژي هاي جستجو استراتژي جستجو چگونگي گسترش درخت جستجو را مشخص مي کنندسوال: در درخت جستجو کدام گره براي بسط بايد انتخاب شود؟انواع استراتژي هاي جستجو :  استراتژي هاي جستجوي نا آگاهانه Uninformed Search استراتژي هاي جستجوي آگاهانه Informed Search

اسلاید 19: جستجوي نا آگاهانه Blind Searchيا جستجوي کورکورانهناآگاهي اين است که الگوريتم هيچ اطلاعاتي غير از تعريف مسئله در اختيار ندارداين الگوريتمها فقط ميتواند عملگرها را اعمال و وضعيتهاي جديد را توليد و هدف را از غير هدف تشخيص دهندفصل سوم: جستجوي ناآگاهانه

اسلاید 20: جستجوي سطحي جستجوي با هزينه يکنواخت جستجوي عمقي جستجوي عمقي محدود شده جستجوي عمقي تکرار شونده جستجوي دوطرفهانواع استراتژي هاي جستجوي نا آگاهانه : فصل سوم: استراتژي هاي جستجوي ناآگاهانه

اسلاید 21: معيارهاي ارزيابي : 1) کامل بودن: (Completeness)2) بهينه بودن: (Optimality)3) پيچيدگي زماني: (Time Complexity)4) پيچيدگي مکاني: (Space Complexity)چقدر طول ميکشد تا راه حل را پيدا کند؟ تعداد گره هاي توليد شده در اثناي جستجوبراي جستجو چقدر حافظه نياز دارد؟ حداکثر تعداد گره هاي ذخيره شده در حافظهدر صورت وجود راه حل آيا بهترين راه حل است يا نه؟در صورت وجود راه حل آيا استراتژي قادر به پيدا کردن راه حل است؟فصل سوم: استراتژي هاي جستجوي ناآگاهانه - ادامه

اسلاید 22: فصل سوم: استراتژي جستجوي سطحي 1- جستجوي سطحي –جستجوي اول سطحBreadth-First Search (BFS)ابتدا ريشه گسترش پيدا مي کند سپس فرزندان ريشه گسترش پيدا مي کنند و ....در حقيقت تمام گره ها در يک سطح d بسط (گسترش) داده مي شود و سپس گره هاي سطح بعدي d+1 گسترش داده مي شوند که براي پياده سازي اين استراتژي از تابع صف استفاده مي کنند .ABCDEFGHIJKLNMOPQفضاي حالتمثال

اسلاید 23: درخت جستجوي با استفاده از جستجوي اول سطحABCDEFGHIJKLNMOPQوضعيت هدفعمق صفرعمق يکعمق دوعمق سهفصل سوم: استراتژي جستجوي سطحي– تشکيل درخت جستجو

اسلاید 24: درخت جستجوي با استفاده از جستجوي اول سطحABCDEFGHIJKLNMOPQوضعيت هدفعمق صفرعمق يکعمق دوعمق سهمسير پاسخ يا راه حل مسئلهفصل سوم: استراتژي جستجوي سطحي– تشکيل درخت جستجو

اسلاید 25: معيارهاي ارزيابي استراتژي جستجوي اول سطح: 1) کامل بودن: 2) بهينه بودن: کامل است و کم عمق ترين گره هدف را پيدا مي کند اگر تمام هزينه عملگر ها يکسان باشد آنگاه مي توان گفت بهينه هم استدر جستجوي سطحي هميشه کم عمق ترين گره هدف پيدا مي شودآيا کم عمق ترين گره هدف، هدف بهينه است؟فصل سوم: استراتژي جستجوي سطحي– ارزيابي

اسلاید 26: 3) پيچيدگي زماني: 4) پيچيدگي مکاني: b: فاکتور انشعاب (branching factor)d: عمق گره هدف 1 + b1 + b2 + b3 + … + bd حداکثر تعداد گره هاي بسط داده شده O(bd)پيچيدگي فضا مشابه پيچيدگي زمان است، زيرا تمام گره هاي برگي درخت در يک زمان بايد در حافظه نگهداري شوندO(bd)فصل سوم: استراتژي جستجوي سطحي– ارزيابي

اسلاید 27: در اين استراتژي به جاي گسترش کم عمق ترين گره ،گره اي توسط تابع g(m) انتخاب مي شود که هزينه کمتري را دارد. اگر هزينه راه حل يکسان باشد اين الگوريتم معادل الگوريتم سطحي است.g(m) : هزينه هر گره (هزينه رسيدن از ريشه به آن گره ، يعني جمع هزينه عملگر ها تا رسيدن به آن گره2- جستجوي با هزينه يکنواختUniform-Cost Search (UCS)فصل سوم: جستجو با هزينه يکنواخت ABCDEFGHIJKLNMOPQفضاي حالتمثال

اسلاید 28: درخت جستجوي با استفاده از جستجو با هزينه يکنواختABCDEFGHILNM31142414122وضعيت هدفنکته : در صورتي که هزينه عملگرها يکسان باشند در اين صورت جستجو با هزينه يکنواخت همان جستجوي سطحي است :g(n)=DEPTH(n)فصل سوم: جستجو با هزينه يکنواخت-تشکيل درخت جستجو g(B)=1

اسلاید 29: درخت جستجوي با استفاده از جستجو با هزينه يکنواختABCDEFGHILNM31142414122وضعيت هدفنکته : در صورتي که هزينه عملگرها يکسان باشند در اين صورت جستجو با هزينه يکنواخت همان جستجوي سطحي است :g(n)=DEPTH(n)مسير پاسخ يا راه حل مسئلههزينه هدف = 4فصل سوم: جستجو با هزينه يکنواخت-تشکيل درخت جستجو

اسلاید 30: معيارهاي ارزيابي استراتژي جستجو با هزينه يکنواخت: 1) کامل بودن: 2) بهينه بودن: فصل سوم: جستجو با هزينه يکنواخت - ارزيابي بهينه است چون کم هزينه ترين گره هدف پيدا مي شودکامل است در صورتي که هزينه هر مرحله بزرگتر يا مساوي يک مقدار ثابت و مثبت ε باشد. - يعني هر عملگر هزينه غير منفي داشته باشد، سپس هزينه يک مسير با ادامه مسير، کاهش پيدا نخواهد کرد. (هزينه مسير با حرکت در مسير افزايش مي يابد)

اسلاید 31: 3) پيچيدگي زماني: 4) پيچيدگي مکاني: O(bd)پيچيدگي فضا مشابه پيچيدگي زماني است، زيرا تمام گره هاي برگي درخت در يک زمان بايد در حافظه نگهداري شوندO(bd)پيچيدگي زماني مشابه پيچيدگي زماني جستجوي اول سطح است فصل سوم: جستجو با هزينه يکنواخت - ارزيابي

اسلاید 32: فصل سوم: جستجوي عمقي اين استراتژي، يکي از گره‌ها را در پائين‌ترين سطح درخت بسط مي‌دهددر صورتي که جستجو به يک گره غير هدف بدون امکان بسط ميرسد آنوقت به سراغ گره هايي در سطوح کم عمق تر ميرود3- جستجوي عمقي – جستجوي اول عمقDepth-First Search (DFS)ABCDEFGHIJKLNMOPQفضاي حالتمثال

اسلاید 33: ABEFJKLدرخت جستجوي با استفاده از جستجوي اول عمقCDGHINOPQMوضعيت هدففصل سوم: جستجوي عمقي - تشکيل درخت جستجو فرض شود که گره هدف پيدا نشود آنگاه ادامه جستجو بدين صورت خواهد بود

اسلاید 34: معيارهاي ارزيابي استراتژي جستجوي عمقي: 1) کامل بودن: 2) بهينه بودن: فصل سوم: استراتژي عمقي - ارزيابي بهينه نيستکامل نيست، اگر زير درخت چپ عمق نامحدود داشت و فاقد هر گونه راه حل باشد، جستجو هرگز خاتمه نمي يابد3) پيچيدگي زماني: 4) پيچيدگي مکاني: O(bm)اين جستجو، نياز به حافظه نسبتاً کمي فقط براي ذخيره مسير واحدي از ريشه به يک گره برگي، و گره‌هاي باقي‌مانده بسط داده نشده دارد.O(bm)m: ماکزيمم عمق درخت

اسلاید 35: فصل سوم: مقايسه استراتژي سطحي و عمقي بررسي جستجوهاي سطحي و عمقي :فرض: برنامه اي داريم که در هر ثانيه 1000 گره را بسط مي دهد و هر گره 100 بايت فضا اشغال مي کند و با فاکتور انشعاب b=10 آنگاه در جستجوي سطحي داريم:Depth NodeTimeTimeMemoryMemory011 milliseconds100Bytes21110.1Seconds11Kilobytes411.11111Seconds1Megabytes610618Minutes111Megabytes810831Hours11Gigabyte101010128Days1Terabytes12101235Years111Terabytes1410143500Years11.111Terabytesپيچيدگي زماني و مکاني در جستجوي سطحي

اسلاید 36: با استفاده از جستجوي عمقي ميزان مصرف حافظه کاهش پيدا کرده استبراي مثال: با استفاده از مفروضات مشابه در جدول قبلي، جستجوي عمقي به جاي 111 ترابايت فقط نياز به 12 کيلو بايت در عمق 12 دارد. پس در حدود 10 بيليون بار، فضاي کمتري نياز دارد کاربرد جستجوي عمقي: براي مسائلي که راه حل زيادي دارند آنگاه جستجوي عمقي سريعتر از جستجوي سطحي عمل مي کند زيرا شانس بهتري براي يافتن راه حل در يک قسمت کوچک از کل فضا است.عيب جستجوي عمقي: مسائل زيادي هستند که فضاي حالتشان بزرگ و عمق نامحدود دارند، در اين صورت جستجوي عمقي نخواهد توانست از يک انتخاب نادرست جان سالم بدر ببردفصل سوم: مقايسه استراتژي سطحي و عمقي - ادامه فصل سوم: مقايسه استراتژي سطحي و عمقي

اسلاید 37: فصل سوم: جستجوي عمقي محدود شده 4- جستجوي عمقي محدود شدهDepth-Limited Search (DFS)مشکل استراتژي قبل افتادن در يک عمق نا محدود و يا در يک حلقه بي نهايت بود .در اين استراتژي براي برخورد با مشکل قبلي، آنگاه يک برش بر روي درخت جستجو در نظر مي گيرددر صورتي که هدف در سطح برش و يا قبل از آن وجود داشته باشد جستجو کامل خواهد بود ولي بهينه نيست و چون ممکن است در سطح پايين تر جواب داشته باشيم که هزينه کمتري دارد .L = 2ABCDEFGHIJKLNMOPQفضاي حالتمثال

اسلاید 38: ABEFJKLدرخت جستجوي با استفاده از جستجوي عمقي محدود شدهCDGHINOPQMوضعيت هدفL = 2فصل سوم:جستجوي عمقي محدودشده– تشکيل درخت جستجو

اسلاید 39: معيارهاي ارزيابي استراتژي جستجوي عمقي محدود شده: 1) کامل بودن: 2) بهينه بودن: فصل سوم: جستجوي عمقي محدود شده - ارزيابي بهينه نيست اگر L>d انتخاب شود، اين راهبرد بهينه نخواهد بود.کامل نيست، اگر L<d و سطحي ترين هدف در خارج از عمق محدود قرار داشته باشد، اين راهبرد کامل نخواهد بود.3) پيچيدگي زماني: 4) پيچيدگي مکاني: O(bL)O(bL)L: عمق محدود شده درخت

اسلاید 40: فصل سوم: جستجوي عمقي تکرار شونده 4- جستجوي عمقي تکرار شوندهIterative-Deepening Search (IDS)مشکل قبلي انتخاب يک عمق نا مناسب براي برش بوداين استراتژي انتخاب بهترين محدوده عمقي را توسط امتحان تمام محدوده ها ياد آوري مي کند. اول عمق 0 ، سپس عمق 1 ، سپس عمق 2 ، و الي آخرتا هدف مورد نظر را در صورت وجود پيدا شودABCDEFGHIJKLNMOPQفضاي حالتمثال

اسلاید 41: ABEFJKLدرخت جستجوي با استفاده از جستجوي عمقي تکرار شوندهCDGHINOPQMLimit = 0فصل سوم: جستجوي عمقي تکرارشونده- تشکيل درخت جستجو با امتحان عمق محدود شده صفر

اسلاید 42: ABEFJKLدرخت جستجوي با استفاده از جستجوي عمقي تکرار شوندهCDGHINOPQMLimit = 1فصل سوم: جستجوي عمقي تکرارشونده- تشکيل درخت جستجو با امتحان عمق محدود شده يک

اسلاید 43: ABEFJKLدرخت جستجوي با استفاده از جستجوي عمقي تکرار شوندهCDGHINOPQMوضعيت هدفLimit = 2فصل سوم: جستجوي عمقي تکرارشونده- تشکيل درخت جستجو با امتحان عمق محدود شده دو

اسلاید 44: ABEFJKLدرخت جستجوي با استفاده از جستجوي اول عمقCDGHINOPQMLimit = 3فصل سوم: جستجوي عمقي تکرارشونده- تشکيل درخت جستجو با امتحان عمق محدود شده سه

اسلاید 45: معيارهاي ارزيابي استراتژي جستجوي عمقي تکرار شونده: 1) کامل بودن: 2) بهينه بودن: بهينه است اگر هزينه تمام عملگرها يکسان باشد.کامل استاين استراتژي ترکيبي از دو استراتژي سطحي و عمقي مي باشديعني مزاياي اين دو استراتژي ها ترکيب شده پس مانند:جستجوي سطحي کامل و بهينه استجستجوي عمقي به حافظه اندکي نياز داردفصل سوم: جستجوي عمقي تکرارشونده - ارزيابي

اسلاید 46: 3) پيچيدگي زماني: 4) پيچيدگي مکاني: O(bd)O(bd)به نظر ميرسد جستجو عمقي تکرار شونده زمان زيادي را صرف ميکند؟براي بيشتر مسائل اين سرريزي بسيار کوچک است زيرا در يک درخت جستجوي نمايي، تقريباً تمام گره ها در سطح پايين قرار دارند مثال: براي b=10 و عمق d=5 داريم:1 + b1 + b2 + b3 + … + bd 111111 = 100000 + 10000 + 1000 + 100 + 10 + 11(d+1) + b1(d) + b2(d-1) + b3(d-2) + … + bd(1) در جستجوي عمقيدر جستجوي عمقي تکرار شونده123456 = 100000 + 20000 + 3000 + 400 + 50 + 6فصل سوم: جستجوي عمقي تکرارشونده - ارزيابي

اسلاید 47: 3) پيچيدگي زماني: 4) پيچيدگي مکاني: O(bd)O(bd)به نظر ميرسد جستجو عمقي تکرار شونده زمان زيادي را صرف ميکند؟براي بيشتر مسائل اين سرريزي بسيار کوچک است زيرا در يک درخت جستجوي نمايي، تقريباً تمام گره ها در سطح پايين قرار دارند مثال: براي b=10 و عمق d=5 داريم:1 + b1 + b2 + b3 + … + bd 111111 = 100000 + 10000 + 1000 + 100 + 10 + 11(d+1) + b1(d) + b2(d-1) + b3(d-2) + … + bd(1) در جستجوي عمقيدر جستجوي عمقي تکرار شونده123456 = 100000 + 20000 + 3000 + 400 + 50 + 6کاربرد اين استراتژي:در مسائلي که فضاي جستجو بزرگ باشد و عمق راه حل نامشخص آنگاه جستجوي عمقي تکرار شونده روش ناآگاهانه خوبي استفصل سوم: جستجوي عمقي تکرارشونده - ارزيابي

اسلاید 48: فصل سوم: جستجوي دو طرفه 5- جستجوي دو طرفهBidirectional Search (BS)انجام دو جست و جوي همزمان، يکي از حالت اوليه به هدف Forward ديگري از هدف به حالت اوليه Backwardتا زماني که دو جست و جو به هم برسند الگوريتم متوقف مي شود

اسلاید 49: براي پياده‌سازي الگوريتم سؤالات زير بايد پاسخ داده شوند:1. سؤال اصلي اين است که، جستجو از سمت هدف به چه معني است؟ ماقبل‌هاي (predeccessors) يک گره n ، را گره‌هايي درنظر مي‌گيريم که n مابعد (successor) آنها باشد. جستجو به سمت عقب بدين معناست که توليد ماقبل‌ها از گرة هدف آغاز شود.2. براي بعضي از مسائل محاسبه والدها ممکن است بسيار مشکل باشد يعني عملگرها قابل وارونه شدن نباشند3. چه کار مي‌توان کرد زماني که هدف‌هاي متفاوتي وجود داشته باشد؟ اگر ليست صريحي از حالت‌هاي هدف وجود داشته باشد، مي‌توانيم يک تابع ماقبل براي مجموعه حالت تقاضا کنيم در حاليکه تابع مابعد يا (جانشين) در جستجوي مسائل چندوضعيته به کار مي‌رود.فصل سوم: جستجوي دو طرفه - ادامه

اسلاید 50: 4. بايد يک راه موثر براي کنترل هر گره جديد وجود داشته باشد تا متوجه شويم که آيا اين گره قبلاً در درخت جستجو توسط جستجوي طرف ديگر، ظاهر شده است يا خير. – قطع دو گراف و اجتناب از گره هاي تکراري5. نياز داريم که تصميم بگيريم که چه نوع جستجويي در هر نيمه قصد انجام دارد.فصل سوم: جستجوي دو طرفه - ادامه

اسلاید 51: معيارهاي ارزيابي استراتژي جستجوي دو طرفه: 1) کامل بودن: 2) بهينه بودن: بهينه است اگر هزينه تمام مراحل يکسان باشدکامل است، اگر هر دو جستجو، عرضي باشند3) پيچيدگي زماني: 4) پيچيدگي مکاني: O(bd/2)O(bd/2)فصل سوم: جستجوي دو طرفه - ارزيابي

اسلاید 52: فصل سوم: اجتناب از حالتهاي تکراري اجتناب از حالتهاي تکراريوجود حالتهاي تکراري در يک مسئله قابل حل، ميتواند آن را به مسئله غير قابل حل تبديل کندبراي مسائل زيادي که عملگرها قابل وارونه شدن باشند، حالات تکراري غيرقابل اجتناب هستند. اجتناب از وقوع حالات تکراري موجب کاهش نهايي در هزينه جستجو مي شود

اسلاید 53: سه راه براي حل مشکل حالات تکراري جهت مقابله با افزايش مرتبه و سرريزي فشار کار کامپيوتر وجود دارد:1. به حالتي که هم اکنون از آن آمده‌ايد، برنگرديد. تابع گسترشي(يا مجموعه عملگرها ) تعريف کنيم که از توليد مابعدهاي يک گره که با والد آن گره يکسان هستند، جلوگيري مي‌کند.2. از ايجاد مسيرهاي دوار بپرهيزيد. تابع گسترشي(يا مجموعه عملگرها ) تعريف کنيم که از توليد مابعدهاي يک گره که با اجداد آن گره يکسان است ، جلوگيري مي‌کند.3. حالتي را که قبلاً توليد شده است، مجدداً توليد نکنيد. در اين صورت همه حالتهايي که توليد مي شوند بايد در حافظه نگهداري شود، پيچيدگي فضايي O(bd) داشته باشدفصل سوم: اجتناب از حالتهاي تکراري – راه حل

اسلاید 54: فصل سوم: مقايسه استراتژي هاي ناآگاهانهمقايسه استراتژي‌هاي جستجو: b فاکتور انشعاب، d عمق پاسخ، m ماکزيمم عمق درخت جستجو،L محدوديت عمق