- 在线时间
- 138 小时
- 最后登录
- 2018-11-1
- 注册时间
- 2015-8-26
- 听众数
- 13
- 收听数
- 0
- 能力
- 0 分
- 体力
- 366 点
- 威望
- 0 点
- 阅读权限
- 30
- 积分
- 146
- 相册
- 0
- 日志
- 0
- 记录
- 0
- 帖子
- 70
- 主题
- 23
- 精华
- 0
- 分享
- 0
- 好友
- 17
升级   23% TA的每日心情 | 难过 2016-5-14 14:04 |
|---|
签到天数: 18 天 [LV.4]偶尔看看III
- 自我介绍
- 软件开发工程师
 |
本帖最后由 释永思 于 2015-9-23 16:16 编辑
9 }6 O5 p, |; ^! Q$ f
1 N2 E! @7 G5 m# R最短路径算法的弗洛伊德算法的数学归纳法冥想证明 Version 1.0. j$ m1 Y# P6 ?( {
) @, [( j% N- r$ t5 v- l0 |4 u" a3 k# q
作者:李均宇(李恒星) 2015.09.070 o$ ^1 P+ B2 f6 p* e
9 h+ [2 S' N1 A3 D5 R
我二十年前已了解迪杰斯特拉算法,最近忽有兴趣开发了一款最短路径算法小软件EXE,了却二十年前的心愿。余庆未了,网上了解了还有多种方法,如A-Star,johnson,bellman,SPFA等算法,其中最感兴趣的是弗洛伊德算法。百度了,看了很多源码,大同小异。但对弗洛伊德算法原理,网上讲的,我看后也觉似懂非懂。利用抗战70周年纪念日放假期间,我闭关冥想,想到了N步的方法,但冥想出来的源码,总比网上讲的多一层循环。于是继续冥想,想到了要用数学归纳法来证明弗洛伊德算法。百度下,好似网上暂没这方面资料,于是共享出来,与诸君分享,不知对错也,网上讲到的什么迭代法,总是不太对似的,弗法可能并没有这么简单的:
0 |. {5 R6 ~: N% V$ b( T; N4 U假设顶点数为N,
) p& D2 z" b- H9 ?- e N=4,5,6时,具体的弗法正确性,我就不想验证了。, d' R! @9 k1 W9 Z
假设N<=n时,弗法是正确的,如何证明N=n+1时,弗法仍是正确的?! }4 Z) R& }5 D, g' W
先研究下N=n弗法正确时的特性。5 g. Y6 ^7 y* v, T+ p
N=n时,所有的n个顶点两两组合的边D[i,j],不论虚边实边(直接的称实边,要通过其他顶点的叫虚边,我如此定义先),全部有值,且为最小值最短路径。N<n时,也就是最外层循环,每到一个值K时,此值K的弗法全是正确。; x4 Q6 ^) |/ X f" a
当N=n+1时,新加一点,称最后一点K。
U0 Z/ @) t% y1 a9 K7 j) D令最后一点K总在循环中排在最后一位,三重循环中都是排在最后一位。/ q/ b( \* E& p8 E$ h
令最外层循环为k,中间层循环为j,最内层循环为i。
9 r. e2 q- b, Y- Z定理一:
* Y! _' V9 A- g/ ?: G, E' r5 U 最后一点k若改变i与j之距D[i,j],则所有经过i与j之最短路必同步更新且不分先后。8 Q0 f! v3 r! M& N& p
证明:
# F" X! C- m- l0 c% f 假设点x经过最短路径D[i,j],D[i,x]=D[i,j]+D[j,x]或D[i,x]=D[i,j]-D[j,x]。. i$ b ~1 |0 _$ v7 H
D[i,j]已被替换成为了D[i,k]+D[j,k],而D[j,k]+D[j,x]>=D[k,x]或D[j,k]+D[j,x]>=D[k,x].
9 q. a b! j. O所以D[i,x]>=D[i,k]+D[k,x],所以x点必被更新,也就是执行松驰操作。
" Q ~. Q. h4 u, ~. l- d定理二:
! T7 r1 A% _5 c3 Z9 J 最后一点k若改变i与j之距D[i,j],则经过i与j之最短路必不经过最后一点k。( b5 @5 Z; z# P+ E B7 P
证明:7 P" ^& T) Z2 V, _# j
由定理一知,如果经过最后一点k,则D[i,k]本身要变,但正是用D[i,k]来执行松驰操作的,所以矛盾。2 n6 @9 D% O! W* j0 }) J
* F; }" c7 V) l3 u1 [5 C
定理四:
\9 W5 X; |9 G0 d! K+ J 最后一点k与任一点之连线D[i,k]或D[j,k]必非无穷大,即必已连接(不论虚边实边)。1 h5 s% m& @5 A' f- N0 e
证明:; J9 Y7 k! t1 ?) G3 B
k为最内层循环点最后一位。取i,j最小者位于中间层循环,最大者位于最外层循环。
9 {; N9 I& E- P1 f8 X3 M' W" u此为max(i,j)<n之弗法,弗法已假设N<=n时全成立,现在求证N=n+1时情况。
3 J. U8 E+ W5 v/ P9 J I; q1 a6 z可知i,j必连通,即D[i,j]必非无穷大。9 g) F# d) [, b1 }3 v9 Q
D[i,k],D[j,k]两个不可能都是无穷大,这可以取min(i,j)来递归而知,min迭代到一条实边则可止,或本身数学归纳法内部要嵌套另一个数学归纳法来证明其中小引理。7 n, \# T/ }' u8 |
即知D[i,k],D[j,k]必有一个是连通的,D[i,j]也是连通的,从而三点必全连通,必非无穷大。% l" o W( Z& y& j
定理五:" z9 t) ^ B8 a8 ^/ s) |5 S2 C) v
与k相连已经全是最短路。
* @: q, n3 F2 N: H; s3 A) B2 D# Y证明:
* {0 j5 z- V% l8 l' | 因为与最后一点k相连的,全部没有变动,全部已非无穷大,所以经过k点的必是最短路。
0 [6 P$ ]: q7 B9 c2 `7 K
' ^* p6 E( q: g* ], X所以新增一点k,由定理五知,当最外层循环到最后一位k时,所有经过k点的已是最短路。 [8 Z8 Y$ m. ]' ?9 q
所有对原来N=n时的弗法最短路的调整松弛操作,全能同步更新经过相关点的最短路,也就是原来的n个点的弗法,后来仍是最短路。
7 i) \0 Y% r0 }! p; u8 I5 a+ i则N=n+1时,全部三重循环后,全部仍是最短路。
! r5 \2 x. a$ [1 r/ \& \/ }& g由数学归纳法知,三重循环的弗洛伊德算法是正确的。: X D0 p6 x! `1 X# x
///////////////////////////////////////////////////////////////////////////////////////) G0 U" ^, ]; A5 w# K
关于弗洛伊德算法的新证明:2015.09.23
~/ ^, W6 P& W3 O
; u- F I' X1 I经过弗法的三重循环后,任意两点之间的距离已是最短路。
' K6 d6 g" x+ {# ]8 J仍用数学归纳法,假设N <= n时,弗法是正确的,要证明,N = n+1时,弗法仍是成立的。
% C( @( x) ?& I, A I设k = n+1是最后一点。" v O p! D" L @
如果任意两点间的最短路径结过的顶点数是小于k的,那么根据假设知弗法正确是最短路的。' F1 j: X1 Y- @+ |& r+ P+ C
如果任意两点间的最短路径结过的顶点数是等于k的。那么知摘去最后3个顶点即只剩下(k-3)个点时,是N <= n的情形。$ N( Z- d. |7 x# q0 P
起点是a点,终点是b点,与k点直接相连的是c点,d点 。& G$ g8 y H2 _
当最外层第三重循环循环到最后三点k,c,d时,ac,bd已经连通了是N <= n的弗法情形。
6 j+ g' G& ~4 Kk,c,d三点,无论哪个是先是后的组合,都必定能够令ab连通且最短路。8 W2 e! W B3 w
例如k点连通cd,c点连通ad,d点连通ab。
; M* F; j. i$ {, |' [# j5 c又如c点连通ak(ck不用c点连通,因为原始边长早已有数值早已连通),k点连通ad,d点连通ab。; {$ e' h: V L
所以命题得证。 s/ y U. ~; u7 y5 a) B1 P
- ~6 c, l* c$ D0 l/ V
5 u% \) \! ]5 u E% ~1 j. L/ J3 X. f& v% k
7 f& E. I" e3 _/ x
! ]7 V! ^. R A' d$ a5 ?' |; S6 D5 A. `$ O3 B
% A& j! }* c" P: R' y; [8 g2 k
4 X" T% x v z% a# X* r; Q5 p. @( F+ I3 K/ J
& o! [# f7 }; M- m( R
) [; q: _* [) g: @7 P0 O0 i! o' ?. K$ P
]: K, }+ A! p0 n0 N+ x9 `
0 c& \& v; O7 Y! [- D5 n2 o" d0 `. U4 Y1 C
6 ^7 c- s4 M- n5 C; v* u0 i+ _; K3 D* x/ _3 n
6 N9 w& Q' X; ]: m/ M! ]' H, l7 ]
6 f s5 P5 D9 w6 `0 X9 M2 F6 F
0 n, P- ]% Q# y5 n3 U d( N% r; ~, A
f. |9 I5 y u7 k |
zan
|