【已总结】[第119期]假如你是无人驾驶车上的电脑，你想好了怎么走吗？

唐伯狼

challenge24 发表于 2018-2-17 22:36
好复杂啊，有没有人讲讲思路？

思路就是把从起点开始到所有点的所有的路径和距离都列出来
然后把终点是B的挑出来,最后把距离最短的挑出来

列出所有路径的过程需要使用到递归(有些答案用字典,我没仔细看过)

1808835746

大赞上面的代码。收集了，

临时用用的

老师，帮忙看下我帖子上的问题能不能解决，谢谢啦！

micch

学了一周才勉强搞明白，练习一个

1. Sub car()
   
2.     Dim d, Ar, Br
   
3.     Set d = CreateObject("scripting.dictionary")
   
4.     Ks$ = Sheet1.[a2]:  Js$ = Sheet1.[b2] '开始点，结束点
   
5.     Ar = Sheets("题目").[a2:c13]
   
6.     d(Ks) = ""
   
7.     For i% = 1 To UBound(Ar) '顶点和顶点间距离存入字典
   
8.         d(Ar(i, 1)) = "": d(Ar(i, 2)) = ""
   
9.         d(Ar(i, 1) & "-" & Ar(i, 2)) = Ar(i, 3)
   
10.         d(Ar(i, 2) & "-" & Ar(i, 1)) = Ar(i, 3)
    
11.     Next
    
12.     d.Remove (Js): d(Js) = ""
    
13.     Br = Filter(d.keys, "-", False) '开始点为第一个，结束点为最后一个的所有顶点
    
14.     n = UBound(Br) '顶点数量
    
15.     ReDim JL%(n): Path = JL '定义距离结果数组，和路径数组
    
16.     ReDim T(n) As Boolean
    
17.     For i = 0 To n
    
18.         x$ = Ks & "-" & Br(i)
    
19.         If d.exists(x) Then JL(i) = d(x) Else JL(i) = IIf(Br(i) = Ks, 0, 9999)
    
20.     Next i
    
21.     m% = 0: T(0) = True: Path(0) = 0
    
22.         For i = 1 To n
    
23.             Min = 9999
    
24.                 For k% = 0 To n
    
25.                     If Not T(k) And JL(k) < Min Then Min = JL(k): m = k
    
26.                 Next k
    
27.             T(m) = True
    
28.                 For k = 0 To n
    
29.                     x$ = Br(m) & "-" & Br(k)
    
30.                     If d.exists(x) Then mn% = d(x) Else mn = IIf(Br(k) = Br(m), 0, 9999)
    
31.                     If Not T(k) And JL(m) + mn < JL(k) Then
    
32.                         JL(k) = JL(m) + mn:         Path(k) = m
    
33.                     End If
    
34.         Next k, i
    
35.     m = n: Route = Br(n)
    
36.         Do Until m = 0 '路径转化为文本
    
37.             Route = Br(Path(m)) & "-" & Route
    
38.             m = Path(m)
    
39.         Loop
    
40.     With Sheet1 '输出结果
    
41.         .[c2] = JL(n)
    
42.         .[d2] = Route
    
43.     End With
    
44. End Sub
    

复制代码

duquancai

图论之 Dijkstra 算法，用python实现如下：

1. # -*- coding: utf-8 -*-
   
2. # version: Python 3.7.0
   
3. import heapq
   
4. 
   
5. class Dijkstra(object):
   
6.     def __init__(self, alist):
   
7.         self.__D = {}
   
8.         for i in alist:
   
9.             if self.__D.get(i[0]):
   
10.                 self.__D[i[0]][i[1]] = i[2]
    
11.             else:
    
12.                 self.__D[i[0]] = {i[1]: i[2]}
    
13.             if self.__D.get(i[1]):
    
14.                 self.__D[i[1]][i[0]] = i[2]
    
15.             else:
    
16.                 self.__D[i[1]] = {i[0]: i[2]}
    
17. 
    
18.     def dijkstra(self, start, end):
    
19.         queue = []
    
20.         heapq.heappush(queue, (0, start))
    
21.         seen = set()
    
22.         part = {start: None}
    
23.         dist = {v: float('inf') if v != start else 0 for v in self.__D}
    
24.         while queue:
    
25.             pair = heapq.heappop(queue)
    
26.             d = pair[0]
    
27.             v = pair[1]
    
28.             if v == end:
    
