Page 181 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Unit 9: Search and Control Strategies

9.4.2 Best-first Search Notes

Best-first search is a search algorithm which explores a graph by expanding the most promising
node chosen according to a specified rule. It is described as estimating the promise of node n by
a “heuristic evaluation function which, in general, may depend on the description of n, the
description of the goal, the information gathered by the search up to that point, and most
important, on any extra knowledge about the problem domain.”
Some authors have used “best-first search” to refer specifically to a search with a heuristic that
attempts to predict how close the end of a path is to a solution, so that paths which are judged to
be closer to a solution are extended first. This specific type of search is called greedy best-first
search. Efficient selection of the current best candidate for extension is typically implemented
using a priority queue. The A* search algorithm is an example of best-first search, as is B*.
Best-first algorithms are often used for path finding in combinatorial search.

Algorithms
OPEN = [initial state]
CLOSED = []
while OPEN is not empty
do
1. Remove the best node from OPEN, call it n, add it to CLOSED.
2. If n is the goal state, backtrace path to n (through recorded
parents) and return path.
3. Create n’s successors.
4. For each successor do:
(a) If it is not in CLOSED: evaluate it, add it to OPEN, and
record its parent.
(b) Otherwise: change recorded parent if this new path is better
than previous one.
done

9.4.3 A* Algorithm

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.

Example: Since airline distance never overestimates actual highway distance, and
Manhattan 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

LOVELY PROFESSIONAL UNIVERSITY 175