UNIT -II

SEARCH
ALGORITHMS

Dr. Ayesha Ameen

Professor And Head Of Department(I.T)
Deccan College Of Engineering And Technology
CONTENTS

1.Search Algorithms,

2. Random search,

3. Search with closed and open list,

4. Depth first and Breadth first search,

5. Heuristic search,

6. Best first search,

7. A* algorithm

1. Search Algorithms
A search method is defined by picking the order of node expansion. Strategies are evaluated
along the following dimensions:
completeness: does it always find a solution if one exists?
time complexity: number of nodes generated
space complexity: maximum number of nodes in memory
optimality: does it always find the shortest path solution?

Time and space complexity are measured in terms of

b: maximum branching factor of the search tree
d: depth of the shortest path solution
m: maximum depth of the state space (may be ∞)

1.1 Uninformed techniques

Systematically searches complete graph, unguided. Also known as brute force, naïve, or blind.
While searching you have no clue whether one non-goal state is better than any other. Your
search is blind. Uninformed search algorithms have no additional information on the goal node
other than the one provided in the problem definition. The plans to reach the goal state from the
start state differ only by the order and length of actions.
Examples: Depth First Search and Breadth First Search.
We do not use the path cost when executing uninformed search. The transition model
defines a state space, which can be represented as a directed graph (vertices are states, edges are
actions).
 For example, consider the 8-puzzle game, which requires that tokens are shifted around until a
particular goal state is reached. Search space size makes the search tedious. This problem is
called Combinational Explosion.

1.2 Informed techniques

Use problem specific information to guide search in promising directions. Informed Search
algorithms have information on the goal state which helps in more efficient searching. This
information is obtained by a function that estimates how close a state is to the goal state. These
strategies often depend on the use of heuristic information (heuristic search function). Heuristic
search function h(n), is estimated cost of the cheapest path from node n to goal node.
Example: Best first search, A* algorithm.

1.3 Search Algorithms categorization

1.4 Difference between uninformed and informed search

Uninformed Search is a class of general purpose algorithms that operates in a brute force way. The
search space is explored without leveraging on any information on the problem. Also called
blind search, or naïve search
Since the methods are generic they are intrinsically inefficient. Uninformed search strategies that do
not take into account the location of the goal. Intuitively, these algorithms ignore where they are
going until they find a goal and report success.
E.g. Random Search
2. Random Search
This method selects randomly a new state from the current one. If the goal state is reached, the
search terminates. Otherwise the methods randomly select an other operator to move to the next
state. Goal achievement is not insured in finite time.

Algorithm : Random Search

Step 1: n=initial node.
Step 2: Finish if n is the goal.
Step 3: Expand n to get a set S of child-nodes.
Step 4: Select a node n’ from S at random.
Step 5: n=n’, return to 2.

A key issue in search is limiting the portion of the state space that must be explored to find a
solution.
The portion of the search space explored can be affected by the order in which states (and thus
solutions) are examined.
The search strategy determines this order by determining which node (partial solution) will be
expanded next.

Repeated states
Failure to detect repeated states can turn a linear problem into an exponential.

Avoiding Repeated States

Do not re-generate the state you just came from.
Do not create paths with cycles.
Do not generate any state that was generated before (using a hash table to store all generated
nodes) Markov Assumption
Add Closed list to search algorithm or cleverly construct search space Closed list contain the
states that are already visited.

3. Search with closed and open list

To avoid repeated state, Search is implemented using two lists called OPEN and CLOSED are
maintained.
The OPEN list contains those states that are to be expanded and CLOSED list keeps track
of states already expanded.
Here OPEN list is used as a queue. CLOSED list as a stack.

Advantage of open and closed list

The CLOSED list is a collection of all expanded nodes. This means that those are nodes that
were already "searched". This prevents the search from visiting nodes again and again.
 CLOSED list generally improves the speed of algorithm. It prevents the algorithm from
