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

صفحه 1:


صفحه 2:
]| عامل های حل مسئلناده و۸ وستناه5 سعاطه” ا ل ‎era RS ee‏ | جهت ساخت لایه: ۱ -t ba el | On emp Pe eee Problem Reduction a ۳ Constraint Satisfaction 8 7 ‏ا‎ | cls IL .3 Knowledge Base ‏استفاده از دانش‎ .4 #۹ 

صفحه 3:
فصل سوم: جستجو فرآيند اول: فرموله سازي هدف (مصتعص") ١-م2))‏ هدف براي عامل كاملاً مشخص مي شود و به عبارت دیگر اهدافي که ‎Penne ee‏ 00 فرآیند دوم: ل كك الب ا ا فرآيندي که تصمیم مي گیرد چه عملياتي جهت رسیدن به هدف در نظر گرفته شود 5 ۹ ۱ 

صفحه 4:
فصل سوم: جستجو بس از مشخص نمودن اين دو فرآيند. عامل دنباله اي از اعمال را براي ر ی يعني فرآيند جستجو را مي توان ۱ ‎a fe Caton Pee CeCe‏ ل ا ‎nr‏ 00 . استراتژي جستجو ‎Choe SO aT So‏ ا ‎enc st] Pp‏ را ‎Fon vere‏ به هدف ادامه می یابد و بدین صورت درخت جستجو تشکیل می گردد 

صفحه 5:
UAV Mar eee) eS 1. جستجو در فضاى حالت ‎State Space‏ براي حل مسئله ۲ به روش جستجو از طریق فضاي ‎Searghu.‏ ‏پارامترهاي زیر مشخص شوند: ۱ 9000 ‏ا‎ OPE FOP CO ETE un ‏عملگرها (60613015) - تابع مابعد‎ «۰ eee ORC ae Cc ac ‏عامل تولید فضاي جستجو ل فرموله سازي مسئله‎ - 

صفحه 6:
) .. ‏لللجوه: مستهوىي فضاى هالت رادامه‎ as g (Goal State - Goal 1.2 ‏وضعیت‎ ‎[1 ‏اب‎ ‎3 تابع هزینه مسیر (۳00 او60-طاج۳) > ‏دا‎ AN aN ‏هزينه ها ذر طول مسير از مبداء تا كره جا‎ 

صفحه 7:
|۱9 ay eee | gv) :1 ‏مثال‎ مسئله: مرتب سازي يك آرايه سه عنصري [(0 , © , (0)>-[0]0..9) به صورت 5 5-00 آرليه (0 , © , ©) -[]0) ۳ 350 0 جابجايي دو عنصر ‎(cc) cnn‏ ا 0 5 , 69 )مسب ۱ ‎G 332 cxsdy‏ تا ‎sc)‏ ل ا لك 5556 ا ل ۷ ‎had‏ تابع هزینه مسیر هر عمل ارزش یک دارد ۹ 

صفحه 8:
۱ را ارائه می دهد 

صفحه 9:
فصل سوم: مستمو 075255-5-097 3 39 اب | شرح كلي این روش: ‎Fee en OCs a ede nee ere hance RCS oad‏ جستجو (درخت جستجو) مي نمائيم ‎SPC CCIE RORY‏ ل 0[ ‎eee Nee sed ce ene Rove BES ew eee‏ | ‎FrCoatc mpd COIS FO spanner oC‏ 1. به وضعيتى برسيم كه هدف است در ايبن صورت راه“خل"ارئة می شود 2.درخت جستجو کاملا تولید شده ولی هدف در آن دیده نمی شود دراين صورت مسئله ياسخ ندارد 

صفحه 10:
‎UL 0 Pet)‏ - سافتار درفت مستمو ‎۱ eed od ‎ ‏يك كره به عنوان ساختار داده: ۳ وضعيتي كه كره در فضاي حالت داراست لا كره والد ‎Ses Roney ciet a‏ ا ا لت ‎aN Re‏ ‎BOCK CoS DE Ux ey‏ ‎ 

صفحه 11:
فصل سوم: مستموى فضاى مالت-نضرس 9 ‎Te ee ge ag‏ )| يکي از 8 حالت ممکن ۳ 1. حركت به سمت جب با [] 2. حركت به سمت راست © [] ‎0G fso Jor 3‏ ‎Ree Re peree ry a]‏ وضعيتي از مسئله که در آن هیچ یک از چهار خانه ها خاكي نداشته باشد لا تابع هزینه مسیر | ۹ 

صفحه 12:
۱ ies |v) 8 وضعیت ممکن مسئله : af سس ‎=i‏ ‏۳ ۱۷ 

صفحه 13:
گراف کامل: 

صفحه 14:
1۱9 Wart war Vurirey yey.) معن جد وضعیت ابتدایی دنياي 0 ف كس عادو حالت تكراري ce errors 

صفحه 15:
1۱9 Wart war Vurirey yey.) فرض: در مثا ۱ د مسير ياسخ دنياي 0 2200111 © كس عادو حالت تكراري 1 a mc errors 

صفحه 16:
Pepe Lyne ae | et} Chea 8 ‏مثال3- يعماى‎ [ | +] eRe perenne r yd ef {| Ce ‏ل‎ ees ۳ |: |: | es - اگر سمت راست خانه | خالي باشد حرکت به سمت راست ‎Se ed eee Tele Cera‏ ۳۹| ‎Roe‏ ا ‎Reon Oren Te‏ |_|]: 0 Ser ۳5 [9 1110 8 ‏كا تابع هزينه مسير‎ هر قدم ارزش 1 دارد. بنابراين هزينه مسير همان طول مسير است. 

صفحه 17:
]۱ Cee way Ae) Ve 2) eke 8 ‏معمای‎ 7 2 وضعيت ابتدايي هر حالتي را ميتوان به عنوان حالت اوليه در نظر كرفت د لت ۳ [۱ ae Se ‏عر ای انس دزن ع ل‎ ۱ neocon yc Tey ure Ke I Bc ul ree) Oe a el ‏ا‎ eae ed tee dt 2- - اگر سمت راست خانه خالي عدد باشد حرکت خانه خالي به سمت راست pooner We ear ue reuse ares ready ‏اكر سمت بالا خانه خالي‎ -3 3 - اكر سمت يايين خانه خالي .عدد باشد حرکت خانه خالي به سمت پایین 

