[已解决]python小练习（057）：回溯法求解最优路径问题

jerryxjr1220

已知：
0，1，2，3，4五个点到其他各点的路径权重，用字典形式表示。

求：
从起点2到终点4的最优路径（权重总和最小）。

1. weight={0:{1:2,2:4,3:6,4:8},
   
2.         1:{0:1,2:3,3:1,4:4},
   
3.         2:{0:2,1:5,3:4,4:9},
   
4.         3:{0:5,1:2,2:6,4:6},
   
5.         4:{0:7,1:9,2:4,3:7}}

复制代码

除了利用排列组合，还有什么更好的解题思路么？

貌似用回溯+递归应该也能解，但是想不到好的递归结束的条件，容易进入无限循环。

优化后的解法见3楼

最佳答案

月排行榜 / 总排行榜

jerryxjr1220

2017-1-4 22:26:51

我自己找到优化的方法了，还是借用字典，把所以走过的路径都记录下来，然后依次比较，有比记录更短的路径就添加进去，依次类推，不断循环，直到最后最优值不变了即为最优解。

1. #coding:utf-8
   
2. '''题目要求：起点（0），终点（9），找出权重最小的路径即为最优路径'''
   
3. 
   
4. weight={0:{1:3,2:5,3:6,4:8,5:4,6:9,7:8,8:9,9:16,10:3,11:2},
   
5.         1:{0:2,2:3,3:3,4:4,5:3,6:7,7:2,8:8,9:12,10:4,11:5},
   
6.         2:{0:2,1:5,3:4,4:9,5:3,6:6,7:2,8:5,9:10,10:3,11:3},
   
7.         3:{0:5,1:2,2:6,4:6,5:5,6:3,7:6,8:7,9:10,10:4,11:4},
   
8.         4:{0:7,1:9,2:2,3:7,5:3,6:8,7:3,8:2,9:10,10:5,11:4},
   
9.         5:{0:4,1:3,2:3,3:2,4:2,6:8,7:4,8:5,9:11,10:4,11:5},
   
10.         6:{0:2,1:2,2:3,3:3,4:4,5:5,7:6,8:5,9:6,10:4,11:5},
    
11.         7:{0:3,1:3,2:2,3:4,4:3,5:4,6:3,8:2,9:9,10:4,11:5},
    
12.         8:{0:2,1:2,2:4,3:1,4:2,5:3,6:1,7:3,9:6,10:4,11:5},
    
13.         9:{0:1,1:3,2:5,3:7,4:2,5:4,6:6,7:3,8:8,10:4,11:5},
    
14.         10:{0:1,1:3,2:5,3:7,4:2,5:4,6:6,7:3,8:8,9:12,11:5},
    
15.         11:{0:1,1:2,2:5,3:7,4:2,5:4,6:6,7:3,8:8,9:12,10:4}}
    
16. 
    
17. dic = {}
    
18. 
    
19. def dp(x,y):
    
20.         if (x,y) not in dic:
    
21.                 dic[(x,y)] = [weight[x][y], [x,y]]
    
22.         else:
    
23.                 for ea in dic:
    
24.                         a,b = ea
    
25.                         if a == x:
    
26.                                 for ch in dic:
    
27.                                         c,d = ch
    
28.                                         if b==c and d==y:
    
29.                                                 if dic[(x,y)][0] > dic[(a,b)][0] + dic[(c,d)][0]:
    
30.                                                         dic[(x,y)][0] = dic[(a,b)][0] + dic[(c,d)][0]
    
31.                                                         dic[(x,y)][1] = dic[(a,b)][1] + dic[(c,d)][1]
    
32. 
    
33. for i in range(12):
    
34.         for j in range(12):
    
35.                 if i != j:
    
36.                         dp(i,j)
    
37. record = dic[(0,9)][0]
    
38. 
    
39. while True:
    
40.         for i in range(12):
    
41.                 for j in range(12):
    
42.                         if i != j:
    
43.                                 dp(i,j)
    
44.         if record == dic[(0,9)][0]:
    
45.                 print (dic[(0,9)])
    
46.                 break
    
47.         else:
    
48.                 record = dic[(0,9)][0]

复制代码

输出：
[12, [0, 11, 11, 4, 4, 8, 8, 9]]
[Finished in 0.2s]

可以看到比之前的程序快了将近200倍

