数学建模社区-数学中国
标题: 最短路径算法之燃线法 [打印本页]
作者: 释永思 时间: 2016-3-28 08:22
标题: 最短路径算法之燃线法
本帖最后由 释永思 于 2016-4-1 10:34 编辑 $ \% F o, v4 b+ }, f
. M& Z# w/ E h; d1 j! E最短路径算法之燃线法
* W1 V0 T% Q6 P* C# O# p: h最短路径算法，有迪杰斯特拉算法，有弗洛伊德算法等多种方法，这里介绍一种作者新想出来的算法：燃线法。
设想连接各个顶点的是一条条燃线，在起点用火柴点燃，燃线以匀速直线运动，遇到顶点后以匀速直线运动扩散开去，这样，最先到达终点的，就是最短路径。
以这样简单的思想为基础，作者开发成了小软件，截图如下：
===不好意思，以前打字打错了，不是匀变速直线运动，是匀速直线运动，多打一个变字，就令人不知什么意思，不好意思. [- ~" E$ v2 x( C
2 ~) c+ M6 a) M! j# }0 I+ |* t/ k" f& @& M
最短路算法小软件EXE1.0.rar
(1.1 MB, 下载次数: 8)
Q0 C$ O, H3 g
5 t( y1 H! {- H( Y$ g. M
0 z! _. u2 G# P+ l
+ V7 C' }9 p" `$ T3 U& T: W
作者: 释永思 时间: 2016-4-1 12:01
本帖最后由 释永思 于 2016-4-2 15:52 编辑 ; f1 H4 A& { p1 D/ Z! t, d
9 ~+ p, G% ]' ^5 p# e% l关于经过起点S和终点E一定要中途经过P1,P2,P3，，，Pn个点的最短路径的算法。5 z. N- ?1 K. I7 d! A
可以把N个中途点排序，在所有排序中，求出最短路径。
- j; R( ^# H8 P$ [# O至于连接任两点的最短路径，则以弗洛伊德算法求出，或以燃线法求出来，代入排序中就行。+ R9 \' S& t$ q+ I3 X, S
这是我偶然想到的算法。- Y0 i7 B# M2 w
3 r4 [! v2 I7 C% Z1 E
与哈密顿回路可能不同处在于可以重复顶点乎
9 a- b( |2 ]" M- i+ ^' z$ Y, r6 i: k m' l
其实是TSP问题，要用到退火算法，遗传算法，蚁群算法之类，已不是单纯的最短路径算法了。" A8 p$ L c4 g l$ ~/ y4 I
作者: ＆中义 时间: 2016-4-5 09:08
看看是什么东东，学意义
" h! d- K( |& w. o7 n" Y
作者: 洪洞大槐树 时间: 2016-4-5 23:08
不错，可以
: w5 s5 |7 \$ B
作者: 永久的平常心 时间: 2016-4-13 10:35
: t' Y6 l$ O. d$ I
楼主，挺有想法，能把算法分享一下？？
) F! U5 w ~9 k9 O) U* U) w, \ A
作者: 释永思 时间: 2016-4-13 11:24
永久的平常心 发表于 2016-4-13 10:35 
# K5 g& {$ n' J楼主，挺有想法，能把算法分享一下？？
算法太简单，我不是三两句话就说完了吗，就是这么简单的，简易，变易，不易：
P' P2 `& c( ~ D设想连接各个顶点的是一条条燃线，在起点用火柴点燃，燃线以匀速直线运动，遇到顶点后以匀速直线运动扩散开去，这样，最先到达终点的，就是最短路径。
" k& E& J B4 ^* V2 _* P: W" W
| 欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) |
Powered by Discuz! X2.5 |