数学建模社区-数学中国
标题: 最短路径算法之燃线法 [打印本页]
作者: 释永思 时间: 2016-3-28 08:22
标题: 最短路径算法之燃线法
本帖最后由 释永思 于 2016-4-1 10:34 编辑 0 N w- \5 c6 ]/ M2 X0 b5 { z
; B4 N, _) s4 W( R& ~4 \
最短路径算法之燃线法
3 ?6 x1 _1 v6 L
最短路径算法，有迪杰斯特拉算法，有弗洛伊德算法等多种方法，这里介绍一种作者新想出来的算法：燃线法。
设想连接各个顶点的是一条条燃线，在起点用火柴点燃，燃线以匀速直线运动，遇到顶点后以匀速直线运动扩散开去，这样，最先到达终点的，就是最短路径。
以这样简单的思想为基础，作者开发成了小软件，截图如下：
===不好意思，以前打字打错了，不是匀变速直线运动，是匀速直线运动，多打一个变字，就令人不知什么意思，不好意思4 w# Y. E: c- |9 h/ U) k
; U6 A/ `& a7 h5 ]) M( a
3 L+ d$ K2 s. O; Z! l
最短路算法小软件EXE1.0.rar
(1.1 MB, 下载次数: 8)
* B, ]/ z, }% G8 t" \5 ]
% p) b5 U& N% ?0 e/ C/ Q- v2 [( e
0 U" x2 k+ |# H+ _9 C) @
6 O7 }/ Y. h0 z* j( Q9 R/ ~, ~/ H
作者: 释永思 时间: 2016-4-1 12:01
本帖最后由 释永思 于 2016-4-2 15:52 编辑 5 b; L9 C8 T% Z1 R) n+ ]- Q
) h) z# O! N* ?( r" s& ?. d( {
关于经过起点S和终点E一定要中途经过P1,P2,P3，，，Pn个点的最短路径的算法。4 r" a. g1 h$ _5 l
可以把N个中途点排序，在所有排序中，求出最短路径。
4 ^7 e3 m0 h8 _& m% d8 n c至于连接任两点的最短路径，则以弗洛伊德算法求出，或以燃线法求出来，代入排序中就行。* Q5 ?8 s1 {% `7 Z( v
这是我偶然想到的算法。
3 @+ c8 [- H( U( I& t& S5 q8 I' O1 v3 m A- j2 t8 X( F
与哈密顿回路可能不同处在于可以重复顶点乎
2 u. e% n; U/ i6 x
' V& _$ c: B3 e2 ~7 P. `' q8 z其实是TSP问题，要用到退火算法，遗传算法，蚁群算法之类，已不是单纯的最短路径算法了。
$ |+ r7 m2 B5 P
作者: ＆中义 时间: 2016-4-5 09:08
看看是什么东东，学意义
, n- y- |3 V. i; i' T
作者: 洪洞大槐树 时间: 2016-4-5 23:08
不错，可以
/ a2 @/ Q% p7 t5 U T" B# t8 d g
作者: 永久的平常心 时间: 2016-4-13 10:35
+ G% G* o# r, u/ l5 g
楼主，挺有想法，能把算法分享一下？？
& m" k( X2 \* J2 w8 ]
作者: 释永思 时间: 2016-4-13 11:24
永久的平常心 发表于 2016-4-13 10:35 
: I \( [0 c3 I1 {5 U0 S; E楼主，挺有想法，能把算法分享一下？？
算法太简单，我不是三两句话就说完了吗，就是这么简单的，简易，变易，不易：7 G7 q- a3 a% _) R8 s
设想连接各个顶点的是一条条燃线，在起点用火柴点燃，燃线以匀速直线运动，遇到顶点后以匀速直线运动扩散开去，这样，最先到达终点的，就是最短路径。1 r6 Q5 b4 _7 N+ D
| 欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) |
Powered by Discuz! X2.5 |