حل مسئله توسط جستجو

صفحه 1:
رامین اعیان‌زاده ‎Email: grandee@ayanzadeh.ir‏ 1389 

صفحه 2:
مقدمه * عاملهاى حل مسأله * انواع مسأله * فرموله سازى مسأله * مسائل نمونه 5 الگوریتم های ابتدایی جستجو 

صفحه 3:
عامل حل مسأله عامل حل مسأله يكك نوع عامل هدف كرا مى باشد. عامل حل مسأله. مسأله داده شده را از طريق يافتن دنباله اى از عمليات كه آنرا از حالت اولیه مسأله به یک حالت هدف می برد؛ حل مى كند. مراحل حل مسأله توسط عامل حل مسأله: (۱) فرموله سازی هدف (۲) فرموله سازی مسأله ( انتخاب حالات و عملیات به دنبال فرموله سازی هدف) (۳) جستجو ( برای یافتن دنباله عملیات مورد نظر یا راه حل مسأله) (۴) اجرا 

صفحه 4:
مشخص كردن وضعیت ها * هر وضعیت را به صورت ( ,36) نشان مى دهيم به طوريكه: سیک : مقدار آبموجود در تنگة لیتری می باشدو # : مقدار آبهوجود در تنگا لیتری می باشد 

صفحه 5:
تعیین وضعیت هدف هدف : در این مسأله هدف این است که به وضعیتی برسیم که ‎SS al yo‏ ۴ لیتزی حاوی ۲ لشر لب و تنگ ۳ لیتری خالی باشد. بنابراین می توان وضعیت هدف را به شکل زیر فرموله (2, 0) 7. 

صفحه 6:
تعيين وضعيت اولیه وضعیت اولیه : در ۱ ين مسأله از وضعیتی شروع می کنیم که در نهر و تکفا تبللن می باشتقد. بتابراین می اتوان, وعنمیت یذ را به شکل زیر فرموله نمود: (0, 0) 0 

صفحه 7:
مد مد مد هما جز هك كذ اذ تعيين عملكرها تنگ "ا ليترى در تنكك ؟ ليترى تا پرشدن آن تنگ ۴ لیتری در تنگگ ۳ لیتری تا پرشدن آن خالی کردن مقداری از خالى کردن مقداری از خالی کردن تمام آب تنگ ۴ لیتری در ۳ لیتری خالى كردن تمام آب تنگ ۳لیتری در ۴ لیتری خالى كردن تنگگ ۴ لیتری خالى كردن تنكك ‎SAY‏ در صفحه بعد اين عملكرها فرموله سازى شده اند 

صفحه 8:
عملگرها (XY | X < 4) > (4, Y) ‘GY |Y <3) > & 3) (XY |X+Y>=4,Y > 0) > (4, Y-(4-X)) (XY |X+Y>=3,X > 0) > (KX - (3 - Y), 3) (OY | RY s<=5,, 5:20) 200 ey (YY|X+Y<=4,Y>0) > (X+Y, 0) (SY) X >'0) > (0, Y) (X,Y | Y > 0) > (X, 0) خ ‎by‏ د ارك ‎el‏ 

صفحه 9:
تابع آزمون هدف و هزینه مسیر تابع آزمون هدف: اگر وضعیت فعلی برابر (۲,۰) باشد مقدار درست و در غیر این صورت مقدار نادرست را بر می گرداند. تلبع هزينه مسير: هزينه هر عمل برابر یک می باشد. بنابراین هزینه یک مسیر برابر با طول آن مسیر ( تعداد عملیات) می باشد. 

