Best-First Search Algorithm – Artificial Intelligence – Artificial Intelligence
We have studied two uninformed search algorithms such as Breadth-First Search (BFS) and Depth First Search (DFS) Algorithm.
DFS is good because it allows a solution to be found without all competing branches having to be expanded.
BFS is good because it does not get branches on dead-end paths.
One way of combining the two is to follow a single path at a time, but switch paths whenever some competing path looks more promising than the current one does.
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
It proceeds in steps, expanding one node at each step until it generates a node that corresponds to a goal state.
At each step, it picks the most promising of the nodes that have so far been generated but not expanded.
It generates the successors of the chosen node, applies the heuristic function to them, and adds them to the list of open nodes, after checking to see if any of them have been generated before.
By doing this check, we can guarantee that each node only appears once in the graph, although many nodes may point to it as a successor.
To implement such a graph-search procedure, we will need to use two lists of nodes:
OPEN â nodes that have been generated and have had the heuristic function applied to them but which have not yet been examined (i.e., had their successors generated).
CLOSED â nodes that have already been examined. We need to keep these nodes in memory if we want to search a graph rather than a tree since whenever a new node is generated, we need to check whether it has been generated before.
We will also need a heuristic function that estimates the merits of each node we generate. This will enable the algorithm to search for more promising paths first. Call this function fâ.
For many applications, it is convenient to define this function as the sum of two components that we call g and h’.
The function g is a measure of the cost of getting from the initial state to the current node.
Note that g is not an estimate of anything; it is known to be the exact sum of the costs of applying each of the rules that were applied along the best path to the node.
The combined function then represents an estimate of the cost of getting from the initial state to a goal state along the path that generated the current node.
If more than one path generated the node, then the algorithm will record the best one. Note that because g and h’ must be added, it is important that h’.
Algorithm: Best-First Search
1. Start with OPEN containing just the initial state.
2. Until a goal is found or there are no nodes left on OPEN do:
a) Pick them best node on OPEN.
b) Generate its successors.
c) For each successor do:
i) if it has not been generated before, evaluate it, add it to OPEN, and record its parent.
ii) If it has been generated before, change the parent if this new path is better than the previous one.
In that case, update the cost of getting to this node and to any successors that this node may already have.
Example: Best-First Search
Here C is the initial or source node and L and Z are goal nodes.
Open: C
Closed: —
Now, C is added to Closed, and B, T, O, E and P are added to Open.
Open: T, O, E, B, P
Closed: C
Now, T has the least distance hence, T is added to Closed.
Open: O, E, B, P
Closed: C, T
As T does not have any successors, the next node from open that is O is removed from Open and added to closed.
Open: E, B, P
Closed: C, T, O
The successors of node O that is node I and N are added to Open.
Open: I, E, B, P, N
Closed: C, T, O
Now, node I is removed from Open and added to closed.
Open: E, B, P, N
Closed: C, T, O, I
The successor of I that is Z is added to Open.
Open: Z, E, B, P, N
Closed: C, T, O, I
Now, node Z is removed from Open and added to closed.
Open: E, B, P, N
Closed: C, T, O, I, Z
The Goal is found. The final path is C – O – I – Z.
Summary
This article discusses Best-First Search Algorithm – Artificial Intelligence. If you like the material share it with your friends. Like the Facebook page for regular updates and YouTube channel for video tutorials.