صفحه 18:
رل زر کر رل | سوال: در درخت جستجو کدام گره براي بسط باید انتخاب شود؟ استراتژي هاي جستجو استراتژي جستجو چگونگي گسترش درخت جستجو را مشخص مي کنند انواع استراتژي هاي جستجو : ‎Ie‏ ‎Uninformed 7 ۱ ۳۹‏ ‎emerson‏ وت و Informed 7 CORN gat pe em CMC Scere it] ae 

صفحه 19:
فصل سوم: مستجوی ناآگاهان» ‎ed‏ كت 5 جستجوي كوركورانه ۰-۵۷ ‎Search‏ ‎000 NTE Opes ST SPARE PCC BOR Cah ‏در اختیار ندارد‎ 5 ‎POCTER TT‏ ا ‎RAK‏ 00 وضعيتهاي ‎Rernagene serge NYSee a0 een W eal ene 

صفحه 20:
فصل سوم استراتژی هاي مستجوي ناآگاهان» TC eae es eer) جستجوي سطحي * جستجوي با هزينه يكنواخت جستجوي عمقی محدود شده ۱ با 5 د ‎XY 0 CNC ee‏ جستجوي دوطرفه 

صفحه 21:
۱ Mayu) ey) Vey eT.) معيارهاي ارزيابي : ‎(Completeness) :y 59: Jol (1‏ در صورت وجود راه هل آیا استراتژي قادر به بيدا كردن راه حل است؟ ‎(Optimality) :ys92 ding (2‏ در صورت وجود راه هل آیا بهترین راه هل است یا نم؟ ‏3 يبجيد كي زماني: ‎(Time Complexity)‏ 3 ‎۰ ‏ات‎ ‎۳ ‎Rene ren Aci ty ‎Space) Deel ‏ا‎ ‎9 ۳ 7 (Complexity ‏مداکثر تعداد گره هاي ذفیره ش 

صفحه 22:
فصل سوم: استراتزى مستموى سطمي 1- جستجوي سطحي -جستجوي اول سطح (86) تس تا ابتدا ريشه ترش بيدا مي ند سپس فرزندان ريشه ترش بيدا مي شند و سس | ال ‎tS oie its Een Ne Ce‏ 0[ استفاده مي کنند . ۱ ۱2 eb 5lbas 2 ٠ 

صفحه 23:
| SR eS) mayo ۱۳1۲۳۲ ‏م‎ جت م د 00 وضعيت هدف با 

صفحه 24:
| SR eS) درخت جستجوي با استفاده از جستجوي اول سطح ۱ ۱ هل عمق ‎phe‏ ‏مسیر پاسخ ۱ 00 0 د سانا وضعيت هدف حب عمق سد 

صفحه 25:
فصل سوم: استراتژی مستجوي سطمي_ ارب معيارهاي ارزيابي استراتژي جستجوي اول سطح: 0 کامل است و کم عمق ترین گره هدف را پیدا مي کند 4 5 Se Ree MC SC ee cee eS eee NS : ١ 00 ‏اا ل ل‎ اكر تمام هزينه عملكر ها يكسان باشد آنكاه مي توان كفت بهینه هم است 

صفحه 26:
۱7 ee Le 3) پيچيدگي زماني: ۲ فاکتورلنشعاب ‎eee‏ ‏۳ ‏حداكثر تعداد كره هاي بسط داده شده وج ‎ak ae‏ وي ‎meme 0000‏ 50 ل ل ل ل ال ۱ یک زمان باید در حافظه نگهداري شوند ‎On‏ 0 ‎y‏ 

صفحه 27:
فصل سوم: مستجو با هزينه يكنوافت 2- جستجوي با هزینه یکنواخت ا 00 ‎(el (ta) nice erate SC et ne Sent ents pono‏ انتخاب مي شود كه هزينه كمتري را دارد. اكر هزينه راه حل يكسان باشد اين الكوريتم معادل الگوریتم سطحي است. ا ا ل ا ل ل ال ا للم 20 مال 

صفحه 28:
eat eM eR Verve yet درخت جستجوي با استفاده از جستجو با هزینه یکنواخت Cd ا ال | يكسان باشند در اين صورت جستجو با هزينه يكنواخت همان جستجوي سطحي است : وضعیت هدف 7 350-07 

صفحه 29:
eat eM eR Verve yet درخت جستجوي با استفاده از جستجو با هزینه یکنواخت ا ال | يكسان باشند در اين صورت جستجو با هزينه يكنواخت همان جستجوي ECG ne ores) on ۹ 0-0۳۳0 

صفحه 30:
فصل سوق: مستجو با هزينه يكنوافت يم معيارهاي ارزيابي استراتژي جستجو با هزینه یکنواخت: 0 ‎ad od‏ ی 0 مثبت ع باشد. ‎ee‏ ا ل ا 1 ‎eed alice Capea)‏ ا ل 1 ا 2) ببينه بودن: بهینه است چون کم هزینه ترین گره هدف پیدا مي شود ظ 

صفحه 31:
فصل سوم: مستجو با هزينه يكنوافت سن 3) پيچيدگي زماني: ‎eRe‏ ا ا ‎een Ie‏ 910 ) 5 ] ۳ ee euch ‏بگيدرخت در‎ 1 ASTM Fe SURO E EMT TEL ve یک زمان باید در حافظه نگهداري شوند تليق ۰ ۹ ) 

صفحه 32:
فصل سوم: مستجوي عمقي ‎LY ae RS aa‏ تا ‎al eee eee oes a ee RCS Decl‏ ‎ete seen mete CREB ES Re ee ESS ‏گره هايي در سطوح کم عمق تر میرود‎ ‎ 

صفحه 33:
rea ear er | oY.) درخت جستجوي با استفاده از جستجوي اول عمق | ۹ 1 Ione Tee CK ‏ا‎ OU Seng Se) 

صفحه 34:
0 guy elias eS cea me LSS SL a) 1) کامل بودن: ‎Rear rag Re Cee Sete Tote OE a eC eC Oona PCy‏ ‎Se a cee ioc‏ 2) ب#هبينه بودن: بهينه نيست O(b 0 m) ‏ماکزیمم‌عمقدرخت‎ 7 4) ييجيدكي مكاني: ‎١‏ لين جستجو نياز به حافظه نسبتاً كمي فقط براي ذخيره مسير واحدي از ريشه به یک گره برگي. و گره‌هاي باقي‌مانده بسط داده نشده دارد. 00 \ 

