Page 55 - DCAP506_ARTIFICIAL_INTELLIGENCE

Unit 4: Heuristic Search Techniques

4.4.1 Best First Search Algorithm Notes

1. Begin with OPEN holding the initial state
2. Choose the best node on OPEN
3. Produce its successors

4. For each successor Do
(i) If it has not been produced before evaluate it add it to OPEN and record its parent
(ii) If it has been produced before change the parent if this new path is better and in that
case update the cost of obtaining to any successor nodes
5. If a goal is located or no more nodes left in OPEN, quit, else return to 2.
Figure 4.1

STEP 1

STEP 2

STEP 3

STEP 4

All figures indicate “cost” of move

4.4.2 The A* Algorithm

Best first search is a simplified A*.
1. Begin with OPEN holding the initial nodes.
2. Choose the BEST node on OPEN such that f = g + h’ is minimal.

LOVELY PROFESSIONAL UNIVERSITY 49