Texas State CS 5346 - The Best-First Search Algorithm (17 pages)

Previewing pages 1, 2, 3, 4, 5, 6 of 17 page document View the full content.
View Full Document

The Best-First Search Algorithm



Previewing pages 1, 2, 3, 4, 5, 6 of actual document.

View the full content.
View Full Document
View Full Document

The Best-First Search Algorithm

80 views

Lecture Notes


Pages:
17
School:
Texas State University
Course:
Cs 5346 - Advanced Artificial Intelligence
Advanced Artificial Intelligence Documents

Unformatted text preview:

The Best First Search Algorithm Implementing Best First Search In spite of their limitations algorithms such as backtrack hill climbing and dynamic programming can be used effectively if their evaluation functions are sufficiently informative to avoid local maxima dead ends and related anomalies in a search space In general however use or heuristic search requires a more flexible algorithm this is provided by best first search where with a priority queue recovery from these situations is possible Like the depth first and breadth first search algorithms or Chapter 3 best first search uses lists to maintain states open to keep track or the current fringe of the search and closed to record states already visited An added step in the algorithm orders the states on open according to some heuristic estimate or their closeness to a goal Thus each iteration or the loop considers the most promising state on the open list The pseudo code for the function best first search appears below begin open Start initialize closed while open do states remain begin remove the leftmost state from open call it X if X goal then return the path from Start to X else begin generate children of X for each child of X do case the child is not on open or closed begin assign the child a heuristic value add the child to open end the child is already on open if the child was reached by a shorter path then give the state on open the shorter path the child is already on closed if the child was reached by a shorter path then begin remove the state from closed add the child to open end end case put X on closed re order states on open by heuristic merit best leftmost end return FAIL open is empty end At each iteration best first search removes the first element from the open list If it meets the goal conditions the algorithm returns the solution path that led to the goal Note that each state retains ancestor information to determine if it had previously been reached by a shorter path and to allow the



View Full Document

Access the best Study Guides, Lecture Notes and Practice Exams

Loading Unlocking...
Login

Join to view The Best-First Search Algorithm and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view The Best-First Search Algorithm and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?