水木社区手机版
- 主题:我不了解图的遍历，一个题求助一下
- 看这个图，如何找出最快遍历所有城市的路线？节点可以重复。
进一步，最快遍历所有大陆上省会城市的路线？
再进一步，根据目前时刻表，给出实际经过所有大陆省会城市的最快的车次安排？
我想试一把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.* - 标准的图论题目，挺简单的呀，网上绝对有现成的方案，就是需要自己初始化一下信息
【 在 shire 的大作中提到: 】
: 看这个图，如何找出最快遍历所有城市的路线？节点可以重复。
: 进一步，最快遍历所有大陆上省会城市的路线？
: 再进一步，根据目前时刻表，给出实际经过所有大陆省会城市的最快的车次安排？
: ...................
--
FROM 116.233.22.* - 嗯，应该不太难，不过很久不编程了，主要会VC++，还需要搭建编译环境。
excel里的vb，倒是可以随时开始，不用再搭建环境。
有没有什么简单好上手的工具，介绍一下？
- 来自 水木社区APP v3.4.1
【 在 lby20180710 的大作中提到: 】
: 标准的图论题目，挺简单的呀，网上绝对有现成的方案，就是需要自己初始化一下信息
--
FROM 124.64.16.* - 啊？我一直都是用C和C++，在linux下开发的，如果你是在windows下搞，安装一下vs 2020就可以了
如果觉得c、c++不好用，就用python，这个上手快
【 在 shire 的大作中提到: 】
: 嗯，应该不太难，不过很久不编程了，主要会VC++，还需要搭建编译环境。
: excel里的vb，倒是可以随时开始，不用再搭建环境。
: 有没有什么简单好上手的工具，介绍一下？
: ...................
--
FROM 116.233.22.* - https://www.baeldung.com/cs/shortest-path-visiting-all-nodes
【 在 shire 的大作中提到: 】
: 看这个图，如何找出最快遍历所有城市的路线？节点可以重复。
: 进一步，最快遍历所有大陆上省会城市的路线？
: 再进一步，根据目前时刻表，给出实际经过所有大陆省会城市的最快的车次安排？
: ...................
--
FROM 213.95.148.* - 查了一下，这个居然是个经典的NPC算法，大陆三十个省会城市，似乎算不出来
不算拉萨乌鲁木齐
复杂度是O(30！)
第二个算法没看懂
【 在 moudy (moudy) 的大作中提到: 】
: https://www.baeldung.com/cs/shortest-path-visiting-all-nodes
--
FROM 116.52.95.* - NP问题，这么多节点，用标准算法一般电脑搞不定
可以先按出入度把有欧拉环路的子图分割出去
然后找子图间的最短连接
【 在 lby20180710 的大作中提到: 】
: 标准的图论题目，挺简单的呀，网上绝对有现成的方案，就是需要自己初始化一下信息
:
: 【 在 shire 的大作中提到: 】
: ....................
--
FROM 117.136.38.* - Python太慢。
【 在 lby20180710 的大作中提到: 】
: 啊？我一直都是用C和C++，在linux下开发的，如果你是在windows下搞，安装一下vs 2020就可以了
: 如果觉得c、c++不好用，就用python，这个上手快
:
: ....................
--
FROM 117.136.38.* - 太复杂，还有简单点的局部最优解吗？
【 在 finlab (挨踢卢瑟) 的大作中提到: 】
: NP问题，这么多节点，用标准算法一般电脑搞不定
: 可以先按出入度把有欧拉环路的子图分割出去
: 然后找子图间的最短连接
: ...................
--
FROM 123.116.132.* - 大神能不能编个程序算算？
- 来自 水木社区APP v3.4.1
【 在 finlab 的大作中提到: 】
: Python太慢。
--
FROM 123.116.132.*