数学建模社区-数学中国
标题:
关于弗洛伊德算法发现的怪现象
[打印本页]
作者:
释永思
时间:
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& c
For 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 n
2 G( d( [4 d5 @. Q
For k:=1 to n
$ \, e1 m$ g9 T" ?3 i4 V9 G
If 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 h
For i:=1 to j-1
- _% [' X% T0 e9 n
For 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 C
For i:=j+1 to n
s2 T6 _! k" ~0 K) n2 K
For k:=1 to n
8 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