expanding pre-visited nodes.
Maybe you reach node A that was expanded previously through another branch. This will let you
cut this branch and try another path.

General Search Algorithm

A random search, while never practical , Is nevertheless interesting to consider as a worst case
search. To program this search, modify step 4.a. so that a random state is chosen. Given enough
time, the goal state should be found, But a random search will probably take more time (more
states are checked) than any other method

4. DFS and BFS

General Purpose Search Strategies

Breadth First Search (BFS)
It expands all the states one step away from the initial state, then expands all states two steps
from initial state, then three steps etc., until a goal state is reached. It expands all nodes at a
given depth before expanding any nodes at a greater depth. All nodes at the same level are
searched before going to the next level down.
 For implementation, two lists called OPEN and CLOSED are maintained. The OPEN list
contains those states that are to be expanded and CLOSED list keeps track of states already
expanded. Here OPEN list is used as a Queue. CLOSED list is used as a Stack.

BFS Algorithm checks whether the goal node exist or not. Path from start to goal node can be
obtained by maintaining CLOSED list with pointers back to its parent in the search tree.

Algorithm (BFS)

Input: Two states in the state space START and GOAL

Local Variables: OPEN, CLOSED, STATE-X, SUCCS,FOUND:
Output: Yes or No
Method:
Initialize OPEN list contains a START node and CLOSED list is empty; Found = false;
While (OPEN empty and Found = false)
do
{
Remove the first state from OPEN and call it STATE-X;
Put STATE-X in the front of CLOSED list (maintained as stack)
If STATE-X = GOAL then Found = true else
{
perform EXPAND operation on STATE-X, producing a list of SUCCS;
Remove from successors those states, if any, that are in the CLOSED list;
Append SUCCS at the end of the OPEN list /*queue*/
}
} /* end while */
If Found = true then return Yes else return No
Stop

WATER JUG PROBLEM

Problem statement:
We have two jugs a 5-gallon(5-g) and the other 3-gallon(3-g) with no measuring markers on
them. There is an endless supply of water through tap. Our task is to get 4 gallons of water in the
5-g jug.

Solution :
State space for this problem can be described as the set of ordered pairs of integers(X,Y) such
that X represents the number of gallons of water in 5-g jug and Y for 3-g jug.
Start state is (0,0)
Goal state is(4,N) for any value of N<=3

Operations possible are

Fill 5-g jug from the tap and empty the 5-g jug by throwing water down the drain.
Fill 3-g jug from the tap and empty the 3-g jug by throwing water down the drain.
Pour some or 3-g water from 5-g jug into the 3-g jug to make it full.
Pour some or full 3-g jug water into 5-g jug.
Water jug problem using BFS Algorithm
At each stage ,we apply the first applicable rule. If it generates previously generated state then
cross it and try another rule in the sequence to avoid looping. If the new state is generated then
expand this state in breadth-first fashion. Rules are enclosed in {}.

At first two rules are applied

RULE 1: which causes 5 Gallon jug to be filled

RULE 3: Which causes 3 Gallon jug to be filled

Applying RULE 2(empty 5-g jug) to (5,0) will give (0,0) start state. Put a cross mark.
Applying RULE 3 (fill 3-g jug) to (5,0)will give (5,3) new state.
Applying RULE 8 ( pour water from 5-g jug to 3-g jug until 3-g jug is full) to (5,0) will give
(2,3) new state.
Applying RULE 1( full 5-g jug) to (0,3) will give (5,3) already explored state. Put a cross mark.
Applying RULE 4 (empty 3-g jug) to (0,3) will give (0,0) start state. Put a cross mark.
Applying RULE 5( empty 3-g jug into 5-g jug) to (0,3) will give (3,0) state.

