精读笔记
Problem Setting
《An Exact Continuous Conductance Formulation of the Hamiltonian Path Problem》（arXiv preprint / 2026）处理的是 HPP 的 exact continuous formulation，而不是一个新的实用 HPP solver。它把给定无向图中指定端点的 Hamiltonian path 问题嵌入到 conductance cube [0,1]^|A| 上的连续最小化问题中，并证明在有解前提下全局 minimizer 与 Hamiltonian path 一一对应。
真正困难点不是写出一个 penalty，而是避免连续松弛常见的伪解：fractional edge selection、局部分叉、只覆盖部分节点的流、带环流的结构、以及边上有非零 conductance 但不属于路径的情况。作者的目标是让这些伪解在全局零目标处全部不可能出现。
关键矛盾是：Hamiltonian path 是全局组合约束，但目标函数希望由局部电流行为构成；如果只做 degree penalty，会得到 cycle cover / disconnected path fragments；如果只做 flow penalty，会得到 branching arborescence 或 fractional flow。本文的解法是让电势场承担全局拓扑约束，让 penalty 只负责局部行为。
Motivation
已有路线各自缺一块：Held-Karp / exact search 是算法路线但指数复杂；QUBO / Ising 是离散能量编码，变量仍是二进制，主要服务 annealing 硬件；Hopfield/TSP 类型连续能量有启发式意义，但 exactness 一般不足。本文想要的不是更快，而是一个严格的连续等价表述。
作者的核心观察是，Ohmic network 不是普通 flow network：电流方向由 scalar potential 决定，因此天然不允许沿正电流方向形成环。这一点很关键，因为很多 flow-based formulation 需要额外 subtour elimination 或全局约束来排环；这里电势单调性把 acyclicity 变成物理定律的直接后果。
缺口在于：能否用足够少的、局部的 penalty 结合电势结构，精确刻画 Hamiltonian path 的全局支撑。论文的答案是可以，但代价是只保证 global minima 的语义，不保证优化可达性。
Core Idea
核心思想是把边选择变量解释为 conductance，而不是直接解释为 path indicator。给定 conductance 后，整个图上的电势由 Dirichlet 边界条件和 Kirchhoff 方程唯一决定，电流由 Ohm 定律诱导。于是一个 conductance configuration 不只是一个静态子图，而是一个带方向、带强度、带电势排序的流结构。
目标函数只做两件事：要求每个非 vOUT 节点的正向外流为 1；要求每个节点不能有两个正向 outgoing currents。前者强迫所有节点参与正电流支撑，后者强迫支撑非分叉。再由于正电流沿电势严格下降，支撑中不可能存在有向环。于是零 penalty 的支撑只能从每个节点沿唯一后继最终流向 vOUT，并覆盖所有节点；结合 vIN/vOUT 的 terminal construction，得到一条 spanning simple path。
和 prior 的本质区别是：QUBO/Ising 通常直接编码排列或边选择约束；本文把一部分组合结构交给连续物理系统的解算过程，即通过 Laplacian Dirichlet problem 隐式产生全局 ordering。新的 inductive bias 是“电势下降 + 无分叉单位外流”而不是“二进制变量 + degree/subtour penalty”。
Method
1. Terminal augmentation：它解决端点与源汇连接不统一的问题。通过引入 vIN/vOUT 并保证二者 degree=1，原图中的指定端点 Hamiltonian path 被规整为 augmented graph 上从 vIN 到 vOUT 的 Hamiltonian path。这个构造使证明里可以把 vIN 当作唯一源端、vOUT 当作唯一 sink 端，不需要额外讨论端点 degree。
2. Conductance cube：原图边的 g_a∈[0,1] 是优化变量，augmentation 边 conductance 固定为 1。这一步看似是连续松弛，但并不是普通 LP/QP relaxation，因为目标不是直接作用于 g，而是作用于由 g 解出的电势和电流。
3. 固定电压差 N−1：这是尺度闭合条件。Hamiltonian path 在 augmented graph 中恰有 N−1 条边；若每条路径边 conductance=1，总电阻 N−1，施加电势差 N−1，则每条边电流为 1。没有这个校准，outflow=1 的零 penalty 目标不会自然对应 conductance=1 的路径。
4. Outflow penalty：它要求除 vOUT 外每个节点有单位正向外流，vOUT 无正向外流。它的作用不是单纯 degree 约束，而是同时强迫所有节点进入绝对电流支撑；未被电流触达的节点会因 O_i=0 被惩罚。
5. Branching penalty：它惩罚同一节点多个正向 outgoing currents。结合 outflow=1 后，每个非 vOUT 节点只能有一个正向后继。这一步把可能的 arborescence / split flow 压成 path-like functional graph。
6. 全局 minimizer 到 binary path 的最后一步：零 penalty 先推出电流支撑是 Hamiltonian path；再利用总电势差 N−1 与路径长度 N−1，证明每条路径边电压降至少 1 且总和正好 N−1，因此每条 conductance 必为 1；非路径边若 conductance>0，由于路径上节点电势互异，会产生非零电流，矛盾，因此 conductance 必为 0。
Key Insight / Why It Works
这篇论文最核心的 insight 是：acyclicity 不需要显式 penalty。正电流只能沿电势下降方向流动，而 scalar potential 不可能沿闭环严格下降，所以任何正电流有向环自动被排除。这相当于用电网络的可积势函数替代了传统 Hamiltonian formulation 中最麻烦的 subtour elimination。
第二个关键点是 outflow 与 branch penalty 的组合非常“刚性”。outflow=1 让每个非 sink 节点必须有后继；branch=0 让后继唯一；acyclicity 让沿后继迭代不能循环；所以每个节点最终必须到达唯一无后继节点 vOUT。这已经非常接近一棵 oriented in-tree。再用 vIN/vOUT 的 terminal degree 和 Kirchhoff 守恒，排除多叶结构，得到 spanning path。
第三个关键点是 conductance 上界 g≤1 与电压差 N−1 的配合，把连续零解压回 cube 顶点。若路径边电流为 1，则电压降为 1/g≥1；路径有 N−1 条边，总电压降也只有 N−1，因此所有边只能 g=1。这是 exactness 的细节核心：没有 g≤1 或没有电压尺度校准，fractional conductance 可能存活。
我认为实质贡献在于这个三元闭环：电势排环、局部 penalty 排分叉并强制覆盖、conductance bound + voltage calibration 排 fractional 解。objective 的具体权重 α1,α2 只要为正即可，基本是辅助；使用 squared positive part 主要是 smoothness engineering，不是理论核心。
这不是 scaling、data coverage、retrieval 或 test-time compute 的故事；它是一个 better inductive bias / latent structure formulation：把离散路径结构嵌入到电势-电流几何里。但这种 inductive bias 只保证零集正确，不保证优化路径好走。所谓 continuous formulation 不应被误读为 relaxation 更易解；很可能只是把 NP-hardness 转移到 nonconvex landscape 的全局优化难度中。
Relation To Prior Work
最接近的谱系有三条：flow-based integer programming、QUBO/Ising penalty encoding、以及 Hopfield/Tank 式物理启发连续能量。本文和 flow formulation 的共同点是用源汇流表达路径；不同点是这里的流不是自由变量，而是 conductance 经 Laplacian Dirichlet problem 诱导出来的 Ohmic current，因此自带 potential ordering。
相对 QUBO/Ising，本文不是把 Hamiltonian constraints 翻译成二进制 penalty，而是允许连续 conductance，并通过物理方程让方向、流量和可达性成为隐变量。看似仍是 penalty method，但真正新增信息来自电网络解算器：每次评估目标都隐式解一个全局耦合的 Laplacian system。
相对 Hopfield/Tank，本文最大的不同是 exactness theorem。Hopfield 类方法通常把组合结构软编码到能量中，更多依赖经验收敛；这里明确证明 global minimizer 的零集等于 Hamiltonian path 集合。不过这也意味着贡献边界很清楚：它不是一个新启发式优化器，而是一个可证明的 continuous exact encoding。
有些“新”其实是已有思想重组：单位流、无分叉、端点源汇、penalty 都不新；实质创新是将它们放进 Ohmic conductance model，让电势单调性承担 subtour elimination 的角色，并用电压尺度把 fractional conductance 压回 binary。
Dataset / Evaluation
论文没有实质性实验 benchmark 支撑算法性能；讨论区只提到 straightforward projected gradient descent 在中等规模图上常失败。因而 evaluation 不能被理解为验证了 scalable solver claim，事实上作者也没有提出这种 claim。
这篇的 claim 主要是数学刻画，所以证明本身就是主要 evidence。若按优化论文标准看，缺少对 landscape 的系统实验：不同图族上的 local minima 数量、basin size、初始化敏感性、梯度法失败模式、与 QUBO/ILP relaxation 的比较都没有充分展开。
因此它验证的是“全局最优集合正确”，没有验证“连续表述更容易被找到”。benchmark 对核心理论 claim 足够，但对任何实用求解含义都不够。
Limitation
最大限制是定理前提强：给定端点必须存在 Hamiltonian path。若不存在，目标最小值如何解释、是否有 gap、是否能用于判定，文中未充分说明。对于一般 HPP，端点未知时仍需枚举或使用外部策略；这部分没有被 formulation 本身消化。
第二，非凸性是本质问题，不是实现细节。目标依赖电势，而电势由 conductance-dependent Laplacian system 隐式定义；conductance 为零导致 conducting component 改变时，函数结构还会出现分段行为。虽然文中提到 squared positive part 改善电流过零处的可微性，但整体 landscape 的可优化性没有保证。
第三，continuous relaxation 的优势不清。它排除了 global minimizer 的 fractional 伪解，但并不说明 fractional stationary points 或低 penalty fractional valleys 不存在。实际优化很可能被大量非解吸引，尤其在稠密图中 parallel conductance 会产生复杂分流。
第四，augmentation 与固定电压差是为证明量身定制的 construction。它优雅但也脆弱：若希望扩展到 Hamiltonian cycle、k-path cover、weighted variants 或 directed graphs，需要重新检查电压尺度、端点条件和 branch penalty 是否仍能保持 exactness。
第五，所谓“连续化”没有降低复杂性；它只是把组合可行性问题转移为寻找非凸连续目标的全局零点。任何把该方法宣传为高效算法的解读都是不成立的。
Takeaway
- 1. 最值得迁移的 insight 是用 scalar potential 的单调性替代显式 subtour elimination；这可能对其他路径 / arborescence / ordering 类组合问题有价值。
- 2. Exact continuous formulation 的关键不在“变量连续”，而在“连续物理隐变量携带全局结构”。
- 这里 Laplacian solve 充当了一个全局 consistency layer。
- 3. 对 HPP 本身，这篇更像一个理论 encoding，而不是 solver。
一句话总结
这篇论文在 HPP 方向中的位置是一个用 Ohmic conductance、电势单调性和局部电流 penalty 构造的 exact continuous encoding，真正贡献是证明全局零解恰为 Hamiltonian path，但它没有缓解寻找全局最优的计算难度。