صفحه 35:
۱ بررسي جستجوهاي سطحي و عمقي : فرض: برنامه اي داریم که در هر ثانیه 1000 گره را بسط می دهد و هر گره 100 بایت فضا | 100 سای 0 0 aad 04 44 6 0 406 ‏عصطل0 4 ع6‎ aoe ao 4100 1 006 Od Wows 00 ‏صطع6‎ Od 199 0 006 99 ‏عدا‎ 000 dow 960000 0 

صفحه 36:
[۱ eat Foe ‏و‎ Ces CO Eyecare Oe ee eles oe Cel ‏ا ل‎ Reem eS Ce OE einen ar fos Wan Pegs econ Flees 8 8 Pes ل ل ل ا ل ا ‎pean Cel‏ Bees ‏ع ا م ا ا‎ Beene po ee ore 35 1 Fer ee eas ome ‏ام ا‎ Bane Cer 9 ۱ ‏ات جان سالم بدرببرد‎ 

صفحه 37:
3 ‎eet)‏ | عمقئ ممدود شده ‏4- جستجوی عمقی محدود شده ‎Depicted Geack (DPC)‏ ‎ee ere re ee‏ 1 ‎oe IE TCS eee ne ae eed SSS ee aCe Spies eS‏ در نظر مي گیرد ۱ در صورتي كه هدف در سطح برش و يا قبل از لن وجود داشته باشد جستجو كامل خواهد م چون ممکن است در سطح پایین تر جواب داشته باشیم 1۹ ‎ ‎ ‎ 

صفحه 38:
اپ ۱ درخت جستجوي ‎ey‏ سر | 

صفحه 39:
000 00 ‏ات اد ل‎ ‏ل‎ ‎| ‎[0 ge ace eee ree BOR Peay tar pangs pce epee sel ea ‏بودن:‎ ‏بيجيدكي زماني:‎ )3 9102 ‏عمقمحدود شده درخت‎ 7 4) بيجيدكي مكاني: 0 ۹ 7 

صفحه 40:
فصل سوم: مستجوى عمقي تكرار شونده ‎ee‏ السب يي ‎a ae‏ * مشکل قبلي انتخاب یک عمق نا مناسب براي برش بود ۱ محدوده ها یاد آوري مي كند. اول عمق 0 . سيس عمق 1 . سيس عمق 2 . و الي آخر مثال Se Re a i ean 

صفحه 41:
Ee se Y wipe eros Verne Tey) درخت جستحوىي ا م تکرار شونده ‎tennr ean ew‏ 00 

صفحه 42:
۱ ‏ل‎ we درخت دج با استفاده 0 ‎ee‏ شونده با امتحان عمق محدود شده يك او ده aA 

صفحه 43:
Ee se Y wipe eros Verne Tey) درخت جستجوي ‎eet ee eee‏ تکرار شونده ‎eee‏ 0000000 

صفحه 44:
Ee se Y wipe eros Verne Tey) درخت دج اي ‎ere ms Een‏ 0200 با امتحان عمق محدود شده سه 

صفحه 45:
PO ‏ده‎ اس دز مس سا این استراتژي تركيبي از دو استراتژي سطحي و عمقي مي باشد يعني مزاياي این دو استراتژي ها ترکیب شده 7 جستجوي سطحي کامل و بیینه است سس ‎reaper en‏ 000 000 1) كامل بودن: كامل است 00 ding = (2 RWS EN ed pea ea Par eer aa ‏بودن:‎ ۹ 

صفحه 46:
PO ‏ده‎ 3) پيچيدگي زماني: ۱ براي مسائل اين سرريزي بسيار كوجك است زيرا در يك درخت جستجوي ا ا 5200000000 ‎EO cet a (ONCE Led‏ ‎aD‏ ا ا ‎ASNT SS‏ 111111 = 100000 + 10000 + 1000 + 100 + ۳۹ ۳ ات ی 6+ 50 + 400 + 3000 + 20000 + 100000 = 123456 Olen ۹ ۱ 5000 ay 

صفحه 47:
فصل سوم: مستجوي عمقي تكرارشوتدة .سم 3) پيچيدگي زماني: | مسائل این سرريزي بسیار کوچک است زیرا در یک درخت جستجوي ‎REN eer enn recat Ws.‏ مثال: براي 9-00 و عمق 26 داریم: را ۲ ...+ کی + گر + ی در جستجوي عمقي 111111 = 100000 + 10000 + 1000 + 100 + براي جوي عمقي 1+10 4+0(1) + (1)"ط + ... + (0:)0-2 + (1حلين 

صفحه 48:
0 6 SOS eC ae ee ced See 000 8 110000 

صفحه 49:
]۱ rae yes! Y) ce Re SE on Sy Ses te ‏سؤال ۳ ۳ است که, جستجو از سمت هدف به جه معني است؟‎ 1 ‏لسن‎ el ‏يي ا ال‎ ‏آنهاباشد. جستجو به سمت عقب بدین معناست که تولید‎ eee 0-0007 ‏براي بعضي از مسائل محاسبه والدها ممكن است بسيار مشكل باشد يعني عملكرها قابل‎ .2 . ‏وارونه شدن نباشند‎ [0 Ser BED FOP OER CIDE PSR SCO OR Cea) Ce le cee ea ee Se ell ا م ‎Fee‏ ee eee icd 

صفحه 50:
]۱ rae yes! Y) Cer Re aCe ey ete ee mre Te pecan 1 OP Serene Care ee IR ND ICE Saoe A] ‏ات‎ en ys een Fe eR eee Ree sO SBI دا و ۰ 5 

صفحه 51:
فصل سوم: مستموى دو طرفه رمب ‎CL SL)‏ ا یا 1) كامل بودن: كامل است. ‎Slt eee eae‏ ‎Ae (2‏ بهينهاست بودن: ‎See et ee ae asad‏ ‏3) پيچيدگي زماني: ‎ur O(b??) ‏بلك ۰ ۹ ‏4( ييجيدكي مكاني: 

صفحه 52:
[0 OrES cre earn NERC CN URE cc PCCP IEE OE اجتتاب هستند. ‎SES cae eave)‏ ا 0 غير قابل حل تبديل كند ‎ed‏ ل ا ا ل ل ‎SE ee see‏ 

صفحه 53:
فصل سوم: امتناب از مالتهاي تكراري -رهس سه راه براي حل مشكل حالات تكراري ی یت ل كن 1 ‏اي‎ ‎۱ oR @ Sento ee semi SRC Se ‏ا‎ Pe SEMEL Bega Sees Cae Somme ‏هت‎ ee ۱ en) eased 1 ‏ل ل‎ ca Ki 5 ‏حالتى را كه قبلاً توليد شده است. مجدداً توليد نكنيد.‎ .3 ۱ ‏ل‎ ene ee ‏ل‎ كى فضايى (8ط)0) داشته باشد 

