上传者: 38661466
|
上传时间: 2022-05-04 14:36:58
|
文件大小: 68KB
|
文件类型: PDF
巡回售货员问题
【巡回售货员问题】
有一位巡回售货员,他必须访问n个城市,分别记作v1,v2,v3,…,vnv_1,v_2,v_3,…,v_nv1,v2,v3,…,vn,售货员从他所居住的城市v1v_1v1出发,想找一条旅行路径,访问所有的其他城市最后回到家的顺序。目标是整个旅行路径的距离尽可能的小。
对于每一对城市(vi,vjv_i,v_jvi,vj),城市的距离为d(vi,vj)d(v_i,v_j)d(vi,vj)。并且,距离不是对称的,即d(vi,vj)≠d(vj,vi)d(v_i,v_j) \neq d(v_j,v_i)d(vi,vj)=d(vj,vi)。