数学建模社区-数学中国
标题: 最短路径算法之燃线法 [打印本页]
作者: 释永思 时间: 2016-3-28 08:22
标题: 最短路径算法之燃线法
本帖最后由 释永思 于 2016-4-1 10:34 编辑 0 h* F: d7 j# ?+ k, r
/ A( \" R! G3 d. m& W+ w
最短路径算法之燃线法
3 ` Q& P& C* q- N; }' }最短路径算法，有迪杰斯特拉算法，有弗洛伊德算法等多种方法，这里介绍一种作者新想出来的算法：燃线法。
设想连接各个顶点的是一条条燃线，在起点用火柴点燃，燃线以匀速直线运动，遇到顶点后以匀速直线运动扩散开去，这样，最先到达终点的，就是最短路径。
以这样简单的思想为基础，作者开发成了小软件，截图如下：
===不好意思，以前打字打错了，不是匀变速直线运动，是匀速直线运动，多打一个变字，就令人不知什么意思，不好意思
; A' E h9 i9 s
# r2 T M; c7 x) n' O, a+ F
) L3 ]8 ~5 K$ c5 c" @
最短路算法小软件EXE1.0.rar
(1.1 MB, 下载次数: 8)
; k9 l: q: D# k" t$ s6 b M+ \; L
( ^+ G6 k; [7 |# A& C. X
' v1 O) w' x3 Q( U; z d4 x' i! j2 e9 @9 Y. a$ `
作者: 释永思 时间: 2016-4-1 12:01
本帖最后由 释永思 于 2016-4-2 15:52 编辑 , [ \1 d, ]# j% I/ P8 `
9 S% R- t" _$ ? ~关于经过起点S和终点E一定要中途经过P1,P2,P3，，，Pn个点的最短路径的算法。
0 v; A' z d6 n可以把N个中途点排序，在所有排序中，求出最短路径。
7 \" m3 E5 S9 w: U6 A至于连接任两点的最短路径，则以弗洛伊德算法求出，或以燃线法求出来，代入排序中就行。
) V, v0 \3 V) L4 `- ~4 n这是我偶然想到的算法。
4 R+ I3 M/ z! h5 q, P; f5 t0 V
与哈密顿回路可能不同处在于可以重复顶点乎( R- f6 J2 G9 S" k' K z
e5 e/ `# o; v2 u
其实是TSP问题，要用到退火算法，遗传算法，蚁群算法之类，已不是单纯的最短路径算法了。- e( z4 g4 f- B3 W
作者: ＆中义 时间: 2016-4-5 09:08
看看是什么东东，学意义
X& L/ t2 @4 O1 Z, q
作者: 洪洞大槐树 时间: 2016-4-5 23:08
不错，可以) g9 o8 A; Z7 c- X$ j7 J
作者: 永久的平常心 时间: 2016-4-13 10:35
+ Y) u, v: U2 g; J3 P3 J& ?& `' `楼主，挺有想法，能把算法分享一下？？7 x8 B( K3 G& c7 K4 G# d: q
作者: 释永思 时间: 2016-4-13 11:24
永久的平常心 发表于 2016-4-13 10:35 
$ Z, ?5 t& W; A. w$ i7 O楼主，挺有想法，能把算法分享一下？？
算法太简单，我不是三两句话就说完了吗，就是这么简单的，简易，变易，不易：% p/ P( S+ s4 q
设想连接各个顶点的是一条条燃线，在起点用火柴点燃，燃线以匀速直线运动，遇到顶点后以匀速直线运动扩散开去，这样，最先到达终点的，就是最短路径。9 U7 ?4 }2 h; ?; }* @7 f; ~
| 欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) |
Powered by Discuz! X2.5 |