tailieunhanh - Artificial Intelligence - Lecturer 5: Advanced search methods

Outline: Memory-bounded heuristic search, Hill-climbing search Simulated annealing search. Some solutions to A* space problems (maintain completeness and optimality). Iterative Deeping version of A*, still admissible. | Artificial Intelligence For HEDSPI Project Lecturer 5 - Advanced search methods Lecturers Dr. Le Thanh Huong Dr. Tran Due Khanh Dr. Hai V. Pham HUST Outline Memory-bounded heuristic search Hill-climbing search Simulated annealing search 1 Memory-bounded heuristic search Some solutions to A space problems maintain completeness and optimality Iterative-deepening A IDA Here cutoff information is the Acost g h instead of depth Recursive best-first search RBFS Recursive algorithm that attempts to mimic standard best-first search with linear space. simple Memory-bounded A S MA Drop the worst-leaf node when memory is full Iterative Deeping A Iterative Deeping version of A use threshold as depth bound To find solution under the threshold of f . increase threshold as minimum of f . of previous cycle Still admissible same order of node expansion Storage Efficient - practical but suffers for the real-valued f . large number of iterations 2 Iterative Deepening A Search Algorithm for tree search Recursive best-first search A variation of Depth-first search Keep track of f-value of the best alternative path Unwind if f-value of all children exceed its best alternative When unwind store f-value of best child as its f-value When needed the parent regenerate its children again.