2025-11-24T18:19:18.135266

The frequency $K_i$s for symmetrical traveling salesman problem

Wang

The frequency $K_i$s ($i\in[4,n]$) are studied for symmetrical traveling salesman problem ($TSP$) to identify the edges in optimal Hamiltonian cycle ($OHC$). A frequency $K_i$ is computed with a sort of ${{i}\choose{2}}$ optimal $i$-vertex paths with given endpoints (optimal $i$-vertex path) in a corresponding $K_i$ in $K_n$. In frequency $K_i$, the frequency of an edge is the number of the optimal $i$-vertex paths containing the edge in the corresponding $K_i$. Given an $OHC$ edge related to $K_i$, it has a frequency bigger than $\frac{1}{2}{{i}\choose{2}}$ in the corresponding frequency $K_i$, and that of an ordinary edge not in $OHC$ is smaller than $\frac{1}{2}{{i}\choose{2}}$. On average, an $OHC$ edge in $K_i$ has the expected frequency bigger than $\frac{i^2-4i+7}{2}$ whereas an ordinary edge has the expected frequency smaller than 2. Moreover, given a frequency $K_i$ containing an $OHC$ edge related to $K_n$, the frequency of the $OHC$ edge is bigger than $\frac{1}{2}{{i}\choose{2}}$ in the worst average case. It implies that the average frequency of an $OHC$ edge computed with frequency $K_i$s is bigger than $\frac{1}{2}{{i}\choose{2}}$. It also found that the probability that an $OHC$ edge is contained in optimal $i$-vertex paths keeps stable or increases according to $i\in [4, n]$. As the frequency $K_i$s are used to compute the frequency of an edge, each $OHC$ edge has its own peak frequency at $i=P_0$ where $P_0=\frac{n}{2} + 2$ for even $n$ or $\frac{n+1}{2} + 1$ for odd $n$. For ordinary edges out of $OHC$, the probability that they are contained in optimal $i$-vertex paths decreases according to $i$. Moreover, the average frequency of an ordinary edge will be smaller than $\frac{1}{2}{{i}\choose{2}}$ if $i \geq [0.3660n + 5.5849]$. Based on these findings, an algorithm is presented to find $OHC$ in $O(n^62^{0.3660n})$ time using dynamic programming.

academic

The frequency $K_i$ s for symmetrical traveling salesman problem

基本信息

论文ID: 2504.19608
标题: The frequency $K_i$ s for symmetrical traveling salesman problem
作者: Yong Wang (North China Electric Power University)
分类: cs.DM math.CO math.OC
发表时间: 2025年10月15日 (arXiv v3)
论文链接: https://arxiv.org/abs/2504.19608v3

摘要

本文研究对称旅行商问题(TSP)中的频率 $K_i$ s ( $i\in[4,n]$ )以识别最优哈密顿回路(OHC)中的边。频率 $K_i$ 通过 $K_n$ 中对应 $K_i$ 内的 $\binom{i}{2}$ 个给定端点的最优 $i$ 顶点路径计算得出。在频率 $K_i$ 中，边的频率是包含该边的最优 $i$ 顶点路径的数量。研究发现：OHC边在对应频率 $K_i$ 中的频率大于 $\frac{1}{2}\binom{i}{2}$ ，而普通边小于此值；OHC边的期望频率大于 $\frac{i^2-4i+7}{2}$ ，普通边小于2；当 $i \geq [0.3660n + 5.5849]$ 时，普通边的平均频率小于 $\frac{1}{2}\binom{i}{2}$ 。基于这些发现，提出了 $O(n^62^{0.3660n})$ 时间复杂度的动态规划算法。

精确算法时间复杂度高：如Bellman和Held-Karp的动态规划算法需要 $O(n^22^n)$ 时间
启发式方法缺乏理论保证：虽然LKH等启发式算法在实践中表现良好，但缺乏理论基础
边的结构特性难以识别：OHC边在距离上没有显著特征，难以与普通边区分

研究动机

现有研究表明，基于频率 $K_4$ s可以有效识别OHC边，但缺乏对更一般情况频率 $K_i$ s ( $i > 4$ )的系统研究。本文旨在：

建立OHC边和普通边在频率 $K_i$ s上的理论界限
分析边的频率和概率随 $i$ 的变化规律
基于频率特性设计高效的OHC识别算法

核心贡献

建立了频率下界理论：证明了OHC边在频率 $K_i$ 中的频率大于 $\frac{1}{2}\binom{i}{2}$ ，普通边小于此值
分析了频率变化规律：揭示了OHC边频率随 $i$ 增加而增加或保持稳定，普通边频率单调递减
确定了临界点：证明当 $i \geq [0.3660n + 5.5849]$ 时，可完全区分OHC边和普通边
提出了高效算法：基于频率特性的 $O(n^62^{0.3660n})$ 时间算法
提供了概率递减条件：给出了识别普通边的概率递减判据 $p_{i+1}(g) < [1-\frac{2}{i(i-1)}]p_i(g)$

当 $i=4$ 时，通过枚举所有可能的频率 $K_4$ 验证
对于 $i>4$ ，使用归纳法，证明从 $K_i$ 扩展到 $K_{i+1}$ 时OHC边频率的单调性

计算频率 $K_i$ ：对选定的 $i$ 值，计算所有 $K_i$ 的频率
边分类：根据频率阈值 $\frac{1}{2}\binom{i}{2}$ 分类边
概率递减检测：使用条件 $p_{i+1}(g) < [1-\frac{2}{i(i-1)}]p_i(g)$ 识别普通边

时间复杂度分析

计算单个 $K_i$ 的OP^i需要 $O(i^42^i)$ 时间
对于 $i = [0.3660n + 5.5849]$ ，总时间复杂度为 $O(n^62^{0.3660n})$

实验设置

数据集

小规模TSP实例： $n \in [4,14]$ 的构造实例和Oliver30的子图
真实TSP实例：TSPLIB中的48个实例，包括：
- Euclidean TSP：att48, eil51, pr76等
- ATT TSP：att532等
- GEO TSP：多个地理距离实例
- Matrix TSP：si535, si1032等

评价指标

频率准确性：OHC边和普通边的频率分布
分离效果：使用频率阈值能正确分类的边的比例
算法效率：计算时间和空间复杂度

实现细节

使用动态规划计算OP^i
对于大规模实例，随机采样1000个 $K_i$ 计算平均频率
C++实现，在2.3GHz CPU、4GB内存的笔记本上运行

OHC边频率：最小频率始终大于 $\frac{7}{18}\binom{i}{2}$ ，多数情况大于 $\frac{1}{2}\binom{i}{2}$
普通边频率：最大频率小于 $\frac{1}{2}\binom{i}{2}$ ，平均频率接近2
频率比：OHC边与普通边的平均频率比从4（ $n=4$ ）增长到37.3（ $n=14$ ）