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

صفحه 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۹ مقایسه استرا تژي‌هاي جستجو