数学建模社区-数学中国
标题: 最短路径算法之燃线法 [打印本页]
作者: 释永思 时间: 2016-3-28 08:22
标题: 最短路径算法之燃线法
本帖最后由 释永思 于 2016-4-1 10:34 编辑
, `8 p$ k* z7 L3 p1 x5 X$ m
9 T, m: A7 j$ ?) x最短路径算法之燃线法
( u0 c. {' D# V) Z" E' @最短路径算法，有迪杰斯特拉算法，有弗洛伊德算法等多种方法，这里介绍一种作者新想出来的算法：燃线法。
设想连接各个顶点的是一条条燃线，在起点用火柴点燃，燃线以匀速直线运动，遇到顶点后以匀速直线运动扩散开去，这样，最先到达终点的，就是最短路径。
以这样简单的思想为基础，作者开发成了小软件，截图如下：
===不好意思，以前打字打错了，不是匀变速直线运动，是匀速直线运动，多打一个变字，就令人不知什么意思，不好意思
$ B; R: Y6 U `0 V6 C) |
% c( D$ t/ O2 c, T
! m! }: O/ \) ?3 x, r& F3 U6 ]* j
最短路算法小软件EXE1.0.rar
(1.1 MB, 下载次数: 8)
) ]3 l. B- j2 {. ^3 X- |9 U, F$ z% a& j, @; e
# O P3 Q, N- z5 w R) R/ b
. P$ N2 \) }9 J3 F0 H
作者: 释永思 时间: 2016-4-1 12:01
本帖最后由 释永思 于 2016-4-2 15:52 编辑
7 A' X" }! ^; P+ x2 i k* f( X7 m# @" v: F1 K+ Y
关于经过起点S和终点E一定要中途经过P1,P2,P3，，，Pn个点的最短路径的算法。3 M/ r0 Q P) o8 o# N7 u' p P
可以把N个中途点排序，在所有排序中，求出最短路径。
, l9 f0 d, F& J5 z C9 }. |至于连接任两点的最短路径，则以弗洛伊德算法求出，或以燃线法求出来，代入排序中就行。
4 [/ N% J/ C( X3 i! _这是我偶然想到的算法。
+ h7 l0 z- m4 m" C8 Z. `6 j/ u n6 b/ _: ^
与哈密顿回路可能不同处在于可以重复顶点乎/ ]* l% T3 u3 d: B4 s. A2 f1 q' A
% s& [8 d: d, i P3 V+ r, g( m
其实是TSP问题，要用到退火算法，遗传算法，蚁群算法之类，已不是单纯的最短路径算法了。
& q0 [. I9 X7 N% H6 `* q
作者: ＆中义 时间: 2016-4-5 09:08
看看是什么东东，学意义8 l1 z$ Q* q3 p
作者: 洪洞大槐树 时间: 2016-4-5 23:08
不错，可以
8 p# G; ], s; r; P0 l
作者: 永久的平常心 时间: 2016-4-13 10:35
9 h: u; g2 _9 @. v; x; A- j( b
楼主，挺有想法，能把算法分享一下？？
$ ~( u! }' S6 N- A* m
作者: 释永思 时间: 2016-4-13 11:24
永久的平常心 发表于 2016-4-13 10:35 
4 ^. n8 [4 f" U8 U: m4 ]
楼主，挺有想法，能把算法分享一下？？
算法太简单，我不是三两句话就说完了吗，就是这么简单的，简易，变易，不易：
6 ?! m. L- W0 v. `9 a设想连接各个顶点的是一条条燃线，在起点用火柴点燃，燃线以匀速直线运动，遇到顶点后以匀速直线运动扩散开去，这样，最先到达终点的，就是最短路径。
: I4 N" S) |) o; x' y: [% h b: e
| 欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) |
Powered by Discuz! X2.5 |