Page 56 - DCAP506_ARTIFICIAL_INTELLIGENCE

Artificial Intelligence

Notes 3. If BEST is goal node quit and return the path from initial to BEST Otherwise
4. Eradicate BEST from OPEN and all of BEST’s children, labelling each with its path from
initial node.

A* Search

 Minimizes whole estimated solution cost
 Measures nodes by combining g(n) – the cost to reach node n -, and h(n) – the cost to get
from node n to the goal, thus
f(n) = g(n) + h(n) = estimated cost of the cheapest solution through n.

A* is most constructive if h(n) is an admissible heuristic – that is, h(n) never overrates the cost to
reach the goal.

Disadvantages of A*

 Although usually better than the uninformed searches, the computation time of A* is too
large
 As it keeps all generated nodes in memory, A* usually runs out of space
 Not practical for numerous large-scale problems.

Example: Eight puzzle Example: The heuristic of number of tiles out-of-position is definitely
less than the definite number of moves to the goal state. So this heuristic (united with best-first
search) is a permissible algorithm. So is the heuristic sum of the distances of out-of position tiles,
since it too undervalues the definite number of moves needed to arrive at a goal state.

Task Discuss how A* Search is performed.
4.4.3 Greedy Best-first Search (GBFS)

 Develop node closest to the goal; choose path with lowest h(n)
 Evaluate nodes by using heuristic function – that is, f(n) = h(n).

Example: Make use of straight-line distance heuristic, hSLD.
In the example, the path A-S-F-B (found by GBFS) is longer than the path
A-S-R-P-B by 32km!!
In going from I to F, the heuristic proposes that N be expanded first, but it is a dead end!!

Worst-case time and space complexity is O(bm), where m is the maximum depth of the search
space.
The option of the heuristic is important.

50 LOVELY PROFESSIONAL UNIVERSITY