标签：#旅行推销员问题

旅行推销员问题

旅行商问题（，縮寫：TSP）是组合优化中的一个NP困难问题，在运筹学和理论计算机科学中非常重要。问题内容为“给定一系列城市和每對城市之间的距离，求解访-{}-问每座城市一次并回到起始城市的最短回路。” TSP是与车辆路径问题的一种特殊情况。 作为计算复杂性理论中一个典型的判定性问题，TSP的一个版本是给定一个图和长度 L，要求回答图中是否存在比 L 短的回路（英语：circuit或tour）。该问题被划分为NP完全问题。已知TSP算法最…