数学建模社区-数学中国
标题: 最短路径算法之燃线法 [打印本页]
作者: 释永思 时间: 2016-3-28 08:22
标题: 最短路径算法之燃线法
本帖最后由 释永思 于 2016-4-1 10:34 编辑
+ T7 A$ a. g) g* Q" X* Z/ |! f! ^' V) I/ ?9 a" ^
最短路径算法之燃线法
, l# Z- Z u5 a8 U1 }, @6 l2 U! l最短路径算法，有迪杰斯特拉算法，有弗洛伊德算法等多种方法，这里介绍一种作者新想出来的算法：燃线法。
设想连接各个顶点的是一条条燃线，在起点用火柴点燃，燃线以匀速直线运动，遇到顶点后以匀速直线运动扩散开去，这样，最先到达终点的，就是最短路径。
以这样简单的思想为基础，作者开发成了小软件，截图如下：
===不好意思，以前打字打错了，不是匀变速直线运动，是匀速直线运动，多打一个变字，就令人不知什么意思，不好意思
: y8 s! E- ?4 u5 f) f
9 U; ^# `9 i8 \4 |
1 J& A/ c- a0 Q
最短路算法小软件EXE1.0.rar
(1.1 MB, 下载次数: 8)
" ?9 G9 d6 S& k+ K# E" z; C' h- c$ o
; w- ~: v$ x+ N9 {; z1 R3 e: W/ t4 b% J, u6 I
作者: 释永思 时间: 2016-4-1 12:01
本帖最后由 释永思 于 2016-4-2 15:52 编辑 ' F4 b$ w1 r+ o+ V1 U) a8 L
$ i: K. o6 D$ g. }) t: h- K
关于经过起点S和终点E一定要中途经过P1,P2,P3，，，Pn个点的最短路径的算法。" R1 J7 W* z6 m0 v3 k
可以把N个中途点排序，在所有排序中，求出最短路径。
6 x8 }6 c3 L0 o7 U R" J至于连接任两点的最短路径，则以弗洛伊德算法求出，或以燃线法求出来，代入排序中就行。
2 B& Y0 Z4 T- I2 F: ~! O8 L; F这是我偶然想到的算法。9 O8 [6 [; V' i! J
: C% r8 B7 W. c6 l2 `# ?' K2 h与哈密顿回路可能不同处在于可以重复顶点乎
, n$ b+ ^. m( C, ]6 f S5 B- q D, a- w& ?3 _
其实是TSP问题，要用到退火算法，遗传算法，蚁群算法之类，已不是单纯的最短路径算法了。# x) H; L w2 o* e
作者: ＆中义 时间: 2016-4-5 09:08
看看是什么东东，学意义
+ z: ^ @8 u; y' `' Y3 I: S
作者: 洪洞大槐树 时间: 2016-4-5 23:08
不错，可以
; H! `! S j' z9 O* ?( M3 l; Z5 y
作者: 永久的平常心 时间: 2016-4-13 10:35
0 y4 g" z& j9 J4 D9 f楼主，挺有想法，能把算法分享一下？？. }% E8 K; S# ?4 R
作者: 释永思 时间: 2016-4-13 11:24
永久的平常心 发表于 2016-4-13 10:35 
4 l. Y0 e' K; L
楼主，挺有想法，能把算法分享一下？？
算法太简单，我不是三两句话就说完了吗，就是这么简单的，简易，变易，不易：4 ?+ E* y* K3 n! p- U- i6 o( E
设想连接各个顶点的是一条条燃线，在起点用火柴点燃，燃线以匀速直线运动，遇到顶点后以匀速直线运动扩散开去，这样，最先到达终点的，就是最短路径。
- f. y0 E& Z+ X. ?
| 欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) |
Powered by Discuz! X2.5 |