1. 课程导入与问题界定

路径规划是运筹优化与机器人、物流、通信网络等领域的共同基础问题：给定起点、终点、可通行区域与代价约束，找出一条（或一组）满足条件的路径。经典方法从 Dijkstra、A*、RRT 到整数规划，已经非常成熟。但当问题规模变大、约束变复杂时，经典求解会遇到两个瓶颈：一是搜索空间随节点数指数增长，二是多约束耦合后问题往往变成 NP-hard，精确求解时间不可接受。

量子路径规划并不是"用量子计算机替代 A*"，而是把路径规划问题重新表述为量子计算可处理的优化模型，借助量子退火或量子近似优化算法（QAOA）在解空间中采样，从而在特定规模与结构下获得更优的近似解或更快的求解速度。理解这一点，是整门课程的起点。

问题定义：从图到二次无约束二值模型

本课程统一采用图模型描述路径规划：地图抽象为带权无向图 G=(V,E)，节点 V 表示可通行位置，边 E 表示相邻可达关系，边权 w(u,v) 表示距离或代价。路径规划即寻找从起点 s 到终点 t 的节点序列，使总代价最小且满足约束（如不重复经过节点、必经某些节点、避开障碍）。

要让量子算法处理它，需要把"选哪些边"变成二值变量。设 x(u,v) ∈ {0,1} 表示边 (u,v) 是否被选中，则目标函数为：

minimize  Σ w(u,v) · x(u,v)
subject to
  流量守恒：对每个中间节点 v，流入边数 = 流出边数
  起点约束：s 的流出边数 = 1
  终点约束：t 的流入边数 = 1
  连通性约束：选中的边必须构成一条从 s 到 t 的连通路径

把约束以罚函数形式并入目标，就得到量子退火可直接读取的 QUBO（二次无约束二值优化）形式：H = Σ w·x + λ·(约束违反量)²。其中 λ 是罚系数，取值过小会导致解不满足约束，过大则压缩有效解空间、降低采样质量。这是本课程后续反复出现的核心参数。

与经典路径规划的关键区别

区别不在"谁更快"这种笼统判断，而在四个具体层面。第一，问题表述：经典方法直接在图上搜索，量子方法必须先转成 QUBO/Ising 模型，建模质量直接决定求解上限。第二，解的性质：经典精确算法给出确定最优解，量子退火给出的是概率性采样结果，需要多次运行取最优并统计成功率。第三，规模限制：当前量子硬件比特数有限，且存在连通性约束，需要嵌入（minor embedding）到硬件拓扑，会额外消耗物理比特。第四，评价指标：不能只看解的质量，还要看采样次数、成功率、嵌入开销与总耗时。

课程目标与学习路线

本课程的目标是让学习者能够独立完成一条完整链路：把实际路径规划场景抽象为图模型 → 构造 QUBO 目标与约束 → 选择量子求解器或模拟器 → 运行采样 → 解码路径 → 评估解质量与可行性。围绕这条链路，30 个章节分为五个阶段。

第一阶段（第 1–6 章）建立问题与数学基础：问题界定、图模型、QUBO 构造、Ising 变换、罚系数设计、约束编码。第二阶段（第 7–13 章）进入算法层：量子退火原理、QAOA 线路结构、参数优化、采样与后处理。第三阶段（第 14–20 章）处理工程实现：硬件拓扑与嵌入、模拟器使用、代码框架、数据接口。第四阶段（第 21–26 章）做案例与对比：网格地图、多约束路径、经典-量子对比实验设计。第五阶段（第 27–30 章）做复盘与扩展：结果分析、失败模式排查、混合算法与展望。

图中上半部分是单次求解的完整数据流：场景抽象为图，图转成 QUBO，再变换为 Ising 模型，嵌入硬件后采样，最后解码校验并评估。红色虚线表示实际工程中最常发生的反馈——解质量不达标时，不是简单"再跑一次"，而是回到罚系数、约束编码或采样次数上做调整。下半部分把 30 章映射到建模、算法实现、案例复盘三个阶段，帮助学习者随时定位自己处在链路的哪一环。

一个最小教学示例

为让抽象定义落地，考虑一个 3×3 网格地图，共 9 个节点，起点为左上角 (0,0)，终点为右下角 (2,2)，中心节点 (1,1) 设为障碍。相邻节点间边权为 1。可行路径只有沿边界绕行的两条，长度均为 4。若用 QUBO 建模，需要为每条可通行边分配一个二值变量，共 12 条边；流量守恒约束对 7 个非起终点节点各写一条，罚系数取 λ=5（大于单条边最大代价 1 的若干倍，确保违反约束的解不会被误判为优）。运行量子模拟器采样 1000 次，统计满足约束且连通的比特串比例，即为该参数下的可行解成功率。这个示例规模很小，经典方法瞬间可解，但它完整覆盖了建模、参数、采样、解码、评估五个环节，后续章节会在此基础上逐步加大规模与约束复杂度。