数学建模社区-数学中国
标题:
关于弗洛伊德算法发现的怪现象
[打印本页]
作者:
释永思
时间:
2016-4-21 17:00
标题:
关于弗洛伊德算法发现的怪现象
关于弗洛伊德算法发现的怪现象：
' x% K* I, c: o/ q/ U" `
2 M1 M; U) h. a, J
我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
Y5 X0 K# T7 k* m) R
原来的弗洛伊德算法是：
9 j3 K7 d( ^6 p; ]
For k:=1 to n
# x5 \! t, o# K- Y2 G0 R. r
For i:=1 to n
" F+ K$ B: B/ o3 u
For j:=1 to n
5 |( x/ V4 W: J( u6 n0 S3 k# P
If D[i,j]>D[i,k]+D[k,j] Then D[i,j]:=D[i,k]+D[k,j];
3 m* Z. V) X4 j9 ?& G
我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
2 S) _ a2 Y9 w, F/ U5 ^
For j:=1 to n
* T/ ~4 Y( j, w0 D" V9 C! s" ~
For i:=1 to n
+ V# L }7 `2 x& m: Q- D8 R
For k:=1 to n
) Y! w8 r: K4 @" A+ U) K0 ~% E
If D[i,j]>D[i,k]+D[k,j] Then D[i,j]:=D[i,k]+D[k,j];
$ F- z: U: O1 t" F; I; N
我再改成如下形式，结果仍是正确的：
1 l3 k. ]8 b* B" O( {
For j:=1 to n
$ P6 U E; F6 c: a
For i:=1 to j-1
; o: y% m8 S: w: [7 U
For k:=1 to n
2 D1 w1 k- k7 g- K
If D[i,j]>D[i,k]+D[k,j] Then D[i,j]:=D[i,k]+D[k,j];
7 ?3 P9 L9 y. R# b* x+ K
如果我改成如下形式，结果出错，不行了：
9 q0 A' c. Q5 X$ ^
For j:=1 to n
3 K$ U+ Q% `2 }. z9 v
For i:=j+1 to n
v; L' J. l& d% K) B5 [
For k:=1 to n
( } I1 l* Z) k$ R
If D[i,j]>D[i,k]+D[k,j] Then D[i,j]:=D[i,k]+D[k,j];
, ]0 j, r/ l% e: o& ~+ O
无法证明，只能用具体值来代入验证。
6 Y. o0 ]/ V! x2 ]4 ?0 f/ d" t6 w
! Q2 Y8 [- f& h4 T/ T% Y1 d) x
( |! @0 A9 g1 b% H9 w
欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)
Powered by Discuz! X2.5