水木社区手机版
- 主题:我不了解图的遍历，一个题求助一下
- 看这个图，如何找出最快遍历所有城市的路线？节点可以重复。
进一步，最快遍历所有大陆上省会城市的路线？
再进一步，根据目前时刻表，给出实际经过所有大陆省会城市的最快的车次安排？
我想试一把80小时环游大陆省会城市（实在不成作个小弊放弃拉萨）
--
发自xsmth (iOS版)
--
- 来自 水木社区APP v3.4.1
※ 修改:·shire 于 May 20 01:26:26 2021 修改本文·[FROM: 123.116.133.*]
※ 来源:·水木社区 http://m.newsmth.net·[FROM: 123.116.133.*]
修改:shire FROM 123.116.133.*
FROM 123.116.133.* - 嗯，应该不太难，不过很久不编程了，主要会VC++，还需要搭建编译环境。
excel里的vb，倒是可以随时开始，不用再搭建环境。
有没有什么简单好上手的工具，介绍一下？
- 来自 水木社区APP v3.4.1
【 在 lby20180710 的大作中提到: 】
: 标准的图论题目，挺简单的呀，网上绝对有现成的方案，就是需要自己初始化一下信息
--
FROM 124.64.16.* - 查了一下，这个居然是个经典的NPC算法，大陆三十个省会城市，似乎算不出来
不算拉萨乌鲁木齐
复杂度是O(30！)
第二个算法没看懂
【 在 moudy (moudy) 的大作中提到: 】
: https://www.baeldung.com/cs/shortest-path-visiting-all-nodes
--
FROM 116.52.95.* - 太复杂，还有简单点的局部最优解吗？
【 在 finlab (挨踢卢瑟) 的大作中提到: 】
: NP问题，这么多节点，用标准算法一般电脑搞不定
: 可以先按出入度把有欧拉环路的子图分割出去
: 然后找子图间的最短连接
: ...................
--
FROM 123.116.132.* - 大神能不能编个程序算算？
- 来自 水木社区APP v3.4.1
【 在 finlab 的大作中提到: 】
: Python太慢。
--
FROM 123.116.132.* - 不知道python和VBA哪个更慢？
【 在 finlab (挨踢卢瑟) 的大作中提到: 】
: Python太慢。
--
FROM 123.116.139.* - 编程的时间和计算的时间综合考虑的话，有时候难以选择。
- 来自 水木社区APP v3.4.1
【 在 finlab 的大作中提到: 】
: 我猜Python更慢。
--
FROM 114.242.250.* - 你录入数据了没有？
我用vba编了个程序，把节点简化了一些，用的修改过的dijkstra算法，试过6个节点，17个，22个节点，能算出最短路径长度。
但是有几个问题，
1 长度能得出，验证了一些情况，没问题，但无法证明算法绝对正确。
2 加了记录路径的算法，能得出完整的链，但是大部分起点的记录路径并不是该起点最短路径，不过
3 最头疼的是，算29个节点时，数组长度超出内存了。
17个节点用两三秒，22个节点用一两分钟，29~31和节点，估计要一天了。
- 来自 水木社区APP v3.4.1
【 在 moudy 的大作中提到: 】
: 就他这个图，python在我的本上十几秒就跑完了，也足够了
--
FROM 123.116.142.* - 我用的就是你四楼叙述的方法二，按我的想法加了路径记录。感觉最小长度相对可靠，但是再节点比较多的时候路径记录大部分情况跟踪不到最小长度。
算法里有个大小是（node, mask=2^node）的二维数组，node达到30的时候，太大了。
【 在 moudy 的大作中提到: 】
: 就他这个图，python在我的本上十几秒就跑完了，也足够了...
※ 修改:·shire 于 May 30 22:40:35 2021 修改本文·[FROM: 123.116.142.*]
※ 来源:·https://exp.newsmth.net·[FROM: 123.116.142.*]
修改:shire FROM 123.116.142.*
FROM 123.116.142.* - 我计算这个局部17个节点的图，最短路径是42个小时，按4楼算法，乌鲁木齐和哈尔滨作为起点，算的总时间都是42小时，其他节点作为起点都更长。
不过，从乌鲁木齐出发记录的路径是对的，也是42小时；从哈尔滨出发的记录路径不对，是45小时了。
- 来自 水木社区APP v3.4.1
不知怎么，忽然就想把这个问题解决掉，总有这个执念，这两天都花了十来个小时了。
我其实不是码农，算是半个建筑师，你们能帮我解决，我就不再纠结了。
【 在 shire 的大作中提到: 】
: 我用的就是你四楼叙述的方法二，按我的想法加了路径记录。感觉最小长度相对可靠，但是再节点比较多的时候路径记录大部分情况跟踪不到最小长度。
:
: 算法里有个大小是（node, mask=2^node）的二维数组，node达到30的时候，太大了。...
※ 修改:·shire 于 May 30 22:55:30 2021 修改本文·[FROM: 123.116.142.*]
※ 来源:·https://exp.newsmth.net·[FROM: 123.116.142.*]
修改:shire FROM 123.116.142.*
FROM 123.116.142.*