صفحه 10:
یک راه حل نمونه حالت اولیه (شریع) ‎m=) (eo) em) (ea) em) (eo) am)‏ -223 و ردم) ود = ~ حالت هدف ( نهايى) دنباله عملیات: (۲, ۶و ۲و ۳: ۷ 1۶ 

صفحه 11:
عامل های حل مسأله شکل محدود شده عامل های عمومی function SIMPLE-PROBLEM-SOLVING-AGENT( p) returns an action inputs: p, a percept static: s, an action sequence, initially empty state, some description of the current world state g,agoal problem, a problem formulation state € UPDATE-STATE( state, p) if sis empty then g © FORMULATE-GOAL( state) problem ¢€ FORMULATE-PROBLEM( state, g) s € SEARCH( problem) action € RECOMMENDATION( s, state) s € REMAINDER( 5, state) 11 

صفحه 12:
مثال: رومانی یک روز تعطیل در رومانی؛ مکان فعلی شهر آراد ‎AS get senna gulip‏ فرموله سازی هدف: بودن در بخارست فرموله سازی سأله: حالت ها: شهرهای مختلم عملیات: رفتن از شهری به شهر دیگر بافتن پاسخ: دنباله ای از شهرهاء مانند: ‎Arad > Sibiu > Fagaras > Bucharest‏ 12 

صفحه 13:
Ara Sibiu, Fagaras | Vaslui Rimnicu Vilcea | ‏لج‎ Pitesti \ 130 ۱0۱ 138 Hirsova 86 ucharest ۳ 9 Eforie Giurgiu 

صفحه 14:
انواع مسأله قطعی كاملا دسترس يدير سل تک - حالته عامل دقیقا می داند در چه حالتی خواهد بود؛ راه حل یک دنباله می باشد. قطعی, غير دسترس يدير ‎slag‏ ‏ممكن است عامل ايده اى درباره اينكه كجاست نداشته باشد؛ راه حل ( در صورت وجود) یک دنباله است. غیر قطعی و ایا دسترس پدیر جزئی > مسائل احتمالی ادرااک اطلاعات جدیدی درباره حالت فعلی فراهم می کند. در حین اجرا باید از حسگرها استفاده کند. راه حل به صورت یک درخت اغلب جستجو و اجرا به صورت 1۳161716376 ‎clad‏ حالت اشناخته 7 مسائل اکتشانی (6صت1ظ0) 14 

صفحه 15:
داد 2 تکت-حالقه. شروع ۵#. مثال: دنیای مکش ‎BR‏ لت که هه | 1 ل 8 

صفحه 16:
مثال: دنياى تك-حالته. شروع #د. لع1ا5 بأاطوتظ] جند-حالته. شروع در }1 ۲ مع ارما ‎Right joc Je‏ به ۱۴۳۲۸۱ 16 له ah Ae 

صفحه 17:
مثال: دنیای مکش تكك-حالقه. شروع #د. ‎(Right, Suck}‏ 1۸,۷۶۵ ۴۳۲,۱۱ ‏چندسحالته» شروع در‎ ۱۴۳۲۸۱۱ ‏به‎ Right je ‏مثال‎ ‎|Right, Suck, Left, Suck) احتمالی» شروع در ۵#. قانون مورفی: مکش می تواند یک فرش تميز را کثیف کند.درک محلی: گرد و خاک و محل ‎(Right, if dirt then Suckj‏ 17 8 ah Ae 18 ah 

صفحه 18:
فرموله سازی مسائل تک-حالته یک مسأله بوسیله چهار مورد تعریف می شود: حالت اولیه‌مثلا بودن در شهر ۸۲۵0 تابع حالت بعدی ((۱6 ‎(Successor function S(‏ ‎x)‏ )5- مجموعه لعاز زوج هایعمل‌حالت ‎S( Arad) = {<Arad > Zerind, Zerind>, ...}‏ تابم تست هدف ‎(Goal test function)‏ ‎"x = “at Bucharest ‘~~‏ ‎NoDirt( x) : 2.6‏ ‎@ath cost function) ju ab‏ مثلا؛ مجموع فواصل» تعداد عمل های انجام شده و ... هزینه گام ‎c( x, a, y) = 0 «Step cost)‏ راه حل:دنباله ای از عملیات که از حالت اولیه شروع وبه حالت هدف ختم می شود. 18 

صفحه 19:
انتخاب یک فضای حالت دنیای واقعی به شدت پیچیده می باشد بنابراین» برای حل مسأله باید فضای حالت انتزاعی باشد. حالت ( انتزاعی) < مجموعه ای از حالت های واقعی عمل ( انتزاعی) - تر کیبی پیچیده از عمل های واقعی ‎uc‏ 2611110 << ۸۵۲80 می تواند مجموعه ای پیچیده از اعمال باشد. ‏راه حل ( انتزاعی) - مجموعه ای از مسیرهای واقعی که در دنیای واقعی راه حل می باشند. ‏هر عمل انتزاعی باید از مسأله اصلی ساده تر باشد! ‎19 

صفحه 20:
مثال: گراف فضای حالت دنیای مکش ۳ Cele te ۳ لعل ‎(FELTED‏ ‏ی -Q ۳ D 

صفحه 21:
مدال: : گراف فضای حالت دنیای مکش 9۹ هل ‎Rie eee‏ ‘fa ۳ ‏]تس‎ (۳ To 5 وجود كرد و خاك و مكان هاى عامل ( بدون در نظر كرفتن مقدار كرد و خاک) ‎Left, Right, Suck‏ نبودن كرد و خاكك بازاء هر عمل ‎١‏ 

صفحه 22:
22 8 Goal State 3 Start State 

صفحه 23:
7 2 4 1 2 3 5 6 4 5 6 8 3 1 7 8 Start State Goal State اعداد صحیح بیانگر محل کاشی ها حرکت خانه خالی به چپ. بالاء راست و پایین حالت هدف ( داده شده) چز بازاء هر حرکت ۱ 

صفحه 24:
ع مساله هشت وزير قراردادن هشت وزير در صفحه شطرنج به طوريكه هيج وزيرى نتواند به وزير ديكرى حمله كند. آزمون هدف: ۸وزیر روی صفحه شطرنج که با هم برخورد ندارند. هزینه مسیر: صفر حالات: ترتیب ۸ وزیر هر کدام در یک ستون تال رویرو: ۴۶۸ ۲و ۷ ۵ ۰۳ ۱) عملگرها: انتقال یک وزیر دارای برخورد به ‎ee‏ دیگری در همان ستون 24 

صفحه 25:
ریاضیات رمزی حالات: یک معمای رمزی که در آن تعدادی حرف با رقم جایگزین شده باشد. عملگرها: جایگزینی یک حرف با رقمی که قبلا در معما ظاهر نشده باشد. آزمون هدف: معما فقط شامل ارقام است و مجموع صحیح باشد. راه حل - هزينه مسير: صفر 25 

صفحه 26:
3 5 مساله كشيش ها و ادمخوارها حالات : يكك سه تايى مرتب كه شامل تعداد كشيشها و تعداد آدمخوارها در ساحلى از رودخانه كه مسأله از آنجا شروع شده و محل قايق ( شمال /جنوب)- مثلا حالت شروع (7, ‎2١,"‏ عملكرها: جابه جايى يكك كشيش» دو كشيش»ء يكك كشيش و يكك آدمخوار» یک آدمخوار و دو آدمخوار توسط قایق به سمت دیگر رودخانه. آزمون هدف : (۰ ۰ ۰) هزینه مسیر: تعداد دفعات عبور قایق از عرض رودخانه 26 

صفحه 27:
الكو رد یتمهای جسنجوی درحت ایده اصلی: کاوش 01111116 و شبیه سازی شده فضای حالت بوسیله تولید حالات بعدی حالت هایی که تا کنون تولید شده اند. ‎function GENERAL-SEARCH( problem, strategy) returns a‏ ‎‘solution , or failure‏ ‎initialize the search tree using the initial state of problem‏ ‎loop do‏ ‎if there are no candidates for expansion then return failure‏ choose a leaf node for expansion according to strategy if the node contains the goal state then return the corresponding solution search tree 2 

صفحه 28:
28 

صفحه 29:
29 

صفحه 30:
30 

صفحه 31:
پیاده سازی: حالت و گره یک حالت ( بیانگر) یک پیکره بندی فیزیکی می باشد یک گره یک ساختار داده ای تشکیل دهنده بخشی از درخت جستجو شامل: پدر؛ فرزندان؛ عمق و هزينه مسير (16 )0 است. parent, action : ‏حالت ها‎ پدن فرزنده عمق و هزینه مسیر ندارند! ‎Node depth = 6‏ 4 هو ‎g=6‏ ‏۱ ‎fe‏ ‏ام 2 ادا ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ae‏ (228111] كره هاى جديد ايجاد مى كند» فیلدهای مختلف را مقدار می دهد و با بي استفاده از ابع 51100۳55001517 مسأله حالت های مربوطه ایجاد می شود. ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 32:
پیاده سازی: جستجوی درخت گلی function TREE-SEARCH( problem, QUEUING-FN) returns a solution or failure nodes € MAKE-QUEUE( MAKE-NODE(INITIAL-STATE|[ problem] ) loop do if nodes is empty then return failure node € REMOVE-FRONT( nodes) if GOAL-TEST[problem] applied to STATE( node) succeeds, then return node nodes € QUEUING-FN( nodes, EXPAND( node, problem) ) 32 

صفحه 33:
پیاده سازی: ناپم گسترش گره ها function EXPAND( node, problem) returns a set of nodes successors € the empty list for each action, result in SUCCESSORS-FN[ problem]( STATE[ node]) s € anew node PARENT-NODE[ s] € node; ACTION[ s] € action; STATE[ s] € result PATH-COST[ s] € PATH-COST[ node] + STEP-COST( node, action, 53) DEPTH s] > [2082111] 2006[ + 1 add sto successors 33 

صفحه 34:
استراتزى هاى جستجو یک استراتژی بوسیله ترتیب گسترش كره ها تعريف مى شود. ابعاد ارزيابى استراتزى ها: كامل بودن - آيا در صورت وجود راه حل» هميشه راه حلى بيدا مى كند؟ پیچید گی زمانی - تعداد گره های تولید شده/گسترش یافته پیچید گی حافظه - حداکثر تعداد گره ها در حافظه بهینگی - آیا همیثه کم هزینه ترین راه حل را بيدا مى كند؟ سید گی زمان و فضا برحسب پارامترهای زیر سنجیده می شوند: 9 - حلا کثر فاکتور انشعابدرختجستجو 0 - عمق كم هزينه ترين راه حل - حللكثر عموؤفضاءئحا لل ممكرلستهه باشد) 34 

صفحه 35:
استرتزی های جستجوی ناآگاهانه وب ع ویس تنها از اطلاعات موجود در تعریف مسأله جستجوی اول-سطح (۳5ظ) جستجوی هزینه-یکسان (1708) جستجوی اول-عمق (عمقی) (1(۳5) جستجوی با عمق محدود (1(1,5) حتقعواق مق کته تک ای( (011) 35 

صفحه 36:
چستجوی سطحی هربار سطحی ترین گره گسترش نیافته را گسترش می دهد. پیاده سازی: 6 ب که ) ۳1۳ می‌باشد 11611100-۳۴1( )ف_رزندلن‌جدید را ۳۹ 

صفحه 37:
چستجوی سطحی هربار سطحی ترین گره گسترش نیافته را گسترش می دهد. پیاده سازی: ‎tL... FIFQs << fringe‏ فرزندان‌جدید به لنتهایم فلضافه ‎eet‏ ‎Q‏ ‎be ©‏ / ۷ /ر ۷ /” 

صفحه 38:
چستجوی سطحی هربار سطحی ترین گره گسترش نيافته را گسترش می دهد. پیاده سازی: 6 بکصنل) ۳1۳ می‌باشد. فرزندن‌جدید به لنتها لضافه می‌شوندد 

صفحه 39:
چستجوی سطحی هربار سطحی ترین گره گسترش نيافته را گسترش می دهد. پیاده سازی: 6 بکصنل) ۳1۳ می‌باشد. فرزندن‌جدید به لنتها لضافه می‌شوندد 4 9 2 <۵ © © © 

صفحه 40:
مثال: جستجوی سطحی > عير که اسات کته 9 ‎(rad) Oradea) Card) 2 lea) Fagara rad‏ 

صفحه 41:
کاما ۲۴ بله ( به شرط محدود بودن ‎(D‏ 1+ 0+ 9+ ... + 9٩ 2 0)0( 6 4, حاذذل ؟؟ (2)08) چونهمه گره ها را در حافظه نگه می‌دارد ‎Wangs‏ بله ( اگر هزینه هر عمل یک باشد)؛ در حالت کلی خیر ‏مشکل اصلی حافظه می باشد. ‎41 

صفحه 42:
میزان مصرف حافظه و زمان در 18۳5 b=10 ‏گره در ثانیه‎ ۰ هر گره ۱۰۰ بایت 42 Memory 100 bytes 11 kilobytes 1 megabyte 111 megabytes 11 gigabytes 1 terabytes 111 terabytes 11,11 terabytes 1 Time Millisecon seconds Seconds Minutes Hours Days Years years 11 18 31 128 35 3500 Node 5 1 111 1,1 1 105 10° 109 10% 10" 10 12 14 

صفحه 43:
جستجوی هزینه -یکسان هربار کم هزینه ترین گره گسترش نیافته را گسترش می دهد. پیاده سازی: 26 - صفیکه برلساس‌وزینه مسیر مرتبشده باش معادل جستجوی سطحی اگر هزینه گام ها مساوی باشند. کامل؟؟ بله اگر هزینه گامها <- ‎٩‏ تعداد گره هایی که هزینه مسیر آنها کوچکتر یا مساوی حجان ‎Ol) ool py‏ پیچید 5 نی حافظه؟؟ مانند پیچید گی زمانی بهينه؟؟ بله ( گره ها به ترتیب صعودی (12 )© گسترش می یابند). 43 

صفحه 44:
مثال: جستجوی هزینه یکسان “STU ‏هتم‎ Grated Cont) ina a) ‏سوه‎ > i (Arad) (Lage) 44 

