Greedy best-first search ordered by h(n) alone on a small graph. Print the expansion order and the path found from A to F.

Answer

import heapq graph = { 'A': [('B', 1), ('C', 1)], 'B': [('D', 1)], 'C': [('F', 1)], 'D': [('F', 1)], 'F': [], } h = {'A': 5, 'B': 4, 'C': 2, 'D': 3, 'F': 0} def best_first(start, goal): counter = 0 open_pq = [(h[start], counter, start, [start])] expanded = [] closed = set() while open_pq: _, _, node, path = heapq.heappop(open_pq) if node in closed: continue closed.add(node) expanded.append(node) if node == goal: return expanded, path for nbr, _cost in graph[node]: if nbr not in closed: counter += 1 heapq.heappush(open_pq, (h[nbr], counter, nbr, path + [nbr])) return expanded, None order, path = best_first('A', 'F') print("expansion order:", ' '.join(order)) print("path:", ' -> '.join(path))