第 5 章 · 经典路线图搜索代码实验¶

# AIMA Romania map：从 Arad 搜索到 Bucharest。
graph = {
    "start": "Arad",
    "goal": "Bucharest",
    "nodes": {
        "Arad": {"name": "Arad", "h": 366},
        "Zerind": {"name": "Zerind", "h": 374},
        "Oradea": {"name": "Oradea", "h": 380},
        "Sibiu": {"name": "Sibiu", "h": 253},
        "Timisoara": {"name": "Timisoara", "h": 329},
        "Lugoj": {"name": "Lugoj", "h": 244},
        "Mehadia": {"name": "Mehadia", "h": 241},
        "Dobreta": {"name": "Dobreta", "h": 242},
        "Craiova": {"name": "Craiova", "h": 160},
        "Rimnicu Vilcea": {"name": "Rimnicu Vilcea", "h": 193},
        "Fagaras": {"name": "Fagaras", "h": 176},
        "Pitesti": {"name": "Pitesti", "h": 100},
        "Bucharest": {"name": "Bucharest", "h": 0},
        "Giurgiu": {"name": "Giurgiu", "h": 77},
        "Urziceni": {"name": "Urziceni", "h": 80},
        "Hirsova": {"name": "Hirsova", "h": 151},
        "Eforie": {"name": "Eforie", "h": 161},
        "Vaslui": {"name": "Vaslui", "h": 199},
        "Iasi": {"name": "Iasi", "h": 226},
        "Neamt": {"name": "Neamt", "h": 234},
    },
    "edges": [
        {"from": "Arad", "to": "Zerind", "cost": 75},
        {"from": "Arad", "to": "Sibiu", "cost": 140},
        {"from": "Arad", "to": "Timisoara", "cost": 118},
        {"from": "Zerind", "to": "Oradea", "cost": 71},
        {"from": "Oradea", "to": "Sibiu", "cost": 151},
        {"from": "Timisoara", "to": "Lugoj", "cost": 111},
        {"from": "Lugoj", "to": "Mehadia", "cost": 70},
        {"from": "Mehadia", "to": "Dobreta", "cost": 75},
        {"from": "Dobreta", "to": "Craiova", "cost": 120},
        {"from": "Craiova", "to": "Rimnicu Vilcea", "cost": 146},
        {"from": "Craiova", "to": "Pitesti", "cost": 138},
        {"from": "Sibiu", "to": "Fagaras", "cost": 99},
        {"from": "Sibiu", "to": "Rimnicu Vilcea", "cost": 80},
        {"from": "Rimnicu Vilcea", "to": "Pitesti", "cost": 97},
        {"from": "Fagaras", "to": "Bucharest", "cost": 211},
        {"from": "Pitesti", "to": "Bucharest", "cost": 101},
        {"from": "Bucharest", "to": "Giurgiu", "cost": 90},
        {"from": "Bucharest", "to": "Urziceni", "cost": 85},
        {"from": "Urziceni", "to": "Hirsova", "cost": 98},
        {"from": "Hirsova", "to": "Eforie", "cost": 86},
        {"from": "Urziceni", "to": "Vaslui", "cost": 142},
        {"from": "Vaslui", "to": "Iasi", "cost": 92},
        {"from": "Iasi", "to": "Neamt", "cost": 87},
    ],
}

start = graph["start"]
goal = graph["goal"]
h = {node: meta["h"] for node, meta in graph["nodes"].items()}
print("起点:", start, "终点:", goal)

# 把边表转成邻接表：搜索算法只需要知道“当前节点能走向哪些邻居”。
adj = {}
for edge in graph["edges"]:
    a = edge["from"]
    b = edge["to"]
    cost = edge["cost"]
    adj.setdefault(a, []).append((b, cost))
    adj.setdefault(b, []).append((a, cost))

for neighbors in adj.values():
    neighbors.sort(key=lambda item: item[0])

adj

# 节点表给出直线距离启发式 h，边表给出相邻城市距离。
nodes_df = pd.DataFrame(
    [
        {"节点": node, "名称": meta["name"], "h(到 Bucharest)": meta["h"]}
        for node, meta in graph["nodes"].items()
    ]
).sort_values("节点")

edges_df = pd.DataFrame(
    [
        {"边": f"{edge['from']}↔{edge['to']}", "代价": edge["cost"]}
        for edge in graph["edges"]
    ]
)

display(nodes_df)
display(edges_df)

# 绘制 Romania map：高亮已展开节点和最终路线。
layout = {
    "Arad": (0.45, 3.25),
    "Zerind": (0.25, 4.18),
    "Oradea": (1.02, 5.02),
    "Sibiu": (2.15, 3.52),
    "Timisoara": (0.38, 2.02),
    "Lugoj": (1.25, 1.32),
    "Mehadia": (1.28, 0.52),
    "Dobreta": (1.62, -0.22),
    "Craiova": (2.95, -0.12),
    "Rimnicu Vilcea": (3.12, 2.35),
    "Fagaras": (4.15, 3.55),
    "Pitesti": (4.42, 1.42),
    "Bucharest": (5.82, 1.18),
    "Giurgiu": (5.58, 0.10),
    "Urziceni": (6.82, 1.90),
    "Hirsova": (7.85, 2.06),
    "Eforie": (8.28, 1.18),
    "Vaslui": (7.55, 3.12),
    "Iasi": (7.25, 4.18),
    "Neamt": (6.45, 4.88),
}


