用拓扑差异指导旅行商问题优化，提升搜索效率。
Edge-wise Topological Divergence Gaps: Guiding Search in Combinatorial Optimization
- 通过边级拓扑差异分解，量化路径与最小生成树的差距。
- 在TSPLIB和随机实例上，优化速度更快、结果更优。
- 适合需要高效求解组合优化问题的研究者。
我们针对旅行商问题（TSP）提出一种拓扑反馈机制，通过分析巡回路径与最小生成树（MST）之间的差异来引导优化。核心贡献是一个规范分解定理，将巡回路径与MST的差距表示为来自RTD-Lite条形码的边级拓扑发散间隙。基于此，我们设计了面向2-opt和3-opt启发式算法的拓扑引导策略，显著提升了其性能。实验在基于热图法获得的路径、TSPLIB实例以及随机实例上进行，结果表明拓扑引导优化在多数情况下实现更优性能与更快收敛。
原文摘要 · Abstract (English)
We introduce a topological feedback mechanism for the Travelling Salesman Problem (TSP) by analyzing the divergence between a tour and the minimum spanning tree (MST). Our key contribution is a canonical decomposition theorem that expresses the tour-MST gap as edge-wise topology-divergence gaps from the RTD-Lite barcode. Based on this, we develop a topological guidance for 2-opt and 3-opt heuristics that increases their performance. We carry out experiments with fine-optimization of tours obtained from heatmap-based methods, TSPLIB, and random instances. Experiments demonstrate the topology-guided optimization results in better performance and faster convergence in many cases.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。