Basic Search Algorithms
Uninformed Search
Uniform Cost Search (UCS)
Uniform Cost Search (UCS)
◼ Uniform-cost search is a searching algorithm used for traversing a
weighted tree or graph. This algorithm comes into play when a different
cost is available for each edge. The primary goal of the uniform-cost
search is to find a path to the goal node which has the lowest
cumulative cost.
◼ Uniform-cost search expands nodes according to their path costs from
the root node. It can solve any graph/tree where the optimal cost is in
demand. A uniform-cost search algorithm is implemented by the priority
queue.
◼ It gives maximum priority to the lowest cumulative cost. Uniform cost
search is equivalent to BFS algorithm if the path cost of all edges is the
same. 2
Uniform Cost Search (UCS)
5 2
[5] [2]
1 4 1 7
[6] [3] [9]
[9]
Goal state
4 5
[x] = g(n) [7] [8]
path cost of node n
3
Uniform Cost Search (UCS)
5 2
[5] [2]
4
Uniform Cost Search (UCS)
5 2
[5] [2]
1 7
[3] [9]
5
Uniform Cost Search (UCS)
5 2
[5] [2]
1 7
[3] [9]
4 5
[7] [8]
6
Uniform Cost Search (UCS)
5 2
[5] [2]
1 4 1 7
[6] [3] [9]
[9]
4 5
[7] [8]
7
Uniform Cost Search (UCS)
5 2
[5] [2]
Goal state
1 4 1
path cost 7
g(n)=[6] [3] [9]
[9]
4 5
[7] [8]
8
Uniform Cost Search (UCS)
5 2
[5] [2]
1 4 1 7
[6] [3] [9]
[9]
4 5
[7] [8]
9
10
Uniform Cost Search (UCS)
▪ In case of equal step costs, Breadth First search finds
the optimal solution.
▪ For any step-cost function, Uniform Cost search
expands the node n with the lowest path cost.
▪ UCS takes into account the total cost: g(n).
▪ UCS is guided by path costs rather than depths.
Nodes are ordered according to their path cost.
11
Basic Search Algorithms
Uninformed Search
Bi-Directional Search (BDS)
Bi-directional Search (BDS)
◼ Main idea: Start searching from
both the initial state and the goal
state, meet in the middle.
◼ Complete? Yes
◼ Optimal? Yes
◼ Time Complexity: O(bd/2), where
d is the depth of the solution.
◼ Space Complexity: O(bd/2), where
d is the depth of the solution.
13
14
