Best First Search traverses Graph similar to BFS and DFS, with the difference being that it uses a heuristic function, and has some ‘knowledge’ about the problem beforehand. It uses Priority Queues to store nodes.
Pseudocode
Algorithm Best_First_Search(G,start,f):
open ← PQueue(min or max) ADT
cwn ← Node ADT
closed ← List
Enqueue start to open, with priority f(start)
While open is not empty do:
cwn ← Dequeue from open
Add cwn to closed
For each successor s of cwn do:
If s = end then:
Return closed
Else if s not in open AND s not in closed then:
Add s to open with priority f(s)
End if
End do
End do
Return "FAIL"
End Algorithm
Heuristic Function ()
A heuristic is an estimate of the cost of expanding it’s input. It can sometimes overestimate or underestimate the ‘true’ cost, but using it makes the algorithm usually much faster. Some factors which can be used in determining f(n) can be:
- Proximity
- Cost(Money, etc.)
- Danger