Posts Tagged ‘Heuristic Search’
Pure Heuristic Search
The simplest of heuristic search algorithms, the pure heuristic search, expands nodes in order of their heuristic values h(n). It maintains a closed list of those nodes that have already been expanded, and a open list of those nodes that have been generated but not yet been expanded. The algorithm begins with just the initial state on the open list. At each cycle, a node on the open list with the minimum h(n) value is expanded, generating all of its children and is placed on the closed list. The heuristic function is applied to the children, and they are placed on the open list in order of their heuristic values. The algorithm continues until a goal state is chosen for expansion.
In a graph with cycles, multiple paths will be found to the same node, and the first path found may not be the shortest. When a shorter path is found to an open node, the shorter path is saved and the longer one is discarded. When a shorter path to a closed node is found, the node is inaved to open and the shorter path is associated with it. The main drawback of pure heuristic search is that since it ignores the cost of the path so far to node n, it does not find optimal solutions.
Breadth-first search, uniform-cost search, and pure heuristic search are all special cases of a more general algorithm called best-first search. In each cycle of a best-first search, the node that is best according to some cost function is chosen for expansion. These best-first search algorithms differ only in their cost functions the depth of node n for breadth-first search, g(n) for uniform-cost search h(n) for pure heuristic search.
The A* algorithm combines features of uniform-cost search and pure heuristic search to efficiently compute optimal solutions. A* algorithm is a best-first search algorithm in which the cost associated with a node is f(n) = g(n) + h(n), where g(n) is the cost of the path from the initial state to node n and h(n) is the heuristic estimate or the cost or a path from node n to a goal. Thus, f(n) estimates the lowest total cost of any solution path going through node n. At each point a node with lowest f value is chosen for expansion. Ties among nodes of equal f value should be broken in favor of nodes with lower h values. The algorithm terminates when a goal is chosen for expansion.
A* algorithm guides an optimal path to a goal if the heuristic function h(n) is admissible, meaning it never overestimates actual cost. For example, since airline distance never overestimates actual highway distance, and manhatten distance never overestimates actual moves in the gliding tile.
For Puzzle, A* algorithm, using these evaluation functions, can find optimal solutions to these problems. In addition, A* makes the most efficient use of the given heuristic function in the following sense: among all shortest-path algorithms using the given heuristic function h(n). A* algorithm expands the fewest number of nodes.
The main drawback of A* algorithm and indeed of any best-first search is its memory requirement. Since at least the entire open list must be saved, A* algorithm is severely space-limited in practice, and is no more practical than best-first search algorithm on current machines. For example, while it can be run successfully on the eight puzzle, it exhausts available memory in a matter of minutes on the fifteen puzzle.