ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

   
EH云课堂-专业的职场技能充电站 Excel转在线管理系统,怎么做看这里 Excel服务器-会Excel,做管理系统 Excel Home精品图文教程库
Excel不给力? 何不试试FoxTable! Excel 2016函数公式学习大典 高效办公必会的Office实战技巧 免费下载Excel行业应用视频
300集Office 2010微视频教程 Tableau-数据可视化工具 精品推荐-800套精选PPT模板,点击获取 ExcelHome出品 - VBA代码宝免费下载
你的Excel 2010实战技巧学习锦囊 欲罢不能, 过目难忘的 Office 新界面 Excel VBA经典代码实践指南
楼主: 蓝桥玄霜

[Excel 程序开发] 【已总结】[第119期]假如你是无人驾驶车上的电脑,你想好了怎么走吗?

[复制链接]

TA的精华主题

TA的得分主题

发表于 2017-12-21 21:45 来自手机 | 显示全部楼层
本帖最后由 aoe1981 于 2017-12-21 21:47 编辑

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

TA的精华主题

TA的得分主题

发表于 2017-12-22 08:49 | 显示全部楼层
aoe1981 发表于 2017-12-21 21:45
如果不考虑所有可能路径而只考虑最短路径时,只需生成由出发点到其他点的距离树即可。

7楼代码 只求最短路径。

TA的精华主题

TA的得分主题

发表于 2017-12-22 09:22 | 显示全部楼层
zopey 发表于 2017-12-22 08:49
7楼代码 只求最短路径。

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

TA的精华主题

TA的得分主题

发表于 2018-1-3 16:26 | 显示全部楼层
本帖最后由 aoe1981 于 2018-1-3 16:43 编辑

  以下附件实现我在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
复制代码


本帖子中包含更多资源

您需要 登录 才可以下载或查看,没有帐号?免费注册

x

TA的精华主题

TA的得分主题

发表于 2018-1-3 16:28 | 显示全部楼层
本帖最后由 aoe1981 于 2018-1-3 16:31 编辑

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

TA的精华主题

TA的得分主题

发表于 2018-1-3 16:45 | 显示全部楼层
zopey 发表于 2017-12-22 08:49
7楼代码 只求最短路径。

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

TA的精华主题

TA的得分主题

发表于 2018-1-3 17:04 | 显示全部楼层
生成距离树的算法中,字典快速写入技巧学自大师“香川”,隆重声明。

TA的精华主题

TA的得分主题

发表于 2018-1-14 09:28 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2018-2-17 22:36 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2018-2-25 16:45 | 显示全部楼层
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

关注官方微信,每天学会一个新技能

手机版|关于我们|联系我们|ExcelHome

GMT+8, 2019-6-17 04:40 , Processed in 2.288310 second(s), 11 queries , Gzip On, MemCache On.

Powered by Discuz! X3.4

© 2001-2017 Wooffice Inc.

   

沪公网安备 31011702000001号 沪ICP备11019229号

本论坛言论纯属发表者个人意见,任何违反国家相关法律的言论,本站将协助国家相关部门追究发言者责任!     本站特聘法律顾问:徐怀玉律师 李志群律师

快速回复 返回顶部 返回列表