巡回售货员问题
【巡回售货员问题】
有一位巡回售货员,他必须访问n个城市,分别记作v_1,v_2,v_3,…,v_n,售货员从他所居住的城市v_1出发,想找一条旅行路径,访问所有的其他城市最后回到家的顺序。目标是整个旅行路径的距离尽可能的小。
对于每一对城市(v_i,v_j),城市的距离为d(v_i,v_j)。并且,距离不是对称的,即d(v_i,v_j) \neq d(v_j,v_i)。也不要求距离之间满足三角不等式。因此巡回售货员问题的目标是使得总距离\sum_{j=1}^{n-1}d(v_{i_j},v_{i_{j+1}})+d(v_{i_n},v_{i_1})最小。
巡回售货员问题的判定形式为:给定n个城市之间的距离的集合以及界限D,问有长度不超过D的路线吗?

0
Posted in 算法设计与分析

Leave a Comment:

电子邮件地址不会被公开。