BEST FIRST SEARCH

BEST FIRST SEARCH. ARTIFICIAL INTELLIGENCE.

BEST FIRST SEARCH. Combines the advantages of both DFS and BFS into a single method. Depth-first search: not all competing branches having to be expanded. Breadth-first search: not getting trapped on dead-end paths ⇒ Combining the two is to follow a single path at a time, but switch paths whenever some competing path look more promising than the current one..

At each step of the BFS search process, we select the most promising of the nodes we have generated so far. This is done by applying an appropriate heuristic function to each of them. We then expand the chosen node by using the rules to generate its successors This is called OR-graph, since each of its branches represents an alternative problem solving path.

OPEN: nodes that have been generated, but have not examined. This is organized as a priority queue. CLOSED: nodes that have already been examined. Whenever a new node is generated, check whether it has been generated before..

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.

ADVANTAGES OF BFS: ● It is very simple to implement and understand. ● It is guaranteed to find the shortest path from the starting point to the goal. ● Breadth First Search tends to find paths with fewer steps than other algorithms, such as Depth First Search. DISADVANTAGES OF BFS: ● It can be slow since it expands all the nodes at each level before moving on to the next level..