Applying RULE 2 (Empty 5-g jug) to (5,3) will give(0,3) already explored state. Put a cross
mark.
Applying RULE 4 (Empty 3-g jug) to (5,3) will give(5,0) already explored state. Put a cross
mark.
Applying RULE 1 (Fill 5-g jug) to (2,3) will give (5,3) already explored state. Put a cross mark.
Applying RULE 2 (Empty 5-g jug) to (2,3) will give (0,3) already explored state. Put a cross
mark.
Applying RULE 4 (Empty 3-g jug) to (2,3) will give (2,0) state.
Applying RULE 1 (Fill 5-g jug) to (3,0) will give (5,0) already explored state. Put a cross mark.
Applying RULE 2 (Empty 5-g jug) to (3,0) will give (0,0) already explored state. Put a cross
mark.
Applying RULE 3 (Fill 3-g jug) to (3,0) will give (3,3) state.
Applying RULE 8 (pour water from 5-g jug to 3-g jug until 3-g jug is full) to (3,0) will give (0,3)
already explored state. Put a cross mark.

Applying RULE 1 (Fill 5-g jug) to (2,0) will give (5,0) already explored state. Put a cross mark.
Applying RULE 2 (Empty 5-g jug) to (2,0) will give (0,0) start state. Put a cross mark.
Applying RULE 3 (Fill 3-g jug) to (2,0) will give (2,3) already explored state. Put a cross mark.
Applying RULE 6 (Empty 5-g jug into 3-g jug) to (2,0) will give (0,2) state.
Applying RULE 1 (Fill 5-g jug) to (3,3) will give (5,3) already explored state. Put a cross mark.
Applying RULE 2 (Empty 5-g jug) to (3,3) will give (0,3) already explored state. Put a cross
mark.
Applying RULE 4 (Empty 3-g jug) to (3,3) will give (3,0) already explored state. Put a cross
mark.
Applying RULE 7 (Pour water from 3-g jug into 5-g jug until 5-g jug is full) to (3,3) will give
(5,1) state.
• Applying RULE 1 (Fill 5-g jug) to (0,2) will give (5,2) state.
• Applying RULE 3 (Fill 3-g jug) to (0,2) will give (0,3) already explored state. Put a cross mark.
• Applying RULE 4 (Empty 3-g jug) to (0,2) will give (0,0) start state. Put a cross mark.
• Applying RULE 5 (Empty 3-g jug into 5-g jug) to (0,2) will give (2,0) already explored state. Put
a cross mark.
• Applying RULE 2 (Empty 5-g jug) to (5,1) will give (0,1) state.
• Applying RULE 3 (Fill 3-g jug) to (5,1) will give (5,3 ) already explored state. Put a cross mark.
• Applying RULE 4 (Empty 3-g jug) to (5,1) will give (5,0) already explored state. Put a cross
mark.
• Applying RULE 8 (pour water from 5-g jug to 3-g jug until 3-g jug is full) to (5,1) will give (3,3)
already explored state. Put a cross mark.
• Applying RULE 2 (Empty 5-g jug) to (5,2) will give (0,2) already explored state. Put a cross
mark.
• Applying RULE 3 ( Fill 3-g jug) to (5,2) will give (5,3) already explored state. Put a cross
mark.
• Applying RULE 4 (Empty 3-g jug) to (5,2) will give (5,0) already explored state. Put a cross
mark.
• Applying RULE 8 (pour water from 5-g jug to 3-g jug until 3-g jug is full) to (5,2) will give (4,3)
.

Depth-First Search
In depth-first search we go as far down as possible into the search tree / graph before backing up
and trying alternatives.
It works by always generating a descendent of the most recently expanded node until
some depth cut off is reached.
then backtracks to next most recently expanded node and generates one of its
descendants.
So only path of nodes from the initial node to the current node is stored in order to execute the
algorithm.
For implementation, two lists called OPEN and CLOSED with the same conventions explained
earlier are maintained.
Here OPEN and CLOSED list are maintained as a stack.
 If we discover that first element of OPEN is the Goal state, then search terminates