صفحه 54:
فاکتور انشعاب. 200 ماكزيمم عمق درخت جستجو.را محدوديت عمق ۹۹9۹ مقایسه استرا تژي‌هاي جستجو 

Alireza yousefpour yousefpour@shomal.ac.ir فصل سوم :حل مسئله عامل هاي حل مسئلهProblem Solving Agent روشهاي حل مسئله يا تکنيک هاي مختلف در هوش مصنوعي جهت ساخت اليه: .1جستجوي فضاي حالت State Space Search .2تقليل مسئله .3با ارضاي محدوديت .4استفاده از دانش ‏Problem Reduction ‏Constraint Satisfaction ‏Problem ‏Knowledge Base فصل سوم :جستجو جستجو (: )Search فرآيند اول :فرموله سازي هدف ()Goal Function هدف براي عامل کام ً ال مشخص مي شود و به عبارت ديگر اهدافي که عامل سعي در رسيدن به آنها را دارد محدود و مشخص مي شوند فرآيند دوم :فرموله سازي مسئله ()Problem Formulation فرآيندي که تصميم مي گيرد چه عملياتي جهت رسيدن به هدف در نظر گرفته شود فصل سوم :جستجو پس از مشخص نمودن اين دو فرآيند ،عامل دنباله اي از اعمال را براي رسيدن به هدف مي يابد که به اين پروسه Searchگفته مي شود مسير جستجو يعني فرآيند جستجو را مي توان مانند يک درخت جستجو در نظر گرفت ريشه درخت يک گره است که با حالت اوليه مسئله مطابقت دارد .استراتژي جستجو گره اي را از درخت به منظور گسترش انتخاب مي کند که اين کار تا رسيدن به هدف ادامه مي يابد و بدين صورت درخت جستجو تشکيل مي گردد عامل حل مسئله داراي مراحل << فرموله سازي – جستجو – اجرا >> مي باشد فصل سوم :جستجوي فضاي حالت ‏State Space .1جستجو در فضاي حالت ‏Search براي حل مسئله pبه روش جستجو از طريق فضاي حالت بايد پارامترهاي زير مشخص شوند: وضعيت ابتدايي مسئله ()Initial State شامل تعريف مسئله ،واقعيتها ،فرضيات و دانسته هاست عملگرها ( – )Operatorsتابع مابعد مجموعه اي از عمليات که براي عامل قابل دسترسي باشد – عامل توليد فضاي جستجو فرموله سازي مسئله فصل سوم :جستجوي فضاي حالت (ادامه ) ... وضعيت هدف (Goal State – Goal )Test ‏g شامل بخشي از مسئله است که نتيجه و پاسخ در آنجا مشخص است فرموله سازي هدف تابع هزينه مسير ()Path-cost Function تابعي که براي هر مسير هزينه اي را در نظر مي گيرد که مجموع هزينه ها در طول مسير از مبداء تا گره جاري فصل سوم :جستجوي فضاي حالت -مثال اول مثال : 1 مسئله :مرتب سازي يک آرايه سه عنصري } A[1..3]={0 , 2 , 1به صورت صعودي وضعيت ابتدايي آرايه }A[ ] = {0 , 2 , 1 عملگرها جابجايي دو عنصر وضعيت هدف g ) Swap( A1 , A2 ) , Swap( A1 , A3 ‏Swap( A2 , A1 ) , Swap( A2 , ) A3 ‏Swap( A3 , A1 ) , Swap( A3 , ) A2 وضعيتي که در آن به ازاي هر دو عنصر مجاور در آرايه عنصر سمت چپ از عنصر سمت راست کوچکتر يا مساوي باشد تابع هزينه مسير هر عمل ارزش يک دارد فصل سوم :جستجوي فضاي حالت 0 2 1 متناظر با يک عملگر 2 0 0 1 2 1 2 0 1 2 -مثال اول -درخت جستجو 0 1 2 0 1 2 0 1 ‏ وضعيتي از مسئله وضعيت هدف الگوريتم جستجو همين جا متوقف مي شود و راه حل (مسير جواب) را ارائه مي دهد فصل سوم :جستجوي فضاي حالت -روش تشکيل درخت جستجو شرح کلي اين روش: جستجوي در فضاي حالت از وضعيت ابتدايي شروع کرده و اقدام به توليد فضاي جستجو (درخت جستجو) مي نمائيم بدين صورت که عملگرها را به وضعيت ابتدايي اعمال کرده و وضعيت هاي جديد مسئله توليد مي شود و وضعيت جديد مسئله نيز مجدداً تحت تاثير عملگر قرار مي گيرد .توليد درخت جستجو تا آنجايي ادامه پيدا مي کند که : .1به وضعيتي برسيم که هدف است در اين صورت راه حل ارئه مي شود .2درخت جستجو کامال توليد شده ولي هدف در آن ديده نمي شود در اين صورت مسئله پاسخ ندارد. فصل سوم :جستجوي فضاي حالت – ساخت<ار درخت جستجو ساختمان داده براي درخت جستجو : يگ گره به عنوان ساختار داده: وضعيتي که گره در فضاي حالت داراست گره والد عملگري که براي توليد گره بکار رفته است عمق گره هزينه مسير ( از حالت اوليه تا گره ) فصل سوم :جستجوي فضاي حالت – مثال دوم مثال : 2 مسئله :دنياي جارو برقي با دو خانه مجاور وضعيت ابتدايي يکي از 8حالت ممکن عملگرها .1حرکت به سمت چپ  L .3عمل مکش  S .2حرکت به سمت راست  R وضعيت هدف g وضعيتي از مسئله که در آن هيچ يک از چهار خانه ها خاکي نداشته باشد تابع هزينه مسير فرض هر عمل ارزش يک داشته باشد فصل سوم :جستجوي فضاي حالت 8وضعيت ممکن مسئله : – مثال دوم فصل سوم :جستجوي فضاي حالت گراف کامل: دنياي جاوبرقي با سه عملگر فضاي حالت – مثال دوم فصل سوم :جستجوي فضاي حالت فرض :در مثال دنياي جاروبرقي وضعيت ابتدايي ‏R حالت تکراري  – درخت جستجو مثال دوم ‏R ‏L ‏L ‏S ‏ ‏S ‏ حالت تکراري وضعيت هدف فصل سوم :جستجوي فضاي حالت فرض :در مثال دنياي جاروبرقي مسير پاسخ يا راه حل مسئله ‏R حالت تکراري  – درخت جستجو مثال دوم ‏R ‏L ‏L ‏S ‏ ‏S ‏ حالت تکراري وضعيت هدف فصل سوم :جستجوي فضاي حالت – مثال سوم مثال -3معماي 8 ‏Start State وضعيت ابتدايي هر حالتي را ميتوان به عنوان حالت اوليه در نظر گرفت عملگرها اگر سمت چپ خانه iخالي باشد حرکت به سمت چپ اگر سمت راست خانه iخالي باشد حرکت به سمت راست اگر سمت باال خانه iخالي باشد حرکت به سمت باال -اگر سمت پايين خانه iخالي باشد حرکت به سمت پايين ‏Goal State وضعيت هدف g وضعيتي از مسئله که با ساختار هدف مطابقت مي‌کند. تابع هزينه مسير هر قدم ارزش 1دارد ،بنابراين هزينه مسير همان طول مسير است. فصل سوم :جستجوي فضاي حالت – مثال سوم مثال -3معماي 8 ‏Start State وضعيت ابتدايي هر حالتي را ميتوان به عنوان حالت اوليه در نظر گرفت عملگرها اگر سمت چپ خانه iخالي باشد حرکت به سمت چپ اگر سمت راست خانه iخالي باشد حرکت به سمت راستباالجمع ًا 32عملگر داريم سمتپس قراربهگيرد باشد 8 اعداد 1تا هر i حرکت تواند iخالي ميباال خانه سمت ازاياگر به - ‏Goal State اگر سمت پايين خانه iخالي باشد حرکت به سمت پايينآيا مي توان عملگر ها را محدود کنيم ولي همان درخت جستجو را داشته باشيم؟ وضعيت هدف g خالي به سمت چپ هدفحرکت ساختارباشد خاليبا ،عدد چپ خانه خانهي‌کند. مطابقت م مسئله که سمتي از -1اگر وضعيت -2اگر سمت راست خانه خالي ،عدد باشد حرکت خانه خالي به سمت راست ‏-3 خالي ،عدد باشد حرکت خانه خالي به سمت باال هزينهخانه سمت باال مسير اگرتابع سمت پايين طولخالي همانخانه حرکت عدد دارد،خالي ، ارزش 1خانه قدم پايين سمت مسيربهاست. باشدمسير هزينه بنابراين -4اگرهر فصل سوم: استراتژي هاي جستجو در فضاي حالت سوال :در درخت جستجو کدام گره براي بسط بايد انتخاب شود؟ استراتژي هاي جستجو استراتژي جستجو چگونگي گسترش درخت جستجو را مشخص مي کنند انواع استراتژي هاي جستجو : استراتژي هاي جستجوي نا آگاهانه استراتژي هاي جستجوي آگاهانه ‏Uninformed ‏Search ‏Informed ‏Search فصل سوم :جستجوي ناآگاهانه جستجوي نا آگاهانه يا جستجوي کورکورانه ‏Blind ‏Search ‏ناآگاه\ي اي\ن اس\ت ک\ه الگوريت\م هي\چ اطالعات\ي غي\ر از تعري\ف مسئله در اختيار ندارد ‏اي\ن الگوريتمه\ا فق\ط ميتوان\د عملگرها را اعمال و وضعيتهاي جديد را توليد و هدف را از غير هدف تشخيص دهند فصل سوم: استراتژي هاي جستجوي ناآگاهانه انواع استراتژي هاي جستجوي نا آگاهانه : جستجوي سطحي جستجوي با هزينه يکنواخت جستجوي عمقي جستجوي عمقي محدود شده جستجوي عمقي تکرار شونده جستجوي دوطرفه فصل سوم :استراتژي هاي جستجوي ناآگاهانه -ادامه معيارهاي ارزيابي : )1کامل بودن)Completeness( : در صورت وجود راه حل آيا استراتژي قادر به پيدا کردن راه حل است؟ )2بهينه بودن)Optimality( : در صورت وجود راه حل آيا بهترين راه حل است يا نه؟ )3پيچيدگي Bزماني)Time Complexity( : چقدر طول ميکشد تا راه حل را تعداد گره هاي توليد شده در اثنا )4پيچيدگBBBيB )Complexity مکاني: (Space براي جستجو چقدر حافظه نياز د حداکثر تعداد گره هاي ذخيره شده در حا فصل سوم: استراتژي جستجوي سطحي ‏Fي سطحي –جستجوي اول سطح )Breadth-First Search (BFS -1جستجو ابتدا ريشه گسترش پيدا مي کند سپس فرزندان ريشه گسترش پيدا مي کنند و .... در حقيق\ت تمام گره ه\ا در ي\ک س\طح dبس\ط (گس\ترش) داده م\ي شود و سپس گره هاي سطح بعدي d+1گسترش داده مي شوند که براي پياده سازي اين استراتژي از تابع صف استفاده مي کنند . مثال ‏A ‏C ‏D ‏I ‏B ‏H ‏Q ‏P ‏G ‏O فضاي حالت ‏N ‏F ‏M ‏L ‏E ‏K ‏J فصل سوم: استراتژي جستجوي سطحي – تشکيل درخت جستجو درخت جستجوي با استفاده از جستجوي اول سطح عمق صفر ‏A ‏C ‏D ‏I وضعيت هدف ‏B ‏H ‏ ‏Q ‏P ‏G ‏O عمق يک ‏N ‏F ‏M ‏L عمق دو ‏E ‏K ‏J عمق سه فصل سوم: استراتژي جستجوي سطحي – تشکيل درخت جستجو درخت جستجوي با استفاده از جستجوي اول سطح مسير پاسخ يا راه حل مسئله ‏A ‏D ‏C ‏I ‏Q ‏P ‏G ‏O عمق يک ‏B ‏H ‏ وضعيت هدف عمق صفر ‏N ‏F ‏M ‏L عمق دو ‏E ‏K ‏J عمق سه فصل سوم: استراتژي جستجوي سطحي – ارزيابي معيارهاي ارزيابي استراتژي جستجوي اول سطح: )1کامل بودن: کامل است و کم عمق ترين گره هدف را پيدا مي کند )2بهينه بودن: در جستجوي سطحي هميشه کم عمق ترين گره هدف پيدا مي شود آيا کم عمق ترين گره هدف ،هدف بهينه است؟ اگر تمام هزينه عملگر ها يکسان باشد آنگاه مي توان گفت بهينه هم است فصل سوم: استراتژي جستجوي سطحي – ارزيابي )3پيچيدگBي زماني: :bف`ا̀کتور ̀ا ̀نش̀عاب ()branching factor :dع`مقگ``ر̀ه هدف حداکثر تعداد گره هاي بسط داده شده ‏O(bd ‏b1 + b2 + b3 + … + bd + 1 ) )4پيچيدگBي مکاني: پيچيدگي فضا مشابه پيچيدگي زمان است ،زيرا تمام گره هاي برگي درخت در يک زمان بايد در حافظه نگهداري شوند ‏d ‏O(b فصل سوم :جستجو با هزينه يکنواخت ‏F -2جستجوي با هزينه يکنواخت )Uniform-Cost Search (UCS در اين استراتژي به جاي گسترش کم عمق ترين گره ،گره اي توسط تابع )g(m انتخاب مي شود که هزينه کمتري را دارد .اگر هزينه راه حل يکسان باشد اين الگوريتم معادل الگوريتم سطحي است. ) : g(mهزي\نه هر گ\\ره\ (هزي\نه ر\س\يدناز ر\ي\شه ب\\ه آ\نگ\\ره\ ،ي\\عنيج\مع هزي\نه ع\ملگر ها ت\\ا ر\س\يدنب\\ه آ\نگ\\ره\ مثال ‏A ‏C ‏D ‏I ‏B ‏H ‏Q ‏P ‏G ‏O فضاي حالت ‏N ‏F ‏M ‏L ‏E ‏K ‏J فصل سوم :جستجو با هزينه يکنواخت -تشکيل درخت جستجو درخت جستجوي با استفاده از جستجو با هزينه يکنواخت ‏A 1 4 ‏I ‏D 4 ‏C 3 1 ‏H نکته :در صورتي که هزينه عملگرها يکسان باشند در اين صورت جستجو با هزينه يکنواخت همان جستجوي سطحي است : )g(n)=DEPTH(n 1 2 ‏G ‏B ‏F 2 2 1 ‏N ‏M ‏L ‏ وضعيت هدف ‏g(B)=1 4 ‏E فصل سوم :جستجو با هزينه يکنواخت -تشکيل درخت جستجو درخت جستجوي با استفاده از جستجو با هزينه يکنواخت ‏A 1 4 ‏I 1 3 ‏D 4 ‏C 1 ‏H نکته :در صورتي که هزينه عملگرها يکسان باشند در اين صورت جستجو با هزينه يکنواخت همان جستجوي سطحي است : )g(n)=DEPTH(n مسير پاسخ يا راه حل مسئله 2 ‏G ‏B ‏F 2 2 1 ‏N ‏M ‏L 4 ‏E ‏ وضعيت هدف هزينه هدف = 4 فصل سوم :جستجو با هزينه يکنواخت -ارزيابي معيارهاي ارزيابي استراتژي جستجو با هزينه يکنواخت: )1کامل بودن: کام\ل اس\ت در ̀صورتي ک\ه هزين\ه ه\ر مرحل\ه بزرگت\ر ي\ا مس\اوي ي\ک مقدار ثابت و مثبت εباشد. يعني هر عملگر هزينه غير منفي داشته باشد ،سپس هزينه يک مسير با ادامهمسير ،کاهش پيدا نخواهد کرد( .هزينه مسير با حرکت در مسير افزايش مي يابد) )2بهينه بودن: بهينه است چون کم هزينه ترين گره هدف پيدا مي شود فصل سوم: جستجو با هزينه يکنواخت -ارزيابي )3پيچيدگBي زماني: پيچيدگي زماني مشابه پيچيدگي زماني جستجوي اول سطح است ‏O(bd ) )4پيچيدگBي مکاني: پيچيدگي فضا مشابه پيچيدگي زماني است ،زيرا تمام گره هاي برگي درخت در يک زمان بايد در حافظه نگهداري شوند ‏d ‏O(b ) فصل سوم :جستجوي عمقي -3جستجوي عمقي – جستجوي اول عمق )Depth-First Search (DFS اين استراتژي ،يکي از گره‌ها را در پائين‌ترين سطح درخت بسط مي‌دهد در صورتي که جستجو به يک گره غير هدف بدون امکان بسط ميرسد آنوقت به سراغ گره هايي در سطوح کم عمق تر ميرود مثال ‏A ‏C ‏D ‏I ‏B ‏H ‏Q ‏P ‏G ‏O فضاي حالت ‏N ‏F ‏M ‏L ‏E ‏K ‏J فصل سوم :جستجوي عمقي -تشکيل درخت جست<جو درخت جستجوي با استفاده از جستجوي اول عمق ‏A ‏D ‏C ‏I ‏B ‏H ‏Q ‏P ‏G ‏O ‏N ‏F ‏M ‏L ‏ ‏E ‏K ‏J وضعيت هدف فرض شود که گره هدف پيدا نشود آنگاه ادامه جستجو بدين صورت خواهد بود فصل سوم :استراتژي عمقي -ارزيابي معيارهاي ارزيابي استراتژي جستجوي عمقي: )1کامل بودن: کام\ل نيس\ت ،اگ\ر زي\ر درخ\ت چ\پ عم\ق نامحدود داش\ت و فاق\د ه\ر گون\ه راه حل باشد ،جستجو هرگز خاتمه نمي يابد )2بهينه بودن :بهينه نيست )3پيچيدگBي زماني: ̀ :mماکز̀يممع`مقد̀ر̀خت )4پيچيدگBي مکاني: ‏O(b ) ‏m اي\ن جس\تجو ،نياز ب\ه حافظ\ه نس\بتاً کم\ي فق\ط براي ذخيره مس\ير واحدي از ريش\ه ب\ه يک گره برگي ،و گره‌هاي باقي‌مانده بسط داده نشده داردO(bm . فصل سوم: مقايسه استراتژي سطحي و عمقي بررسي جستجوهاي سطحي و عمقي : فرض :برنامه اي داريم که در هر ثانيه 1000گره را بسط مي دهد و هر گره 100بايت فضا اشغال مي کند و با فاکتور انشعاب b=10آنگاه در جستجوي سطحي داريم: ‏Node ‏Depth ‏Memory 1 0 111 2 11.111 4 111 Megabytes 18 Minutes 106 6 11 Gigabyte 31 Hours 108 8 1010 10 111 Terabytes 35 Years 1012 12 11.111 Terabytes 3500 Years 1014 14 100 Bytes 11 Kilobytes 1 Megabytes 1 Terabytes ‏Time ‏milliseconds 1 0.1 Seconds 11 Seconds 128 Days پيچيدگي زماني و مکاني در جستجوي سطحي فصل سوم: مقايسه استراتژي سطحي و عمقي -ادامه با استفاده از جستجوي عمقي ميزان مصرف حافظه کاهش پيدا کرده است براي مثال :با استفاده از مفروضات مشابه در جدول قبلي ،جستجوي عمقي به جاي 111ترابايت فقط نياز به 12کيلو بايت در عمق 12دارد .پس در حدود 10بيليون بار ،فضاي کمتري نياز دارد کاربرد جستجوي عمقي :براي مسائلي که راه حل زيادي دارند آنگاه جستجوي عمقي سريعتر از جستجوي سطحي عمل مي کند زيرا شانس بهتري براي يافتن راه حل در يک قسمت کوچک از کل فضا است. ‏عيب جستجوي عمقي :مسائل ز\يادي هستند که فضاي حالتشان بزرگ و عمق نامحدود دارند ،در اين صورت جستجوي عمقي نخواهد توانست از يک انتخاب نادرست جان سالم بدر ببرد فصل سوم: جستجوي عمقي محدود شده -4جستجوي عمقي محدود شده )Depth-Limited Search (DFS مشکل استراتژي قبل افتادن در يک عمق نا محدود و يا در يک حلقه بي نهايت بود . در اي\ن اس\تراتژي براي برخورد ب\ا مشک\ل قبل\ي ،آنگ\اه ي\ک برش بر روي درخ\ت جستجو در نظر مي گيرد در ص\ورتي ک\ه هدف در س\طح برش و ي\ا قب\ل از آ\ن وجود داشت\ه باش\د جس\تجو کامل خواه\د بود ول\ي بهين\ه نيس\ت و چون ممک\ن اس\ت در س\طح پايي\ن ت\ر جواب داشت\ه باشيم که هزينه کمتري دارد . ‏A مثال ‏D ‏C ‏I ‏B ‏H ‏Q ‏P ‏G ‏O ‏N فضاي حالت ‏F ‏M ‏L ‏E ‏K =L 2 ‏J فصل سوم:جستجوي عمقي محدودشده – تشکيل درخت جستجو درخت جستجوي با استفاده از جستجوي عمقي محدود شده ‏A ‏D ‏ ‏C ‏I ‏B ‏G ‏H ‏E ‏F =L 2 وضعيت هدف ‏Q ‏P ‏O ‏N ‏M ‏L ‏K ‏J فصل سوم :جستجوي عمقي محدود شده -ارزيابي معيارهاي ارزيابي استراتژي جستجوي عمقي محدود شده: )1کامل بودن :کامل نيست، اگر L<dو سطحي ترين هدف در خارج از عمق محدود قرار داشته باشد ،اين راهبرد کامل نخواهد بود. )2 بودن: بهينه بهينه نيست اگر L>dانتخاب شود ،اين راهبرد بهينه نخواهد بود. )3پيچيدگBي زماني: :Lع`مقم`حدود ش`د̀ه د̀ر̀خت )4پيچيدگBي مکاني: ‏O(bL ) ‏O(bL فصل سوم: جستجوي عمقي تکرار شونده ‏Fي عمقي تکرار شونده -4جستجو )Iterative-Deepening Search (IDS ‏مشکل قبلي انتخاب يک عمق نا مناسب براي برش بود اين استراتژي انتخاب بهترين محدوده عمقي را توسط امتحان تمام محدوده ها ياد آوري مي کند .اول عمق ، 0سپس عمق ، 1سپس عمق ، 2و الي آخر تا هدف مورد نظر را در صورت وجود پيدا شود مثال ‏A فضاي حالت ‏D ‏C ‏I ‏B ‏H ‏Q ‏P ‏G ‏O ‏N ‏F ‏M ‏L ‏E ‏K ‏J فصل سوم :جستجوي عمقي تکرارشونده -تشکيل درخت جستجو درخت جستجوي با استفاده از جستجوي عمقي تکرار شونده با امتحان عمق محدود شده صفر ‏A ‏D ‏Limit = 0 ‏C ‏I ‏B ‏H ‏Q ‏P ‏G ‏O ‏N ‏F ‏M ‏L ‏E ‏K ‏J فصل سوم :جستجوي عمقي تکرارشونده -تشکيل درخت جستجو درخت جستجوي با استفاده از جستجوي عمقي تکرار شونده با امتحان عمق محدود شده يک ‏A ‏D ‏C ‏I ‏B ‏H ‏Q ‏P ‏G ‏O ‏N ‏Limit = 1 ‏F ‏M ‏L ‏E ‏K ‏J فصل سوم :جستجوي عمقي تکرارشونده -تشکيل درخت جستجو درخت جستجوي با استفاده از جستجوي عمقي تکرار شونده با امتحان عمق محدود شده دو ‏A ‏D ‏ ‏C ‏I ‏B ‏G ‏H ‏E ‏F ‏Limit = 2 وضعيت هدف ‏Q ‏P ‏O ‏N ‏M ‏L ‏K ‏J فصل سوم :جستجوي عمقي تکرارشونده -تشکيل درخت جستجو درخت جستجوي با استفاده از جستجوي اول عمق با امتحان عمق محدود شده سه ‏A ‏D ‏C ‏I ‏B ‏H ‏Q ‏P ‏G ‏O ‏N ‏F ‏M ‏L ‏E ‏K ‏J ‏Limit = 3 فصل سوم: جستجوي عمقي تکرارشونده -ارزيابي معيارهاي ارزيابي استراتژي جستجوي عمقي تکرار شونده: اين استراتژي ترکيبي از دو استراتژي سطحي و عمقي مي باشد يعني مزاياي اين دو استراتژي ها ترکيب شده پس مانند: جستجوي سطحي کامل و بهينه است جستجوي عمقي به حافظه اندکي نياز دارد )1کامل بودن :کامل است )2 بودن: بهينه بهينه است اگر هزينه تمام عملگرها يکسان باشد. فصل سوم: جستجوي عمقي تکرارشونده -ارزيابي )3پيچيدگBي زماني: به نظر ميرسد جستجو عمقي تکرار شونده زمان زيادي را صرف ميکند؟ براي بيشتر مسائل اين سرريزي بسيار کوچک است زيرا در يک درخت جستجوي نمايي ،تقريباً تمام گره ها در سطح پايين قرار دارند مثال :براي b=10و عمق d=5داريم: ‏b1 + b2 + b3 + … + bd + 1 + 100 + 1000 + 10000 + 100000 = 111111 1 + 10 2 3 ‏d ‏b1(d) + b (d-1) + b (d-2) + … + b (1) + )d+1 (1 ‏O(bd در جستجوي عمقي در جستجوي عمقي تکرار شونده 6 + 50 + 400 + 3000 + 20000 + 100000 = 123456 ) )4پيچيدگBي مکاني: ‏O(bd فصل سوم: جستجوي عمقي تکرارشونده -ارزيابي )3پيچيدگBي زماني: به نظر ميرسد جستجو عمقي تکرار شونده زمان زيادي را صرف ميکند؟ براي بيشتر مسائل اين سرريزي بسيار کوچک است زيرا در يک درخت جستجوي نمايي ،تقريباً تمام گره ها در سطح پايين قرار دارند مثال :براي b=10و عمق d=5داريم: ‏b1 + b2 + b3 + … + bd + 1 + 100 + 1000 + 10000 + 100000 = 111111 1 + 10 2 3 ‏d ‏b1(d) + b (d-1) + b (d-2) + … + b (1) + )d+1 (1 ‏O(bd در جستجوي عمقي در جستجوي عمقي تکرار شونده 6 + 50 + 400 + 3000 + 20000 + 100000 = 123456 کاربرد اين استراتژي: در مسائلي که فضاي جستجو بزرگ باشد و عمق راه حل نامشخص جستجوي عمقي تکرار شونده روش ناآگاهانه خوبي است ‏Bيآنگاه مکاني: )4پيچيدگ ) ‏O(bd فصل سوم :جستجوي دو طرفه -5جستجوي دو طرفه )Bidirectional Search (BS انجام دو جست و جوي همزمان، يکي از حالت اوليه به هدف ‏Forward ديگري از هدف به حالت اوليه Backward تا زماني که دو جست و جو به الگوريتم هم برسند متوقف مي شود فصل سوم :جستجوي دو طرفه -ادامه براي پياده‌سازي الگوريتم سؤاالت زير بايد پاسخ داده شوند: .1سؤال اصلي اين است که ،جستجو از سمت هدف به چه معني است؟ ماقبل‌هاي ( )predeccessorsيک گره ، nرا گره‌هايي درنظر مي‌گيريم که n مابعد ( )successorآنها باشد .جستجو به سمت عقب بدين معناست که توليد ماقبل‌ها از گرة هدف آغاز شود. .2براي بعضي از مسائل محاسبه والدها ممکن است بسيار مشکل باشد يعني عملگرها قابل وارونه شدن نباشند .3چه کار مي‌توان کرد زماني که هدف‌هاي متفاوتي وجود داشته باشد؟ اگر ليست صريحي از حالت‌هاي هدف وجود داشته باشد ،مي‌توانيم يک تابع ماقبل براي مجموع\ه حال\ت تقاض\ا کني\م در حاليک\ه تاب\ع مابع\د ي\ا (جانشي\ن) در جس\تجوي مس\ائل چندوضعيته به کار مي‌رود. فصل سوم :جستجوي دو طرفه -ادامه .4بايد يک راه موثر براي کنترل هر گره جديد وجود داشته باشد تا متوجه شويم که آيا اين گره قب ً ال در درخت جستجو توسط جستجوي طرف ديگر ،ظاهر شده است يا خير – .قطع دو گراف و اجتناب از گره هاي تکراري .5نياز داري\م ک\ه تص\ميم بگيري\م ک\ه چ\ه نوع جس\تجويي در ه\ر نيم\ه قص\د انجام دارد. فصل سوم :جستجوي دو طرفه -ارزيابي معيارهاي ارزيابي استراتژي جستجوي دو طرفه: )1کامل بودن :کامل است، اگر هر دو جستجو ،عرضي باشند )2 بودن: بهينه بهينه است اگر هزينه تمام مراحل يکسان باشد )3پيچيدگBي زماني: )4پيچيدگBي مکاني: )O(bd/2 ‏O(bd/ 2 فصل سوم: اجتناب از حالتهاي تکراري اجتناب از حالتهاي تکراري براي مسائل زيادي که عملگرها قابل وارونه شدن باشند ،حاالت تکراري غيرقابل اجتناب هستند. ‏وجود حالتهاي تکراري در يک مسئله قابل حل ،ميتواند آن را به مسئله غير قابل حل تبديل کند ‏اجتناب از وقوع حاالت تکراري موجب کاهش نهايي در هزينه جستجو مي شود فصل سوم: اجتناب از حالتهاي تکراري – راه حل سه راه براي حل مشکل حاالت تکراري جهت مقابله با افزايش مرتبه و سرريزي فشار کار کامپيوتر وجود دارد: .1به حالتي که هم اکنون از آن آمده‌ايد ،برنگرديد. تابع گسترشي(يا مجموعه عملگرها ) تعريف کنيم که از توليد مابعدهاي يک گره که با والد آن گره يکسان هستند ،جلوگيري مي‌کند. .2از ايجاد مسيرهاي دوار بپرهيزيد. تابع گسترشي(يا مجموعه عملگرها ) تعريف کنيم که از توليد مابعدهاي يک گره که با اجداد آن گره يکسان است ،جلوگيري مي‌کند. .3حالتي را که قب ً ال توليد شده است ،مجدداً توليد نکنيد. در اين صورت همه حالتهايي که توليد مي شوند بايد در حافظه نگهداري شود، پيچيدگي فضايي ) O(bdداشته باشد مقايسه استراتژي هاي ناآگاهانه :فصل سوم :مقايسه استراتژي‌هاي جستجو Bidirectional (if applicable) Iterative Deepening Depth-Limited DepthFirst UniformCost BreadthFirst bd/2 bd bl bm bd bd Time bd/2 bd bl bm bd bd Space No No Yes * Yes ?Optimal No Yes* Yes * Yes *Yes * Yes Yes * Yes Criterion ?‍Complete محدوديت عمقL، ماکزيمم عمق درخت جستجوm ، عمق پاسخd ، فاکتور انشعابb