TSP问题的数值模拟

概述

   旅行商问题（Traveling SalesPerson Program, TSP）是一个经典的组合优化问题。给定一个城市列表以及各相邻城市间的旅行代价值（例如物理距离），一个商人从出发城市开始，需要访问并且只访问一次其他所有城市后返回出发地，并要求旅行代价值最小。
   从图论的角度上分析，TSP 问题是 NP 完全问题。实际上，从工程实践的角度上看，它意味着在任何情况下，没有已知算法可以比穷举法更好地解决该问题。但是对于穷举法，随着顶点数的增加，会产生组合爆炸问题。
  虽然如此，目前仍然存在许多近似算法和启发式算法可以使用，例如遗传算法、模拟退火法、蚁群算法、禁忌搜索算法、贪婪算法和神经网络等。

参考 《Introduction to ParallelProgramming》 by Peter Pacheco.

树搜索方法

graph LR
emperor((0)) -- 1 --> emperor1((1))
emperor1((1)) -- 5 --> emperor((0))
emperor((0)) -- 3 --> emperor2((2))
emperor2((2)) -- 1 --> emperor((0))
emperor((0)) -- 8 --> emperor3((3))
emperor3((3)) -- 7 --> emperor((0))
emperor1((1)) -- 2 --> emperor2((2))
emperor2((2)) -- 18 --> emperor1((1))
emperor1((1)) -- 6 --> emperor3((3))
emperor3((3)) -- 4 --> emperor1((1))