I.BEST FIRST SEARCH IN AI

Artificial Intelligence: Introduction, Typical Applications. State Space Search: Depth Bounded
DFS, Depth First Iterative Deepening. Heuristic Search: Heuristic Functions, Best First Search,
Hill Climbing, Variable Neighborhood Descent, Beam Search, Tabu Search. Optimal Search: A
*

algorithm, Iterative Deepening A*
, Recursive Best First Search, Pruning the CLOSED and OPEN
Lists

1. Topic To Be Covered:
I.BEST FIRST SEARCH IN AI
Jagdamba Education Society's
SND College of Engineering & Research Centre
Department of Computer Engineering
SUBJECT: Artificial Intelligence & Robotics
Lecture No-09(I)
Prof.Dhakane Vikas N

2. BEST FIRST SEARCH(BFS)
Thisisinformedsearchtechnique(GreedySearch)alsocalledas
HEURISTICsearch.
This algo. Works using heuristic value.
This algorithm uses evaluation functionto decide which adjacent node is
most promising and then explore.
Priority queue is used to store cost of function.
Space & Time Complexity of BFS is also O(V+E)where V is vertices and
E is edges.
Also Written as:-O(b)^d
Where, b->Branching factor
d->depth

3. BEST FIRST SEARCH(BFS)
TheimplementationofBest
FirstSearchAlgorithminvolves
maintainingtwolists-OPENand
CLOSED.
OPENcontainsthosenodesthat
havebeenevaluatedbythe
heuristicfunctionbuthavenot
beenexpandedintosuccessors
yet.
CLOSEDcontainsthosenodes
thathavealreadybeenvisited.

4. BEST FIRST SEARCH(BFS)
Algorithm
Priority queue ‘PQ’ containing
initial states
Loop
If PQ=Empty Return Fail
Else
Insert Node into PQ(Open-List)
Remove First(PQ) ->NODE(Close-
List)<
If NODE=GOAL
Return path from initial state to
NODE
ELSE
Generate all successor of NODE
and insert newly generated NODE
into ‘PQ’ according to cost value.
END LOOP

5. BEST FIRST SEARCH(BFS)
Advantages of BFS:
Memory efficient as compared with DFS & BFS
It is Complete
Disadvantages of BFS:
It gives good solution but not optimal solution.
In worst case it may behave like unguided DFS