ExcelHome技术论坛

 找回密码
 免费注册

QQ登录

只需一步,快速开始

快捷登录

搜索
EH技术汇-专业的职场技能充电站 妙哉!函数段子手趣味讲函数 Excel服务器-会Excel,做管理系统 Excel Home精品图文教程库
HR薪酬管理数字化实战 Excel 2021函数公式学习大典 Excel数据透视表实战秘技 打造核心竞争力的职场宝典
让更多数据处理,一键完成 数据工作者的案头书 免费直播课集锦 ExcelHome出品 - VBA代码宝免费下载
用ChatGPT与VBA一键搞定Excel WPS表格从入门到精通 Excel VBA经典代码实践指南
楼主: 蓝桥玄霜

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

  [复制链接]

TA的精华主题

TA的得分主题

发表于 2018-2-28 11:38 | 显示全部楼层
challenge24 发表于 2018-2-17 22:36
好复杂啊,有没有人讲讲思路?

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

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

TA的精华主题

TA的得分主题

发表于 2018-11-26 09:44 | 显示全部楼层

TA的精华主题

TA的得分主题

发表于 2019-3-26 22:40 | 显示全部楼层
老师,帮忙看下我帖子上的问题能不能解决,谢谢啦!

TA的精华主题

TA的得分主题

发表于 2019-4-7 13:22 | 显示全部楼层
学了一周才勉强搞明白,练习一个



  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
复制代码


本帖子中包含更多资源

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

x

TA的精华主题

TA的得分主题

发表于 2019-11-4 22:33 | 显示全部楼层
本帖最后由 duquancai 于 2019-11-4 23:46 编辑

图论之 Dijkstra 算法,用python实现如下:
  1. # -*- coding: utf-8 -*-
  2. # version: Python 3.7.0
  3. import heapq

  4. class Dijkstra(object):
  5.     def __init__(self, alist):
  6.         self.__D = {}
  7.         for i in alist:
  8.             if self.__D.get(i[0]):
  9.                 self.__D[i[0]][i[1]] = i[2]
  10.             else:
  11.                 self.__D[i[0]] = {i[1]: i[2]}
  12.             if self.__D.get(i[1]):
  13.                 self.__D[i[1]][i[0]] = i[2]
  14.             else:
  15.                 self.__D[i[1]] = {i[0]: i[2]}

  16.     def dijkstra(self, start, end):
  17.         queue = []
  18.         heapq.heappush(queue, (0, start))
  19.         seen = set()
  20.         part = {start: None}
  21.         dist = {v: float('inf') if v != start else 0 for v in self.__D}
  22.         while queue:
  23.             pair = heapq.heappop(queue)
  24.             d = pair[0]
  25.             v = pair[1]
  26.             if v == end:
  27.                 path = []
  28.                 while end:
  29.                     path.append(end)
  30.                     end = part[end]
  31.                 path.reverse()
  32.                 return dist[v], '->'.join(path)
  33.             seen.add(v)
  34.             nodes = self.__D[v]
  35.             for w, i in nodes.items():
  36.                 if w in seen: continue
  37.                 if d + i < dist[w]:
  38.                     heapq.heappush(queue, (d + i, w))
  39.                     part[w] = v
  40.                     dist[w] = d + i
  41.         return '无此路径!'

  42. def main():
  43.     # 从Excel、txt、csv读取的如下二维"数组"源数据,n行3列
  44.     source = [("A", "TK01", 50),
  45.               ("TK01", "B", 50),
  46.               ("TK01", "TK02", 200),
  47.               ("TK01", "TK03", 100),
  48.               ("TK02", "C", 150),
  49.               ("TK02", "D", 100),
  50.               ("TK03", "E", 40),
  51.               ("TK03", "F", 20),
  52.               ("A", "B", 80),
  53.               ("A", "TK03", 130),
  54.               ("A", "F", 140),
  55.               ("E", "F", 50)
  56.               ]
  57.     g = Dijkstra(source)
  58.     # 输出单源最短路径及距离,可以改变起点与终点
  59.     print(g.dijkstra('A', 'F'))

  60. if __name__ == '__main__':
  61.     main()
复制代码

本帖子中包含更多资源

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

x

TA的精华主题

TA的得分主题

发表于 2019-11-18 12:24 | 显示全部楼层
'学习一下。邻接矩阵+深度搜索,,,

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

评分

2

查看全部评分

TA的精华主题

TA的得分主题

发表于 2020-2-21 15:56 | 显示全部楼层
ykytom 发表于 2017-11-16 22:15
这几天刚才楼主那学到的

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

TA的精华主题

TA的得分主题

发表于 2020-2-21 15:57 | 显示全部楼层
蓝大师:如果有图上有N个点, 这些点以2维平面坐标的的形式体现他们的位置,如何求和所有点走完的最小距离

TA的精华主题

TA的得分主题

发表于 2020-3-12 12:41 | 显示全部楼层
最近开始研究递归,看到这些内容仿佛看到了希望,非常感谢老师们的分享

TA的精华主题

TA的得分主题

发表于 2021-8-4 19:55 | 显示全部楼层
[广告] VBA代码宝 - VBA编程加强工具 · VBA代码随查随用  · 内置多项VBA编程加强工具       ★ 免费下载 ★      ★使用手册
ykytom 发表于 2017-11-16 22:15
这几天刚才楼主那学到的

学习了!太强大了!
您需要登录后才可以回帖 登录 | 免费注册

本版积分规则

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

GMT+8, 2024-7-13 20:08 , Processed in 0.043618 second(s), 12 queries , Gzip On, MemCache On.

Powered by Discuz! X3.4

© 1999-2023 Wooffice Inc.

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

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

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