图搜索 — Wu Chenfeng

任务依赖要先于消费者，导航路线则要成本更低，两者都用图但目标不同。图搜索先固定边语义，再选择拓扑、最短路或启发式。环、负权和过期堆条目改变算法前提。

图表示

资产依赖、任务调度、Shader 节点和关卡连接常是 Graph，不是树。一个节点可有多个父节点，甚至存在环。

表示：

邻接表：适合稀疏图，内存约 $O(V+E)$ ；
邻接矩阵：查询边 $O(1)$ ，内存 $O(V^2)$ ，适合小而稠密；
边列表：交换/批处理简单，但邻居查询需索引。

稳定节点ID 与显示名称分开。重命名不应改变依赖身份。

无向图的连通分量可用 DFS、BFS 或并查集求出。有向图还要区分弱连通与强连通。DFS 中可按发现时间把边分为树、Back、Forward 和 Cross Edge；Back Edge 能帮助判断有向环，具体分类依赖 DFS 森林与有向性。

Floyd-Warshall 用三重循环计算所有点对最短路，允许负权边但不能存在可达负权环，复杂度为 $O(V^3)$ 。把加法与最小值替换成逻辑与、或，可以得到传递闭包，回答任意两点是否可达。

拓扑排序

有向无环图（DAG）可做拓扑排序，得到所有依赖先于使用者的执行顺序。

Kahn算法：

计算每个节点入度；
把入度为 0 的节点入队；
弹出节点并减少其出边邻居入度；
新的 0 入队；
输出数量小于节点总数说明存在环。

资产构建中，纹理/来源先于材质，材质先于 Prefab/Level。环需要报告实际环路径，不能只说“排序失败”。

拓扑排序的输出不足以解释环的位置。Kahn留下的节点可能包括环本身及依赖环的下游节点；在剩余子图里再做带递归栈标记的DFS，发现指向当前栈的边后沿父指针还原具体环，才能给资产作者可修复的诊断。

Dijkstra

边权非负时，Dijkstra 从源点逐步确定最短距离。使用优先队列的复杂度常写为 $O((V+E)\log V)$ 。

它不只用于寻路，也可用于工具中的最小转换成本、依赖影响路径和图布局。所有边权相同时，BFS 更简单。

负权边需要其他算法；Dijkstra 得到错误结果时不一定会报错。

Bellman-Ford 对所有边重复松弛 $V-1$ 轮，可以处理负权边。第 $V$ 轮仍能松弛，说明源点可达范围内存在负权环。从该环还能到达的目标，其路径成本可反复绕环降低，因此没有有限最短距离；其他目标仍可能有有限距离或不可达。它的复杂度为 $O(VE)$ ，适合图规模较小或必须检测负权环的情况。

A*

A* 使用：

f(n)=g(n)+h(n)

$g(n)$ 是已走成本， $h(n)$ 是到目标的启发估计。 $h=0$ 时退化为 Dijkstra。

非负边权、目标启发值为零且允许发现更短路径后重开节点时，可采纳启发函数能保持最优性。Consistent 启发式还能避免频繁重新打开节点。

网格中常用 Manhattan/欧氏距离，但要匹配允许的移动方式和边权。为了速度加权 $h$ 可能牺牲最优性，应显式记录取舍。

四邻接单位成本网格采用曼哈顿距离。八邻接、直移成本1、斜移成本√2时，令dx、dy为两轴格数差的绝对值，八方向距离为max(dx,dy)+(sqrt(2)-1)*min(dx,dy)，欧氏距离也是下界。

边权按时间或地形计费时，距离下界还要乘每单位距离的最小合法成本。若传送连接允许低成本跨越远距离，直接使用空间距离可能高估，需构造包含这些连接的下界，或取h=0。导航接口按游戏AI导航所述的图与代价提交查询。

从A到B有直接边成本10，另有A到C成本1、C到B成本1。最初把B的10入堆，扩展C后发现B成本2，再压入一条B的2。单目标搜索弹出B的2便返回；若继续搜索其他目标，之后弹出的B的10通过entry.cost != bestCost[node]被跳过。堆中保存历史候选，成本表保存当前最优，两者职责不同。

启发值不一致时，一个节点第一次被展开后仍可能从另一条路径获得更小g值。本页实现没有永久关闭集合，所以更短候选可以再次入堆。若加入关闭集合优化，必须同时证明启发一致性，或允许重新打开节点。搜索输入还要拒绝NaN成本，它会破坏比较与堆顺序。

A* 主循环

cpp

Path AStar(const Graph& graph, NodeId start, NodeId goal)
{
    CostTable bestCost(graph.NodeCount(), Infinity);
    ParentTable parent(graph.NodeCount(), InvalidNode);
    MinHeap open;
    bestCost[start] = 0;
    open.Push({start, 0, Heuristic(start, goal)});
    while (!open.Empty()) {
        Entry entry = open.Pop();
        if (entry.cost != bestCost[entry.node]) continue;
        if (entry.node == goal) return Reconstruct(parent, goal);
        for (const Edge& edge : graph.Neighbors(entry.node)) {
            float candidate = entry.cost + edge.cost;
            if (candidate >= bestCost[edge.to]) continue;
            bestCost[edge.to] = candidate;
            parent[edge.to] = entry.node;
            open.Push({edge.to, candidate,
                       candidate + Heuristic(edge.to, goal)});
        }
    }
    return NoPath;
}

这是算法伪代码。堆按估计总成本排序，边代价非负，启发函数在目标处为零。节点找到更短路径后可以再次入堆，因此也支持可采纳但不一致的启发函数。每次搜索独立初始化成本表；弹出目标时得到路径。

在同一张图上分别运行 Dijkstra 和使用可采纳启发函数的 A*，两者路径成本应相等。A* 成本更高时检查启发函数及重开节点逻辑；成本更低时检查代价定义和两种实现。Dijkstra 在非负代价图上已给出最优成本。扩展节点数用于比较搜索效率。

验证方法

小图用穷举或Dijkstra对照，测试不连通、环和重复边。A*使用非负边、目标h为零，非一致可采纳启发函数允许重开节点。导航应用只保存路径前提，完整搜索机制在这里维护。

实现与证据

A*主循环是依赖图、堆与成本表的C++伪代码；新增三节点算例与重开条件。尚未运行独立搜索实现，最优性需按本文前提与Dijkstra对照。

参考资料

MIT6.006课程资料：最短路、Dijkstra与Bellman-Ford讲义。
Hart、Nilsson与Raphael：A Formal Basis for the Heuristic Determination of Minimum Cost Paths：A*原论文，估价与最优路径性质的来源入口。

图表示