旅行售货员问题(travelling salesman problem)是一类组合最优化问题，设有一个售货员从城市1出发，到城市2，3，，n去推销货物，最后回到城市1.假定任意两个城市i，j间的距离dij(dij=dji)是已知的，问他应沿着什么样的路线走，才能使走过的路线最短?容易看出，中国邮递员问题要求走遍所有“线”，而后者要求走遍所有“点”，旅行售货员问题就是在一个完全网络中，找出一个具有最小权的哈密顿圈，寻求旅行售货员问题的有效算法似乎是没有希望的，它属于NP完全类，一个可行的办法是首先求一个哈密顿圈，然后适当修改，以得到具较小权的另一个哈密顿圈，旅行售货员问题有着明显的实际意义，除售货员之外，邮局里负责到各个信箱取信的邮递员，以及去各个分局送邮件的汽车等都会类似地遇到这个问题，还有一些问题表面上似乎与之无关，而实质上却可以归结为旅行售货员问题求解，如计算机线路问题、无中间存储的工件加工问题等。