- 在线时间
- 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
- 自我介绍
- 软件开发工程师
 |
关于弗洛伊德算法发现的怪现象:
, |- V7 o) g! K2 N6 Z8 w; _
$ R. I0 K; a( W; y2 v( |8 m我在用实际顶点代入验证的基础上证实如下现象,无法用理论解释,个人感到弗洛伊德算法象哥德巴赫猜想一样,无法证明的。4 r7 j5 a2 J: r. _" f& g" G& P" x
原来的弗洛伊德算法是:
" {+ L% Y% B4 D. \For k:=1 to n
) V9 V6 L2 ~4 r! \9 x$ N9 }' dFor i:=1 to n+ K6 T! V& c: X9 B! l0 ?' h
For j:=1 to n
' ^: O+ i1 H5 R7 v( hIf D[i,j]>D[i,k]+D[k,j] Then D[i,j]:=D[i,k]+D[k,j];
% X6 d) @, Z" h2 u) M6 l我改成下面的形式,结果具体值代入仍是正确的,当然无法证明:8 S1 y$ t1 O% h+ D* s
For j:=1 to n$ P5 [- d$ x% d1 V1 D% x
For i:=1 to n
1 ?8 p$ `% R1 G0 Q( g3 a+ HFor k:=1 to n
4 }! D2 x1 o8 A; |( jIf D[i,j]>D[i,k]+D[k,j] Then D[i,j]:=D[i,k]+D[k,j];
8 S' _" K: Y; h: O9 C& H9 h我再改成如下形式,结果仍是正确的:
# e5 X# E" `2 L' HFor j:=1 to n( ^, P9 ?6 Q+ B$ h5 V
For i:=1 to j-15 y" c, p* Y: G3 b* Y
For k:=1 to n
: J( m: o3 y' }If D[i,j]>D[i,k]+D[k,j] Then D[i,j]:=D[i,k]+D[k,j];
& p" ]' ]- S+ B! e如果我改成如下形式,结果出错,不行了:1 q5 Q& b! X0 l, g' {) _
For j:=1 to n
0 S- T9 Q8 M5 p$ c7 v0 {) vFor i:=j+1 to n" @6 R1 p8 v5 S
For k:=1 to n! p0 H! B5 _6 H3 a" R9 \
If D[i,j]>D[i,k]+D[k,j] Then D[i,j]:=D[i,k]+D[k,j];7 Z3 s. q! I- d
无法证明,只能用具体值来代入验证。
/ m! y6 |" ^5 W/ S7 D
/ o" c/ w G/ ]" v" E/ u* n7 Y% P) Z) v9 }+ Y3 a
|
zan
|