آموزش گام به گام هوش مصنوعی

صفحه 1:
آموزش گام به گام هوش مصنوعی 

صفحه 2:
منابع | کتاب هوش مصنوعی. رهیافتی نوین ویرایش سوم 

صفحه 3:
فصل اول: مفاهیم پایه 

صفحه 4:
مفاهیم پایه | تعريف هوش مصنوعى ل جهار ديدكاه مختلف در تبيين هوش مصنوعى لأ انسانى فكر كردن - علوم شناختى ل انسانى عمل كردن - ازمون توريئك 1 عقلالی عمل كردن - منطق لا عقلانى عمل كردن - نكرش عامل كرايانه لا دسته بندى ديكر ل نماد كرايانه پیوند گرایانه 

صفحه 5:
تاریخچه هوش مصنوعی پیدایش در دهه ۵۰ میلادی ارزوهای بزرگ در دهه ۶۰ میلادی زمستان اولیه هوش مصنوعی سیستم های خبره و تجاری شدن آن در دهه ۷۰ هوش مصنوعی پیوند گرایانه در دهه:۸ زمستان دوم هوش مصنوعی عامل های هوشمند در دهه ‎٩۰‏ 5-2 صاش كات كاك ييوند با وب در سالهاى اخير 

صفحه 6:
فصل سوم: روشهای جستجو 

صفحه 7:
فضای حالت ل انتزاعى كردن مسئله (00أنأء 8518 ممع ااممرص) ل فرموله سازى مسئله و فرموله سازى هدف 1 مثال از فضای حالت در مسائل طراحی الگوریتم مانند شاخه و حد ] گراف فضای حالت 1 جستجو- راه حل 

صفحه 8:
توصیف گراف فضای حالت حالت اولیه اعمال (اگر قابل انجام باشند) مدل انتقال (تابع جانشین) تست هدف على عر سیر ریت مر 

صفحه 9:
مسئله معمای ۸ 2 Goal State 6 7 2 4 8 6 8 3 1 Start State A typical instance of the 8-puzzle. Figure 3.4 

صفحه 10:
توصیف فضای حالت معمای ۸ 5-2 نت لح نت ال كاك حالات وضعیت آغازین اعمال مدل گذر آزمون هدف هزینه مسیر کل حالت های مستله ‎1٩‏ تعداد حالتهای قابل دسترس برابر است با ۲/۸ 

صفحه 11:
مسئله ۸ وزیر فرموله سازی تدریجی مسئله عدم تهدید سطری و ستونی وضعیت آغازین صفحه خالی اعمال: افزودن وزیر به سطر جدید تعداد حالتهای ممکن کمتر از ۱۸ مدل گذر : حالت صفحه را بعد از افزودن وزیر جدید می دهد SoS Ss os o آزمون هدف: ۸ وزیر بدون تهدید در صفحه باشند 

صفحه 12:
الگوریتمهای جستجو 

صفحه 13:
برخی واژه های کلیدی Search Tree- Generation- Expansion Parent Node- Child Node- Leaf Node Frontier = Open List Repeated States- Loopy Paths- Redundant Paths Explored Sets= Closed Sets ص وص اح هم هه 

صفحه 14:
(a) (b) «© Figure 3.9 The separation property of GRAPH-SEARCH, illustrated on a rectangular-grid problem. The frontier (white nodes) always separates the explored region of the state space (black nodes) from the unexplored region (gray nodes). In (a), just the root has been ex- panded. In (b), one leaf node has been expanded. In (c), the remaining successors of the root have been expanded in clockwise order. 

صفحه 15:
شمای کلی الگوریتم های جستجو function TREE-SEARCH(problem) returns a solution, or failure initialize the fromier using the initial state of problem loop do ifthe frontier is empty then return failure choose a leaf node and remove it from the frontier if the node contains a goal state then return the corresponding solution expand the chosen node, adding the resulting nodes to the frontier function GRAPH-SEARCH( problem) returns a solution, or failure initialize the frontier using the initial state of problem initialize the explored set to be empty loop do if the frontier is empty then return failure choose a leaf node and remove it from the frontier ifthe node contains a goal state then return the corresponding solution add the node to the explored set expand the chosen node, adding the resulting nodes to the frontier only if not in the frontier or explored set Figure 3.7. An informal description of the general tree-search and graph-search algo- rithms. ‘The parts of GRAPH-SEARCH marked in bold italic are the additions needed to handle repeated states. 

صفحه 16:
ملاکهای کارایی روشهای جستجو کامل بودن پیچیدگی زمانی پیچیدگی فضایی فاکتور انشعاب 0 عمق راه حل 0 بیشترین عمق گراف ۲۲ 

صفحه 17:
دسته بندی کلی | روشهای جستجوی اگاهانه | روشهای جستجوی غیر اگاهانه 1 تفاوت بین این روشها 

صفحه 18:
جستجوی غیر اگاهانه 

صفحه 19:
(Brewth-Prot search) Jal gla gaia ۱ وجو اوور وا ‎wb 4‏ وگ Figure 3.12 Breadth-first search on a simple binary tree. At each stage, the node to be expanded next is indicated by a marker. 

صفحه 20:
CRG function BREADTH-FIRST-SEARCH( problem) returns a solution, or failure node —a node with STATE = problem.INITIAL-STATE, PATH-COST = 0 if problem.GOAL-TEST(node.STATE) then return SOLUTION(node) frontier —a FIFO queue with node as the only element explored — an empty set loop do if EMpTy?( frontier) then return failure node — Pop( frontier) /* chooses the shallowest node in frontier */ add node.STATE to explored for each action in problem.ACTIONS(node.STATE) do child — CHILD-NODE( problem, node, action) if child.STATE is not in explored or frontier then if problem.GOaL-TEst(child.STATE) then return SOLUTION( child) frontier — INSERT( child, frontier) Figure 3.11 Breadth-first search on a graph. 

صفحه 21:
ملاکهای مقایسه 00 لا کامل بودن؟ بله 1 بهینگی؟ بله 1 پیچیدگی زمانی؟ - پیچیدگی فضایی؟ ‎b+b?+b3+...+b¢=O(b)+1 9‏ ] چرا (0)00+1 نیست؟ a (0۳*1)) گره در مجموعه مرور شدم و (*0)0) در مجموعه حاشیه نقطه ضعف مهم : فضای مصرفی نمایی 

صفحه 22:
جستجوی هزینه یکنواخت ‎function UNiFORM-CosT-SEARCH( problem) returns a solution, or failure‏ node —a node with STATE = problem.INITIAL-STATE, PATH-Cost = 0 frontier —a priority queue ordered by PATH-Cos', with node as the only element explored —an empty set loop do if Empry( frontier) then return failure node —PoP( frontier) /* chooses the lowest-cost node in frontier */ if problem GOAL-TES1(node.STATE) then return SOLUTION (node) add node.STATE to explored for each action in problem. ACTIONS(node,STATE) do child —CHILD-NobE( problem, node, action) if child. STATE is not in explored or frontier then frontier — INSERT( child, frontier) else if child STATE is in frontier with higher PaTH-Cost then replace that frontier node with child Figure 3.14 Uniform-cost search on a graph. ‘The algorithm is identical to the general graph search algorithm in Figure 3.7, except for the use of a priority queue and the addition of an extra check in case a shorter path to a fronticr state is discovered. The data structure for {frontier needs to support efficient membership testing, so it should combine the capabilities of a priority queue and a hash table. 

صفحه 23:
(Dept-First Search) Jal Goo ‏جستجوی‎ © ‏و‎ a © © Ne 31 ‏مهم مه‎ x ‏يكل ی‎ x «0 eo Yo ‏عه‎ ‏واي‎ ‎0 ‏با دم‎ stom moma. Noes 

صفحه 24:
0۳۳-5 aS eo So ‏ص و‎ با فرض حستجوی گرافی برای گرافهای متناهی کامل است. اما جستجوی درختی ان حتی برای گرافهای متناهی کامل نیست. هم جستجوی گرافی و هم درختی آن بهینه نیستند. پیچیدگی زمانی: (0)05 پیچیدگی فضایی: (0)0۳0 با استفاده از بيجويى به ‎(Back Tracking) cae‏ پیچیدگی فضایی به (0)۳0 کاهش مى يابد. 

صفحه 25:
جستجو با عمق محدود این روش قادر است مشکل کامل نبودن 0۳5 را با تعیین یک محدودیت حل کند. کامل است اگر عمق << باشد (1- عمق محدود شده) اين روش بهینه نیست. پیجیدگی زمانی: ()0 پیچیدگی فضایی: (0)0۱ ص وص اح هم سح 

صفحه 26:
Ad Jo hy vo oh Seeedo ‏وه‎ erative deepening Search ona bay wee 3 

صفحه 27:
“100-00-5 كامل بودن ؟ بله بهینگی؟ بله پیچیدگی فضایی؟ (00)ظ پیچیدگی زمانی؟ (0) 104-0 +... +0-1(02) +00 ص وص اح هم سح بهترين روش از بين روشهاى غيراكاهانه 

صفحه 28:
Figure 3.20. A schematic view of a bidirectional search that is about to succeed when a branch from the start node meets a branch from the goal node. 

صفحه 29:
مقایسه روشها Criterion | Breadth- Uniform- Depth- Depth-_—iterative-—_—Bidirectional First Cost First. Limited Deepening _(if applicable) Complete? Yes" Yes No No Yes" Yes Time O(b4) ‏رك *عاجام)0‎ O(b™) 0) O(b*) O(pe/?) Space O(b*) ‏ان‎ Olbm) — O(bE) O(bd) O(b4/?) Optimal? Yes’ Yes No No Yes® Yes" Figure 3.21 Evaluation of tree-search strategies. b is the branching factor; d is the depth of the shallowest solution; m is the maximum depth of the search tree; | is the depth limit. Superscript caveats are as follows: “ complete if b is finite; ’ complete if step costs > ¢ for positive ¢; © optimal if step costs are all identical; “ if both directions use breadth-first search. 

صفحه 30:
جستجوی اگاهانه 

صفحه 31:
تفاوت روشهای اگاهانه و غیر اگاهانه تابع ارزیابی ‎Evaluation Function: f(n)‏ تعیین میکند که کدام گره بايد بست داده شود ‎Heuristic Function: h(n) ls! ot‏ تابع ابتکاری تخمینی از هزینه مسیر بهینه از وضعیت جاری تا نزدیکترین هدف است. ‏توابع دیگر ‏(9)0 : هزینه مسیر از نقطه شرهع تا بسه گرد 9 ‏(0*)0: کوتاه تریرف اصله ممکراز مبدا تا گرد جایی!] ‏(0*)0: كوتام تريرفاصله از كره جاری] بسه نزمیکتریر‌هدف ‏(ه)* +(9*)0-(0)*]: كوتاهتريزمسير از مبدا تامقصد كداز كره (] عور میکندلگر 10 روی‌مسیر بهينه باشد برلبر با مسير بهينه يا.)* خولهدبود ‎ 

صفحه 32:
جستجوی اول بهترین حریصانه تابع ارزیابی (۴)۲۱(<۱۱)۳ یعنی تابع اکتشاف - تخمین هزینه از گره 0] به هدف ۳ کر می رسد به هدف نزدیکتر است+ کامل است؟ خیر - ممکن است در حلقه بيافتد. بهینه است؟ خیر پیچیدگی زمانی؟ (2)0۳۳) اما با بکاربردن تابع اکتشاف خوب می تواند بسیار بهبود یابد. پیچیدگی فضایی؟ (0)0۳) همه گره ها را در حافظه نگهداری می کند. aS eo So ‏ص و‎ 

صفحه 33:
منال (0) The initial state ‏حو‎ (b) After ee ‏سي‎ ‎a> Ca aD فو ‎co‏ ‏مف له ‎GD Gee‏ حكن نس Figure 323 Stages in a greody best-fist tre search for Bucharest with the straisht-line distance heuristic fis. Nodes are labeled with their h-values. 

