1 第7 章 旅行商问题2 第7章 旅行商问题 1.问题概述 2.求解算法 2.1.下界和上界算法 2.2.分支定界法 目录 2.5.竞赛题 2.3.动态规划法 2.5.近似算法3 7-1 问题概述 一、数学模型 1. 标准TSP 旅行商问题（简称TSP ），也称货郎担问题或 旅行推销员问题，是运筹学中一个著名的问题，其 一般提法为：有一个旅行商从城市1出发，需要到城 市2、3、n 去推销货物，最后返回城市1，若任 意两个城市间的距离已知，则该旅行商应如何选择 其最佳行走路线？4 TSP 在图论意义下又常常被称为最小Hamilton 圈问题， Euler 等人最早研究了该问题的雏形，后来由英国的 Hamilton 爵士作为一个悬赏问题而提出。但这个能让普通人 在几分钟内就可理解的游戏之作，却延续至今仍未能完全解 决，成了一个世界难题。 TSP 有着明显的实际意义，如，邮局里负责到各信箱开 箱取信的邮递员，以及去各分局送邮件的汽车等，都会遇到 类似的问题。有趣的是，还有一些问题表面上看似乎与TSP 无关，而实质上却可以归结为TSP 来求解。已经证明，TSP 是个NP 难题，除非P = N
