问题

计算数学 >> 离散数学 >> 图论
Questions in category: 图论 (Graph Theory).

旅行商问题(TSP)

Posted by haifeng on 2018-05-10 18:40:13 last update 2018-05-10 18:40:59 | Answers (0) | 收藏


旅行商问题(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