递归分支剪枝与启发式上界初始化对精确旅行商问题搜索的影响分析

《Algorithms》：Analyzing the Effect of Recursive Branch Pruning and Heuristic Upper-Bound Initialization in Exact Travelling Salesman Problem Search

　　

本研究针对旅行商问题（Travelling Salesman Problem, TSP）（即在一个完全加权无向图中寻找最小哈密顿环（Hamiltonian Cycle）的问题）展开了研究。研究人员提出并分析了两种递归算法。第一种算法记为递归哈密顿环算法（RecursiveHamiltonianCycle, RHC），它对解空间执行穷举递归搜索；第二种算法记为剪枝哈密顿环搜索算法（PrunedHamiltonianCycleSearch, PHCS），它采用早期分支剪枝机制来消除非有希望的部分解。本研究的主要目标是评估递归分支剪枝和初始上界选择对精确TSP搜索过程计算效率的影响。研究人员利用包含12至21个顶点的完全图进行了一系列计算实验。所得结果表明，两种算法总能产生相同的最优哈密顿环。然而，PHCS算法所需的递归调用次数和执行时间显著更少。进一步的实验证明，初始上界的质量对剪枝效率有实质性影响。因此，研究人员采用最近邻启发式（nearest-neighbor heuristic）来生成高质量的初始解，从而进一步缩小了搜索空间。这些结果证实，将启发式初始化与精确分支剪枝搜索相结合，能够在保持解最优性的同时，显著提升精确TSP算法的实际适用性。

一、研究背景、现存问题与研究动机

旅行商问题（Travelling Salesman Problem, TSP）是最著名的组合优化问题之一，其目标是在完全加权无向图中找到一条总权重最小的哈密顿环（Hamiltonian Cycle）。TSP属于NP难问题，其解空间随顶点数n呈阶乘级增长（(n-1)!种候选路径），这使得精确求解在规模稍大的实例上变得极其困难。现有精确算法如动态规划、分支定界和分支切割等方法虽然能保证最优性，但计算成本极高，通常仅适用于有限规模的输入。尽管已有大量关于递归与迭代方法选择的讨论，但在复杂组合优化问题中，如何有效平衡算法效率与最优性仍是重要科学问题。为此，本研究旨在分析递归分支剪枝与启发式上界初始化对精确TSP搜索效率的影响，探索在不牺牲最优性的前提下提高算法实用性的途径。

二、研究内容、结论与意义

研究人员设计并实现了两种精确递归算法：递归哈密顿环算法（RecursiveHamiltonianCycle, RHC）执行穷举递归搜索，而剪枝哈密顿环搜索算法（PrunedHamiltonianCycleSearch, PHCS）引入早期剪枝机制，当部分构造路径长度超过当前最优解时终止该分支的扩展。通过对包含12至21个顶点的完全图进行实验，发现两种算法总能得到完全相同的最优解，但PHCS的递归调用次数和执行时间显著减少。进一步实验表明，初始上界质量对剪枝效果至关重要，因此研究人员采用最近邻（Nearest-Neighbor, NN）启发式生成高质量初始解作为上界，使剪枝效率进一步提升。该研究的重要意义在于验证了结合启发式初始化与精确分支剪枝可大幅拓展精确TSP算法的实际应用范围，同时保持解的最优性。

三、关键技术方法概述

为开展研究，研究人员使用了以下几个关键技术方法：

1. 1.
   递归深度优先搜索与回溯（Depth-First Search with Backtracking）：用于生成所有有效的哈密顿环，固定起始顶点以避免循环旋转导致的冗余表示，将搜索空间从n!降至(n-1)!。
2. 2.
   早期分支剪枝机制：在PHCS算法中，每当部分构造路径的累计长度大于等于当前最优解长度时，立即终止该分支的递归扩展，前提是所有边权非负。
3. 3.
   最近邻启发式初始化（Nearest-Neighbor Heuristic）：在执行精确搜索前，从每个顶点出发运行一次最近邻算法，选取其中最短的哈密顿环作为精确搜索的初始上界，以加速剪枝。
4. 4.
   全局数据结构与动态数组：包括存储当前路径、最优路径、访问标记和图的权重矩阵等，支持递归过程中的状态记录与更新。

四、研究结果

4.1 RHC与PHCS的性能比较

对于图G₁₂至G₁₆，两种算法均得到相同的最优哈密顿环及其长度，验证了剪枝策略的正确性。在G₁₆上，RHC需要超过7天的执行时间，而PHCS仅需约17秒。随着图规模增大，两种算法的递归调用次数差距呈数量级扩大，PHCS的剪枝效率显著提升。

4.2 初始上界的影响

针对图G₁₇的实验显示，当初始上界设为极大值（MaxInt）时，PHCS需大量递归调用才能收敛；而改用高质量初始解后，递归调用次数减少了约3.8倍，执行时间缩短了约3.6倍，表明初始上界质量直接影响剪枝效率。

4.3 最近邻启发式初始化后的精确搜索

对图G₁₈至G₂₁，首先执行最近邻启发式生成初始解，再运行PHCS。结果显示，最近邻解非常接近最优解：G₁₈的最近邻解直接等于最优解，G₁₉至G₂₁的差异也较小。尽管采用了优化，执行时间仍从G₁₈的约4分钟增长至G₂₁的超过76小时，反映了阶乘增长的固有限制。

五、讨论与结论

讨论部分指出，所有提出的优化技术均显著提升了精确TSP求解器的实际性能。PHCS的剪枝机制在保持最优性的前提下大幅减少了递归调用次数，且剪枝效果随图规模增大而增强。初始上界质量对剪枝效果有直接影响，较紧的上界能在搜索早期消除更多非有希望分支。最近邻启发式被证明是构建高质量初始上界的有效方法，其生成的解要么直接达到最优，要么非常接近最优，使得精确搜索只需少量改进即可达到全局最优。尽管如此，解空间的阶乘增长仍然是主导限制因素，精确算法在处理中等规模以上实例时仍面临巨大计算挑战。

研究结论翻译：旅行商问题是评估精确与近似优化技术的常用基准问题。本研究比较了两种精确递归算法——RHC（穷举搜索）和PHCS（带早期剪枝的搜索）。对G₁₂至G₁₆的实验表明，两者产生相同最优解，验证了剪枝策略的正确性。剪枝机制显著减少了递归调用次数和执行时间，性能提升随图规模增大可达数个数量级。此外，提供高质量初始解能显著提高搜索效率，基于此引入的最近邻启发式初始化使剪枝更加有效。尽管所有优化手段均已应用，解空间的阶乘增长仍是主要限制因素，精确方法即便采用先进剪枝策略，计算需求依然很高。