def edge_key(a, b):
    return tuple(sorted((a, b)))


def path_edges(path):
    return {edge_key(path[i], path[i + 1]) for i in range(len(path) - 1)}


def draw_search_result(path=None, trace=None, title="罗马尼亚路线图搜索"):
    path = path or []
    active_edges = path_edges(path)
    visited_nodes = set(path)
    if trace is not None and not trace.empty:
        visited_nodes.update(trace["取出节点"].tolist())

    fig, ax = plt.subplots(figsize=(11.4, 6.4))
    ax.set_facecolor("#fbfcfd")

    drawn_edges = set()
    for a, neighbors in adj.items():
        for b, cost in neighbors:
            key = edge_key(a, b)
            if key in drawn_edges:
                continue
            drawn_edges.add(key)
            x1, y1 = layout[a]
            x2, y2 = layout[b]
            is_path = key in active_edges
            ax.plot(
                [x1, x2],
                [y1, y2],
                color="#2563eb" if is_path else "#cbd5e1",
                linewidth=3.2 if is_path else 1.8,
                solid_capstyle="round",
                zorder=2 if is_path else 1,
            )
            ax.text(
                (x1 + x2) / 2,
                (y1 + y2) / 2,
                str(cost),
                ha="center",
                va="center",
                fontsize=9,
                color="#1d4ed8" if is_path else "#64748b",
                bbox={"boxstyle": "round,pad=0.18", "fc": "white", "ec": "#e2e8f0"},
                zorder=4,
            )

    for node, (x, y) in layout.items():
        is_start = node == start
        is_goal = node == goal
        is_visited = node in visited_nodes
        face = "#eff6ff" if is_visited else "#ffffff"
        edge = "#2563eb" if is_visited else "#94a3b8"
        if is_start:
            face, edge = "#d1fae5", "#059669"
        if is_goal:
            face, edge = "#ffedd5", "#f97316"
        circle = plt.Circle((x, y), 0.16, facecolor=face, edgecolor=edge, linewidth=1.8, zorder=5)
        ax.add_patch(circle)
        ax.text(x, y, node[:1], ha="center", va="center", fontweight="bold", color="#0f172a", zorder=6)
        ax.text(
            x,
            y - 0.28,
            f"{graph['nodes'][node]['name']}\nh={h[node]}",
            ha="center",
            va="top",
            fontsize=8,
            color="#475569",
            bbox={"boxstyle": "round,pad=0.12", "fc": "white", "ec": "none", "alpha": 0.85},
        )

    if path:
        total = path_cost(path)
        ax.text(
            0.04,
            0.05,
            f"path: {' -> '.join(path)}   cost={total}",
            transform=ax.transAxes,
            ha="left",
            va="bottom",
            fontsize=10,
            color="#334155",
            bbox={"boxstyle": "round,pad=0.32", "fc": "white", "ec": "#e2e8f0"},
        )

    ax.set_title(title, loc="left", fontsize=14, fontweight="bold", color="#0f172a")
    ax.set_xlim(-0.25, 8.65)
    ax.set_ylim(-0.62, 5.45)
    ax.set_aspect("equal", adjustable="box")
    ax.axis("off")
    plt.tight_layout()
    plt.show()


draw_search_result(title="罗马尼亚路线图：Arad 到 Bucharest")

# 运行 DFS：查看栈的展开过程和最终路线。
dfs_path, dfs_trace = dfs(start, goal, adj)
display(dfs_trace)
draw_search_result(dfs_path, dfs_trace, "DFS：栈后进先出")

# 运行 BFS：查看队列的展开过程和最终路线。
bfs_path, bfs_trace = bfs(start, goal, adj)
display(bfs_trace)
draw_search_result(bfs_path, bfs_trace, "BFS：队列先进先出")

# 运行 UCS：查看按累计代价 g 选择节点的过程。
ucs_path, ucs_trace = ucs(start, goal, adj)
display(ucs_trace)
draw_search_result(ucs_path, ucs_trace, "UCS：累计代价最小优先")

# 运行 Greedy：查看按启发式 h 选择节点的过程。
greedy_path, greedy_trace = greedy(start, goal, adj, h)
display(greedy_trace)
draw_search_result(greedy_path, greedy_trace, "贪心搜索：启发式最小优先")

# 运行 A*：查看按 f=g+h 选择节点的过程。
astar_path, astar_trace = astar(start, goal, adj, h)
display(astar_trace)
draw_search_result(astar_path, astar_trace, "A*：g+h 最小优先")

# 汇总五种搜索策略的路线、边数和总代价。
summary_df = pd.DataFrame(
    [
        {"算法": "DFS", "路径": "→".join(dfs_path), "边数": len(dfs_path) - 1, "代价": path_cost(dfs_path)},
        {"算法": "BFS", "路径": "→".join(bfs_path), "边数": len(bfs_path) - 1, "代价": path_cost(bfs_path)},
        {"算法": "UCS", "路径": "→".join(ucs_path), "边数": len(ucs_path) - 1, "代价": path_cost(ucs_path)},
        {"算法": "Greedy", "路径": "→".join(greedy_path), "边数": len(greedy_path) - 1, "代价": path_cost(greedy_path)},
        {"算法": "A*", "路径": "→".join(astar_path), "边数": len(astar_path) - 1, "代价": path_cost(astar_path)},
    ]
)
display(summary_df)