海之美文新闻资讯TSM(旅行商问题(Travelling SalesMan problem))
TSM，即Traveling SalesMan problem，也就是旅行商问题，又译为旅行推销员问题、货郎担问题，简称为TSP问题，也简称为TSM问题，是最基本的路线规划问题，也是一个经典的NP-Hard问题。该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。最早的旅行商问题的数学规划是由Dantzig（1959）等人提出。
基本介绍
- 中文名：旅行商问题、货郎担问题
- 外文名：TSM、TSP
TSM，即Traveling SaleMan problem，也就是旅行商问题，又译为旅行推销员问题、货郎担问题，简称为TSP问题，也简称为TSM问题，是最基本的路线规划问题，也是一个经典的NP-Hard问题。该问题是在寻求单一旅行者由起点出发，通过所有给定的需求点之后，最后再回到原点的最小路径成本。最早的旅行商问题的数学规划是由Dantzig（1959）等人提出。
最明显的算法就是穷举法，即寻找一切组合併取其最短。这种算法的排列数为n!(其中n为节点个数)。用动态规划技术，我们可以在O(n^2·2^n)的时间内解决此问题。虽然这仍然是指数级的，但要比快得多。
它也有诸多的近似解法，例如最基本的模拟退火算法、贪心方法、遗传算法、蚁群算法等等。