Uniform cost search algorithm
- Add the initial node x0 and its cost C(x0) to the open list.
- Get a node x from the top of the open list. (a) If the open list is empty then we can’t proceed further and hence can’t find the solution. So, if open list is empty then stop with failure. (b) If x is the target node then we can stop here. So, if x is target node then stop with success.
- Expand x to get a set S of the child nodes of x, and move x to the closed list.
- Pick each x’ from the set S which is not present in the closed list, find its accumulated cost: C(x’) = C(x) + d(x, x’).
- If x’ is not present in the open list: Add x’, C(x’) and (x, x’) to the open list. (a) If x’ in already present in the open list, update its cost C(x’) and link (x, x’) in the open list if the new cost is smaller than old cost.
- Sort the open list based on the node costs, and return to step-2.
Properties of UCS:
- We can always find the best path from the initial node to the current node.
- C(x) is the accumulated cost of node x, from the initial node.
- d(x, x’) is the cost for state transition from node x to node x’.
- If we set d(x, x’)=1 for all edges, UCS becomes equivalent to Breadth-First Search.
Deriving BFS from UCS:
The cost function in BFS: C(x’) = C(x) + 1 …(1)
The cost function in UCS: C(x’) = C(x) + d(x, x’) …(2)
C(x0) = 1 in BFS and UCS …(3)
If we make transition cost from node x to x’ = 1 then;
UCS: C(x’) = C(x) + 1 …(4)
Thus, from (1) and (4), we conclude that BFS is derived from UCS by making transition cost as 1.
Therefore, BFS is a special case of UCS.
Breadth-first Search is a special case of Uniform-cost search
In AI there are mainly two types of search techniques:
- Un-informed/blind search techniques
- Informed search techniques
Search algorithms under the Uninformed category are:
- Breadth-first search
- Uniform cost search
- Depth-first search
- Depth limited search
- Iterative deepening depth-first search
- Bidirectional search
Search algorithms under the Informed category are:
- Best first search
- A* search
Now, we shall define the steps of BFS and UCS searches, then we will derive BFS from the UCS search algorithm.