AiSc 6

# Graph represented as an adjacency list
graph = {
    "A": [("B", 1), ("C", 4)],
    "B": [("D", 5)],
    "C": [("D", 1)],
    "D": [],
}

# Heuristic values to target node D
heuristic = {"A": 6, "B": 4, "C": 1, "D": 0}


def greedy_best_first(start, goal):
    visited = set()
    queue = [[start]]

    while queue:
        # Sort queue by lowest heuristic value
        queue.sort(key=lambda path: heuristic[path[-1]])

        path = queue.pop(0)
        node = path[-1]

        if node == goal:
            return path

        if node not in visited:
            visited.add(node)

            for neighbor, cost in graph.get(node, []):
                new_path = list(path)
                new_path.append(neighbor)
                queue.append(new_path)

    return None


# Execute search from A to D
solution = greedy_best_first("A", "D")
print(f"Greedy Best-First Search Path: {solution}")