صفحه 34:
الگوریتم جستجوی 3*0 f(n)=g(n)+h(h) a3 eb 4 1 تابع اکتشاف (۱)۳ قابل قبول (20۳01551016) است اگر برای هر گره ۲0۰ (0)*ط > > (۱)۳] باشد که در ان (۲*)۲۱] هزینه واقعی برای رسیدن به هدف از گره 10 | یک اکتشاف قابل قبول هرگز هزینه تخمینی را بیشتر از هزینه واقعی براورد نمی کند. 

صفحه 35:
مثال از جستجوی ‎HEA‏ 

صفحه 36:
حستجوی ‎KA‏ در نقشه رومانی | (a) The initial state 366-0366 جستجوی 586۱۵۲651 با شروع از 130 ‎f(Arad) = g(Arad)+h(Arad)=0+366=366‏ 

صفحه 37:
After expanding Arad 25 30321404253 44721184329 49-7 ‎Bre‏ را باز 0995 9 ‎PCa)‏ براى هر يك ١ذ‏ زيريركها محاسبه ميكنيم: ©©6- © 10+66 - زات )»+ (جاة ,)حت (بجا 0 )"ا 6620+ 106 ( مس( مه( یی 1001 6۵۵+ رن )سا امه )سس ‏بهترین انتخاب شهر ‎ew! Gir‏ 

صفحه 38:
جستجوی ‎EA‏ در نقشه رومانی (¢) After expanding Sibiu Se ‏حون را رس‎ 7 96 ر باز کرده و (۰)* را براى هر يك ‎[١‏ زيربركها محاسبه ميكنيم: ©660- ©0+66 66 (ل8)) (لج 0 ج51 ))ءحزلج 8" ‎Hh 90+0۳0-6‏ ( مه )مس هي )0 ‎P(Orenteu)=o( Gry, Orerteu) th Oredeu) =O O14 O0=9'70‏ ‎Otbru)=r(Obty, Riruins Otooa)+ h( Rimairs Ole =O OHIGO =O‏ حادص )د ‎ppb OAT oy‏ مسل() دس است ‎ 

صفحه 39:
جستجوی ‎EA‏ در نقشه رومانی (a) After expanding Rimnicu Vilcea 275974 وب 47118229 671-291360 415-2394176 040=2600006 55323000253 447=317+100 3664160 مدق کحطل ت6۳ را باز كرده و (0)" را براى هر يك |[ زيربركها مماسبه ميكنيم: 0000+ ۹/0690 ( 0۳ ,من )وت (مرس۳)۵ P(Ptevt)=o( Rrrciru Otrwua, Ptovt) He Prev) =P HID O=P UP ۲) ( ‏سا0 بحص )مت‎ 6+) 3-60 0+666-6©© بهترین انتخاب شهر عسعبه<) است 

صفحه 40:
جستجوی ‎EA‏ در نقشه رومانی ۵ After expanding Fagaras یدوب 7212229 ‎o> ap‏ هه ف ‏مه 2 مك رس 555 520-35616041 450-130 253823 اود ‏یه را باز كرده و (5)" زا براى هر يك اذ زيربركها مماسبه ميكنيم: 666-660+ © © 6- زنج © )!+ بج 6 ,عسوب ”)د (بجا 3 )د ‎P(@uckara!)=o( Pagar, Puchorrat)th(Bickarn)=POO+D=FOO‏ ‏بهترین انتغاب شهر ۳ ۱۱ است. ‎ 

صفحه 41:
جستجوی ‎HEA‏ در نقشه رومانی (6) After expanding ‏لاصيا‎ 4 GD EED Gad => ‏و موه‎ ۱ سس ۳ >= ‎Sp aS‏ مه هه دوه مهد اه وه مه ا باز كرده و (0)" را براى هر یک از زيربركها مماسبه ميكنيم: ‎P(@ charset) =o(Ptevt, Prcharet)+k(Poharret) = PIO +0=P00‏ بهترین انتغاب شهر بسموماس ۱۱۱ است 

صفحه 42:
قضیه امکان پذیری | قضیه: اگر (1)]0] قابل قبول باشد. * با استفاده از جستجوی درختی بهینه است 1 قضیه: اگر ۸/* پایدار باشد ۸ با استفاده از جستجوی گرافی بهینه است لا لم: در هر مرحله قبل از اتمام الگوریتم ۰*۵ همواره گره ای مانند 10" در لیست حاشیه با خواص سه گانه زیر قرار دارد: 1 ۱ رویم سیر بهینه تا هدفقرار دارد. ‎AD‏ پینه تکار را یافته لست ‎af(n’) <=C 1‏ 

صفحه 43:
اثبات بهينكى الكو ريتم 3:0 0غ 01 5 25 يك عدف شرربهينه مانند 62 توليد شده و ذر حاشيه باشد. و ‎1١‏ يك كره توسعه داده نشده در حاشیه باشد بطوری که ۲۱ روى كوتاهترين مسير به سمت هدف بهينه 6 باشد ‎Sort‏ ‏1 از انجایی که ‎gentoo f(G2)=9(G2) 4 h(G2)=0‏ | از انجایی که 32) غیربهینه است پس (9)062(<9)6 " 1 از انجایی که 0)6(<0 پس (۲)0(<9)6 ‎el‏ 92 

صفحه 44:
اثبات بهينكى الكوريتم 3500 أ بس ‎f(G)‏ > (2ه16 لا از انجايى كه ‎!١‏ قابل قبول است يس (م)*#طع-> ‎h(n)‏ g(n)+h(n) <=g(n) ‏ا‎ ‎+h*(n) f(n) <=f(G) ‏بيس‎ 1 لا پس (22(<۲)۳))؟ است و ۵* هرگز 22) را برای توسعه انتخاب نخواهد کرد 

صفحه 45:
بهینگی الگوریتم 20 1 #۵ گرد هارا به ترتیمفزلیش قدار ‎f‏ توسعه می‌دهد 1 به کانتور-؟ گره ها به تدریج افزوده می شود. | کانتور ام شامل گره هایی با 76 است زا Figure 3.28 Map of Romania showing ‏ز بو نموم‎ 300 f = 400, and f = 420, with Arad as the stan state, Nodes inside a given contour have f-costs less than or equal to the contour value 

صفحه 46:
خواص الكوريتم 3:00 | کامل است؟ بله (مگر اینکه تعداد گره هایی که مقدار ۴ انها از (63)؟ کوچکتر است بینهایت زیاد باشد. 0 نامحدود باشد یا هزینه مراحل غیر مثبت باشد) ‎O‏ بهینه است؟ بله 1 پیچیدگی زمانی؟ نمایی لا پیچیدگی فضایی؟ تمام گره ها در حافظه نگهداری می شود 

صفحه 47:
توابع اکتشاف ساز گار ] یک تابع اکتشاف سازگار یا یکنواخت است اگر برای هر گره 10. هر گره بعدی ۳ بنام 0* که با هر عملی مانند 8 تولید شده است. داشته باشیم: ا ‎h(n)<= c(n, a, n’) + h(n’)‏ 1 (0)] بر روی‌هر مسیری‌غی رکاهشیاست لا هر الگوریتم سازگار ۵/* قابل قبول است. 

صفحه 48:
غلبه توابع اکتشاف لا اگر دو نسخه از الگوریتم /* به نامهای ,۸۵ و و۸ برای حل یک مسئله داشته باشیم بگونه ای که باشد انگاه و*۵اگاه تر از ‎۸٩۴,‏ نامیده می شود. 1 اگر م۵ اگاه تر از ۵ باشد. در زمان اتمام این دو جستجو بر روی هرمثالی از مسئله هر گره ای که توسط و۸۴ بسط داده شده توسط ۸۴ نیز بسط داده خواهد شد. لا هرچقدر میزان ‎Sos ah oA‏ تر باشد میزان اگاهی افزایش می یابدالبته این مقدار نباید از 0]: بيشتر باشد كه در اين صورت غیرقایل قبول خواهد بود. | اگاهی یعنی بسط گره های کمتر برای رسیدن به جواب 

صفحه 49:
حستحوی اکتشافی با حافظه محدوه ‎2A) alDA 0‏ با تمیق کرایی ها ی ‎Ls aA) aSMA 1‏ حافظه محود ساده شدم) ‎ 

صفحه 50:
#100 لأ اين روش تطبيق ايده تعميق تكرارى در روش /* است. مبنای هربار تکرار ‎AIDA‏ میزان (11)] است. يعنى از كوجكترين (1)11 ها يه سمت بزركترين تكرار صورت مى يذيرد. لا اين روش كامل و بهينه است و فضاى مصرفى ان يك يشته خواهد بود كه حداكثر به ‎O(bd)‏ فضا نياز داردو مشكل فضاى مصرفى /* را حل می کند. 1 مشکل عمده این روش دوباره کاری است تا بتواند با تکرارهای مکرر مسئله را حل کند. هرگاه وزن لبه های گراف مسئله متنوع باشند میزان ‏ ها کاملا متنوع خواهد شد و تعداد دفعات تکرار قابل تحمل نخواهد بود. 

صفحه 51:
۳۳040۵ 1 این روش برپایه روش عمق اول عمل می کند اما به جای حرکت بی پایان در عمق. بهترین مقدار ؟ که تا بحال کسب شده را به عنوان مسیر جایگزین نسبت به مسیر جاری ذخیره می کند. یعنی از بین فرزندان گره جاری ان را انتخاب می کند که کمترین 6 را دارد ولی اگر این مقدار از ] جایگزین بزرگتر باشد مسیر جاری متوقف شده و مسیر جایگزین فعال ‎oa dale‏ لا اگر تابع (] امکان پذیر باشداین روش کامل و بهینه خواهد بود و فضای مصرفی ان نیز ‎eam) (10)‏ ۳ روش در احتمال تکرر در تغییر مسیر است یعتی ممکن است بارها مسیر اصلی و جایگزین عوض شوند و اين می تواند تعداد گره های بررسی شده را به شدت افزایش دهد. 

صفحه 52:
660 function RECURSIVE-BEST-FIRST-SEARCH( problem) returns a solution, or failure return RBFS( problem, MAKE-NODE(problem.INITIAL-STATE), 20) function RBFS(problem, node, f-limit) returns a solution, or failure and a new f-cost limit if problem.GOAL-TEST(node.STATE) then return SOLUTION(node) successors —[] for each action in problem. ACTIONS(node.STATE) do add CHILD-NoDE( problem, node, action) into successors if successors is empty then return failure, > for each s in successors do /* update f with value from previous search, if any */ s.f—max(s.g + s.h, node.f)) loop do dest — the lowest f-value node in successors if best.f > [limit then return failure, best.f alternative —the second-lowest f-value among successors result, best. f —RBFS( problem, best, min( f_limit, alternative)) if result + failure then return result Figure 3.26 The algorithm for recursive best-first search, 

صفحه 53:
مثال از ‎ROPE‏ (a) After expanding Arad, Sibiu, and Rimnicu Vilcea 

صفحه 54:
مثال از ‎ROPE‏ (b) After unwinding back to Sibiu and expanding Fagaras 

صفحه 55:
مثال از ‎ROPE‏ (c) After switching back to Rimnicu Vilcea and expanding Pitesti 419 

صفحه 56:
2000 1 این روش در واقع همان روش ۵* است با این تفاوت که هرگاه صف اولويت بر شود گره ای با بیشترین مقدار ]را از صف خارج می کند تا جا برای گره جدید باز شود. | نکته مهم در این روش این است که اثری از گره کنارگذاشته شده باقی نمی ماند که اگر مقدار ‏ ان بعدا از دیگر مقادیر موجود در صف کوچکتر شود دوباره به صف باز گردد. 1 500۵* کاملو بهینه لستگر طولم سیر بهينه از طولص فاولويتك وجكتر يا مساو بان 

