释
旅行商问题
lǚ xíng shāng wèn tí · ㄌㄩˇ ㄒㄧㄥˊ ㄕㄤ ㄨㄣˋ ㄊㄧˊ
修撰于 2026-06-30 13:21:46
音义
| 拼音 | lǚ xíng shāng wèn tí |
|---|---|
| 字母 | lv xing shang wen ti |
| 首字母 | lxswt |
| 注音 | ㄌㄩˇ ㄒㄧㄥˊ ㄕㄤ ㄨㄣˋ ㄊㄧˊ |
| 注音符号 | ㄌㄩ ㄒㄧㄥ ㄕㄤ ㄨㄣ ㄊㄧ |
广训
旅行推销员问题（英语：Travelling salesman problem, TSP）是这样一个问题：给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的最短回路。它是组合优化中的一个NP难问题，在运筹学和理论计算机科学中非常重要。最早的旅行商问题的数学规划是由Dantzig（1959）等人提出，并且是在最优化领域中进行了深入研究。许多优化方法都用它作为一个测试基准。尽管问题在计算上很困难，但已经有了大量的启发式算法和精确方法来求解数量上万的实例，并且能将误差控制在1%内。