Question

求一道tsp问题的解答过程，从一个点遍历五个点回到原点的最短距离（ps表中给的数据是每两个点之间到

求一道tsp问题的解答过程，从一个点遍历五个点回到原点的最短距离（ps表中给的数据是每两个点之间到达时间，不是对称的）

Answer 1

旅行路程：1→2→4→5→3→6→1 ,共用去时间1+1+1+1+2+3=9（单位时间）。

Answer 2

设时间的单位为小时，然后见以下分析：
首先，从城市 1~5 到城市 6 都需要 3 小时，从城市 6 到城市 1~5 都需要 2 小时；
所以，不管行程如何安排，城市 6 的出入时间必定为 3+2=5 小时，这 5 小时是固定的，不能做调整，所以暂且排除城市 6；
然后，城市 1~5 之间要有 4 次城市转换，所以最少要用 4 小时（ 从图表可知，每次城市转换最少要用 1 小时 ）；
也就是说，时间最少的可能是 5+4 = 9 小时，所以我们要尽量规划出一条用 9 小时的路线；
于是，考虑以下路线：
1 → 3 → 5 → 4 → 2 → 6 → 1
这条路线只用 9 小时，所以花费时间最少；
.
事实上，一共有 5 条路线都只用 9 小时 (花费时间最少)，
先考虑路线：
1 → 3 → 5 → 4 → 2 → 1
这个路线花费时间 5 小时，然后因为 6 的出入时间恒为 5 小时，所以把城市 6 插入到以上任意两个城市之间，总时间都是 5+5-1 = 9 小时；又因为总共有 5 个位置可以插入城市 6，所以总共有 5 条路线花费 9 小时，即花费时间最少.
－－－－－－－－－
( 有问题欢迎追问 @_@ )