2. 路径规划基础与量子计算视角

在把路径规划问题交给量子算法之前，必须先把它“翻译”成量子计算能够接受的形式。这一节我们先回到经典路径规划，把它的三个核心要素——图、代价、约束——拆开看清楚，再讨论它们各自如何映射到量子计算的表达体系中。理解这条映射链，是后续建模与仿真的前提。

一、经典路径规划的三大要素

图（Graph）是路径规划的空间骨架。一个带权图 G=(V,E) 由顶点集合 V 和边集合 E 构成，顶点表示可到达的位置（路口、航点、栅格单元、机器人位姿），边表示两点之间存在可行连接。图的结构决定了问题的搜索空间规模：n 个顶点的完全图有 n(n−1)/2 条边，而栅格地图的边数通常与格子数成正比。实际建模时还要区分有向与无向、连通与不连通、静态与动态图。

代价（Cost）是衡量路径优劣的标尺。每条边 e 赋予权重 w(e)，表示距离、时间、能耗或风险；一条路径的总代价是各边权重之和。代价的设计直接决定最优解的含义：以距离为代价得到最短路径，以时间为代价得到最快路径，以风险为代价得到最安全路径。多目标场景下常用加权和 c = α·距离 + β·时间 + γ·风险 把多个指标压缩为单一标量，权重 α、β、γ 的取值需要归一化处理，否则量纲差异会淹没真实偏好。

约束（Constraint）是可行性的边界。常见约束包括：避障（某些顶点或边不可通行）、容量限制（如车辆载重、无人机电量）、时间窗（必须在某时段内到达）、必经点（路径必须经过指定节点）、禁行区与转向限制。约束把“所有路径”缩小为“可行路径集合”，最优解必须在这个集合内寻找。

二、从经典求解到量子视角的转换

经典算法如 Dijkstra、A*、Bellman-Ford 在多项式时间内求解单源最短路径，但它们依赖逐点松弛的串行过程，难以直接并行化到量子线路。量子视角的切入点不是“加速某一步松弛”，而是把路径选择重新表述为组合优化问题：用一组二进制变量表示“是否选择某条边”，把总代价写成这些变量的函数，把约束写成等式或不等式，于是路径规划变成在 2^m 维空间中寻找使目标函数最小的比特串（m 为候选边数）。

这一转换的关键是二次无约束二值优化（QUBO）形式。设 x_e ∈ {0,1} 表示边 e 是否被选中，目标函数写作：

H_cost = Σ_e w(e)·x_e
H_penalty = λ·Σ_v (Σ_{e∈δ(v)} x_e − b_v)²
H_total = H_cost + H_penalty

其中 δ(v) 是与顶点 v 关联的边集合，b_v 是流量守恒要求的取值（起点为 +1、终点为 −1、中间点为 0），λ 是惩罚系数。第一项鼓励低代价，第二项惩罚违反流量守恒的选边组合。当 λ 足够大时，H_total 的最小值对应一条合法路径。这就是经典图问题向量子可处理形式的第一次映射。

三、量子化表达的初步思路

得到 QUBO 之后，下一步是把它变成量子线路能演化的哈密顿量。常用做法是把二值变量替换为泡利 Z 算符：x_e → (1 − Z_e)/2，于是 H_total 变成只含 Z 算符及其乘积的伊辛哈密顿量。此时问题的基态就是最优路径对应的比特串。量子算法（如量子近似优化算法 QAOA）通过交替施加代价哈密顿量和混合哈密顿量，逐步把初态演化到接近基态的状态，最后测量得到候选解。

需要清醒认识的是：量子化表达并不自动带来优势。当前含噪中等规模量子设备的比特数与相干时间有限，能表达的图规模还很小；QUBO 的惩罚系数 λ 若设置不当，会把合法解与非法解的能量次序打乱，导致测量结果不可用。因此建模阶段必须做规模评估与参数校验：先估算候选边数 m 与所需比特数，再检查 λ 是否大于单条边最大代价与最小代价之差，确保约束项在能量上真正“压得住”代价项。

四、一个可动手的建模示例

考虑一个 3×3 栅格地图，起点在左上角 (0,0)，终点在右下角 (2,2)，只允许向右和向下移动，共 12 条有向边。设每条边代价为 1，则最短路径长度为 4。用 QUBO 建模时，12 个二值变量对应 12 条边，流量守恒约束对 9 个顶点各写一条：起点出度减入度等于 1，终点等于 −1，其余等于 0。惩罚系数取 λ=5（大于单边最大代价 1 与最小代价 0 之差），可保证任何违反守恒的选边组合能量都高于合法路径。

把这个模型交给 QAOA 仿真时，可以观察两个量：一是测量得到的比特串中合法路径的比例，二是合法路径中代价为 4 的比例。若前者很低，说明 λ 偏小或线路层数不足；若后者很低，说明代价项与惩罚项的量级失衡。这两个观察点构成了建模是否成功的直接判据，也是后续章节做仿真实验时的基本检查项。

总结本节：经典路径规划由图、代价、约束三要素刻画；量子化的第一步是把选边决策写成二值变量，把代价写成线性项、把约束写成平方惩罚项，得到 QUBO；第二步是把二值变量替换为泡利算符，得到伊辛哈密顿量，再交给 QAOA 等算法演化求解。这条映射链的每一环都需要用具体参数校验，才能保证量子模型忠实反映原始路径规划问题。