A* with an admissible heuristic on a weighted graph. Print the optimal path and cost, and show A* expands fewer nodes than uniform-cost search (h=0).

Answer

import heapq graph = { 'S': [('A', 2), ('D', 1)], 'A': [('G', 4)], 'D': [('E', 1)], 'E': [('G', 8)], 'G': [], } h = {'S': 6, 'A': 4, 'D': 9, 'E': 8, 'G': 0} # h(D)=9 <= true 10: admissible def search(start, goal, heuristic): counter = 0 open_pq = [(heuristic[start], 0, counter, start, [start])] g_best = {start: 0} expanded = 0 while open_pq: _f, g, _, node, path = heapq.heappop(open_pq) if g > g_best.get(node, float('inf')): continue expanded += 1 if node == goal: return path, g, expanded for nbr, cost in graph[node]: ng = g + cost if ng < g_best.get(nbr, float('inf')): g_best[nbr] = ng counter += 1 heapq.heappush(open_pq, (ng + heuristic[nbr], ng, counter, nbr, path + [nbr])) return None, None, expanded path, cost, exp_astar = search('S', 'G', h) zero = {k: 0 for k in h} _, _, exp_ucs = search('S', 'G', zero) print(f"A* path: {path} cost {cost} (expanded {exp_astar} nodes)") print(f"uniform-cost expanded {exp_ucs} nodes; A* fewer: {exp_astar < exp_ucs}")