旅行商问题(TSP)
旅行商问题(TSP) 也称旅行售货员问题
设 $c_1,c_2,\ldots,c_n$ 是 $n$ 个不同的城市. 有个售货员居住在某个城市 $c_{i_0}$, 他从 $c_1$ 出发到其他城市 $c_2,\ldots,c_n$ 去推销商品(货物), 最后要回到城市 $c_{i_0}$.
假定任意两个城市间的距离是已知的, $d_{ij}:=d(c_i,c_j)$.
问他应沿着怎样的路线走, 才能使得所走的路线最短?
References:
赵静、但琦主编《数学建模与数学实验》(第四版)P.106--107
宋增民 主编 《图论及其应用》1.1.3