游戏tsp是什么意思

⑴ TSP是什么意思啊

TSP即旅行商问题，即TSP问题（Traveling Salesman Problem）又译为旅行推轮察销员问题、货郎担问题，是数学领域租猛中着名问题之一。

假设有一个旅行商人要拜访n个城市，他必腊型茄须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市，路径的选择目标是要求得的路径路程为所有路径之中的最小值。

TSP问题是一个组合优化问题。该问题可以被证明具有NPC计算复杂性。因此，任何能使该问题的求解得以简化的方法，都将受到高度的评价和关注。

(1)游戏tsp是什么意思扩展阅读：

描述

TSP问题作为图论问题可以用无向加权图来对TSP建模，则城市是图的顶点，道路是图的边，道路的距离就是该边的长度。它是起点和终点都在一个特定顶点，访问每个顶点恰好一次的最小化问题。通常，该模型是一个完全图（即每对顶点由一条边连接）。

如果两个城市之间不存在路径，则增加一条非常长的边就可以完成图，而不影响计算最优回路。

TSP问题非对称和对称，在对称TSP问题中，两座城市之间来回的距离是相等的，形成一个无向图。这种对称性将解的数量减少了一半。