Search algorithms are used to resolve search problems. For example, search for the shortest path between two given points, searching for a goal, and so on.
Suppose we want to move from point A to point B and there are two paths between these two points. Which path would you choose? These types of problems can be solved using search algorithms.
Uniform Cost Search (UCS) is a type of
The path cost of going from path A to path B is 5 and the path cost of path A to C to B is 4 (2+2). As UCS will consider the least path cost, that is, 4. Hence, A to C to B would be selected in terms of uniform cost search.
The node at the top of the frontier list will be added to the
Add the Starting node
S in the frontier list
with the path cost g(n) = 0 (starting point is at 0 path cost).
Add this node to the Explored list
, as we only have a single node in the frontier list
. If we have multiple nodes, then we will add that one node at the top of the frontier.
Now, explore this node by visiting all of its child nodes. After that, add this node to the Explored list
, as it is now fully explored.
Check if the added node is the goal node or not. Stop if the goal node is found, or else move on to the next step.
Since new nodes are added to the frontier list, we need to compare and set the priority queue
again, depending upon the priority, that is, the minimum path cost g(n).
Now, move to back to step 2 and repeat the steps until the goal node is not added to the explored list.
Actual path: This is obtained by the frontier list.
Traversed path: This is obtained by the explored list.
Consider the following graph. Let the starting node be A and the goal node be G.
Implementing UCS:
Frontier List | Expand List | Explored List | |
{(A,0)} | A | NULL | |
2. | {(A-D, 3), (A-B, 5)} | D | {A} |
3. | {(A-B, 5), (A-D-E, 5), (A-D-F, 5)} | B | {A, D} |
4. | {(A-D-E, 5), (A-D-F, 5), (A-B-C, 6)} | E | {A, D, B} |
5. | {(A-D-F, 5), (A-B-C, 6), *here B is already explored | F | {A, D, B, E} |
6. | {(A-B-C, 6), (A-D-F-G,8)} | C | {A, D, B, E, F} |
7. | {(A-D-F-G,8), *here E is already explored | G | {A, D, B, E, F, C} |
8. | {(A-D-F-G,8)} | NULL | {A, D, B, E, F, C, G} # GOAL Found! |
Hence we get:
Actual path => A -- D -- F -- G , with Path Cost = 8.
Traversed path => A -- D -- B -- E -- F -- C -- G
The uniform cost search algorithm can be evaluated by four of the following factors:
Completeness: UCS is complete if the branching factor b is finite.
Time complexity: The time complexity of UCS is exponential O(b^{(1+C/ε)}),
because every node is checked.
Space completeness: The space complexity is also exponential O(b^{(1+C/ε)}),
because all the nodes are added to the list for comparisons of priority.
Optimality: UCS gives the optimal solution or path to the goal node.