صفحه 45:
مثال: جستجوی هزینه یکسان “Ls | 15 ce G 11 ۰.0 

صفحه 46:
جستجوی عمفی هربار عمیق ترین گره گسترش نیافته را گسترش می دهد. پیاده سازی: ‎fringe‏ - يشته 1۳*00[ فرزندان جدید را در ابتدا درج می کند. ۵۰ -- or 3 8 % 4 % S DW GF ۵ ico ss al at) 89 ۵ ‏ب‎ ۵ ۵ ( © © 46 

صفحه 47:
جسنجوی عمقی هربار عمیق ترین گره گسترش نیافته را گسترش می دهد. پیاده سازی: ‎fringe‏ - يشته 1۳*00[ فرزندان جدید را در ابتدا درج می کند. oo 7 وتم 0 5 له ‎go»‏ PN Ie of Day 9 © ( ۵ ( 49 9 © 47 

صفحه 48:
جسنجوی عمقی هزبار عمیق ترین گره گسترش نیافته:را گسترش می دهد: پیاده سازی: ‎fringe‏ - يشته 1۳*00[ فرزندان جدید را در ابتدا درج می کند. ‎wk‏ ام و کم ‎DOD‏ © ف © ن 42 ‎48 

صفحه 49:
جسنجوی عمقی هزبار عمیق ترین گره گسترش نیافته:را گسترش می دهد: پیاده سازی: ‎fringe‏ - يشته 1۳*00[ فرزندان جدید را در ابتدا درج می کند. PVA Souk ' 0 © © 2 ‏«ن‎ © © 49 

صفحه 50:
جسنجوی عمقی هزبار عمیق ترین گره گسترش نیافته:را گسترش می دهد: پیاده سازی: ‎fringe‏ - يشته 1۳*00[ فرزندان جدید را در ابتدا درج می کند. ۸ ۵ 8 ها ری ع 2 © © «4 4 5 2 0 50 

صفحه 51:
جسنجوی عمقی هزبار عمیق ترین گره گسترش نیافته:را گسترش می دهد: پیاده سازی: ‎fringe‏ - يشته 1۳*00[ فرزندان جدید را در ابتدا درج می کند. #۴ © 4 ۵ Pe oh ‏لوح‎ ‎0 © © 9 © © 51 

صفحه 52:
جسنجوی عمقی هربار عمیق ترین گره گسترش نیافته را گسترش می دهد. پیاده سازی: ‎fringe‏ - يشته 1۳*00[ فرزندان جدید را در ابتدا درج می کند. 52 

صفحه 53:
جسنجوی عمقی هربار عمیق ترین گره گسترش نیافته را گسترش می دهد. پیاده سازی: ‎fringe‏ - يشته 1۳*00[ فرزندان جدید را در ابتدا درج می کند. 53 

صفحه 54:
جستجوی عمفی هزبار عمیق ترین گره گسترش نیافته:را گسترش می دهد: پیاده سازی: 6 - پشته ‎LIFO‏ فرزندان جدید را در ابتدا درج می کند. 1 ۵ / EO OOOO 54 

صفحه 55:
جستجوی عمفی هزبار عمیق ترین گره گسترش نیافته:را گسترش می دهد: پیاده سازی: 6 - پشته ‎LIFO‏ فرزندان جدید را در ابتدا درج می کند. ا / و ۵ ۵ ۵ 55 

صفحه 56:
جستجوی عمفی هزبار عمیق ترین گره گسترش نیافته:را گسترش می دهد: پیاده سازی: 6 - پشته ‎LIFO‏ فرزندان جدید را در ابتدا درج می کند. 56 

صفحه 57:
جستجوی عمفی هزبار عمیق ترین گره گسترش نیافته:را گسترش می دهد: پیاده سازی: 6 - پشته ‎LIFO‏ فرزندان جدید را در ابتدا درج می کند. 57 

صفحه 58:
مثال: جستجوی عمقی مهنم Ge) 1 حلقه بى يايان ! 8 بی پایان ! ‎G,‏ ‎Greet‏ ‏در این جستجو نیاز به فضای حالت محدود و بدون چرخه داریم. ۱ ‎iP‏ 5 ‎and) (Sibia) mi‏ پا باید عالات تکرازق جيك شويد. رس ی و 58 

صفحه 59:
خصوصیات جستجوی عمقی کامل 19 خر (در فضاهای حالت با عمق نامحدود» دارای حلقه) برای اجتناب از حالات تکرای در طول مسیر نیاز به اصلاح دارد. بنابراین؛ در فضای حالت محدود کامل است. پیچی د کی زمانی؟1 (۳ )0 اگر 1 خیلی بیشتر از 4 باشد» بسیار زياد آما اگر تعداد راه حل ها زياد باشد» سریعتر از جستجوی سطحی پیچید گی حافظه؟؟ (110 )0 بسه صورتخطلل ‎Beg‏ خير 59 

صفحه 60:
جستجوی پا عمق محدود < جستجوی عمقی با محدوده عمقی 1 يعنى»فرزندان گره های واقع در عمق / تولید نخواهند شد. در این استراتژی با در نظر گرفتن یک محدوده عمقی مانند 1 از به دام افتادن جستجوی عمقی در یک حلقه بی پایان جلوگیری می شود.( برش روی درخت جستجو) مثلا در نقشه رومانی چون ۲۰ شهر وجود دارد بنابراین طول راه حل بايد حداکثر ۱۹ باشد. بنابراین هیچ وقت گره ای با عمق بیش از ‎۱٩‏ بررسی نخواهد شد. اگر در محدوده عمقی 7راه حلی وجود داشته باشد» بالاخره پیدا خواهد شدة اما هیچ تضمینی برای یافتن راه حل بهینه وجودندارد. 60 

صفحه 61:
جستجوی پا عمق محدود Ho )[ < 6 ‏بله (اگر‎ پیچید گیی زمانی19 ‎O(b)‏ 2 ‎Fovsey‏ _ حافظه؟1 0) Bain ‏خير‎ 

صفحه 62:
جستجوی پا عمق محدود ‎function DEPTH-LIMITTED-SEARCH( problem, limit) returns‏ ‎soln/fail/cutoff‏ RECURSIVE-DLS(MAKE-NODE(INITAIL-STATE[ problem), problem, limit) function RECURSIVE-DLS( node, problem, limit) returns soln/fail/cutoff cutoff occurred? € false if GOAL-TESTI problem]( STATE[ node]) then return node else if DEPTH node] = limit then return cutoff else for each successor in EXPANDE( node, problem) do result € RECURSIVE-DLS( successor, problem, limit) if result = cutoff then cutoff occurred? € true 

صفحه 63:
جستجوی عمیق کننده تکراری مشکل اصلی در جستجوی عمقی با عمق محدود شده (101.5) انتخاب ‎8S‏ ‏محدوده عمقی مناسپ است. در نقشه رومانی طول بزرگترین مسیر بین دو شهر ‎٩‏ می باشد(قطر» و این محدوده عمقی مناسب تر از ‎۱٩‏ می باشد. اما در بیشتر فضاهای حالت انتخاب محدوده مناسب قبل از حل مسأله میسر نمی باشد. جستجوی عمیق کننده تکراری روشی برای تعیین محدوده عمقی مناسب با امتحان کردن تمامی محدوده ها ( از صفر به بالا) می باشد. یعنی اول عمق صفر بعد عمق ١ح‏ بعد عمق ۲ و ... 63 

صفحه 64:
جستجوی عمیق کننده تکراری ‎function ITERATIVE-DEEPENING-SEARCH( problem)‏ returns a solution inputs: problem, a problem for depth € 0 to ~ do result € DEPTH-LIMITTED-SEARCH( problem, depth) if result + cutoffthen return result 64 

صفحه 65:
جستجوی عمیق کننده تکراری جستجوی عمیق کننده تکراری مزایای جستجوی سطحی و عمقی رابا هم تركيب مى كند: جستجوى سطحى كامل و بهينه است. جستجوى عمقى داراى مصرف حافظه خطى مى باشد. اين جستجو از نظر بيجي د كى زمانى مانند جستجوى سطحى مى باشد به جز اينكه برخى حالات جند بار بسط داده مى شوند. 65 

صفحه 66:
جستجوی عمیق کننده تکراری (0 < [) 20. a Limit = 0 

صفحه 67:
جستجوی عمیق کننده تکراری (1 > [) 

صفحه 68:
جستجوی عمیق كننده تكرارى (2 > [) شب يسيس تيم ات کبک مر ۳۹ 

صفحه 69:
جستجوى عميق كللده تكرارى ‎3B)‏ = 0 Limit ~3 ao 0 & By doe ck wok 83 ‏ك8 ن 0 ف‎ 5 01 ١ 4 ‏أن نب و‎ © 0 

صفحه 70:
خواص جستجوی عمیق کننده تکراری کامل ۲ بله ‎(dm 1) b® + db! + (d.— 1) 2 2 as es‏ O(b?) O(bd) seats ‏پیچیدگی‎ بهینه 1۶ بله (اگر هزینه گام - یک) می تواند برای کاوش درخت جستجوی هزینه یکسان اصلاح شود. 

صفحه 71:
تعداد گره های گسترش یافته در ۳9۳5: 0 + 01 + ... + 2 +ط + 1 اگر 10 < طو 5 < 0: 111,111 = 000 ,100 + 10,000 + 000 ,1 + 100 + 10 + 1 ‎IDS 53‏ 123,456 = 100,000 + 20,000 + 3,000 + 400 + 50 + 6 محاسبه میزان سربار: 11% = 100 *)111111)/111111 - 123456(( با فزایش فاکتور انشعاب 8 میزان سربار کاهش می یابد. در بدترین حالت 2 < 0 سربار 1۱۰۰ است و این جستجو دو برابر زمان می برد. برای له های بز رگ: (1 - ظ) / ‎Nurs = b‏ /عمل 71 

صفحه 72:
استدلال جلورو در مقابل عقبرو هدف روال جستجوء کشف یک مسیر از میان فضای حالت مسأله از یک حالت اولیه به یک حالت هدف می باشد. چنین جستجویی به دو روش ممکن است: (۱) رو به جلو از حالت اولیه به سمت حالت هدف (۲) رو به عقب. از حالت هدف به سمت حالت اولیه فا کتورهای موثر در انتخاب جهت جستجو ۱- تعداد حالت های اولیه و حالت های هدف ( کمتر به بیشتر) مثال: رانند گی از یک محل ناآشنا به سمت منزل( عقبرو) ۲- فا کتور انشعاب در دو جهت ( کمتر) مثال: اثبات تتوری ( از یکك اصل می توان تعداد زيادى تثورى نتيجه كرفت)( عقبرو) ۳- طبیعی بودن جهت جستجو مثال: سیستم خبره تشخیص بیماری ‎MYCIN‏ جلورو) 272 

صفحه 73:
جستجوی دو طرفه ‎(Bidirectional Search)‏ ‎co!‏ جستجوی همزمان: ( به شرطی که میسر باشد) از حالت اولیه به سمت حالت هدف (0۳773۳0) ؛ و از حالت هدف به سمت حالت ‎(Backward). Js)‏ اگر عملیات قلبل وارهنه کردن باشند( مانند معمای هشت)؛ می توان از جستجوی دو طرفه استفاده نمود؛ اما مثلا در مسأله تنگ ‎OT‏ تمام عملیات قابل وارونه سازی نمی باشند: مثال: 10 < ط و6 < 0 حستجوی سطحی: ۱:۱۱۱:۱۱۱ گره را بررسی می کند جستجوی دو طرفه تنها ۱,۱۱۱ + 2۱,۱۱۱ ۲:۲۲۲ را بررسی می کند. 73 

صفحه 74:
چستجوی دو طرفه ‎@idirectional Search)‏ در مسایلی که دارای حالات اولیه و هدف متعددی باشند. ممکن است با ت روبرو شود. باید یک راه موثر برای کنترل هر گره جدید وجود داشته باشدتا متوجه شویم که آیا این گره قبلا در درخت جستجوی طرف دیگر ظاهر شده است یا خبر ( اغلب با جدول پراکندگی) بايد د ‎age‏ که در هر جهت از کدام روش جستجو استفاده ‎Sab eat‏ گره های -داقل یکی | 5 ‎tiga‏ لقره عردو ابر سطحی) بنابراین ۷ حافظه و زمان (0)109/2) است. 74 

صفحه 75:
مقایسه استراتزیهای جستجو Criterion |Breadt Unifor Depth- Depth- Iterativ Bidirectio ‎m- First Limited e- nal‏ خط ‎First Cost Deepen (if‏ ‎ing _ applicable‏ ) ‎Time bt ‘bt be BD bt bi? ‎Space bt bt bm bl bd be ‎Optimal | Yes Yes No No Yes Yes 2 ‎Complet | Yes Yes No Yes, if Yes Yes ‎2 120 ‎ ‎75 ‎ ‎ ‎ ‎ 

صفحه 76:
‎ONG‏ تکراری ‏شکست در تشخیص حالت های تکرای می تولند یک مسأله خطی ‎EK aa ly‏ مسأله نمایی تبدیل کند! ‎ ‎76 

صفحه 77:
جستجوی گراف function GRAPH-SEARCH( problem, fringe) returns a solution o! failure closed € an empty set fringe € INSERT( MAKE-NODE(INITIAL-STATE[ problem), fringe) loop do if fringe is empty then return failure node € REMOVE-FRONT( fringe) if GOAL-TESTI problem)( STATE[ node]) then return node if STATE[ node] is not in closed then add STATE[ node] to closed fringe € INSERTALL( EXPAND( node, problem), fringe) end 

صفحه 78:
خلاصه فرموله سازی مسأله اغلب نیاز به انتزاع جزیبات مسأله دارده تا بتوان فضای حالتی بدست آورد که به صورت مقرون به صرفه ای قابل ‏ کاوش کرد ن و جستجو باشد. انواع استراتژی های نا گاهانه وجود دارد. مصرف حافظه جستجوی عمیق کننده تکراری دارای مرتبه خطی می باشد و زمان خیلی بیشتری نسبت به سایر روشهای نا گاهانه مصرف نمی کند. 78