Search Algorithms for Discrete Optimization Problems Ananth Grama, Anshul Gupta, George Karypis, and Vipin Kumar

Best-First Search (BFS) Algorithms

• BFS algorithms use a heuristic to guide search.

• The core data structure is a list, called Open list, that stores unexplored nodes sorted on their heuristic estimates.

• The best node is selected from the list, expanded, and its off-spring are inserted at the right position.

• If the heuristic is admissible, the BFS finds the optimal solution.

Best-First Search (BFS) Algorithms

• BFS of graphs must be slightly modified to account for multiple paths to the same node.

• A closed list stores all the nodes that have been previously seen.

• If a newly expanded node exists in the open or closed lists with better heuristic value, the node is not inserted into the open list.

The A* Algorithm

• A BFS technique that uses admissible heuristics.

•