数学建模社区-数学中国

标题: 关于弗洛伊德算法发现的怪现象 [打印本页]

作者: 释永思    时间: 2016-4-21 17:00
标题: 关于弗洛伊德算法发现的怪现象
关于弗洛伊德算法发现的怪现象:
) x$ z! l& {1 }# e9 \# Z
. s2 }6 ~; A1 e& }$ V4 Z我在用实际顶点代入验证的基础上证实如下现象,无法用理论解释,个人感到弗洛伊德算法象哥德巴赫猜想一样,无法证明的。, @8 R# o1 S# c) `! J/ B; Z4 q4 {
原来的弗洛伊德算法是:
( g8 S- e2 U3 O; M. [For k:=1 to n
2 E9 T) w3 T: h0 U: L3 X1 C& cFor i:=1 to n( |" P" C0 Q8 K# S% O8 C  A
For j:=1 to n% y9 B# g9 T( n+ K4 l# Q( e% I7 [% e- e
If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];- a9 B  Y; |: f" J2 t0 \
我改成下面的形式,结果具体值代入仍是正确的,当然无法证明:  q" y: Y1 j4 G: Q4 d& h2 b
For j:=1 to n# G* [! n% ]. ~) R( e4 ?& |9 H
For i:=1 to n2 G( d( [4 d5 @. Q
For k:=1 to n
$ \, e1 m$ g9 T" ?3 i4 V9 GIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];8 f' `6 h1 ?# h) J# z
我再改成如下形式,结果仍是正确的:( A* l$ {, z; H2 d" t, a
For j:=1 to n
: T6 Y6 L$ `& N5 k  S2 hFor i:=1 to j-1
- _% [' X% T0 e9 nFor k:=1 to n
, c! Q9 Q6 c3 d9 a5 `If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];, O, M# f  u' q% l$ o0 w0 y' N
如果我改成如下形式,结果出错,不行了:( Q8 @9 k, ~8 Q) D
For j:=1 to n
/ d3 o6 |5 z6 C3 CFor i:=j+1 to n  s2 T6 _! k" ~0 K) n2 K
For k:=1 to n8 q5 |, c4 r) r0 s# h* w6 _
If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];/ ~% Y1 a7 @+ u, K) N8 G
无法证明,只能用具体值来代入验证。7 x; a+ U7 \" K5 s- R9 e  @

6 Q' c# q  a! i. N6 U& i, |% B! b: k5 D% [, [) D* ]





欢迎光临 数学建模社区-数学中国 (http://www.madio.net/) Powered by Discuz! X2.5