Program 3: Greedy Best-first Search
Concept Explanation: Greedy best-first search algorithm always selects the path which appears
best at that moment. It uses a priority queue to explore the node which is closest to the goal.
Python Code:
import heapq
def greedy_best_first_search(graph, start, goal):
open_list = [(0, start)]
heapq.heapify(open_list)
closed_list = set()
came_from = {start: None}
while open_list:
_, current = heapq.heappop(open_list)
if current in closed_list:
continue
if current == goal:
break
closed_list.add(current)
for neighbor, weight in graph[current]:
if neighbor not in closed_list:
heapq.heappush(open_list, (weight, neighbor))
came_from[neighbor] = current
path = []
while current:
path.append(current)
current = came_from[current]
return path[::-1]
graph = {
'A': [('B', 1), ('C', 3)],
'B': [('D', 3), ('E', 1)],
'C': [('F', 1), ('G', 2)],
'D': [],
'E': [],
'F': [],
'G': []
}
path = greedy_best_first_search(graph, 'A', 'G')
print(path)
Output:
['A', 'C', 'G']
Program 4: A* Search
Concept Explanation: A* Search algorithm is a search algorithm that finds the shortest path
from a starting node to a goal node. It uses both the actual distance from the start node and the
estimated distance to the goal node to prioritize the nodes to be explored.
Python Code:
import heapq
def heuristic(node, goal):
return abs(ord(node) - ord(goal))
def a_star_search(graph, start, goal):
open_list = [(0, start)]
heapq.heapify(open_list)
closed_list = set()
g_costs = {start: 0}
came_from = {start: None}
while open_list:
_, current = heapq.heappop(open_list)
if current in closed_list:
continue
if current == goal:
break
closed_list.add(current)
for neighbor, weight in graph[current]:
tentative_g_cost = g_costs[current] + weight
if neighbor not in g_costs or tentative_g_cost <
g_costs[neighbor]:
g_costs[neighbor] = tentative_g_cost
f_cost = tentative_g_cost + heuristic(neighbor,
goal)
heapq.heappush(open_list, (f_cost, neighbor))
came_from[neighbor] = current
path = []
while current:
path.append(current)
current = came_from[current]
return path[::-1]
graph = {
'A': [('B', 1), ('C', 3)],
'B': [('D', 3), ('E', 1)],
'C': [('F', 1), ('G', 2)],
'D': [],
'E': [],
'F': [],
'G': []
}
path = a_star_search(graph, 'A', 'G')
print(path)
Output:
['A', 'C', 'G']