跳转到最佳答案楼层

jerryxjr1220

下面的方法用的是排列组合的方法，但是对于节点非常多的情况，速度会非常慢，所以必须要优化。

1. #coding:utf-8
   
2. '''题目要求：起点（2），终点（4），找出权重最小的路径即为最优路径'''
   
3. weight={0:{1:2,2:4,3:6,4:8},
   
4.                 1:{0:1,2:3,3:1,4:4},
   
5.                 2:{0:2,1:5,3:4,4:9},
   
6.                 3:{0:5,1:2,2:6,4:6},
   
7.                 4:{0:7,1:9,2:4,3:7}}
   
8. 
   
9. import itertools
   
10. dp = weight[2][4]
    
11. for i in range(1,4):
    
12.         permutation = itertools.permutations([0,1,3],i)
    
13.         for p in permutation:
    
14.                 combination = [2]+list(p)+[4]
    
15.                 tmp = 0
    
16.                 for c in range(len(combination)-1):
    
17.                         tmp += weight[combination[c]][combination[c+1]]
    
18.                 if tmp < dp:
    
19.                         dp = tmp
    
20.                         best = combination
    
21. print (best, dp)

复制代码

输出：
[2, 0, 1, 4] 8
[Finished in 0.1s]

jerryxjr1220

当节点达到12个的时候，用时已经要超过半分钟了。

1. #coding:utf-8
   
2. '''题目要求：起点（0），终点（9），找出权重最小的路径即为最优路径'''
   
3. weight={0:{1:3,2:5,3:6,4:8,5:4,6:9,7:8,8:9,9:16,10:3,11:2},
   
4.                 1:{0:2,2:3,3:3,4:4,5:3,6:7,7:2,8:8,9:12,10:4,11:5},
   
5.                 2:{0:2,1:5,3:4,4:9,5:3,6:6,7:2,8:5,9:10,10:3,11:3},
   
6.                 3:{0:5,1:2,2:6,4:6,5:5,6:3,7:6,8:7,9:10,10:4,11:4},
   
7.                 4:{0:7,1:9,2:2,3:7,5:3,6:8,7:3,8:2,9:10,10:5,11:4},
   
8.                 5:{0:4,1:3,2:3,3:2,4:2,6:8,7:4,8:5,9:11,10:4,11:5},
   
9.                 6:{0:2,1:2,2:3,3:3,4:4,5:5,7:6,8:5,9:6,10:4,11:5},
   
10.                 7:{0:3,1:3,2:2,3:4,4:3,5:4,6:3,8:2,9:9,10:4,11:5},
    
11.                 8:{0:2,1:2,2:4,3:1,4:2,5:3,6:1,7:3,9:6,10:4,11:5},
    
12.                 9:{0:1,1:3,2:5,3:7,4:2,5:4,6:6,7:3,8:8,10:4,11:5},
    
13.                 10:{0:1,1:3,2:5,3:7,4:2,5:4,6:6,7:3,8:8,9:12,11:5},
    
14.                 11:{0:1,1:2,2:5,3:7,4:2,5:4,6:6,7:3,8:8,9:12,10:4}}
    
15. 
    
16. 
    
17. import itertools
    
18. dp = weight[0][9]
    
19. best = [0, 9]
    
20. for i in range(1,11):
    
21.         permutation = itertools.permutations(list(range(1,9))+[10,11],i)
    
22.         for p in permutation:
    
23.                 combination = [0]+list(p)+[9]
    
24.                 tmp = 0
    
25.                 for c in range(len(combination)-1):
    
26.                         tmp += weight[combination[c]][combination[c+1]]
    
27.                 if tmp < dp:
    
28.                         dp = tmp
    
29.                         best = combination
    
30. print (best, dp)

复制代码

输出：
[0, 11, 4, 8, 9] 12
[Finished in 36.6s]

jerryxjr1220

我自己找到优化的方法了，还是借用字典，把所以走过的路径都记录下来，然后依次比较，有比记录更短的路径就添加进去，依次类推，不断循环，直到最后最优值不变了即为最优解。

1. #coding:utf-8
   
2. '''题目要求：起点（0），终点（9），找出权重最小的路径即为最优路径'''
   
3. 
   
