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.
Starting node
S in the frontier list
with the path cost g(n) = 0 (starting point is at 0 path cost). 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.Explored list
, as it is now fully explored. priority queue
again, depending upon the priority, that is, the minimum path cost g(n).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:
The uniform cost search algorithm can be evaluated by four of the following factors:
RELATED TAGS
CONTRIBUTOR
View all Courses