数学建模社区-数学中国
标题: 最短路径算法之燃线法 [打印本页]
作者: 释永思 时间: 2016-3-28 08:22
标题: 最短路径算法之燃线法
本帖最后由 释永思 于 2016-4-1 10:34 编辑 8 k* {2 O* |9 b3 K, e' g
6 u* q/ J% y( N6 G4 p3 I0 T3 J
最短路径算法之燃线法
& l j" R! Z) d) c6 S最短路径算法，有迪杰斯特拉算法，有弗洛伊德算法等多种方法，这里介绍一种作者新想出来的算法：燃线法。
设想连接各个顶点的是一条条燃线，在起点用火柴点燃，燃线以匀速直线运动，遇到顶点后以匀速直线运动扩散开去，这样，最先到达终点的，就是最短路径。
以这样简单的思想为基础，作者开发成了小软件，截图如下：
===不好意思，以前打字打错了，不是匀变速直线运动，是匀速直线运动，多打一个变字，就令人不知什么意思，不好意思
6 e# ]; w s4 L! v! ^
' w4 L, ~/ X+ W4 E
- Q1 z& W# o% }3 h
最短路算法小软件EXE1.0.rar
(1.1 MB, 下载次数: 8)
0 o8 j/ t$ r" U9 @: ^2 F4 y# p
& t# g7 R$ G; c
3 [. P) \/ _8 s/ T7 v2 r/ N
! ^8 i# t% e; z: [) L
作者: 释永思 时间: 2016-4-1 12:01
本帖最后由 释永思 于 2016-4-2 15:52 编辑 9 u5 B/ p5 C% l( o# ?
+ ?* M, {3 C& \
关于经过起点S和终点E一定要中途经过P1,P2,P3，，，Pn个点的最短路径的算法。! E; \; q% U5 B ^* M
可以把N个中途点排序，在所有排序中，求出最短路径。
& ^: p5 E9 h" N) ~( d3 |至于连接任两点的最短路径，则以弗洛伊德算法求出，或以燃线法求出来，代入排序中就行。
6 [. \( V$ C4 Y* Q这是我偶然想到的算法。; I2 ~) m7 S( M* N* e
, T/ ^3 E; ^! [2 H5 w% Q$ G5 O" S与哈密顿回路可能不同处在于可以重复顶点乎! f, ~* r/ G: ~" {, k! l$ x2 A
5 ~ }3 v# p% p9 m$ Y其实是TSP问题，要用到退火算法，遗传算法，蚁群算法之类，已不是单纯的最短路径算法了。 c0 e7 j; I/ ]' J$ X; c/ @
作者: ＆中义 时间: 2016-4-5 09:08
看看是什么东东，学意义
8 V0 i' n- ~3 n
作者: 洪洞大槐树 时间: 2016-4-5 23:08
不错，可以1 S7 F7 d$ m* m( l# a( z; `! C/ {
作者: 永久的平常心 时间: 2016-4-13 10:35
) O3 {. R3 a) C4 Z& J3 u8 ]6 [楼主，挺有想法，能把算法分享一下？？* B. j8 b; i' @& `8 o& U
作者: 释永思 时间: 2016-4-13 11:24
永久的平常心 发表于 2016-4-13 10:35 
% }. g9 g3 _' j楼主，挺有想法，能把算法分享一下？？
: K1 E) B4 Y1 z! N1 v% w算法太简单，我不是三两句话就说完了吗，就是这么简单的，简易，变易，不易：
9 u W, S1 P* p, r设想连接各个顶点的是一条条燃线，在起点用火柴点燃，燃线以匀速直线运动，遇到顶点后以匀速直线运动扩散开去，这样，最先到达终点的，就是最短路径。
% B: Q$ b' }* F7 k4 j
| 欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) |
Powered by Discuz! X2.5 |