29.                 path = []
    
30.                 while end:
    
31.                     path.append(end)
    
32.                     end = part[end]
    
33.                 path.reverse()
    
34.                 return dist[v], '->'.join(path)
    
35.             seen.add(v)
    
36.             nodes = self.__D[v]
    
37.             for w, i in nodes.items():
    
38.                 if w in seen: continue
    
39.                 if d + i < dist[w]:
    
40.                     heapq.heappush(queue, (d + i, w))
    
41.                     part[w] = v
    
42.                     dist[w] = d + i
    
43.         return '无此路径!'
    
44. 
    
45. def main():
    
46.     # 从Excel、txt、csv读取的如下二维"数组"源数据,n行3列
    
47.     source = [("A", "TK01", 50),
    
48.               ("TK01", "B", 50),
    
49.               ("TK01", "TK02", 200),
    
50.               ("TK01", "TK03", 100),
    
51.               ("TK02", "C", 150),
    
52.               ("TK02", "D", 100),
    
53.               ("TK03", "E", 40),
    
54.               ("TK03", "F", 20),
    
55.               ("A", "B", 80),
    
56.               ("A", "TK03", 130),
    
57.               ("A", "F", 140),
    
58.               ("E", "F", 50)
    
59.               ]
    
60.     g = Dijkstra(source)
    
61.     # 输出单源最短路径及距离,可以改变起点与终点
    
62.     print(g.dijkstra('A', 'F'))
    
63. 
    
64. if __name__ == '__main__':
    
65.     main()

复制代码

一把小刀闯天下

'学习一下。邻接矩阵+深度搜索，，，

Option Explicit

Sub test()
  Dim arr, i, first, n, dic, last, m
  Set dic = CreateObject("scripting.dictionary")
  arr = Sheets("题目").[a1].CurrentRegion
  ReDim brr(UBound(arr, 1) * 2, UBound(arr, 1) * 2), crr(1 To 3, 1 To 100)
  For i = 2 To UBound(arr, 1)
    If Not dic.exists(arr(i, 1)) Then n = n + 1: dic(arr(i, 1)) = n: brr(n, 0) = arr(i, 1)
    If Not dic.exists(arr(i, 2)) Then n = n + 1: dic(arr(i, 2)) = n: brr(n, 0) = arr(i, 2)
    brr(dic(arr(i, 1)), dic(arr(i, 2))) = arr(i, 3)
    brr(dic(arr(i, 2)), dic(arr(i, 1))) = arr(i, 3)
  Next
  ReDim flag(n), temp(1, n), result(1 To 1000, 1 To 3)
  With Sheets("sheet1")
    temp(0, 0) = .[a2].Value
    first = dic(temp(0, 0)): last = dic(.[b2].Value)
    Call dfs(brr, n, first, last, 1, flag, temp, result, m)
    .[c2].Resize(Rows.Count - 1, 3).ClearContents
    If m > 0 Then .[c2].Resize(m, 3) = result
  End With
End Sub

Function dfs(brr, n, first, last, cnt, flag, temp, result, m)
  Dim i, j, sum, s
  If first = last Then
    m = m + 1: result(m, 3) = cnt - 1
    For j = 0 To cnt - 1
      result(m, 2) = result(m, 2) & "->" & temp(0, j)
      result(m, 1) = result(m, 1) + temp(1, j)
    Next
    result(m, 2) = Mid(result(m, 2), 3): Exit Function
  End If
  flag(first) = 1
  For i = 1 To n
    If flag(i) = 0 And brr(first, i) > 0 Then
      temp(0, cnt) = brr(i, 0): temp(1, cnt) = brr(first, i)
      dfs brr, n, i, last, cnt + 1, flag, temp, result, m
    End If
  Next
  flag(first) = 0
End Function

felix301

ykytom 发表于 2017-11-16 22:15
这几天刚才楼主那学到的

大师：如果有图上有N个点， 这些点以2维平面坐标的的形式体现他们的位置，如何求和所有点走完的最小距离

felix301

蓝大师：如果有图上有N个点， 这些点以2维平面坐标的的形式体现他们的位置，如何求和所有点走完的最小距离

pattonzhai

最近开始研究递归，看到这些内容仿佛看到了希望，非常感谢老师们的分享

五指山888

ykytom 发表于 2017-11-16 22:15
这几天刚才楼主那学到的

学习了！太强大了！