4. weight={0:{1:3,2:5,3:6,4:8,5:4,6:9,7:8,8:9,9:16,10:3,11:2},
   
5.         1:{0:2,2:3,3:3,4:4,5:3,6:7,7:2,8:8,9:12,10:4,11:5},
   
6.         2:{0:2,1:5,3:4,4:9,5:3,6:6,7:2,8:5,9:10,10:3,11:3},
   
7.         3:{0:5,1:2,2:6,4:6,5:5,6:3,7:6,8:7,9:10,10:4,11:4},
   
8.         4:{0:7,1:9,2:2,3:7,5:3,6:8,7:3,8:2,9:10,10:5,11:4},
   
9.         5:{0:4,1:3,2:3,3:2,4:2,6:8,7:4,8:5,9:11,10:4,11:5},
   
10.         6:{0:2,1:2,2:3,3:3,4:4,5:5,7:6,8:5,9:6,10:4,11:5},
    
11.         7:{0:3,1:3,2:2,3:4,4:3,5:4,6:3,8:2,9:9,10:4,11:5},
    
12.         8:{0:2,1:2,2:4,3:1,4:2,5:3,6:1,7:3,9:6,10:4,11:5},
    
13.         9:{0:1,1:3,2:5,3:7,4:2,5:4,6:6,7:3,8:8,10:4,11:5},
    
14.         10:{0:1,1:3,2:5,3:7,4:2,5:4,6:6,7:3,8:8,9:12,11:5},
    
15.         11:{0:1,1:2,2:5,3:7,4:2,5:4,6:6,7:3,8:8,9:12,10:4}}
    
16. 
    
17. dic = {}
    
18. 
    
19. def dp(x,y):
    
20.         if (x,y) not in dic:
    
21.                 dic[(x,y)] = [weight[x][y], [x,y]]
    
22.         else:
    
23.                 for ea in dic:
    
24.                         a,b = ea
    
25.                         if a == x:
    
26.                                 for ch in dic:
    
27.                                         c,d = ch
    
28.                                         if b==c and d==y:
    
29.                                                 if dic[(x,y)][0] > dic[(a,b)][0] + dic[(c,d)][0]:
    
30.                                                         dic[(x,y)][0] = dic[(a,b)][0] + dic[(c,d)][0]
    
31.                                                         dic[(x,y)][1] = dic[(a,b)][1] + dic[(c,d)][1]
    
32. 
    
33. for i in range(12):
    
34.         for j in range(12):
    
35.                 if i != j:
    
36.                         dp(i,j)
    
37. record = dic[(0,9)][0]
    
38. 
    
39. while True:
    
40.         for i in range(12):
    
41.                 for j in range(12):
    
42.                         if i != j:
    
43.                                 dp(i,j)
    
44.         if record == dic[(0,9)][0]:
    
45.                 print (dic[(0,9)])
    
46.                 break
    
47.         else:
    
48.                 record = dic[(0,9)][0]

复制代码

输出：
[12, [0, 11, 11, 4, 4, 8, 8, 9]]
[Finished in 0.2s]

可以看到比之前的程序快了将近200倍

jerryxjr1220

把上述的解法封装了一下，然后加入“途经”其他节点的功能。

带权重的最优路径解法是现在用的许多导航地图算法的基础，所以还是很有必要研究一下的。

bestway（s，e，a，b）函数中，s代表起始点，e代表终点，a和b代表途径点（可选）。

1. #coding:utf-8
   
2. '''题目要求：起点（0），终点（9），找出权重最小的路径即为最优路径'''
   
3. 
   
4. weight={0:{1:3,2:5,3:6,4:8,5:4,6:9,7:8,8:9,9:16,10:3,11:2},
   
5.         1:{0:2,2:3,3:3,4:4,5:3,6:7,7:2,8:8,9:12,10:4,11:5},
   
6.         2:{0:2,1:5,3:4,4:9,5:3,6:6,7:2,8:5,9:10,10:3,11:3},
   
7.         3:{0:5,1:2,2:6,4:6,5:5,6:3,7:6,8:7,9:10,10:4,11:4},
   
8.         4:{0:7,1:9,2:2,3:7,5:3,6:8,7:3,8:2,9:10,10:5,11:4},
   
9.         5:{0:4,1:3,2:3,3:2,4:2,6:8,7:4,8:5,9:11,10:4,11:5},
   
10.         6:{0:2,1:2,2:3,3:3,4:4,5:5,7:6,8:5,9:6,10:4,11:5},
    
11.         7:{0:3,1:3,2:2,3:4,4:3,5:4,6:3,8:2,9:9,10:4,11:5},
    
12.         8:{0:2,1:2,2:4,3:1,4:2,5:3,6:1,7:3,9:6,10:4,11:5},
    
13.         9:{0:1,1:3,2:5,3:7,4:2,5:4,6:6,7:3,8:8,10:4,11:5},
    
14.         10:{0:1,1:3,2:5,3:7,4:2,5:4,6:6,7:3,8:8,9:12,11:5},
    
15.         11:{0:1,1:2,2:5,3:7,4:2,5:4,6:6,7:3,8:8,9:12,10:4}}
    
