数学建模社区-数学中国
标题: 最短路径算法之燃线法 [打印本页]
作者: 释永思 时间: 2016-3-28 08:22
标题: 最短路径算法之燃线法
本帖最后由 释永思 于 2016-4-1 10:34 编辑 9 ]: f# V8 u9 n9 U+ p# Y
R' }, S2 f( ^* d$ T; I
最短路径算法之燃线法
D- p2 m" G3 x; ~$ r+ C- m. w最短路径算法，有迪杰斯特拉算法，有弗洛伊德算法等多种方法，这里介绍一种作者新想出来的算法：燃线法。
设想连接各个顶点的是一条条燃线，在起点用火柴点燃，燃线以匀速直线运动，遇到顶点后以匀速直线运动扩散开去，这样，最先到达终点的，就是最短路径。
以这样简单的思想为基础，作者开发成了小软件，截图如下：
===不好意思，以前打字打错了，不是匀变速直线运动，是匀速直线运动，多打一个变字，就令人不知什么意思，不好意思- j% z/ c6 Z+ O" O/ \2 c0 ?2 f
1 K+ J- @; n# q+ F/ \' u, M; H/ y$ }7 k' {5 |' n
最短路算法小软件EXE1.0.rar
(1.1 MB, 下载次数: 8)
/ ~4 ^" \' e+ X' @2 w# T" I I' u* o
( ?5 V8 q- [+ n! ]" O. g
0 k7 e% ~1 ?5 u4 h( w
/ u6 D. d( {' H# i; e' T
作者: 释永思 时间: 2016-4-1 12:01
本帖最后由 释永思 于 2016-4-2 15:52 编辑
' V+ e4 Q! P, p
S9 X8 b4 h; h7 G. D关于经过起点S和终点E一定要中途经过P1,P2,P3，，，Pn个点的最短路径的算法。/ G% _6 A' I- w3 b8 V6 B1 w
可以把N个中途点排序，在所有排序中，求出最短路径。! k' r( m! r; E% J m
至于连接任两点的最短路径，则以弗洛伊德算法求出，或以燃线法求出来，代入排序中就行。* {+ v# d' T- `9 d- |9 z- v
这是我偶然想到的算法。4 A# F# y9 y5 H n: [8 H
% t3 Q" A& E$ n* K) }4 X与哈密顿回路可能不同处在于可以重复顶点乎
: o5 M$ F2 m% \; ^. _# m
( s9 Y) E' a, `1 X3 K其实是TSP问题，要用到退火算法，遗传算法，蚁群算法之类，已不是单纯的最短路径算法了。
Y3 B# o4 M% }/ o' b
作者: ＆中义 时间: 2016-4-5 09:08
看看是什么东东，学意义
, K$ R& h) e' A- |8 \6 m% Q
作者: 洪洞大槐树 时间: 2016-4-5 23:08
不错，可以% Q* e. J# P5 \- \3 K. U
作者: 永久的平常心 时间: 2016-4-13 10:35
$ I7 e# h% L2 \! v' v, d楼主，挺有想法，能把算法分享一下？？
! d8 M+ O0 v! H# X% u
作者: 释永思 时间: 2016-4-13 11:24
永久的平常心 发表于 2016-4-13 10:35 
' Q* {* v! e5 ^2 D- F) M
楼主，挺有想法，能把算法分享一下？？
算法太简单，我不是三两句话就说完了吗，就是这么简单的，简易，变易，不易：- V5 ?& Z/ a; Y/ j9 ~5 j6 F v
设想连接各个顶点的是一条条燃线，在起点用火柴点燃，燃线以匀速直线运动，遇到顶点后以匀速直线运动扩散开去，这样，最先到达终点的，就是最短路径。
- l- M) D" i+ F! G5 ^# ~/ \
| 欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) |
Powered by Discuz! X2.5 |