Page 182 - DCAP310_INTRODUCTION_TO_ARTIFICIAL_INTELLIGENCE_AND_EXPERT_SYSTEMS

Introduction to Artificial Intelligence & Expert Systems

Notes 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.
A* uses a best-first search and finds a least-cost path from a given initial node to one goal node
(out of one or more possible goals). As A* traverses the graph, it follows a path of the lowest
expected total cost or distance, keeping a sorted priority queue of alternate path segments along
the way. It uses a knowledge-plus-heuristic cost function of node x (usually denoted f(x)) to
determine the order in which the search visits nodes in the tree. The cost function is a sum of two
functions:

the past path-cost function, which is the known distance from the starting node to the
current node x (usually denoted g(x))

a future path-cost function, which is an admissible “heuristic estimate” of the distance
from x to the goal (usually denoted h(x)).
The h(x) part of the f(x) function must be an admissible heuristic; that is, it must not overestimate
the distance to the goal. Thus, for an application like routing, h(x) might represent the straight-
line distance to the goal, since that is physically the smallest possible distance between any two
points or nodes.
If the heuristic h satisfies the additional condition h(x) ≤ d(x, y) + h(y) for every edge x, y of the
graph (where d denotes the length of that edge), then h is called monotone, or consistent. In such
a case, A* can be implemented more efficiently—roughly speaking, no node needs to be processed
more than once (see closed set below)—and A* is equivalent to running Dijkstra’s algorithm with
the reduced cost d(x, y) := d(x, y) – h(x) + h(y).
First search and finds a least-cost path from a given initial node to one goal node (out of one or
more possible goals).

!
Caution Apply full algorithm of any searching technique.

Task Apply BFS in finding the shortest path to reach from one railway station to another
railway station.

Self Assessment

State whether the following statements are true or false:

13. Informed search tries to increase the amount of search that must be done by making
intelligent choices for the nodes that are selected for expansion.
14. A search algorithm is an algorithm for finding an item with specified properties among a
collection of items.
15. Best-first search is a search algorithm which explores a graph by expanding the most
promising node chosen according to a specified rule.
16. A* uses a best-first search and finds a expensive path from a given initial node to one goal
node.

176 LOVELY PROFESSIONAL UNIVERSITY