successfully else move it to closed list and stack its successor in open list.
We can get track of the path through state space as we traversed, but in those
situations where many nodes after expansion are in the closed list, we fail to keep
track of our path.
This information can be obtained by modifying CLOSED list by putting pointer back to its
parent in the search tree.

Comparisons
DFS
DFS is effective when there are few sub trees in the search tree that have only one connection
point to the rest of the states.
DFS can be dangerous when the path closer to the START and farther from the GOAL has been
chosen.
DFS is best when the GOAL exists in the lower left portion of the search tree.
DFS is memory efficient as the path from start to current node is stored, each node should
contain state and its parent.
DFS may not give optimal solution.

BFS
BFS is effective when the search tree has a low branching factor.
It can work even in trees that are infinitely deep.
It requires a lot of memory as number of nodes in level of the tree increases exponentially.
BFS is superior when the GOAL exists in the upper right portion of a search tree.
BFS gives optimal solution.

4.1 Depth First Iterative Deepening (DFID)

DFID is an iterative method that expands all nodes at a given depth before expanding any nodes
at greater depth. For a given depth d, DFID performs a DFS and never searches deeper than
depth d and d is increased by 1 in next iteration if solution is not found.
Advantages:
It takes advantages of both the strategies (BFS & DFS) and suffers neither the drawbacks of BFS
nor of DFS on trees
It is guaranteed to find a shortest - length (path) solution from initial state to goal state (same as
BFS).
Since it is performing a DFS and never searches deeper than depth d. the space it uses is O(d)
(same as DFS).
Disadvantages:
DFID performs wasted computation prior to reaching the goal depth but time complexity
remains same as that of BFS and DFS.
Since DFID expands all nodes any given depth before expanding any nodes at greater depth.
It is guaranteed to find a shortest path or optimal solution from start to goal state.
At any given time ,it is performing a DFS and never searches deeper than depth d
Thus the space used is o(d).
Disadvantage of DFID is that it performs wasted computation before reaching goal depth.

4.2 BIDIRECTIONAL SEARCH

Bidirectional search algorithm is a graph search algorithm that runs two simultaneous searches.
One search moves forward from the start state and other moves backward from the goal and stop
when the two meet in the middle.
It is useful for the problem which have a single start state and single goal state.
The DFID can be applied to bidirectional searches for k=1,2….
kth iteration consists of a generating all states in forward direction from start state up to
depth k using BFS,
 And from goal state using DFS one to depth k and other to depth k+1 not storing states
but simply matching against the stored stated generated from forward direction.
Here the backward search to depth k+1 is necessary to find odd-length solutions. if
match is found ,path can be traced from start state to matched state and from matched
to the goal state.
Each node must have a link to its successor as well as to its parent.
These links help in generating complete path from start state to goal state.

If match is found ,then path can be traced from start state to the matched state and from matched
state to the goal state.
It should be noted that each node has link to its successors as well as to its parents. These links
will help generating complete path from start to goal state.
‘b’ is the branching factor and ‘d’ to be depth of the tree in the worst case.
The reason for this approach is that each searches has time complexity o(b d/2) and o(b d/2 + b d/2 )
is much less than the running time of one search from the beginning to the goal, which would be
o(b d).
This search can be made in already existing graph/tree or search graph/tree can be generated as a
part of search.
STEP 1

STEP 2
 STEP 3

4.3. Analysis of Search methods

Effectiveness of a search strategy in problem solving can be measured in terms of:
1. Completeness: Does it guarantees a solution when there is one?
Completeness mean that an algorithm guarantees a solution if it exists.
2. Time Complexity: How long does it take to find a solution?
Time required by an algorithm to find a solution.
3. Space Complexity: How much space does it needs?
Space required by an algorithm to find a solution.
4.Optimality: Does it find the highest quality solution when there are several different solutions
for the problem?
The algorithm is optimal if it finds the highest quality solution when there are several
different solutions for the problem.

