Best First Search

Best First Search traverses graphs 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 ($f(n)$) §

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

Implementation §

BestFirstSearch.py