UCS
Uniform Cost Search (UCS) is a variant of Dijkstra’s Algorithm but it operates on State Space Search based problems on weighted graphs. With a memory requirement similar to BFS, UCS returns an optimal path even when the edge costs vary 1. The goal of UCS is to find a path to the goal state that has the minimum total cost from the start state. It does so by calculating the cumulative cost from the start state to the next state which has the least edge weight, prioritising lower costs in each move. But UCS can only operate on structures which have non-negative weights. While closely related to Dijsktra’s Algorithm, UCS is rooted in heuristic search 2.
Pseudocode for UCS Algorithm
1. function UCS(graph, start, target):
2. initialise priority_queue with (0, start, [])
3. initialise visited set as empty
4. while priority_queue is not empty:
5. pop (cost, node, path) from priority_queue
6. if node == target, return path + [node], cost
7. if node is not in visited:
8. mark node as visited
9. for each (neighbour, edge_cost) in graph[node]:
10. if neighbour not in visited,
push (cost + edge_cost, neighbour, path + [node]) into priority_queue
11. return None, infinity The data structure that is appropriate for the implementation of UCS is Priority Queue. Let us see an example:
The priority queue will have three tuples as its elements - cost, node, and path. The initialisation will be done by adding the starting node A to the priority queue with a cost = 0. This would lead the priority queue to become :[(0, A, [A])].
- Step 1: Priority Queue is in the state [(0, A, [A])]
- Pop (0, A, [A]). Current node is A and path cost = 0
- Neighbour of A : B with cumulative cost = 1
- Add (1, B, [A, B])
- Neighbour of A: C with cumulative cost = 4
- Add (4, C, [A, C])
- Priority Queue is in the state [(1, B, [A, B]), (4, C, [A, C])]
- Step 2: Priority Queue is in the state [(1, B, [A, B]), (4, C, [A, C])]
- Pop (1, B, [A, B]). Current node is B and path cost = 1
- Neighbour of B : C with cumulative cost = 3
- Add (3, C, [A, B, C])
- Neighbour of B: D with cumulative cost = 6
- Add (6, D, [A, B, D])
- Priority Queue is in the state [(3, C, [A, B, C]), (4, C, [A, C]), (6, D, [A, B, D])]
- Step 3: Priority Queue is in the state [(3, C, [A, B, C]), (4, C, [A, C]), (6, D, [A, B, D])]
- Pop (3, C, [A, B, C]). Current node is C and path cost = 3
- Neighbour of C : D with cumulative cost = 4
- Add (4, D, [A, B, C, D])
- Priority Queue is in the state [(4, C, [A, C]), (6, D, [A, B, D]), (4, D, [A, B, C, D])]
- Step 4: Priority Queue is in the state [(4, C, [A, C]), (6, D, [A, B, D]), (4, D, [A, B, C, D])]
- Pop (4, D, [A, B, C, D]). Current node is D and path cost = 4
- Goal State D is reached and the traversal is to be terminated
The path is A→B→C→D with the total cost =4. This way, UCS ensures that the traversal is optimal and is done through the lowest-cost path using priority queue.
IDDFS Algorithm Implementation
The first code cell imports the heapq module, which is used to implement a priority queue in the Uniform Cost Search (UCS) algorithm. The priority queue allows the algorithm to efficiently select the next node with the lowest cumulative cost, ensuring that the algorithm explores the least costly paths first, which is crucial for finding the optimal solution in a graph with weighted edges.
Code
import heapq # heapq is used to implement the priority queueThe second code cell defines the ucs() function, which implements the Uniform Cost Search algorithm. This algorithm explores the graph by expanding the least costly path first, using a priority queue to store nodes along with their path cost. It ensures that the shortest path (if one exists) from the starting node to the target node is found. The function returns the path and its total cost, or None and infinity if no path is found.
Code
# Function to perform Uniform Cost Search (UCS)
def ucs(graph, start, target):
# Priority queue to store nodes to explore along with their current path cost.
# The queue will store tuples of the form (cost, node, path).
priority_queue = []
# Add the start node to the priority queue with a cost of 0 and an empty path.
heapq.heappush(priority_queue, (0, start, []))
# Set to keep track of visited nodes to avoid revisiting them
visited = set()
while priority_queue:
# Get the node with the lowest cost from the priority queue
cost, node, path = heapq.heappop(priority_queue)
# If the node is the target, return the full path (start -> ... -> target) and its cost
if node == target:
return path + [node], cost
# If the node has already been visited, skip it
if node in visited:
continue
# Mark the current node as visited
visited.add(node)
# Explore the neighbors of the current node
for neighbor, edge_cost in graph[node]:
# If the neighbor has not been visited, add it to the priority queue
if neighbor not in visited:
heapq.heappush(priority_queue, (cost + edge_cost, neighbor, path + [node]))
# If no path is found, return None
return None, float('inf') # No path found, return infinite costIn the third code cell, an example graph is represented as an adjacency list, where each node has neighbors along with the cost of traveling to them. The ucs() function is called with a starting node and a target node. The result is printed, showing the shortest path from the start node to the target node, along with its total cost, or indicating that no path was found if applicable.
Code
# Example graph represented as an adjacency list with edge weights.
# Each node has a list of tuples: (neighbor, cost)
graph = {
'A': [('B', 1), ('C', 4)],
'B': [('A', 1), ('C', 2), ('D', 5)],
'C': [('A', 4), ('B', 2), ('D', 1)],
'D': [('B', 5), ('C', 1)]
}
# Starting and target nodes
start_node = 'A'
target_node = 'D'
# Call the UCS function to find the shortest path
path, cost = ucs(graph, start_node, target_node)
# Print the result
if path:
print(f"Shortest path from {start_node} to {target_node}: {path} with total cost {cost}")
else:
print(f"No path found from {start_node} to {target_node}")Shortest path from A to D: ['A', 'B', 'C', 'D'] with total cost 4