16. 
    
17. dic = {}
    
18. 
    
19. def dp(x,y):
    
20.     if (x,y) not in dic:
    
21.         dic[(x,y)] = [weight[x][y], [x,y]]
    
22.     else:
    
23.         for ea in dic:
    
24.             a,b = ea
    
25.             if a == x:
    
26.                 for ch in dic:
    
27.                     c,d = ch
    
28.                     if b==c and d==y:
    
29.                         if dic[(x,y)][0] > dic[(a,b)][0] + dic[(c,d)][0]:
    
30.                             dic[(x,y)][0] = dic[(a,b)][0] + dic[(c,d)][0]
    
31.                             dic[(x,y)][1] = dic[(a,b)][1] + dic[(c,d)][1]
    
32. #initiate:
    
33. for i in range(12):
    
34.     for j in range(12):
    
35.         if i != j:
    
36.             dp(i,j)
    
37. 
    
38. def find(s,e):
    
39.         global dic
    
40.         record = dic[(s,e)][0]
    
41.         while True:
    
42.             for i in range(12):
    
43.                 for j in range(12):
    
44.                     if i != j:
    
45.                         dp(i,j)
    
46.             if record == dic[(s,e)][0]:
    
47.                 return dic[(s,e)]
    
48.             else:
    
49.                 record = dic[(s,e)][0]
    
50. 
    
51. def bestway(s,e,a=None,b=None):
    
52.         if not b:
    
53.                 if not a:
    
54.                         return find(s,e)
    
55.                 else:
    
56.                         result1 = find(s,a)
    
57.                         result2 = find(a,e)
    
58.                         return [result1[0]+result2[0], result1[1]+result2[1]]
    
59.         else:
    
60.                 result1 = find(s,a)
    
61.                 result2 = find(a,b)
    
62.                 result3 = find(b,e)
    
63.                 return [result1[0]+result2[0]+result3[0], result1[1]+result2[1]+result3[1]]
    
64. 
    
65. print (bestway(0,9,7,3))

复制代码

输出：
[17, [0, 1, 1, 7, 7, 8, 8, 3, 3, 6, 6, 9]]
[Finished in 0.1s]

qaz123765

厉害，我只能想到之后的和直达的比较，写不出来，另外可以把最后的两个for循环去掉一个，写在while里面，取第二次值

小冰冰偶哈哈

厉害

JAY饭

1. weight={0:{1:2,2:4,3:6,4:8},
   
2.         1:{0:1,2:3,3:1,4:4},
   
3.         2:{0:2,1:5,3:4,4:9},
   
4.         3:{0:5,1:2,2:6,4:6},
   
5.         4:{0:7,1:9,2:4,3:7}}
   
6. 
   
7. t = [i for i in range(5)]
   
8. f ={}
   
9. def hui(t,n,m,a,b):
   
10.     t1 = t[:]
    
11.     t1.remove(n)
    
12.     for i in t1:
    
13.         b1 = b + weight[n][i]
    
14.         f[i] = n
    
15.         if i == m:
    
16.             if b1 < a:
    
17.                 print(b1)
    
18.                 v = i
    
19.                 f1 = []
    
20.                 while True:
    
21.                     f1.append(v)
    
22.                     v = f[v]
    
23.                     if v == 2:
    
24.                         f1.append(v)
    
25.                         break
    
26.                 f1.reverse()
    
27.                 print(f1)
    
28.                 return 1
    
29.             else:
    
30.                 return False
    
31. 
    
32.         n1 = i
    
33.         hui(t1,n1,m,a,b1)
    
34.             
    
35.         
    
36. hui(t,2,4,9,0)

