搜索
编程论坛 → 开发语言 → 『 C语言论坛 』 → 求最短路程的C程序
标题：求最短路程的C程序
只看楼主
mr6737
Rank: 1
等　级：新手上路
帖　子：1
专家分：0
注　册：2017-4-13
结帖率：0
楼主
 已结贴√  问题点数：20 回复次数：11 
求最短路程的C程序
从A处出发，按直线所示路线移动，要求必须经历所有点，最后回到A点，求最短路程，求大神用C语言编出程序，数字为路程大小。
搜索更多相关主题的帖子: C语言　
2017-04-13 21:41
寒风中的细雨
Rank: 17Rank: 17Rank: 17Rank: 17Rank: 17
等　级：贵宾
威　望：66
帖　子：1710
专家分：8645
注　册：2009-9-15
第 2 楼
 得分:3 
回复 楼主 mr6737
按提示 这个应该是求图的最小生成树？
2017-04-13 23:51
azzbcc
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来　自：江西财经大学
等　级：贵宾
威　望：81
帖　子：3293
专家分：12919
注　册：2012-11-4
第 3 楼
 得分:3 
欧拉回路还是哈密顿回路来着，忘记了


[fly]存在即是合理[/fly]
2017-04-14 09:21
NiuYoohoo
Rank: 4
等　级：业余侠客
威　望：2
帖　子：65
专家分：216
注　册：2016-10-8
第 4 楼
 得分:3 
用深度或者广度
2017-04-14 10:27
renkejun1942
Rank: 14Rank: 14Rank: 14Rank: 14
来　自：不是这样
等　级：贵宾
威　望：33
帖　子：1645
专家分：5297
注　册：2016-12-1
第 5 楼
 得分:3 
图，好深奥，完全搞不懂。

09：30 05/21 种下琵琶种子，能种活么？等待中……
21：50 05/27 没有发芽。
20：51 05/28 没有发芽。
23：03 05/29 没有发芽。
23：30 06/09 我有预感，要发芽了。
2017-04-14 11:10
yangfrancis
Rank: 16Rank: 16Rank: 16Rank: 16
等　级：贵宾
威　望：141
帖　子：1510
专家分：7661
注　册：2014-5-19
第 6 楼
 得分:3 
就是广度搜索吧
2017-04-14 18:20
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来　自：长长久久
等　级：贵宾
威　望：52
帖　子：5023
专家分：14003
注　册：2016-10-22
第 7 楼
 得分:3 
想到数学建模还要做图论PPT~还要演讲半个小时~
如果想不到更好的算法~深度搜索和广度搜索勉强可以~但感觉比较硬来~看来要学习相关算法才能优化啊~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-04-14 21:39
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来　自：长长久久
等　级：贵宾
威　望：52
帖　子：5023
专家分：14003
注　册：2016-10-22
第 8 楼
 得分:0 
按3楼的说法刚刚百度了一下欧拉回路~感觉这是一个中国邮递员问题~
这要分可以重复遍历和非重复遍历的情况~

看了一下算法思想是先找出其中一条回路并记录其权值~然后删除回路的其中一条边~再重新寻找一条新的路~
如果新路的权值比旧路的要低~则用新路取代旧路~否则则保持该状态不变~直到删除所有多余的回路~剩下的就是最优解~
具体的算法可以去百度一下~

[此贴子已经被作者于2017-4-14 22:06编辑过]


[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-04-14 22:05
marlow
Rank: 6Rank: 6
等　级：侠之大者
威　望：2
帖　子：125
专家分：419
注　册：2016-7-18
第 9 楼
 得分:3 
回复 楼主 mr6737
有点像最小代价生成树，但根据题意，没有禁止边的重复使用，到了最后点之后，还要回到原点，可改写Kruskal等算法得到此算法

一切都在学习、尝试、摸索中
2017-04-15 08:47
九转星河
Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19Rank: 19
来　自：长长久久
等　级：贵宾
威　望：52
帖　子：5023
专家分：14003
注　册：2016-10-22
第 10 楼
 得分:0 
搜索过了~哈密顿回路是一个NPC问题~即除了搜索外没有一种高效的办法~难怪我也想不到有什么好的方法~汗啊~还是老老实实搜索吧~

[code]/*~个性签名:bug是什么意思?bug是看上去没有可能的东西实际上是有可能做到的 就是这样~2018-08-08更~*/[/code]
2017-04-24 04:52



参与讨论请移步原网站贴子：https://bbs.bccn.net/thread-476098-1-1.html




关于我们 | 广告合作 | 编程中国 | 清除Cookies | TOP | 手机版

编程中国 版权所有，并保留所有权利。
Powered by Discuz, Processed in 1.105184 second(s), 8 queries.
Copyright©2004-2025, BCCN.NET, All Rights Reserved