4.4 Performance of BFS

Time complexity
o In worst case BFS must generate all nodes up to depth d.
o At level i there will be bi nodes be generated. So the total number of nodes generated in
the worst case.
1 + b + b2 +b3 + …+ bd-1 = O(bd)
Note on average, half of the nodes at depth d must be examined.
o So average case time complexity is O(bd)
Space complexity
 o Space required for storing nodes at depth d is O(bd).
o The solution obtained using BFS is optimal but it may take higher computational time.
o It will terminate and find the solution if it exists.

4.5 Performance of DFS

If the depth cut off is ‘d’.
Time complexity
In worst case time complexity is O(bd).
DFS requires an arbitrary cut off depth.
If branches are not cut off and duplicates are not checked for, the algorithm may not
terminate.
Space complexity
If the depth cut off is d the space requirement is O(d).

4.6 Performance of DFID

Time complexity
Space requirement of DFID is of O(d), as search is generated using DFS method.
Time requirement for DFID will be based on number of nodes generated during search.
The total nodes in tree are calculated as follows
nodes at depth d are generated once during the final iteration of the search
nodes at depth d-1 are generated twice,
nodes at depth d-2 are generated thrice, and so on.
Thus the total number of nodes generated in DFID to depth d are
N=bd + 2bd-1 + 3bd-2 + …. db
=bd [1 + 2b-1 + 3b-2 + ….db1-d]
=bd [1 + 2x +3x2 + 4x3 + …. + dxd-1] { if x = b-1}
N converges to bd (1-x)-2 for |x|<1. Since (1-x)-2 is a constant and independent of d , we say
that N O(bd) if b > 1.
So its time complexity is of O(bd).
Since DFID also moves level wise , it finds optimal solution.

4.7 Performance comparison

5. Heuristic search
Travelling Salesman problem(TSP)
Statement
In travelling salesman problem(TSP), one is required to find the shortest route visiting all the
cities once and return to the starting point. Assume that there are ‘n’ cities and the distance
between each pair of cities is given.
TSP is one of the most intensely studied problem in computational mathematics and yet
no effective solution method is known for general case.
In this problem, a simple motion causing and systematic control strategy should, in
principle be applied to solve it.
All possible path are explored and the shortest path is returned.This will require (n-1)!
Path to be examined for ‘n’ cities . If number of cities grows ,then the time required to wait a
salesman to get the information about the shortest path is not a practical situation.This
phenomenon is called combinatorial explosion.

The strategy can be improved little bit using the following techniques.
Start generating complete path, keeping track of the shortest path found so far.
Stop exploring any path as soon as its partial length becomes greater than the shortest path length
found so far.
This method is efficient than the first one but still requires exponential time that is directly
proportional to some number raised to ‘n’.
Table shows some possible paths generated using modified approach up to some level.
Some of the partial paths are pruned if the distance computed is less than minimum computed
distance so far between any pair of cities.
Initially ,first complete path is taken to be minimum and √ is put along with the distance, and if
the distance (full or partial ) is greater than previously calculated minimum, then x is put to show
pruning of that path.
Continue till all paths have been explored. In this case, there will be 4!=24 possible paths.
5.1 Heuristic Search techniques
Heuristics Techniques is a criterion for determining which among several alternatives will be the
most effective to achieve some goal. This techniques improves the efficiency of a search process
possibly by sacrificing claims of systematic and completeness. It no longer guarantees to find the
best solution but almost finds a very good solution. Heuristic are to find solution to hard problem
in less than exponential time.

There are two types of heuristic

General-purpose heuristics that are useful in various problem domains
Special purpose heuristic that are domain specific.

General Purpose Heuristics