复制代码

JAY饭

上面这个写错了，不能包括所求位置后面的路径。重写了下，可以是可以可，但特别慢，三四十秒。我再想下

（答案已经更新，说下思路，利用回溯递归的方法，将每一步的路径简化为一个同位置的列表，每走一步，移出对应的位置元素，
递归的结束条件就是对应的列表长度为0，筛选条件是，每一步加权重数得到的和不能超过最直接的那一步的权重，否则跳出迭代，
之前就是忽略这一点。然后用字典记录路径，方便回溯，在途经这里我用的是循环加1的方法，一直到所有的途经出现在相对最短
路径中）

1. weight={0:{1:3,2:5,3:6,4:8,5:4,6:9,7:8,8:9,9:16,10:3,11:2},
   
2.         1:{0:2,2:3,3:3,4:4,5:3,6:7,7:2,8:8,9:12,10:4,11:5},
   
3.         2:{0:2,1:5,3:4,4:9,5:3,6:6,7:2,8:5,9:10,10:3,11:3},
   
4.         3:{0:5,1:2,2:6,4:6,5:5,6:3,7:6,8:7,9:10,10:4,11:4},
   
5.         4:{0:7,1:9,2:2,3:7,5:3,6:8,7:3,8:2,9:10,10:5,11:4},
   
6.         5:{0:4,1:3,2:3,3:2,4:2,6:8,7:4,8:5,9:11,10:4,11:5},
   
7.         6:{0:2,1:2,2:3,3:3,4:4,5:5,7:6,8:5,9:6,10:4,11:5},
   
8.         7:{0:3,1:3,2:2,3:4,4:3,5:4,6:3,8:2,9:9,10:4,11:5},
   
9.         8:{0:2,1:2,2:4,3:1,4:2,5:3,6:1,7:3,9:6,10:4,11:5},
   
10.         9:{0:1,1:3,2:5,3:7,4:2,5:4,6:6,7:3,8:8,10:4,11:5},
    
11.         10:{0:1,1:3,2:5,3:7,4:2,5:4,6:6,7:3,8:8,9:12,11:5},
    
12.         11:{0:1,1:2,2:5,3:7,4:2,5:4,6:6,7:3,8:8,9:12,10:4}}
    
13. 
    
14. t = [i for i in range(12)]
    
15. f ={}
    
16. f2 = []
    
17. f3 = {}
    
18. def hui(t,n,m,a,b):
    
19.     if len(t) == 0:
    
20.         return 1
    
21.     t1 = t[:]
    
22.     t1.remove(n)
    
23.     for i in t1:
    
24.         b1 = b + weight[n][i]
    
25.         if b1 > a:
    
26.             continue
    
27.         f[i] = n
    
28.         if i == m:
    
29.             if b1 <= a:
    
30. 
    
31.                 a = b1
    
32.                 f2.append(b1)
    
33.                 v = i
    
34.                 f1 = []
    
35.                 while True:
    
36.                     f1.append(v)
    
37.                     v = f[v]
    
38.                     if v == 0:
    
39.                         f1.append(v)
    
40.                         break
    
41.                 f1.reverse()
    
42.                 if b1 not in f3:
    
43.                     f3[b1] = [f1]
    
44.                 else:
    
45.                     f3[b1] += [f1]
    
46. 
    
47.             continue
    
48.         n1 = i
    
49.         hui(t1,n1,m,a,b1)
    
50.             
    
51. def tujing(c,d):
    
52.     global f3,f2,f
    
53.     n,m,a,b = 0,9,15,0
    
54.     while True:
    
55.         
    
56.         f,f3,f2,f4 = {},{},[],[]
    
57.         
    
58.         hui(t,n,m,a,b)
    
59.         for i in f2:
    
60.             for j in f3[i]:
    
61.                 if c in j and d in j:
    
62.                     f4.append((i,j))
    
63.         if len(f4) == 0:
    
64.             a += 1
    
65.         else:
    
66.             print(min(f4))
    
67.             
    
68.             break
    
69.         
    
70. tujing(3,7)
    

复制代码

JAY饭

加了个continue缩短到9秒，还不够

JAY饭

又加了一个continue，加上一个筛选条件，秒出，可以啦，用的是回溯递归的方法，本来早就可以解决，一直打游戏思路都是乱的，一开始就瞎写。浪费大量时间。