پاورپوینت پاورپوینت درس چهارم Informed search algorithms (pptx) 21 اسلاید

دسته بندی : پاورپوینت

نوع فایل : PowerPoint (.pptx) ( قابل ویرایش و آماده پرینت )

تعداد اسلاید: 21 اسلاید

قسمتی از متن PowerPoint (.pptx) :

1/19 Informed search algorithms Chapter 4 2/19 Relaxed problemsمسائل تعديل شده A problem with fewer restrictions on the actions is called a relaxed problem The cost of an optimal solution to a relaxed problem is an admissible heuristic for the original problem If the rules of the 8-puzzle are relaxed so that a tile can move anywhere, then h1(n) gives the shortest solution If the rules are relaxed so that a tile can move to any adjacent square, then h2(n) gives the shortest solution تركيب هيوريستيك ها: h(n)=max(h1(n), h2(n), .. hm(n)) 3/19 Local search algorithms In many optimization problems, the path to the goal is irrelevant; the goal state itself is the solution, such as 8 queens problem State space = set of "complete" configurations Find configuration satisfying constraints, e.g., n-queens In such cases, we can use local search algorithms keep a single "current" state, try to improve it 4/19 Example: n-queens Put n queens on an n × n board with no two queens on the same row, column, or diagonal 5/19 مزاياي جستجوي محلي استفاده از حافظه بسيار كم تقريبا ثابت امكان استفاده در فضاهاي حالت بزرگ و نا متناهي (پيوسته) 6/19 Hill-climbing search "Like climbing Everest in thick fog with amnesia” همسايه هاي مجاور(توليد شده توسط تابع پسين) را بررسي مي كند و اگر حالتي بهتر است آن را جايگزين حالت فعلي ميكند 7/19 Hill-climbing search Problem: depending on initial state, can get stuck in local maxima 8/19 Hill-climbing search: 8-queens problem h = number of pairs of queens that are attacking each other, either directly or indirectly h = 17 for the above state تابع پسين تمامي حالتهاي ممكن را كه با جابجا كردن تنها يك وزير به مربعي ديگري در همان ستون توليد مي شود را بر مي گرداند (لذا هر حالت 8*7=56 پسين دارد) 9/19 Hill-climbing search: 8-queens problem A local minimum with h = 1