A General purpose Heuristics is nearest neighbor algorithm that works by selecting the locally
superior alternative.
For such algorithms , it is often possible to prove an upper bound on the error.
It provides reassurance that we are not paying too high a price in accuracy for speed.
In AI, it is often difficult to measure precisely the goodness of a particular solution.

In AI approaches , behavior of algorithms is analyzed by running then on a computer as contrast

to analyze algorithm mathematically.
It is fun to see a program do some thing intelligent than prove it.
Since AI problem domains are usually complex, it is generated not possible to produce analytical
proof that a procedure will work.
It is not possible to describe the range of problems well enough to make statistical analysis of
program behavior meaningful.
It is important to keep performance in mind while designing algorithms.
One of the most important analysis of the search process is to find number of nodes in a
complete search tree of depth ‘d’ and branching factor ‘f’ that is f*d.
These searches which uses a domain knowledge are called Informed Search Strategies.

Example of General purpose techniques

5.2 Branch and bound search
In Branch and bound search method, cost function (denoted by g(X)) is designed that assigns
cumulative expense to the path from start node to the current node X by applying the sequence
of operators.
While generating a search space , least cost path obtained so far is expanded at each iteration till
we reach to goal state., because of this it is also called Uniform cost search.
During the search ,there may be many incomplete paths contending for further consideration.
The shortest one is extended one level further, creating as many new incomplete paths as there
are branches.
These new paths along with the old ones are sorted on the values of cost function ’g’ and again
the shortest path is extended.
Since the shortest path is always chosen for extension, the path first reaching to the goal is
certain to be optimal but it is not guaranteed to find the solution quickly.
If g(X)=1 for all operators, then it degenerates to simple breadth first search.
It is computational equivalent to BFS and DFS its performance can be improved by augmenting
it by dynamic programming.
Dynamic programming can be used to delete redundant paths to improve the efficiency of
algorithm.
The algorithm generally requires generate solution and test it for its goodness .
Solution can be generated using any method and testing might be based on some heuristic.

5.3 Hill climbing

Quality measurement turns depth first search into Hill Climbing.
It is an optimization technique that belong to the family of local searches.
It is a relatively simple technique to implement as a popular first choice is explored.
Hill climbing can be used to solve problems that have many solutions but where some solutions
are better than others.
Travelling salesman problem can be solved with hill climbing,
It is easy to find the solution that visits all the cities , but this solution will be probably be very
bad compared to the optimal solution.
If there is some way of ordering the choices so that the most promising node is explored first,
then the search efficiency may be improved.
Moving through a tree of paths, hill climbing proceeds in depth-first order but the choices are
ordered according to some heuristic value(i.e. measure of remaining cost from current to goal
state).
Ex in TSP straight line(as the crow flies) distance between two cities can be heuristic measure of
the remaining distance.

There are few problems of hill climbing

The search process may reach to a position that is not a solution but from there no move
improves the situation.
This will happen if we have reached a local maxima, a plateau, or a ridge.
Local maximum: It is a state that is better than all its neighbors but not better than some other
states which are far away. From this state all moves looks to be worse. In such situation,
backtracking to some earlier state and try going in different direction to find a solution.
Plateau: It is flat area of the search space where all neighboring states has the same value. It is
not possible to determine the best direction. In such situation make a big jump to some direction
and try to get to new section of the search space.
Ridge : It is an area of search space that is higher then surrounding areas but that cannot be
traversed by single moves in any one direction. It is a special kind of local maxima.Here apply
two or more rules before doing the test i.e. moving in several directions at once.

5.4 Beam Search

Beam Search is a heuristic search algorithm in which W number of best nodes at each level is
always expanded.
It progresses level by level and moves downward only from the best W nodes at each level.
Beam search uses breadth first search to build search tree.
At each level of the tree, it generates all successors of the states at the current level , sorts them
in order of increasing heuristic values.
It considers only W number of states at each level. Other nodes are ignored.
W is called the width of the beam search.
If B is the branching factor, there will be only W*B nodes under consideration at any depth but
only W nodes to be selected.
If beam width is smaller, the more states are pruned.
If W=1, then it becomes hill climbing search where always best node is chosen from the
successor node.
If beam width is infinite, then no states are pruned and beam search is identical to breadth first
search.
The beam width bounds the memory required to perform the search , at the expense of risking
termination or completeness and optimality.

