دانلود فایل پاورپوینت Informed search algorithms

بخشی از پاورپوینت

--- پاورپوینت شامل تصاویر میباشد ----

اسلاید 1 :

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))
• اگر همه hiها قابل قبول باشند h(n) هم قابل قبول و اگر همه سازگار باشند h(n) هم سازگار خواهد بود

اسلاید 2 :

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

اسلاید 3 :

Example: n-queens

• Put n queens on an n × n board with no two queens on the same row, column, or diagonal

اسلاید 4 :

مزاياي جستجوي محلي

• استفاده از حافظه بسيار كم تقريبا ثابت
• امكان استفاده در فضاهاي حالت بزرگ و نا متناهي (پيوسته)

مناسب برای مسائل بهینه سازی.

اسلاید 5 :

Hill-climbing search

• "Like climbing Everest in thick fog with amnesia”
• همسايه هاي مجاور(توليد شده توسط تابع پسين) را بررسي مي كند و اگر حالتي بهتر است آن را جايگزين حالت فعلي ميكند

اسلاید 6 :

Hill-climbing search

• Problem: depending on initial state, can get stuck in local maxima

اسلاید 7 :

Properties of simulated annealing search

• One can prove: If T decreases slowly enough, then simulated annealing search will find a global optimum with probability approaching 1
• Widely used in VLSI layout, airline scheduling, etc

اسلاید 8 :

Local beam search
جستجوي پرتوي محلي

• Keep track of k states rather than just one
• Start with k randomly generated states
• At each iteration, all the successors of all k states are generated
  If any one is a goal state, stop; else select the k best successors (or randomly) from the complete list and repeat.

اسلاید 9 :

Genetic algorithms

• Start with k randomly generated states (population)
• A state is represented as a string over a finite alphabet (often a string of 0s and 1s)
• Evaluation function (fitness function). Higher (sometimes lower) values for better states.
• Produce the next generation of states by selection, crossover, and mutation
• A successor state is generated by combining two parent states
• A suitable GUI for GA in MATLAB: gatool

اسلاید 10 :

• Fitness function: number of non-attacking pairs of queens (min = 0, max = 8 × 7/2 = 28)
  24/(24+23+20+11) = 31%
  23/(24+23+20+11) = 29% etc