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

aoe1981

  如果不考虑所有可能路径而只考虑最短路径时，只需生成由出发点到其他点的距离树即可。

zopey

aoe1981 发表于 2017-12-21 21:45
如果不考虑所有可能路径而只考虑最短路径时，只需生成由出发点到其他点的距离树即可。

7楼代码 只求最短路径。

aoe1981

zopey 发表于 2017-12-22 08:49
7楼代码 只求最短路径。

多谢，目前只认识代码中“邻接矩阵”四字，有功夫了再仔细拜读！！！

aoe1981

　　以下附件实现我在31楼里所说的“生成距离树”：
　　

　　代码如下：

1. Option Explicit
   
2. Sub jlshu()
   
3.     Dim arr, brr, D_ljd As Object, B_jl As Object, t1$, t2$, i&, j&, k&, qd$, zd$, mbjl#, mblj$
   
4.     arr = Sheet2.Range("a1").CurrentRegion
   
5.     Set D_ljd = CreateObject("Scripting.Dictionary")
   
6.     Set B_jl = CreateObject("Scripting.Dictionary")
   
7.     For i = 2 To UBound(arr, 1) '将路径对应的距离，点的邻接表写入字典
   
8.         t1 = arr(i, 1): t2 = arr(i, 2)
   
9.         D_ljd(t1) = D_ljd(t1) & " " & t2 '点_邻接点
   
10.         D_ljd(t2) = D_ljd(t2) & " " & t1
    
11.         B_jl(t1 & "-" & t2) = arr(i, 3) '边_距离
    
12.         B_jl(t2 & "-" & t1) = arr(i, 3)
    
13.     Next i
    
14.     Dim D_jl As Object, D_lj As Object, U As Object, key1, key2, n&, gd, f_dian$, min_dian$, min_jl#, max_jl# '点的距离标记、路径标记、添加标记
    
15.     Set D_jl = CreateObject("Scripting.Dictionary")
    
16.     Set D_lj = CreateObject("Scripting.Dictionary")
    
17.     Set U = CreateObject("Scripting.Dictionary")
    
18.     key1 = D_ljd.keys: n = D_ljd.Count
    
19.     For i = 0 To n - 1 '初始化各点标记
    
20.         D_jl(key1(i)) = 0: D_lj(key1(i)) = key1(i)
    
21.     Next i
    
22.     max_jl = WorksheetFunction.Sum(B_jl.items) + 1: min_jl = max_jl
    
23.     qd = Sheet3.Range("a2").Value: zd = Sheet3.Range("b2").Value: U(qd) = 1 '首先添加根结点
    
24.     For i = 1 To n - 1 '至多添加其余n-1个点
    
25.         key1 = U.keys
    
26.         For j = 1 To U.Count '遍历U中每一点
    
27.             gd = Split(D_ljd(key1(j - 1)), " ")
    
28.             For k = 1 To UBound(gd) '扫描U中每一点的不属于U的邻接点
    
29.                 If Not (U.exists(gd(k))) Then
    
30.                     If D_jl(key1(j - 1)) + B_jl(key1(j - 1) & "-" & gd(k)) < min_jl Then '父点距离标记+路径距离
    
31.                         f_dian = key1(j - 1): min_dian = gd(k): min_jl = D_jl(key1(j - 1)) + B_jl(key1(j - 1) & "-" & gd(k)) '寻找最短距离的点
    
32.                     End If
    
33.                 End If
    
34.             Next k
    
35.         Next j
    
36.         D_jl(min_dian) = min_jl '更新最短距离点的距离数据
    
37.         D_lj(min_dian) = D_lj(f_dian) & "-" & min_dian '记录最短距离点的路径数据：最短距离点&"-"&父点路径标记
    
38.         U(min_dian) = 1 '添加最短距离点
    
39.         min_jl = max_jl '每比较完一轮将最小距离重置为距离和+1
    
40.     Next i
    
41.     ReDim brr(1 To n, 1 To 2)
    
42.     key1 = D_jl.items: key2 = D_lj.items
    
43.     For i = 1 To n
    
44.         brr(i, 1) = key1(i - 1): brr(i, 2) = key2(i - 1)
    
45.         gd = Split(key2(i - 1), "-")
    
46.         If gd(UBound(gd)) = zd Then mbjl = brr(i, 1): mblj = brr(i, 2)
    
47.     Next i
    
48.     Sheet3.Range("a4:b" & Rows.Count).ClearContents
    
49.     Sheet3.Range("a4").Resize(n, 2).Value = brr
    
50.     MsgBox "起点" & qd & "到终点" & zd & "的最短距离是：" & mbjl & "，最短路径是：" & mblj
    
51. End Sub

复制代码

aoe1981

E点出发的距离树：

170	E-TK03-A
140	E-TK03-TK01
190	E-TK03-TK01-B
340	E-TK03-TK01-TK02
40	E-TK03
490	E-TK03-TK01-TK02-C
440	E-TK03-TK01-TK02-D
0	E
50	E-F

A点出发的距离树：

0	A
50	A-TK01
80	A-B
250	A-TK01-TK02
130	A-TK03
400	A-TK01-TK02-C
350	A-TK01-TK02-D
170	A-TK03-E
140	A-F

B点出发的距离树：

80	B-A
50	B-TK01
0	B
250	B-TK01-TK02
150	B-TK01-TK03
400	B-TK01-TK02-C
350	B-TK01-TK02-D
190	B-TK01-TK03-E
170	B-TK01-TK03-F

C点出发的距离树：

400	C-TK02-TK01-A
350	C-TK02-TK01
400	C-TK02-TK01-B
150	C-TK02
450	C-TK02-TK01-TK03
0	C
250	C-TK02-D
490	C-TK02-TK01-TK03-E
470	C-TK02-TK01-TK03-F

D点出发的距离树：

350	D-TK02-TK01-A
300	D-TK02-TK01
350	D-TK02-TK01-B
100	D-TK02
400	D-TK02-TK01-TK03
250	D-TK02-C
0	D
440	D-TK02-TK01-TK03-E
420	D-TK02-TK01-TK03-F

F点出发的距离树：

140	F-A
120	F-TK03-TK01
170	F-TK03-TK01-B
320	F-TK03-TK01-TK02
20	F-TK03
470	F-TK03-TK01-TK02-C
420	F-TK03-TK01-TK02-D
50	F-E
0	F

TK01点出发的距离树：

50	TK01-A
0	TK01
50	TK01-B
200	TK01-TK02
100	TK01-TK03
350	TK01-TK02-C
300	TK01-TK02-D
140	TK01-TK03-E
120	TK01-TK03-F

TK02点出发的距离树：

250	TK02-TK01-A
200	TK02-TK01
250	TK02-TK01-B
0	TK02
300	TK02-TK01-TK03
150	TK02-C
100	TK02-D
340	TK02-TK01-TK03-E
320	TK02-TK01-TK03-F

TK03点出发的距离树：

130	TK03-A
100	TK03-TK01
150	TK03-TK01-B
300	TK03-TK01-TK02
0	TK03
450	TK03-TK01-TK02-C
400	TK03-TK01-TK02-D
40	TK03-E
20	TK03-F

aoe1981

zopey 发表于 2017-12-22 08:49
7楼代码 只求最短路径。

把生成距离树的算法做出来了，有空了再和您的对比一下。

aoe1981

生成距离树的算法中，字典快速写入技巧学自大师“香川”，隆重声明。

text888877

虽然不懂VBA，但是还是想跟大家继续学习

challenge24

好复杂啊，有没有人讲讲思路？

temp17

学习模块，学习思路