ALGORITHM BEAM SEARCH

Input: START and GOAL states

Local variable: OPEN, NODE, SUCCs, W_OPEN,FOUND
OUTPUT: Yes or No
Method:
Node =Root_Node; Found=false;
If NODE is goal node, then Found=true else find SUCCs of NODE, if any
with its estimated cost and store in OPEN list;
While(Found=false and not able to proceed further) do
{
Sort OPEN list;
Select top W elements from OPEN list and put it in W_OPEN list and
empty OPEN list;
For each NODE from W_OPEN list
{
If NODE=GOAL state then FOUND =True else find SUCCS
of NODE, if any with its estimated cost and store it OPEN list;
}
} /*end while*/
If FOUND=true then return Yes otherwise return No;
Stop
6. Best-first search
Best-first search is based on expanding the best partial path from current node to goal node.
Here the forward motion is from the best open node so far in the partially developed tree.
The cost of partial path is calculated using some heuristic.
If the state has been generated earlier and new path is better than the previous one, then change the
parent and update the cost.
It must be noted that in hill climbing, sorting is done on in the successor nodes, whereas in the best-
first search, sorting is done on the entire list.
It does not guarantee to find optimal solution but generally it finds some solution obtained from any
other method.
The performance varies directly with the accuracy of the heuristic evaluation function.

Condition for Termination

Instead of terminating when a path is found, terminate when the shortest incomplete path is
longer then the shortest complete path.
In most problems the entire search space graph will be too large to be explicitly represented in a
computer memory, the problem specification however will contain rules that will allow a
computer program to generate the graph(tree) incrementally from the start node in any desired
direction.

7. A* Algorithm
A* Algorithm was proposed by Hart in 1972 is a combination of branch and bound and best
search methods combined with the dynamic programming.
It uses heuristic or evaluation function usually denoted by f(X) to determine the order in which
the search visits the node in the tree.
The heuristic function for a node N is defined as follows

f(N)=g(N)+H(N)

The function g is a measure of the cost of getting from the start node to the current node N. i.e
Sum of cost of the rules that were applied along the best path to the current node. The function h
is an estimate of additional cost of getting from the current node N to the goal state.
This is the place where knowledge about the problem domain is exploited.
A* is called OR graph/tree search algorithm.
A* incrementally searches all the routes starting form the start node until it finds the shortest
path to a goal.
Starting with the given node, the algorithm expands the node with lowest f(X) values.
It maintains a set of partial solution.
Unexpanded leaf node of expanded nodes are stored in a queue with the corresponding values.
This queue can be maintained as priority queue.
 Algorithm A*
Input: Two states in the state space, START and GOAL
Local Variables: OPEN, CLOSED, Best_Node,SUCCs,OLD,FOUND
Output: Yes or No
Method:

Initialization OPEN list with Start node: CLOSED = Ф:g=0,f=h, FOUND=false;