صفحه 57:
مقایسه روشها از لحاظ مدیریت حافظه روش سطح اول چون غیراگاهانه است و از صف استفاده می کند(یا جستجوی هزینه یکنواخت که از صف اولویت استفاده می کند) نیاز به فضای بسیار زیادی دارند و از همه روشها ضعیف ترند. 1 روش /* چون اگاهانه است نیاز به حافظه کمتری نسبت به سطح-اول دارد. ۲ روش #۱۳۵ از يشته استفاده می کند و مصرف نمایی حافظه را به خطی تقلیل می دهد ولی چون در هربار تکرار فقط یک مقدار ] را ملاک قرار می دهد ضعیف است 1 885 از (0)00 خانه حافظه استفاده میکند بنابراین از ۶110/0 بهتر است اما نمی تواند از حلفظه بیشتری استفاده کند | نهایتا بهترین روش ]99 است که می تواند صف اولوبت را تا اندازه ممکن گسترش دهد و فقط در صورت پر شدن حافظه فرایند حذف عنصر با ] بزرگ فعال خواهد شد. 

صفحه 58:
فصل جهارم: فرای جستجوی کلاسیک 

صفحه 59:
الگوریتم های جستحوی محلی لا مسائل بهینه سازی لا تابع هدف لا کامل بودن و بهینگی ل بى اهميت بودن مسير در بيشتر اين مسائل ‎D‏ فضای حالت - یک مجموعه پیکربندی های کامل مثلا در مسئله ۸ وزیر 1 عدف ال بیکردی ای است که محدودیت های مسئله را براورده سازد لأ براى حل این مسائل از الگوریتم های جستجوی محلی استفاده می شود ۲ وت ها ای كسد كه يك حالت را نگد داشته و سمی می کنند که ان را بهبود دهتد. 

صفحه 60:
منظره فضای حالت objective function _—lobal maximum local maximum flat” local maximum state space current state Figure4.1 A one-dimensional state-space landscape in which elevation corresponds to the objective function. The aim is to find the global maximum. Hill-climbing search modifies. the current state (o try to improve it, as shown by the arrow. The various topographic features are defined in the text. 

صفحه 61:
جستجوی تبه نوردی function HILL-CLIMBING( problem) returns a state that is a local maximum current — MAKE-NODE(problem.INITIAL-STATE) loop do neighbor —a highest-valued successor of current if neighbor. VALUE < current. VALUE then return currend.STATE current — neighbor re 4.2. The hill-climbing search algorithm, which is the most basic local search tech- nique. At each step the current node is replaced by the best neighbor; in this version, that means the neighbor with the highest VALUE, but if a heuristic cost estimate hh is used, we would find the neighbor with the lowest h. 

صفحه 62:
مسئله ۸ وزیر با تبه نوردی is 7 15 ‏در‎ ww 14 ۱701 fa) 0 Figure 4.3 (a) An 8-queens state with heuristic cost estimate A= 17, showing the value of 1 for each possible successor obtained by moving a queen within its column. The best moves, are marked. (b) A local minimum in the 8-queens state space; the state has k= 1 but every successor has a higher cost 

صفحه 63:
سه مشکل اساسی تبه نوردی Figure 4.4 Illustration of why ridges cause difficulties for hill climbing. The grid of states (dark circles) is superimposed on a ridge rising from left to right, creating a sequence of local maxima that are not directly connected to each other. From each local maximum, all the available actions point downhill. 

صفحه 64:
جستجوی شبیه سازی تبرید آیده اصلی آن روش فرار از بهینه محلی با اجازه دان به برخی از حرکات بد است اما با کاهش تدریجی فراوانی انها | می توان ثابت کرد که اگر ۲ به اندازه کافی به تدریج کاهش یابد جستجوی شبیه سازی تبرید بصورت احتمالی جواب بهینه کلی را خواهد یافت | در طراحی ۷151 زمان بندی خطوط هوایی و ... بسیار کاربرد دارد 

صفحه 65:
الگوریتم شبیه سازی تبرید function SIMULATED-ANNEALING( problem, schedule) returns a solution state inputs: problem. a problem schedule, a mapping from time to “temperature” current — MA for ‏هل عد 6 1 ع غ‎ T — schedule(t) if T = 0 then return current next — a randomly selected successor of current AE —nect.VALUE — current. VALUE if AE > 0 then current — neat else current — next only with probability e Nov(problem.INITIAL-STATE) AE/T Figure 4.5 The simulated annealing algorithm, a version of stochastic hill climbing where some downhill moves are allowed. Downhill moves are accepted readily early in the anneal- ing schedule and then less often as time goes on. The schedule input determines the value of the temperature Tas a function of time. 

صفحه 66:
جستجوی پر تو محلی حالتوا به جای ی کحا لب صورت‌هم‌زمان دیابیمیکند با »ا حالت كه بصورت تصادفی تولید شده اند شروع می کند در هر تکرار تمام بعدی های تمام >! حالت تولید می شود بح تس صاخ اگر یکی از ‎kal‏ حالت هدف باشد الگوریتم متوقف می شود در غیر این صورت بهترین 16 حالت را از کل مجموعه انتخاب می کند (عیب این روش) و دوباره تکرار می کند. در پیاده ساری های موازی مفید است جستجوی پرتو تصادفی نیز وجود دارد 

صفحه 67:
الگوریتم های ژنتیک یک حالت بعدی از ترکیب دو حالت والد تولید می شود با حالت که بصورت تصادفی تولید شده اند شروع می کند (جمعیت) هر حالت بصورت یک رشته بر روی یک الفبای معین (اغلب ۰ و ۱) نمایش داده می شود ‎at‏ ارزیابی ۴۱۳620۴ 1]1۱655]) به حالت های بهتر مقادیر بالاتری نسبت می دهد. نسل بعدی حالت ها با انتخاب, تقاطع و جهش تولید می شود. ص وص اح هم سح 

صفحه 68:
عمل تقاطع ( Figure 4.7 The 8-queens states corresponding to the first (wo parents in Figure 4.6(¢) and the first offspring in Figure 4.6(d). The shaded columns are lost in the crossover step and the unshaded columns are retained. 

صفحه 69:
#0 1 اوه میب 24748552 32752411 ۱23 6 24748552 24752411 - 1 322۴24 سس 32752124۳ مر 32752411 | 26% 20 | 24415124 9 ۱۲244151111 24415124 |~ 149 14 [ 32543213 3 3 0 0 0 Initial Population Fitness Function Selection Crossover Mutation Figure4.6 The genetic algorithm, illustrated for digit strings representing 8-queens states, The initial population in (a) is ranked by the fitness function in (b), resulting in pairs for mating in (c). They produce offspring in (d), which are subject to mutation in (e) 0 تابع ارزیابی برلبر است با تعداد جفت هایی که همدیگر را تهدید نمی کنند 

صفحه 70:
الگوریتم ژنتیک ] GENETIC-ALGORITHM( population, FITNESS-FN) returns an individual inputs: population, a set of individuals FITNESS-FN, a function that measures the fitness of an indi repeat nnew-population — empty set for i= 1 to Size population) do 2 RANDOM-SELECTION( population, FITNESS-FN) y — RANDOM-SELECTION( population, FITNESS-FN) child — REPRODUCE, y) if (small random probability) then child — Murare(child) add child to new-population population — new-population ‘until some individual is fit enough, or enough time has elapsed return the best individual in population, according to FITNESS-FN function REPRODUCE(2, y) returns an individual inputs: 7, y, parent individuals nn LENGTH(2); ¢— random number from 1 to n return APPEND(SUBSTRING(2, I, ¢), SUBSTRING(y,¢ + 1,n)) Figure 4.8 A genetic algorithm, The algorithm is the same as the one diagrammed in Figure 4.6, with one variation: in this more popular version, each mating of two parents produces only one offspring, not two, 

صفحه 71:
جستجوی محلی در فضای پیوسته 1 الگوریتم های قبلی به غیراز تپه نوردی و شبیه سازی حرارت در فضای پیوسته کار نمی کنند لا مثال از فضای حالت پیوسته: تعیین مختصات سه فرودگاه جدید بطوری که مجموع مکعبات فواصل انها از هر شهری در نقشه کمینه شود. ] هر حالت توسط محتصات سه نقطه تعیین می شود تعداد متغفییرها برابر با ۶ S (trys, Ya, a, wh ۳ ‏روا‎ + (Yee)? - 0 1و 

صفحه 72:
جستجوی محلی در فضای پیوسته ‎eee‏ رک سازی همساید های هر حالت است برای مثال هر اک راعی ونیم به اندازه مشخصی جابجا کنیم لا سپس می توانیم هر کدام از الگوریتم های محلی را استفاده کنیم ‏1 همچنین می توان از تپه نوردی تصادفی یا شبیه سازی تبرید بصورت مستقیم استفاده کرد ‎ 

صفحه 73:
جستجو با اعمال غير قطعى لأ ذر محيط هاى ياره أى قابل مشاهده يا غير قطعى ذرك محيط مقيد است 1 در محيط هاى ياره اى قابل مشاهده هر درك به كاستن از تعداد حالتهاى ممكن كمك مى كند لأ در محيط هاى غيرقطعى ادراكات به عامل مى كويد كه كدام يك از خروجى هاى هر عمل اتفاق افتاده است 

صفحه 74:
جهان جاروبرقی نامنظم م Figure 4.9 The eight possible states of the vacuum world; states 7 and 8 are goal states. 

صفحه 75:
جهان جاروبرقی نامنظم لا در اين دنيا عمل مکش بصورت زیر انجام می گیرد: ل وقتی به خانه کثیف اعمال می شود ان خانه را تمیز می کند و در برخی از مواقع خانه مجاور را نیز تم می ند ل وقتى كه به خانه تميز اعمال مى شود اين عمل برخى از مواقع کثیفی را نیز پخش نیز پخش می کند ل در اين دنيا نتيجه هر عمل ممكن است يكى از جند حالت ممكن باشد ل همجنين راه حل در اين دنيا يك طرح ريزى است (شامل اكر - اما) برای مثال ‎(Suck. if State =5 then [Right, Suck] else []] .‏ !| جواب در این حالت بجای توالی. درخت است ‎ 

صفحه 76:
درخت های 00-04۲ لا شاخه شدنی که توسط انتخاب های خود عامل در هر مر حله ایجاد می شود گره های ‎0٩‏ ‏تس ی نود 1 شاخه شدن ممکن است بر اثر انتخاب خروجی توسط محیط برای هر عمل ایجاد شود كه به ‎ge ADN cola oF la oF oul‏ گویند ‎See eee oe‏ زير درخت است که لآ در هر برگ آن یک گره هدف دارد لا در هر كره 018 ان يك عمل مشخص شده است ‏لآ شامل همه شاخه هاى خروجى از هر ‎plas‏ از كره هاى ‎cul LAND‏ ‎ 

صفحه 77:
- [= |=] Goan 1 Suck (l-] i.) Le i.) LA & oor. Loop Sug, Kt oor GOAL [5 | ‏ع‎ ‎Goat ۳7 Figure 4.10 The first two levels of the search tree for the erratic vacuum world, State nodes are OR nodes where some action must be chosen. At the AND nodes, shown as circles, every outcome must be handled, as indicated by the arc linking the outgoing branches. The solution found is shown in bold Lines. 

صفحه 78:
الگوریتم جستجو در درخت های ‎PMOD-OR‏ function AND-OR-GRAPH-SEARCH(problem) returns « conditional plan, or failure OR-SEARCH(problem.INITIAL-STATE, problem. {]) function OR-SEARCH( state, problem, path) returns a conditional plan, or failure if problem.GOaL-TEST( state) then return the empty plan if state is on path then return failure for each action in problem.ACTIONS( state) do plan — AND-SEARCH(RESULTS( state. action), problem, [state | path]) if plan + failure then return [action | plan] return failure function AND-SEARCH( states, problem, path) returns « conditional plan, or failure for each 5; in states do plan, —OR-SEARCH(s:. problem, path) if plan, = failure then return failure return [if s: then plan, else if s then plan else ...if s.—1 then plan, else plan] Figure 4.11 An algorithm for searching AND-OR graphs generated by nondeterministic environments. It retums a conditional plan that reaches a goal state in all circumstances. (The notation [| J] refers to the list formed by adding object 2 to the front of list .) 

صفحه 79:
جهان جاروبرقی لغزنده ل فرش کنید اعمال جابجایی جاروبرقی در برخی از حرکات باشکست مواجه می شود و جاروربرقی در همان موقعیت قبلی خود باقی می ماند. ‎yal)‏ ا 0000000 يك راه حل جرخه ای وجود داشته باشد (مثلاابا حرکت به. سمت راست در شکل) این راه حل را می توانیم با یک برچسب مشخص کنیم و از اين برچسب بعدا بجای تکرار نقشه استفاده کنیم [Suck, Ly: Right. if State =5 then 1) else Suck] . 

صفحه 80:
جهان جاروبرقی لغزنده Figure 4.12 Part of the search graph for the slippery vacuum world, where we have shown, (some) cycles explicitly. All solutions for this problem are cyclic plans because there is no way to move reliably. 

صفحه 81:
جهان جاروبرقی لغزنده لا با توجه به تعریف يك راه حل چرخه ای. عاملی که چنین راه حلی را اجرا می کند سرانجام به هدفی که هر خروجی یک عمل غیر قطعی سرانجام رخ می دهد. دست می یابد ل البته این به تعریف قطعیت نیز بستگی دارد مثلا 1 انداختن تاس ل داخل كردن كارت هتل براى باز كردن قفل در 

صفحه 82:
جستجو با مشاهدات جزئی لا حالت باور: اعتقاد جاری عامل در مورد حالتهای فیزیکی ای که ممکن است دران قرار داشته باشد با توجه به توالی از اعمال و ادراکاتی که تاکنون بدست امده است. را نشان می دهد. 

صفحه 83:
جستجو بدون مشاهده لا اين نوع مسائل را مسائل بدون سنسور یا مسائل تطبیقی نیز گفته می شود ‎ [[‏ مثلا در مورد دنیای جاروبرقی فرض کنید که جاروبرقی جغرافیای دنیا را می داند اما موقعیت خود و کشیفی با تمیزی خانه را درگ نمی کند. ‏لآ براى حل مسائل بدون سنسور ما جستجو را در حالتهای باور انجام می دهیم به جای حالتهای ‏1 در فضای حالت باور مسئله کاملا قابل مشاهده است چون عامل هميشه حالت باور خود را می داند. ‎ 

صفحه 84:
جستجو بدون مشاهده 1 تعریف مسائل بدون سنسور لآ فرض كنيد يك مسئله ‏ كه با 6081-1856 ,۴65۱۷۱۲۳ ,۵۸0005۳ و -560 1 تعريف مى شود 1 حالتهای باور: برای مسئله ای با لا| حالت یکی مسئله بدون سنسور شامل 2۷ که همه انها قابل دسترس حالت اولیه: مجموعه تمام حالتها اعمال: اگر اعمال غیر قانونی تاثیری در حل مسئله نداشته باشند اجتماع تمام لعمال در غیر اینصورت اشتراک تمام اعمال مدل انتقال: 

صفحه 85:
جستجو بدون مشاهده | مدل انتقال: ل برلى اعمال قطعى . ‎RESULT p(s.) and s € b}‏ | برای اعمال غیرقطعی ‎bo’ = Resut(b,a) = {s’: s’ © RESULTS p(s,a) and s € b}‏ . (هبعام وتاتاقعع للا = ‎seb‏ / /4] ع (6,0) اناد ع> زا لا ایجاد حالت باور جدید بعد از انجام یک عمل پیش بیتی نامیده می شود 

صفحه 86:
جستجو بدون مشاهده 1 تست هدق: یک حالت باور هدف است اگر تمام حالتهای فیزیکی در آن شرط 6031-7651 را اوه ۱۱۹ لا فر .اور نک عمل مشاه در حالتهای مختلف بتواند هزینه های متفاوتی داشته باشد بنابراین هر اه نک عمل در یک حالت مشخس می تواند یکی از چندین مقدار باشد. 

صفحه 87:
(a) (b) Figure 4.13 (a) Predicting the next belief state for the sensorless vacuum world with a deterministic action, Right. (b) Prediction for the same belief state and action in the slippery version of the sensorless vacuum world. 

صفحه 88:
جستجو بدون مشاهده . 1 عات ا 1 « | كاز كاه | هاه ل حالتهاى قابل دسترس ‎am ne‏ 5 1 ۱۲ حالت از ۲۵۶ ۲۸ حالت ‎“te 5‏ 5 3 3 شیاه ‎LAs‏ بت[ ‎tells (pe)‏ ‎b=‏ ۲ 2 5 1 ‎ey ft ty fe‏ ‎iz‏ 3 ت۳2 ات 5 > 4 ~ Figure 4.14 The reachable portion ofthe belif-state space for he deterministic, sensor- Jess vacuum world, Each shaded box corresponds toa single belief state. At any given point, the agent is ina particular belief state but does ot know which physical state i ein. The initial belief state (complete ignorance) isthe top center box. Actions are represented by ] inks. Solf-loaps are emitted for clarity. 

صفحه 89:
جستجو بدون مشاهده 1 پس از فرموله سازی مسئله هرکدام از روشهای جستجوی فصل ۳ را می توان اعمال کرد. ل اگر یک توالی اعمال جوابی برای یک حالت باور ‏ باشد. ان یک جواب برای هر زیر مجموعه از 0 نیز خواهد بود. بنابراین اگر متلا (۵, ۷) ایجاد شده است می توانیم مسیری که به (۱, ۳, ۵, ۷ ختم می شود را دور بياندازيم. اين باعث یک نوع هرس در درخت فضای حالت ‎ge‏ شود. مشكل اساسى در مسائل بدون ستسور مربوظ به اندازة هر حالت باور استء 1 يك راه حل اين است كه حالتهاى باور را به شكل فشرده ترى نمايش دهيم 0 یک راه دیگر استفاده از الگوریتم های جستجوی فضای باور افزایشی است که یک حالت فیزیکی را در هر لحظه تولید می کنند مثلا اگر نیاز به عملی داریم که برای هر ۸ حالت موجود در حالت باور باید کار کند میتوانیم ابتدا عملى را بيابيم كه براى حالت ‎١‏ كار مى كند سپس کارکرد این عمل را برای حالتهای دیگر بررسي کنیم. برخلاف جستجوى 010-018 كه ممكن است راه حلهاى متفاوتى براى هر شاخه ييدا کند در حالیکه این روش یک راه حل را که برای همه کار می كند بيدا مى كند. 

صفحه 90:
لا برای مسائل پاره ای قابل مشاهده ما بايد مشخص کنیم که محیط چگونه ادراکات را برای عامل تولید می کند. ‎(Percept(s))‏ آا تابع (۳6۲60۷5)5 در مسائل کاملا قابل مشاهده 5 و در مسائل ‎NUIL oaaline goa‏ را برمی گرداند ل انتقال از یک حالت باور به حالت بعدی برای یک عمل خاص در سه مرحله انجام می شود. ۳ پیش بینی: اگر 8 یک عمل و 0 یک حالت باور باشد داریم ‎b= PREDICT(b, a).‏ ۲ پیش بیتی متاهده تعیین مجموعه ای از ادراکات 0 که ممکن است در حالت باور پیش بینی شده قابل مشاهده باشد. ۳ ‎PoSsIBLE-PERCEPTS (b) = {0 : 0=PERCEPT(s) and s € b}‏ 7 بروز رسانی: برای هر ادراک ممکن حالت باوری که ممکن است از آن نتیجه شود را تعیین می کند by = UpDATE(b, 0) = {s : o=PERCEPT(s) and s € b} 

صفحه 91:
toot fale =] 1 ‏وس‎ a Right al ow | aa ‏که ات۱‎ ۲ ‏دزد تاه‎ Figure 4.18 Two example of transitions in local-sensing vacuum worlds. (a) In the de- terministic world, Right is applied in the initial belie state, resulting in a new belief state ‘with two possible physical sates; for those states, the possible percepts are [13, Dirty) and [B, Clean}, leading to two belief states, each of which is a singleton. (b) In the slippery ‘world, Right is applied in the initial belief state, giving a new belief state with four physi cal tates: for those sates, the posible percept are [A, Dirty), [B, Dirty) and [B, Clean, leading ta thre belie sates wx shown, 

صفحه 92:
آا هر حالت باور پیش بینی شده 00 نمی تواند بزرگتر از حالت باور پیش بینی شده باشد: مشاهدات فقط برای كاهش عدم قطعيت بكار مى روند. لا بدست اوردن حالت هاى باور ممكن مننتج از يك عمل معين و ادراكات ممكن بعدى RESULTS (b, a) = {bg : by = UPDATE(PREDICT(b, a), 0) and € POSSIBLE-PERCEPTS (PREDICT(b, a))} 0 

صفحه 93:
حل مسائل باره ای قابل مشاهده 7 ادراک ‎[A, Dirty]asy‏ 7 راه حل یک برنامه شرطی است| = {6} then Suck else ] [| first level of the AND-OR search tree for a problem in the local-sensing is the first step of the solution | در محیط قابل مشاهده جزئی یک عامل نمی تواند راه حلی را اجرا کند که نیازمند تست یک حالت واقعی باشد Figure4.16 Th vacuum world; Sue 

صفحه 94:
عاملی برای محیط های پاره ای قابل مشاهده آا عامل مسئله را فرموله سازی کرده و یک الگوریتم جستجو (مانند جستجوی گراف ‎)۱]0-001٩‏ را برای حل ان اعمال می کند و راه حل را اجراامی کند. ل دو تفاوت اصلی وجود دارد: 1 راه خل در این مساول ممکن است یک برنامه شرطی باشد به جای توالی اعمال ‎١‏ ل ‎eee‏ که انمال را نام می دهد و اراکات را دریافت می کند نگهداری کند: | باداشتن یک حالت باور او عمل 8 و یک ادراک 0 حالت باور جدید بضورت زیر است. ‎b! = UPDATE(PREDICT(b, a), 0)‏ 

صفحه 95:
عاملی برای محیط های پاره ای قابل مشاهده 0 حالت باوری که در جهان جاروبرقی 061670310610 (كودكستان) با سنسور محلی نگهداری می شود را نشان می دهد که در آن هر خانه در هر لحظه ای می توان کثیف شود مگر اینکه عامل بطور فعال در حال تميز كردن ان در ان لحظه باشد ]۸ Figure 4.17 Two prediction-update cycles of belief-state maintenance in the kindergarten vacuum world with local sensing. AY 

صفحه 96:
منال رباتی با وظیفه محلی سازی با داشتن نقشه ای از محیط و توالی ای از ادراکات و اعمال شامل ۴ سنسور در هر جهت برای تشخیص شی ‎Move jac‏ پصورت تصادفی عمل می کند ‏کار ربات تعیین موقعیت جاری است ‎ ‏در ابتدا ریت نمی داند در کجا قرار دارد ‏ادراک 15۷۷ يعنى مانع در شمال, غرب و شرق ‎ ‎ ‎ ‎(b) Possible locations of robot After Ey = NSW, Ep = NS ‎Figure 4.18 Possible positions of the robot, ©, (a) after one observation Ey = NSW and (b) aftera second observation £2 = NS. When sensorsare noiseless and the transition model is accurate, there are no other possible locations for the robot consistent with this sequence of two observations. ‎ ‎ ‎ ‎ ‎ ‎ ‎ ‎ 

صفحه 97:
عاملهای جستجوی انلاین و محیطهای ناشناخته 0 تاكن تام ود تاکنون تمام روشها افلاین بودند یعنی تا زمان پیدا نشدن راه حل عامل حتی یک قدم نیز بر نمی دارد. دار 1 در جستجوی انلاین عامل. نند. ابت این عامل» محاسبه و عمل را با هم ادغام می کند. ابتدا | انجام می دهد سپسر ‎fora‏ عملی را انجام می دهد سپس محیط را مشاهده 0 ان سره ‎‘i‏ حيط بحیط اخته اجتتجوى اللاين براق محيطهاى يوياء نيمه يويا غیرقطعی شناخته ضر ‎ae‏ بويا و محيطهاى غير و برای های نا ورى أ 

صفحه 98:
مسائل جستجوی انلاین ]با فرض محیط كاملا قابل مشاهده و قطعی ‎ScLl> 50 pleilLigfbet J Actions(s) ۴‏ 1 (5 ,8 ,605 تابع‌هزینه: مقدرلیرتابح تا زمانی‌که عاملعملر| لنجام ندهد قابلمحاسبه نیست ‎Goal-Test(s)‏ sce ovale [5 Joc pled! jl L3 Result(s, 3( ‏در این مسائل‎ 0 a G 1 20 3 Figure 4.19 A simple maze problem, The agent starts at $ and must reach G but knows nothing of the environment 

صفحه 99:
مسائل جستجوی انلاین آا عامل ممکن است به یک تابع اکتشاف قابل قبول دسترسی داشته باشد که فاصله از حالت جاری به هدف را تخمین بزند. لا مثلا در شکل قبل عامل ممکن است فاصله تا هدف را با استفاده از تابع اکتشاف فاصله منهتن تخمین بزند. لا هزینه در واقع هزینه کل مسیری است که عامل بطور واقعی ی کرده است. | این فاصله ممکن است با فاصله واقعی رسیدن به هدف (در صورت دانستن) مقایسه شود که به آن ‎et,‏ شود. !! عدف 5 درس نت رقابتی است اما ان نسبت ممکن است بی نهایت شود. مثلا در صورت غیرقابل بازگشت بودن اعمال ممکن است عامل په حالت مرگ پرسد "| حالت مرگ مشکل اساسی در این روشهاست اما در برخی از مسائل محیط را می توان بطور امن قابل مرور فوض کرد & 

صفحه 100:
مسائل جستجوی انلاین 4 | 0 Figure 4.20 (a) Two state spaces that might lead an ontine search agent into a dead end. Any given agent will fail in at east one of these spaces. (h) A two-dimensional environment that can cause an online search agent to follow an arbitrarily ineflicient route to the goal Whichever choice the agent makes, the adversary blocks that route with another long, thin ‘wall, so that the path followed is much longer than the best possible path, 

صفحه 101:
عاملهای جستجوی انلاین ‎I 0‏ و[ ,9 می دا تاه لز لين اطلاعات راجبه نقشه منحيط مى تود بير ‏از نقشه جارى براى تصميم كيرى براى مسير اينده استفاده مى كند ‏يك الكوريتم جستجوى انلاين لمن كره را اشغال كردة است. ‏براق اين حالت الكوريتم غمق اول مناسب تر است. ‏برخلاف روشهاى قبل فقط جانشين هاى كره اى را مى تواند كشف كند كه بطور فيزي ‎ 

صفحه 102:
عاملهای جستجوی انلاین ۱ inputs: s', a percept that identifies the current state persistent: result, a table indexed by state and action, initially empty untried, «table that lists, for each state, the actions not yet tried unbacktracked, a table that lists, for each state, the backtracks not yet tried s, a, the previous state and action, initially null if GoAL-TesT(s') then return stop if s’ is a new state (not in untried) then untried| s'| — ACTIONS(s') if s is not null then results, a] — add s to the front of unbacktracked| s‘] if wntried| sis empty then if unbacktracked|s’] is empty then return stop else a— an action b such that result{ s’,b| = PoP(unbacktracked| s!) else a — PoP(untried|s’]) 5 return a 8 Figure 4.21, ‏مخ‎ online search agent that uses depth-first exploration. The agent is appli cable only in state spaces in which every action can be “undone” by some other action. 

صفحه 103:
عاملهای جستجوی انلاین در جستجوی عمق اول افلاین حالت به راحتی از صف خارج می شود در حالیکه در حالت انلاین عامل باید بصورت فیزیک بازگشت به عقب را انجام دهد 1 عامل در بدترین حالت هر اتصال را دقیقا دوبار مرور می کند. ل این الگوریتم فقط در فضاهای حالتی کارمیکندکه اعمال قابل برگشت باشند. 

صفحه 104:
جستجوی انلاین محلی 1 الگوریتم تپه نوردی به این دلیل که فقط یک گره جاری را در حافطه نگه می دارد خود یک الگوریتم انلاین محسوب می شود ل اما تبه نوردى تصادفى در حالت انلاين امكان يذير نيست 7 لا به جاى شروع مجدد تصادفى مى توان از یک گام تصادفى (31!6لالا 830000177]) براى مرور محيط مى توان استفاده کرد. ل یک گام تصادفی یکی از اعمال موجود را از حالت جاری بطور تصادفی انتخاب میکند عملی اولویت دارد که تاکنون امتحان نشده است؛ این کار سرانجام یا هدف را می یابد یا مرور تمام فضای حالت را کامل میکند. اما اين فرایند بسیار کند ! 

صفحه 105:
جستجوی انلاین محلی آا شکل زیر محیطی را نشان می دهد که گام تصادفی بطور نمایی تعداد مراحل برای رسیدن به هدف را افزایش می دهد Cr VS > ES) ١ ع ‎cas i pe‏ 5 1 ۸ 7 0 al Figure 4.22 An environment in which a random walk will take exponentially many steps to find the goal. 

صفحه 106:
جستجوی انلاین محلی استفاده از حافظه در تپه نوردی مفید تر است. ايده اين است كه بهترين تخمین جاری برای هر حالت بصورت (1)5] نگهداری شود. (۲1)5 در لبتتا بسولبر با تابعلکتشافلس تما در مرلحلعدیا بسدستوردنتچارتجدید بسروز وسانی‌میشود ۶ این روش یادگیری زمان واقعی /* یا ‎@LRTA‏ نامیده می شود. اين روش برخلاف /* برای فضاهای حالت نامتناهی کامل نیست در بدترین حالت محیط ۲۱ حالتی را در (0)1۱) مرحله مرور می کند اما اغلب بهتر است 

صفحه 107:
جستجوی انلاین محلی function LRTA*-AGENT(s!) returns an action inputs: s/. a percept that identifies the current state persistent: result, a table, indexed by state and action, initially empty Ha table of cost estimates indexed by stale, initially empty a, the previous state and action, initially null if GOAL-TEST(s’) then return stop ifs! is a new state (not in 11) then H|s"|— his’) if s is not null result|s,a]—s’ H|s|—_ min — LRTA*-Cost(s. b,result|s, b].H) bEACTIONS(s) @ —an action b in ACTIONS(s!) that minimizes LRTA*-Cost(s/, 5, result{s!,b]. 7) return @ function LRTA*-COsT(s, ¢, s', H) returns a cost estimate if s! is undefined then return ii(s) else return c(s,a,s") + Hs!) cording to the values of ‏د‎ ‎1 Moves about the state space. Figure 4.24 LRTA*-AGENT selects an action a states, which are updated as the ag. 

صفحه 108:
جستجوی انلاین محلی سلم( )مکی( لت المح ی 7 )> 5 ‎(Gj‏ ‏حلم( و بملم( و )حلم((6))منم(ق)/علم( و )عنم( و )حله ‏ \ ل ‎OTP OP‏ J ‏و‎ aM, = S FES 1 ‏تسا ما 1 ا‎ 1 1 @ «(8 jete(9 ‏)علس(‎ (Sa 3 ‏حلم‎ ‎So Nae Rs 0 ‏2ن‎ 2 Figure 4.23 Five iterations of LRTA* on ‏د‎ one-dimensional state space. Each state is labeled with H(s), the current cost estimate to reach a goal, and each link is labeled with its step cost. The shaded state marks the location of the agent, and the updated cost estimates at each iteration are circled 

صفحه 109:
فصل پنجم: جستجوی ر قابتی 

صفحه 110:
جستجوی رقابتی نظریه بازی ازیای چم صفر داشتن اطلاعات کامل از بازی بازی دونفره (چند نفره - گروهی) باز ‎Se‏ ‎Saree!‏ تعریف برد- باخت- تساوی Seo Ses ooo ‏ص‎ مدل سازی رقیب 

صفحه 111:
درخت بازی MAX (®) MIN (0) MAX (0 MIN (0) اه ‎x)‏ ‏| ‏ا 60 + TERMINAL ده Utility Figure 5.1 A (partial) game tree for the game of tic-tac-toe. The top node is the initial state, and MAX moves first, placing an X in an empty square. We show part ofthe tree, giving altemating moves by MIN (O) and MAX (X), until we eventually reach terminal states, which can be assigned utilities according to the rules of the game, 

صفحه 112:
کرمونز() لأ درخت بازی در واقع شکل خاصی از گراف فضای حالت است که در ان به دلیل وجود نوبت. دو سطح متفاوت ۷/3 (خودی) و ۷10 (رقیب) از هم متمایز شده اند. به همین علت به ان درخت -۱۷/:۴ 13 نیز گفته می شود. [1 اساس تصمیم گیری بهینه در درخت بازی برپایه رابطه زیر صورت می گیرد: MINIMAX(s) = ‏نا‎ if TERMINAL-TEST(s) mitXac Actions(s) MINIMAX(RESULT(s,@)) if PLAYER(s) = MAX mingc Actions(s) MINIMAX(RESULT(s,a)) if PLAYER(s) = MIN لأ فرض اين رابطه اين است كه هر دو بازیکن تصمیم گیری بهینه انجام میدهند. 

صفحه 113:
الگور یتم نومه 3 An algorithm for calculating minimax decisions. It returns the action corre sponding to the best possible move, that is, the move that leads to the outcome with the best utility, under the assumption that the opponent plays to minimize utility. The functions MaX-VALUE and MIN-VALUE go through the whole game tree, all the way to the leaves, to determine the backed-up value of a state, The notation argmax, < f(a) computes the function MINIMAX-DECISION(staie) returns an action return argmax, ACTIONS) MIN-VALUE(RESULT(state, a)) function MAX-VALUE(tate) returns a utility value if TERMINAL-TEST( state) then return UTILITY(state) va-o0 for each a in ACTIONS( state) do v— MAX(a, MIN-VALUE(RESULT(s, a))) return 3 function MIN-VALUE(state) returns @ wility value if TERMINAL-TEsT(state) then return UTILITY(state) ‏ونه‎ ‎for each «in ACTIONS(state) do v= MIN(v, MAX-VALUE(RESULT(s, a))) return @ Figure element a of set $ that has the maximum value of f(a). 

صفحه 114:
MIN Figure 5.2. A two-ply game tree. The A nodes are “MAX nodes,” in which it is MAX’s turn to move, and the Y nodes are “MIN nodes.” The terminal nodes show the utility values for MAX: the other nodes are labeled with their minimax values. MAX’s best move at the root is ax, because it leads to the state with the highest minimax value, and MIN’s best reply is ba, because it leads to the state with the lowest minimax value, 

صفحه 115:
ایا کامل است؟ بله (اگر درخت محدود باشد) ايا بهينه است؟ بله (در مقابل رقیب بهینه) پیچیدگی زمانی؟ (0)0۳ پیچیدگی فضایی؟ (0)010) (مرور عمق اول) برای شطرنج است برای یک بازی معمولی | راه حل دقیق کاملا غیرقابل دسترس است 

صفحه 116:
بازی های چند نفره 1 تغییر در استراتفی ۲۱۱۳۳۵۷ آا درخت به تعداد سطح بازیکنان متمایز خواهد بود. لا تابع سودمندی (متباز) برای گره های برگی به جای یک مقدار. ! مقدار برای > بازیکن خواهد در وآقع چون بازی جمع صفر نیست هر بازیکن میزان سودمندی خود را مستقل از دیگران حساب کرده و حاصل برداری > مقداری خواهد شد 1 

صفحه 117:
مثالی از بازی چند نفره to move سب ‎B (1, 2,6) (1, 5,2)‏ ~ 1 6 (2,6) [x] 61,2) [] 5,2) (5.4.5) (5,4,5) 3) 612) 0,4,2 GAN) (5 Figure 5.4 The first three plies of a game tree with three players (A, B, C’). Each node is labeled with values from the viewpoint of each player. The best move is marked at the root. 

صفحه 118:
هرس الفا-بتا | الگوریتم هرس الفا تاه در واقع توسعه ای بر الگوریتم ۲1۱101110316 است که در ان گره های بسط ۳ ۱ و رش زير درختان کاهش می باید. 0 0 اين روش بايد بر اساس جستجوى عمق اول (يا همان عمق محدود شده) يياده سازى شود. يياده سازى به روش سطح اول شانس برش را به صفر مى رساند و تحت اين شرايط همانند ‎minimax‏ اول- سطح عمل خواهد كرد. 

صفحه 119:
هرس الفا- 1 اصول هرس الفا - بتا لآ مقادير الفا كره هاى 11036 هيج وقت كاهش نمى يابد. لآ مقادير بتا كره 160117 هيج كاه افزايش نمى يابد. 1 دو قانون زیر همواره برقرار است: 1 عمل چستجو تحت هر گره ۲۱3 که مقدار الفای ان بزرکتر یا مساوی مقدار بتای هر گره ۲10110 اجداد ان كره است قطه می شود. مقداری که تا بحال به گره 1031] نسبت داده شده به عنوان مقدار نهایی الفای ان گره انتخاب خواهد شد. (برش ‎(ty‏ [ا عمل جستجو تحت هر گره ۲7۱17 که مقدار بتای ان كوجكتر يا مساوی مقدار الفای هر گره ۲18 اجداد ان گره است» قطع می شود. مقداری که تابحال به گره 11018 نسبت داده شده به عنوان مقدار نهایی بتای آن گره انتخاب خواهد شد. (برش الفا) 

صفحه 120:
نمای شماتیک هرس الفا-بتا 

صفحه 121:
الگوریتم هرس الفابتا function ALPHA-BETA-SEARCH( tate) returns an action U— MAX-VALUE(state, —00, +90) return the action in ACTIONS(state) with value © function MAX-VALUE(state,a, 3) returns a utility value if TeRMINAL-TEST( state) then return UTILITY( state) for each a in ACTIONS(state) do v-—MAX(, MIN-VALUE(RESULT(s,a),2, 8)) ify > § then return © a MAX(a, ») return v funtion MIN-VALUE(state, a, 8) returns a utility value If TERMINAL-TEST(stafe) then return UTILITY( state) for each a in ACTIONS(state) do ۳ MAX-VALUE(RESULT(s,0) ,0,)) ity < a then return» 8 —MING, v) return 9 Figure 5.7 The alpha-beta search algorithm. Notice that these routines are the same as the MINIMAX funetions in Figure 5.3, except for the two lines in each of MIN-VALUE and. ‘MAX-VALUE that maintain oc and 6 (and the bookkeeping to pass these parameters along). 

صفحه 122:


صفحه 123:
منال 

صفحه 124:
منال 

صفحه 125:
منال 

صفحه 126:
منال 

صفحه 127:


صفحه 128:
نکات تکمیلی ‎eee‏ ا ‏ب گره های فرزند وابستگی دار ‏1 اگر فرزندان گره ۲86 به ترتیب نزولی و فرزندان که ۰0 رس سمودی برحسب مقادیر ها چیده شده باشد انگاه ۳ برش به حداکثر خواهد ‎jy‏ ‏لا در حالت کلی نمی توان ادعا کرد که در هر مثالی برش روی خواهد داد. حتی اگر اولین فرزند ‏6 بزرگترین مقدار و اولین فرزند ‎MIN‏ کوچکترین مقدار را داشته باشد. باز هم خاصیت فوق ‏برقرار است. ‏عمل چیدن مرتب فرزندان به شرح فوق روش ترتبی دهی (0۲06۲1۳9 ۷10۷6) نام دارد. ‏1 در این شرایط پیچیدگی زمانی کاهش می یابد یعنی اگر 0 میزان فاکتور انشعاب در ‎Minimax‏ ‎ath cole‏ با اعمال هرس الفا- بتا این مقدار به کاهش می یاب ‎ ‎ ‎ ‎ ‏اگر چیدمان فرزندان را تصاوفی فرض کنیم مرتبه زمانی خواهد بود. 

صفحه 129:
تصمیمات زمان واقعی ناکامل لا هرس الفا- بتا نیز نیز به جستجوی عمقی از درخت دارد. این عمق معمولا غیر عملی است. ل جستجو بايد با اعمال تابع ارزيابى مناسب در فضای حالت باید زودتر قطع شود 0 براى اين كار 1 تابع سودمندی ]11لا را با تابع ارزيابى اکتشافی ۳۷۵1 که سودمندی یک موقعیت را تخمين مى زند لا ازمون پایان (۲65 ۲6۲۳۱/۳۵۱) را با ازمون قطع (]165 0۲۲]لان) جانشین کنید. H-MINIMAX(s,d) = EVAL(s) if CUTOFF-TEST(s, d) MAXa¢ Actions(a) H-MINIMAX(RESULT(s,@),d +1) if PLAYER(s) = MAX MiNge Actions(s) H-MINIMAX(RESULT(s. a).d+1) if PLAYER(s) = MIN. 

صفحه 130:
تابع ارزیابی تابع ارزیابی در واقع تخمین شانس برد یک حالت در درخت بازی است. اولا تابع ارزیابی باید حالتهای نهایی (6۲۲۳۲۱31) را مانند روش تابع سودمندی مرتب کند. دوما محاسبات نباید زیاد طول بکشد. بح تس صاخ ثالثا براى حالت هاى غير نهايى تابع ارزيابى بايد بطور قوى این حالتها را با شانس برنده شدن واقعی ‎gee‏ كه ل بيشتر توابع ارزيابى با محاسبه ويزكى هاى كوناكون حالتها كار مى كنند. ‎٠‏ توابع ارزيابى توزيع هاى عددى جداكانه اى براى ويذكى هاى مختلف در نظر كرفته و براى بدست اوردن مقدار نهایی آنها را با هم ت رکیپ مى کنند. EvAL(s) = wy fis) + wafols) +++ +0 nia(s) = ۵) i=] 

صفحه 131:
(a) White to move (b) White to move Figure 588 Two chess postions that differ only in the position of the rook a lower right In (a), Black has an a ight and two pawns, which should be enough to win the game. In (b), White will capture the queen, giving it an advantage that should be strong enough to win. 

صفحه 132:
تابع ارزیابی ] این نوع ارزیابی مستلزم این است که ویژگیها را جدا از دیگر در نظر بگیریم. 1 ممکن است از ترکیبات غیرخطی برای ویژگی ها استفاده شود 

صفحه 133:
| جایگزین کردن دو خط مربوط به تست نهایی در الگوریتم با خط زیر ‎if CuTorr-TEsT (state, depth) then return EVAL(sfate)‏ یکی از روشهای ساده برای کنترل مقدار جستجو تعیین عمق ثابت است. روش قوی تر استفاده از تعمیق تکراری است. این روشهای ساده با توجه به خاصیت تخمینی بودن تابع ارزیابی ممکن است دچارخطا شوند. تایع ارزیابی فقط باید به موقعیت هایی اعمال شود که ساکن هستند یعنی نوسانات چندانی را در اينده نزدیک در مقدارشان نشان نخواهند داد. زمانی که به حالتهای ساکن برسیم (جستجوی ساکن) Seo oc 8 ل ل ا تك شود 

صفحه 134:
۲ تحل ‎gall lp sas‏ ات که زمانی رخ مي دهد که حرکت حریف منجر به ضربه جبران ناپذیری خواهد شد. 1 برای مثال در بازی شطرنج رسیدن پیاده به سمت مقابل و تبدیل ان به وزير ل اين حالت فقط با بكار كيرى حركت هايى بطور موقت به تاخير بافتد. 

صفحه 135:
هرس رو به جلو ‎eee‏ ۰ دی سکن رااز همان ابندا حذف می کنیم یعنی بذون مقایسا, با مقادیر زیر درخت این عمل صورت می گیرد. ‏| معمولا عامل انسانی این عمل را برای کاهش فضای حالت در بازی انجام میدهد ولی ممکن است ‎clea‏ ربرشاعه ای هری شود که در آن حرکت بهینه وجود داشته است. 

صفحه 136:
بازیهای تصادفی | دو تفبیر نسبت به روش پایه ۲0۱۳۱۳۵ [ا اضاقه شدن سطح جدید حاوی گره های شانس | امتیاز دهی به روش زیر EXPECTIMINIMAX(s) = UTILITY(s) if TERMINAL-TEST(s) maxXg EXPECTIMINIMAX(RESULT(s, @)) if PLAYER(s MAX ming EXPECTIMINIMAX(RESULT(s, @)) if PLAYER(s MIN P(r )EXPECTIMINIMAX(RESULT(s,1")) if PLAYER(s) = CHANCE 

صفحه 137:
بازیهای تصادفی 1 مرتبه زمانی الگوریتم بالا (00)0۳۲۱۳ است که در ان لا 6 متوسطتعداد حرکتهایمجاز بسعدی 1 ۲0 عمق‌حدکثر جستجو | 0 تسعداد حا لتهایسمکرهاملت صادفی‌در بایی 

صفحه 138:
بازیهای تصادفی Figure 5.10 A typical backgammon position, The goal of the game is to move all one’s pieces off the board. White moves clockwise toward 25, and Black moves counterclockwise toward 0. A piece can move to any position unless multiple opponent pieces are there: if there is one opponent, itis captured and must start over. In the position shown, White has rolled 6-5 and must choose among four legal moves: (5-10,5-11), (5-11,19-24), (5-10,10-16), and (5-I1,11-16), where the notation (5-I1,11-16) means move one piece from position 5 to 11, and then move a piece from 1110 16. 

صفحه 139:
بازیهای تصادفی MAX CHANCE, MIN CHANCE MAX ‘TERMINAL 2 1 a4 Figure 5.11 Schematic game tree for a backgammon position. 

صفحه 140:
توابع ارزیابی در بازیهای حاوی شانس MIN 2۵ 20 30 30 1 1 400 400 Figure 5.12 An order-preserving transformation on leaf values changes the best move. 

صفحه 141:
بازیهای قابل مشاهده جزثی 1 ۴۲:695016۱: ب ازیش طرنج قابلشاهدهم جزئى ل سفید و سیاه هرکدام فقط بخشی از صفحه را می بینند که مهره های انها در ان قرار دارد یک داور که همه را می بیند بازی را قضاوت می کند سفید حرکتی را به داور اراله می دهد که ممکن است قانونی باشد اگر سپاه وجود نداشته باشد اگر حرکت غیر مجاز باشد داور به آن اطلاع می دهد الع ع ا سبهاد مي بهد نا زمانى كه حركت قانوتي باشد با اين كار در مورد موقعيت سياه یاد oe 0 این نوع حرکات یاداور حالت های باور است که قبلا مطرح شد ۲ حالت ردان است که برای هر توالی ادراک ممکن, هر حالت صفحه در حالت باور جاری بدون توجه به حرکت حریف به مات شدن ان ختم شود 

صفحه 142:
Figure 5.13 Part of a guaranteed checkmate in the KRK endgame, shown on a reduced board. In the initial boli state, Black's king is in one of theee possible locations. By a combination of probing moves, the strategy narrows this down to one. Completion of the checkmate is left as an exercise 

صفحه 143:
فصل ششم: مسائل ارضای محدودیت 

صفحه 144:
مسائل ارضای محدودیت 1 مسائل ارضای محدودیت (9۳)) بصورت مجوعه متغیرهای ,,262:۰۰.,26,و26 و مجموعه محدودیت ‎Cin slo‏ لا هر متغير ,! به دامنه اى همانند ,(] از مقادير ممكن تعلق دارد. ‎٠‏ ن) تعريف مى شود. ‎ ‏هر محدوديت إن) مقادير مجاز براى زير مجموعه اى را معين مى كند. ‎Cole eet eee ete‏ متاك .ر به برخى با تمامى متغير هاست, 1 5 سد را نقض تكند سازكار نام فارد. ‎te ea‏ ۱ ای تامی مرها به ونه اى است كه تمامى محدوديت هارا رعايت كند. 

صفحه 145:
مسائل ارضای محدودیت 1 مسائل ارضای محدودیت (9۳)) بصورت مجوعه متغیرهای ,,262:۰۰.,26,و26 و مجموعه محدودیت ‎Cin slo‏ لا هر متغير ,! به دامنه اى همانند ,(] از مقادير ممكن تعلق دارد. ‎٠‏ ن) تعريف مى شود. ‎ ‏هر محدوديت إن) مقادير مجاز براى زير مجموعه اى را معين مى كند. ‎Cole eet eee ete‏ متاك .ر به برخى با تمامى متغير هاست, 1 5 سد را نقض تكند سازكار نام فارد. ‎te ea‏ ۱ ای تامی مرها به ونه اى است كه تمامى محدوديت هارا رعايت كند. 

صفحه 146:
مسئله نمونه: رنگ امیزی گراف متغیرها 7 ,5۸ ,۷ ,۷5۷۷ ,۵ ,۸۷7 ,۷۷۵ ‎D,= {red,green,blue} ts axls‏ محدودیت ها: نواحی همسایه نباید رنگ یکسانی داشته باشند ۱۷۷۸۵ ‏مثلا 18 (۷۷۸۵,۱۲۲) ۵۲ ,۱۲ ع<‎ {(red,green),(red,blue),(green,red), (green, blue),(blue,red),(blue,green)} 52 كات 5 9 

صفحه 147:
Cxanple: Dup-Covloriagy mies ‎la Jo ol,‏ انتساب هایی کامل و سازگار است ‎WA = red, NT = green,Q = red,NSW = 1 green,V = red,SA = blue,T = green ‎0 ‎ 

صفحه 148:
مثال: زمان بندی کار لأ مسئله زمان بندی مونتاژ خودرو لأ متغيرها: کارهایی که باید انجام شود Wheelzp, Wheelzp, Nutsre, “ X = {Anlep, Axlep, Wheelpe, Wheelrr, apie, Cap pp, Capzp, Inspect} « Nutspr, Nutspp, Nulszp. Capp. 1 محدودیت ها: زمان لازم برای انجام انها (برخی از کارها باید قبل از کار دیگری انجام شون ما۱۷ > 10 + مش ما۷ > 10 + مش .اک 0 +1 ۰ »۱۸ > ۱0 جوم ‎Avlez +10 < Wheelpp:‏ 

صفحه 149:
انواع محدودیت ها | یکانی: محدودیت هایی شامل یک متفیر ] مثلا 6۲66۳ # ‎SA‏ 0 دودویی: محدودیت هایی شامل دو متغیر 1 منلا ۷۷۸ < 5۸ لا درجه بالاتر: محدودیت هایی شامل سه یا بیشتر متغیر لا مثلا محدودیت های ریاضیات رمزی 

صفحه 150:
مثال: مسئله ریاضیات رمزی 1 متغیره؛ ,06,6 ۶۱۷۷ ۵0 (0 ( ‎TY‏ ‏[ دامته ها: (۰,۱,۲,۳,۳,۵,۶,۷۸,۹) لا محدودیت ها: ‎Alldiff (F,T,U,W,R,O)‏ ۳ 2 0+ 0-۲ 10۰ 1 1 و20۰ + لا < ۷۷ + ۷ + رز ‎ae X,+T+T=O0+10-X,0‏ 10 + 0 < 7 + 7 خر ‎recta‏ FOUR 2,2 ۶ 7140,F 700 

صفحه 151:
روش استاندارد فرموله سازی مسئله (افزایشی) 1 حالت اولیه: انتساب خالی () یک مقدار را به یک متغیر بدون مقدار انتساب می دهد بطوری که با انتساب های ‎el‏ ‏ادی نداشته باشد. ازمون هدف: انتساب جاری کامل باشد. برای هر مسئله 5۳ اين روش انجام می شود با داشتن ۱ متغیر هر راه حلی در عمق ۱ یافت می شود از جستجوى عمعی استفاده می شود مسیر مهم نیست بثابراین می تون از فرموله سازی حالت کامل نیز استفاده کرد 

صفحه 152:
انتشار محدودیت: استنتاج در 000 ها ‎١ 2 resem‏ | تام و استفاده از انتشار محدودیت است. ‏۲ یی فاد از محذودیت ها برای کاهش تعداد مقادیر معتبر برای یک متفیر که به همین ترتیب مقادیر معتبر برای متغیرهای دیگر را نیز تغییر می دهند ‎ous! 1‏ اصلی برای این کار سازگاری محلی است که انواع مختلفی دارد 

صفحه 153:
سازگاری گره یک متفیر سازگار گره نامیده مى شود اگر تمام مقادیر موجود در دامنه ان محدودیت هاى يكانى ان متغير را براورده می کند. (arc-consistancy) Jb ‏سازكارى‎ | 0 اگر تمام مقادیر موجود در دامنه متغير تمام محدوديت هاى دودويى ان را براورده سازد به ان سازكار يال مى كويند 1 ,26 سازگار یالباتوجه به متغیر رز( لستگر برلی‌هر مقدار در دلمنه جليئ(] قدارعدر دلمنه ز0] وجود دلشته باشد که بیتهودوییی ال( ,26 ,,26) را ۷ ‏رس‎ (X.Y), {(0,0), (1, 1), (2,4), (3,9) }) Se ‏براورده‎ 

صفحه 154:
Oro vousistewy 1 Simplest form of propagation makes each arc consistent 0 XQYis consistent if 1 for every value x of X there is some allowed y ك2 3 = Nsw ov 5 [5 7 7 ~~ ره wr 

صفحه 155:
Oro vousistewy 1 Simplest form of propagation makes each arc consistent 0 XQYis consistent iff 0 for every value x of X there is some allowed y ك2 sa = xs درد 0 wa = 

صفحه 156:
Oro vousistewy 1 Simplest form of propagation makes each arc consistent 0 XQYis consistent iff 1 for every value x of X there is some allowed y U If Xloses a value, neighbors of X need to be rechecked ك2 wa 07 ‏مه‎ 71 ۲ ‏هو‎ neem 

صفحه 157:
Oro vousistewy Simplest form of propagation makes each arc consistent X(]Yis consistent iff "for every value x of X there is some allowed y If X loses a value, neighbors of X need to be rechecked Arc consistency detects failure earlier than forward checking Can be run as a preprocessor or after each assignment ك2 wa 07 9 Nsw ۷ 

صفحه 158:
الگوریتم 2-5 برای بررسی سازكارى يال function AC-3( csp) returns false if an inconsistency is found and true otherwise inputs: esp, a binary CSP with components (X, D, C) local variables: queue, a queue of arcs, initially all the ares in esp while queue is not empty do (X;, X;) — REMOVE-FIRST(queue) if REVISE(csp, X;, X,) then if size of D; = 0 then return false for each Xx in X;.NEIGHBORS - {X;} do add (X,, X;) to queue return true function REVISE( csp, X;, X;) returns true iff we revise the domain of X; revised — false for each 2 in D; do if no value y in D, allows (x,y) to satisfy the constraint between X; and X; then delete « from D; revised — true return revised 

صفحه 159:
لا یک متغیر :2 سازگار یال کلی است که با توجه به محدودیت ‏ تایی اگر برای هر مقدار ۷ در دامنه ,26 یک سری از مقادیر وجود داشته باشد که محدودیت های چندتاپی را براو, ده ساند. مثاا . 2 > ۲ > زر {0,1,2,3} ۲ محدودیت 1 دامنه ها | مقادیر ۲ و ۲ باید از دامنه 26 حذف گردد چون محدودیت با وجود انها براورده نخواهد 

صفحه 160:
سازكارى مسير لا يك مجموعه دوتایی از متفیرها (ز26 ,,26) با توجه به متغیر سوم ررر26 سازگار مسیر اند اگر برای هر انتساب (0 < ,26 ,2 < ,6) سازگار با محدودیت های [ز26 ,ز۰)6 یک انتساب به م26 وجود داشته باشد که محدودیت های (م26 ,,26) و (ز26 ,مم16 را براورده ساز 1 متال رنگ امیزی تشه با دو ريك | بررسی سازگاری (۷۷/۵,5/۵) با توجه به ۱۷۲ لا فقط دو انتساب ‎WA = blue,SA =} , {WA = red ,SA = blue}‏ 60 میتواند وجود داشته باشد. 1 در هر دو انتساب لا نه می تواند قرمز و نه ابی باشد. بنابراین هيج انتساب مجازی برای [۷/۵,5۸) وجود نخواهد داشت. 

صفحه 161:
سازگاری ۲ 1 روش قوی تر از انتشار محدودیت | یک 5 سازگار ‏ است اگر برای هر مجموعه 1- متغیر و برای هر انتساب سازگار به ان متغفیرهاء یم مقدار سازگار همیشه قابل انتساب به هر ‎K‏ امین متغير باشد. [ا سازگار ۱ معادل سازگار گره. سازگار ۲ معادل سازگاری یال و سازگار ۳ معادل سا رس مسآ ۱ ‏افر سازکار و سازگار 1و .بو سازگار‎ ۱ 5 21 SP esau! 

صفحه 162:
محدودیت های کلی 1 رای مثال محنودیت ۸۱0111 می گوید که تمامی متفیرهای باید یک مقدار متمایزی داشته باشنهٌ 1 شکل ساده تشخیص ناسازگاری 1 اک ۱۱+ در مجدودینی درگیر واگر نها ۱] مقدار متمايز ممكن باهم داشته باشند و 13 <1 باشد پس محدودیت نمی تواند براورده شود. 0 یعنی ۲ ار ری در توت که دامنه تک دارد را حذف کرده و مقدار آن را نیز از دامنه متفیرهای دیگر حذف کنید. إن عمل را تكرار كنرد نا ران كه ستفيرهاي تى دامنه اي موجود باشد. لا اک در كر نقطه اى يك ذامنه خالى توليد شود يا جند عتغير بيشتر از تعداد مقادير دامنه ها باقی بماند يك ناسازكارى تشخيص داده مى شود. 

صفحه 163:
محدودیت های کلی 1 محدودیت منابع: یکی دیگر از محدودیت های درجه بالا که محدودیت حداکثر یا 310705 نیز نامیده می شود, ‎Atmost(10, P,, P), P3, Ps)‏ لأ ناسازكارى را مى توان به سادكى با کنترل کردن مجموع مینیمم مقادیر دامنه های جاری ت داد. همچنین سازگاری را می توان با حذف ماکزیمم مقادیر هر دامنه اگر با مینیمم مقادیر سایر دامنه ها سازگار ‎atl‏ می توان اعمال کرد. 

صفحه 164:
مثال: بازل ‎Gude‏ | یک سودوکو یک مسئله 29۳ با ۸۱ متغير است (به ازای هر خانه یکی) ‎{VAN FOF NY} pls pared 1‏ 1 شامل ۷۲ محدودیت ۸۵۱91۴۴ 48, A9) B7, BS, B9) Alldiff (A1 Alldiff (Bl, B2, Alldiff (Al, B1,C1, D1, F1, Fl, G1, 1,11) Alldiff (A2, B2, C2, D2, E2, F2, G2, H2, 12) Aldi Aldi 3) 6) BA, B2, B3,C1, , BA, BS, Bb, C Figure6.4 (a) A Sudoku puczle and (b) is solution, ۱۳ 

صفحه 165:
مثال: بازل ‎Gude‏ ل روشهايى مانند 80-3 براى حل سودوكو هاى ساده مفيدند اما در حالتهاى ييشرفته نياز به استنتاج ‎le‏ يجيد ای وجود دارد. 1 مثلایک روش انسانی بصورت زیر عمل مى کند. 7 در هر واحد (سطر. ستون یا مریع) سه مریعی را بیابید که هر کدام دامته ای داشته پاشند که شامل سه عدد مشاپه یا زیرمجموعه ای از انها باشند. 1 برای متال (۰۱ ۰۱۸ (۰۳ ۰۱۸ ‎{AYN}‏ ‏1 می توانیم این اعداد را از دامنه هر مربع دیگر در آن واحد حذف 

صفحه 166:
جستجوی پی جویی به عقب ‎(Bachktrackicry)‏ ویژگی مهم مسائل ‎CSP‏ جابجاپذیر بودن انهاست. یک مسئله جابجا پذیر است اگر ترتیب کاربرد هر مجموعه از اعمال» تاثیری در خروجی ندارد. جستجوی عمقی در ۹۳ با انتساب های تک متفیری جستجوی پی جویی به عقب نامیده می ‏ پی جویی به عقب یک الگوریتم غیراگاهانه اولیه برای مسائل 9۳) محسوب می شود در این الگوریتم مقادیر برای یک متغیر در هر بار انتخاب می شود و وقتی که یک متغیر هیچ مقدار مجازی برای انتساب نداشته باشد. به عقب باز مى كردد. ص وص اح هم هه جستجوى بى جويى به عقب فقط يك نمايش واحد از يك حالت را نكهدارى مى كند و ان را تغيير ميدهد به جاى اينكه حالت هاى جديد را ايجاد كند 

صفحه 167:
جستجوی پی جویی به عقب ‎(Bachtrackicry)‏ function BACKTRACKING-SEARCH(csp) returns a solution, or failure return BACKTRACK({ }. esp) function BACKTRACK( assignment, csp) returns a solution, or failure if assignment is complete then return assignment var — SELECT-UNASSIGNED- VARIABLE( csp) for each value in ORDER-DOMAIN-VALUES(war, assignment, csp) do if value is consistent with assignment then add {var = value} to assignment inferences — INFERENCE(csp, var, value) if inferences 4 failure then add inferences to assignment result — BACKTRACK (assignment, csp) if result # failure then return result remove { var = value} and inferences from assignment return failure 

صفحه 168:
yr ‏ظ‎ که ۳ ۱ 

صفحه 169:


صفحه 170:


صفحه 171:
بهبود کارایی پی جویی به عقب 1 سرعت روش های همه منظوره را با در نظر گرفتن موارد زیر می توان افزایش داد: لأ كدام متغير بايد به عنوان متغير بعدى مقدار دهى شود؟ و مقادير انها به جه ترتيبى بايد بررسى شود؟ 1 لأ جه استنتاج هایی در هر مرحله از جستجو باید انجام گیرد؟ لأ وقتی که جستجو در یک انتساب به جایی می رسد که یک محدودیت جستجو می تواند از تکرار چنین حالتی جلوگیری کند؟ 

صفحه 172:
مرتب سازی متغیرها و مقادیر لا معمولا متفیر بعدی از یک صف انتساب داده نشده ها انتخاب می شود. 1 انتخاب بهتر انتخاب متفیری با کمترین مقدار معتبر است که به ان اکتشاف حداقل مقادیر باقی مانده یا ۷18 می ‎ee‏ 2 | ان را متفیرهای بیشتر محدود شده (۷۵۲/۵016 60۳051۲۵1060 0۵51 یا اکتشاف ۲۵11-۴۲5 نيز مى كود Bo ‏بل‎ 

صفحه 173:
اکتشاف 39 >4 ل[ ف ‎MRV‏ در انتخاب اولین ناحیه کمکی نمی کند در اين مورد اکتشاف درجه را می توان بکار برد. لأ اين روش با انتخاب متغيرى که در بیشترین تعداد محدودیت ها با دیگر متفیرهای مقداردهی نشده در گیر است, سعی در کاهش فاکتور انشعاب در انتخاب های اینده دارد. لا برای مثال در رنگ امیزی گراف 9/۸ با درجه ۵ باید ابتدا رنگ امیزی شود. 

صفحه 174:
اکتشاف مقادیر محدود کننده کمتر (ب<هدرا ده بنعوو) لأ بعد از انتخاب متغير بايد ترتيب انتخاب مقادیر ان نیز تعیین شود. 5 روش برای این کار انتخاب مقادیری با کمترین محدود کنندگی است. لأ این روش مقادیر را ترجیه می دهد که انتخاب کمتری را برای متفیرهای همسایه در یک گراف محدودیت باقی می گذارد. 

صفحه 175:
ادغام حستجو و استنتاج در هنكام انجام جستجو فرصت های بیشتری نیزبرای استنتاج بوجود می اید | یکی از ساده ترین روشهای ساده برای استنتاج بررسی روبه جلو (70۳۷//3۲0 ‎cul Checking‏ و .2 داده شود فرایند بررسی روبه جلو برای ان سازگاری یال را تشکیل می دهد؛ برای هر متغیر مقداردهی نشده ۷ که با قیدی به 26 متصل 0115 5 11 كار .؟ مندار انتحات شده برای 26 است حذف می شود. 

صفحه 176:
1 1 سى رو به جلو ‎<TR‏ 69 bls al {WA=red, Q=green, V =blue} cust le a ‏بررسى رو‎ ‏ایجاد ناسازگاری حذف می کند‎ بررسی رو به جلو بهتر است همراه با روش ۷1۴۷] استفاده شود. Figure 6.7 The progress of a map-coloring search with forward checking. WA = red is assigned first; then forward checking deletes red from the domains of the neighboring variables NT and SA. After Q= green is assigned, green is deleted from the domains of NT, SA, and NSW. After V = blue is assigned, blue is deleted from the domains of NSW , leaving SA with no legal values 

صفحه 177:
جستجوی محلی برای 00۴ ها | از جستجوی برای 9۳ن) های می توان استفاده کرد 1 از فرمول بندی حالت کامل برای این مسائل استفاده می شود ۲ برای مثال برای ۸ وزیر از اکتشاف کمترین تهدید ها استفاده می شود 

صفحه 178:
جستجوی محلی برای 00۴ ها Figure 6.9 A two-step solution using min-conflicts for an 8-queens problem. At each stage, a queen is chosen for reassignment in its column. The number of conflicts (in this case, the number of attacking queens) is shown in each square. The algorithm moves the queen to the min-conflicts square, breaking ties randomly. 

صفحه 179:
جستجوی محلی برای 200 ها لا مشکل روش کمترین تداخل در هنگام ایجاد فلات است ‎A‏ روش برای حل این مشکل جستجوی تابو است؛ لیستی از گزینه های اخیرا مرور شده نگهداری می شود و از بازگشت الگوریتم به این حالتهای جلوگیری می شود روش دیگر وزن دهی قیود است که به تمرکز جستجو بر روی قیود مهمتر کمک می كند 0 

صفحه 180:
ساختار مسائل | در بررسی گراف های محدودیت برخی از گره ها ممکن است غیر وابسته به گره های ‎So‏ باشند بنابراین تغبیر ترتیب انها نقشی در مقادیر متغیرهای دیگر ندارد. ‏ل با یافتن زیرگرافهای مستقل می توانیم مسائل بزرگ را به زیرمسائل کوچکتر تبدیل کنیم و انها را جدا حل کنیم که این کار غالبا موجب کاهش بسیار زیاد پیچیدگی زمانی میشود. اما اين زیر گرافها محدودند. ‏| برخی دیگر از ساختارهای مانند درختها برای حل ساده ترند. هر 5۳) با ساختار درختی را می توان در زمان خطی نسبت به تعداد متغیرها حل کرد ‏0 هر 5۳ سازگار یال جهتی یا 0۸6 است که تحت ترتیب متغیرها بصورت. 0 201,262,۰۰۰ اگر و تنها اگر هر 26 سازگار یال با هر 26 برای أ<[ باشد. 

صفحه 181:
ساختار مسائل 0 حل 658 با ساختار درختى 0 0 انتخاب متغير به عنوان ريشه ل انتخاب مقادير برلى هر كره به ترتيب مورد نظر (جون همه يالها سازكارند) 2ن تهج 0 (by مرتب سازی متغیرهای بطوری هر متفیر بعد از وللد خود در درخت قرار گیرد (مرتب سازی توپولوژیکی) 7 Figure 6.10 (a) The constraint graph of a tree-structured CSP. (b) A linear ordering of the variables consistent with the tree with A as the root. This is known as « topological sort of the variables 

صفحه 182:
ساختار مسائل لا چگونه می توان گرافها را تبدیل به درخت کرد 1 روش اول انتخاب برخى مقادير براى )@ ا ‎OM‏ و ره راوید ‎os dp]‏ ‎AAS Hee Cay‏ متفیرهای مرتبط یک درخت ایجاد می 9 @ 0 شود Figure 6.12 ‏نه‎ The original constraint graph from Figure 6.1. (b) The constraint graph after the removal of SA. 

صفحه 183:
ساختار مسائل ‎OT‏ روش دوم تجزیه درختی گراف به یک مجموعه از زیرمسائل متصل ‏]هر زیر مسئله بصورت مجزا حل شده و نتایچ ان با هم ترکیب مي شوند ‎O—~® ‏که‎ ‎0 ‎ ‎ ‎Figure 6.13 A tree decompo ‎ ‎ ‎ ‎ ‎ 

صفحه 184:
فصل هفتم: عاملمای منطقی 

صفحه 185:
عاملهای منطقی عاملهای مبتنی بر دانش جهان ۷۷۱۱۲۱۵۱5 منطق بصورت کلی منطق گذاره ای (بولی) قوانین استنتاج ص وص اح هم سح 

صفحه 186:
عاملهای مبتنی بر دانش | پایگه دانش- مجموعه ای از جملات در یک زبان رسمی لأ روشى بیانی برای ساخت یک سیستم: 1 اا6] چیزیلسکه نیز به دلنسترواييم 1 سپس ان می توان از خودش بپرسد ۵516 كه جه كارى را انجام دهده جوابها باید پایگاه دانش را بسازد 0 عاملها را مى توان در سطح دانش ديده يعنى جه مى دانند بدون توجه به يياده سازى انها ] با در سطح پیاده سازی یعنی ساختارهای داده در پایگاه دانش و الگورینم هایی که انها را پیاده سازی ‎us‏ ‏می 

صفحه 187:
منطق بصورت کلی ار ها وبانهی رسمی برای نمایش اطلاعات هستند که نتایجی می تواند از انها استخراج شود 1 52/۲۱23 جمااترا در یکوبان‌تسعریفمی‌کند 1 56191811165 معانىجملا:(بيعنوديستوجملاتدر جهان را تعريفقموكد 

صفحه 188:
نتیحه دادن 0[ 511811156518 يعنيجيزواز جيز هميكرىئي دستموليد KB ka ل پایاه دانش 163 جملات :0 را نتيجه گیری میکند اگر و تنها اگر 0 در تمام جهان هایی که 8 درست است درست باشد [_برای مثال ۷<4+ نتیجه می دهد که ۷-۴+( 1 نتیجه گیری ارتباط بین جملات است که مبتنی بر معانی انهاست 

صفحه 189:
مدلها ۲ ی 0 10007 ‎١‏ منای مدلها فکر می کنند که جهان هایی هستند که بصورت رسمی با توجه ‎olay emcees‏ ارربلی کرد سازمان دهی شده اند. | ۷ را مدلیاز جمله 0 می‌نامیملگر 0 در 0 دیستب اشد | (۱۸)0 مجموعه لعاز مدلهای0 لستهس0 لگر و تنهااگر 

صفحه 190:
استنتاج | جمله 0 می تواند از تک نتیجه شود با روال ‏ | مفهوم: