大规模随机点位场景下遍历全点最短路径求解最优方法咨询

该场景本质是带终点约束的旅行商问题（TSP），属于NP难问题，点位规模极大的情况下，暴力枚举、动态规划等精确解法完全不适用，需结合精度、性能要求选择适配方案：

• 若点位规模在1000以内，且要求100%精准的最优解：可将固定终点设为强制收尾节点，调用Concorde这类专业TSP精确求解器，添加约束后求解即可得到全局最优结果。
• 若点位规模超过1000，属于超大规模场景，优先选择近似求解方案：
  • 首选蚁群优化算法（ACO）：天生适配路径寻优场景，仅需在算法终止规则中增加终点必须为指定点位的约束即可，收敛速度快，大规模点位下的路径优化效果稳定，解的精度高。
  • 次选遗传算法（GA）：编码时固定最后一个基因位为指定终点，交叉、变异操作时保留该位不变即可，实现难度低，可在可接受时间内得到接近最优的可行解。
  • 若对求解速度要求极高，适配万级及以上点位的场景：可选用贪心+2-opt局部优化的组合方案，先从起点出发每次访问最近的未访问点位，最终落到固定终点，再用2-opt算法反复调整路径交叉段缩减总长度，实现最简单、运行速度最快。

注意：不存在适配所有场景的绝对最优方案，可根据你能接受的解误差、可用计算时间、算力资源从上述方案中选择最适配的即可。

内容的提问来源于stack exchange，提问作者Newyen minh