技术摘要：旅行商问题的多项式时间解析松弛法

问题陈述

旅行商问题（TSP）被认为是典型的 NP-hard 组合优化挑战。传统的精确解法，如整数线性规划（ILP）和 Held-Karp 动态规划算法，需要评估加权图的哈密顿回路空间。这些方法受限于阶乘级 $O(N!)$ 或指数级 $O(N^2 2^N)$ 的计算复杂度，使得处理规模大于约 $N \le 25$ 的实际应用问题变得不切实际。

方法论

本文提出了一种全新的连续解析框架，将离散排列空间映射到连续概率流张量流形上。该方法并非遍历离散搜索树，而是将优化任务重新表述为一个代数张量传播问题。该方法受三个核心公理支配：

1. 连续流形嵌入： 将离散排列嵌入到连续概率流张量空间 $P \in \mathbb{R}^{N \times N}$ 中。转移可能性由逆成本幂律定义，其中概率 $P_{ij}$ 与边权重梯度的倒数成正比，并受缩放参数 $\alpha$ 控制。
2. 依赖历史的累积与超越归一化： 为了在不使用指数级子集掩码的情况下强制执行哈密顿约束，路径概率被动态加权。本文引入了三种解析公式：
   • 方法 1（标准概率流）： 根据概率与边成本的比率对转移进行评分。
   • 方法 2（$\pi$-指数启发式）： 使用 $\pi$ 对概率值进行超越缩放。
   • 方法 3（超越性 HK 松弛）： 利用预计算的静态数组因子 $\gamma(N) = \pi^{(N^2 / 2^N)}$。
3. 谱级数截断： 使用矩阵指数生成函数 $e^{tW}$ 的截断麦克劳林级数展开来近似不可计算的循环覆盖永久值（permanent）。这通过将系数提取减少到多项式矩阵乘法界限内，具体为 $O(N)$。

生成的算法包含三个阶段：张量初始化、转移张量构建和序列状态传播。它执行 $N$ 步以评估未访问节点，选择最小的“成本-概率”得分，从而实现严格的确定性执行时间 $O(N^3)$。

核心贡献

• 算法转向： 通过利用随机矩阵、超越缩放因子和截断麦克劳林级数，提供了一种绕过指数级子集枚举的确定性算法。
• 复杂度降低： 将 TSP 路径生成的理论复杂度从指数时间降低到严格的 $O(N^3)$ 多项式时间。
• 实现： 提供了 Python (NumPy) 和 Java 的代码实现，证明了张量传播方法的可行性。
• 可扩展性： 展示了该方法在企业级图拓扑结构上的稳定扩展性，即使随着 $N$ 的增加，执行时间仍保持在较低水平。

结果

本文展示了针对问题规模 $N = 1$ 到 $100$ 的全面基准测试结果，并将提出的解析方法与精确的 Held-Karp 基准进行了对比。

• 执行时间： 提出的 $O(N^3)$ 方法比 Held-Karp 展示出显著更快的执行速度。对于 $N=20$，提出的方法耗时 0.205 ms，而 Held-Karp 需要 870,000 ms。对于 $N=100$，提出的方法在 15.80 ms 内完成，而 Held-Karp 被标注为需要“静态数组”查找（暗示指数级方法已不可行）。
• 解质量： 据报告，生成的路径成本与已知的最优基准高度一致。
  • 方法 1 和 方法 3： 在所有测试实例（$N=1$ 到 $100$）中，这些方法产生的成本与精确的 Held-Karp 基准完全一致。
  • 方法 2： 该方法表现出轻微偏差（例如，在 $N=6$ 时，成本为 399.10，而精确值为 398.50），但仍接近最优基准。
• 大规模扩展： 本文包含了对高达 $N=10,000$ 的超大规模图的预测。据估计，对于 $N=10,000$，该算法将需要大约 $1.00 \times 10^{12}$ 次浮点运算（FLOPs）、800 MB 内存，以及约 15.80 分钟的执行时间。

意义与主张

本文声称，通过利用连续代数张量、超越缩放和多项式级数近似来重构组合优化，可以确定性地执行多项式时间内完成的 TSP 路径生成。作者断言，该框架允许在保持与最优解经验一致性的同时，绕过指数级的子集枚举。

这项工作的意义在于，它为解决当前 TSP 求解器的可扩展性限制提供了潜在方案，使得处理此前仅限于小规模实例的企业级图拓扑成为可能。论文最后指出，未来的工作将探索通过 GPU 张量核心进行硬件加速，以进一步优化大规模稀疏图实例（$N > 10,000$）的性能。