While (OPEN Ф and Found = false) do
{
Remove the node with the lowest value of f from OPEN list and store it in CLOSED list. Call it as a
Best_Node;
If (Best_Node=Goal state) then FOUND= true else
{
Generate the SUCCS of the Best_Node:
For each SUCC do
{
Establish parent link of SUCC; /* This link will help to recover path once the solution is found*/
Compute g(SUCC)=g(Best_Node)+cost of getting from Best_Node to SUCC;

If SUCC ε OPEN then /* Already being generated but not processed*/

{
Call the matched node as OLD and add it in SUCCESSOR list of the Best_Node:
Ignore the SUCC node and change the parent of OLD. If Required as follows
If g(SUCC)<g(OLD) then make parent of OLD to be Best_Node and change the
values of g and f for OLD else ignore:
}
7.1 Example A* Algorithm
If SUCC ε CLOSED then /* Already processed*/
{
Call the matched node as OLD and add it in the list of the Best_Node Successors;
Ignore the SUCC node and change the parent of OLD . If Required as follows
If g(SUCC)<g(OLD) then make parent of OLD to be Best_Node and change the values of g
and f for OLD and propagate the change to OLD children using depth first search else ignore:
}

If SUCC ∉ OPEN or CLOSED

{
Add it to the list of Best_Node SUCCESSORS:
Compute f(SUCC)=g(SUCC)+h(SUCC):
Put SUCC on OPEN list with its f value
}
}
}
}*/End While*/
If FOUND= true then return Yes otherwise return No
Stop
7.2 Optimal solution by A* Algorithm

A* finds an optimal solution if heuristic function is carefully designed and underestimated.

Underestimation
If we can guarantee that h never overestimates actual value from current to goal, then A*
Algorithm ensures to find an optimal path to a goal, if exists.
Here we assume that h value for each node X is underestimated i.e. heuristic value is less than
actual value from node X to goal node.
Start node A is expanded to B,C and D with f values as 4,5, and 6 respectively. Cost of all arcs
is 1.
 Node B has minimum f value , so expand this node to E which has f value as 5, but C also has f
value as 5 we resolve in favor of E the path currently we are expanding. E is expanded to F with
f value 6.
Expansion of node f is stopped as f value of C is now the smallest.
Thus by underestimating we have wasted some effort but discovered that B was farther away
than we thought.
Now we go back and find another path and will find the optimal solution.

Overestimation
We expand B to E,E to F and F to G for a solution path of length 4.
But assume that there is a direct path from D to a solution giving a path of length 2 as h value of
D is also overestimated.
We will never find it because of overestimating h(D). We may find some other worse solution
without ever expanding D.
So by overestimation h, we cannot be guaranteed to find the shortest path.

7.3 Admissibility OF A* algorithm

A Search algorithm is Admissible, if for any graph, it always terminates in an optimal path from
start state to goal state, if path exist.
If heuristic function ‘h’ is underestimated the actual value from current state to goal state, then it
bounds to give an optimal solution and hence is called admissible function.
 It can be said that A* always terminates with the optimal path in case h is an admissible
heuristic function.

6.4 Monotonic Function

A heuristic function h is monotone if

In this case, heuristic is locally admissible i.e. consistently finds the minimal path to each state
they encounter in the search.
The Monotone property is that the search space which is every where locally consistent with
heuristic function employed i.e. reaching each state along the shortest path from its ancestors.
With monotonic heuristic, if a state is rediscovered , it is not necessary to check whether the new
path is shorted.
Each Monotonic heuristic function is admissible.

7.5 Iterative-Deepening A*
Iterative deepening A*(IDA*) is a combination of the depth-first iterative deepening and A*
Algorithm.
Here the successive iterations are corresponding to increase values of the total cost of a path
rather than increasing depth of the search.
Algorithm works as follows
For each operation ,perform a DFS pruning off a branch when its total cost(g+h) exceeds
a given threshold.
The initial threshold starts at the estimate cost of the start state and increases for each
iteration of the algorithm.
The threshold used for the next iteration is the minimum cost of all values exceeded the
current threshold.
These steps are repeated till we find a goal state.

Example to illustrate the working of IDA*

Initially the threshold value is the estimated cost of the start node In the first iteration ,Threshold =5
All successors of the start node are generated and compute their estimated values as 6,8,4,8 and 9.
Successors having value greater than 5 are to be pruned.
Now for the next iteration we consider the threshold minimum of the pruned nodes value. That is
threshold =6 and the node with 6 value along with the node with the value 4 are retained for
further expansion.