数学建模社区-数学中国

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

---

作者: 释永思    时间: 2016-4-21 17:00
标题: 关于弗洛伊德算法发现的怪现象
关于弗洛伊德算法发现的怪现象：

我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
3 s7 ]2 m& ?( x" N& A" D# P原来的弗洛伊德算法是：
For k:=1 to n
3 P# [0 z- \6 F9 ~  ?For i:=1 to n
  @$ R: B0 m$ T  C2 i' s: |For j:=1 to n
5 W! w& O3 f7 _) R6 A1 wIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
# B$ \+ R( s" Q( g4 Q' Z我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
* i: {1 L9 Z" I9 f- @+ g* LFor j:=1 to n
7 J3 R% ~! Y  b; \1 D2 uFor i:=1 to n
# D8 _+ H; G% t2 M7 [! j9 t! ]9 o  dFor k:=1 to n
$ _2 A) b& `# u8 P( A+ i  kIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
0 o$ U9 K/ y% p2 X7 d' d. w我再改成如下形式，结果仍是正确的：
9 V0 F  J# Q! S4 M- nFor j:=1 to n
" T+ N. u) M+ e9 x. i/ A8 ]& mFor i:=1 to j-1
) @  ~: `# Q& S' z2 a& c% E8 @6 CFor k:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
% w( j6 W. z2 `8 K* G如果我改成如下形式，结果出错，不行了：
For j:=1 to n
( t* @: D8 M# m/ n4 r9 D4 `For i:=j+1 to n
5 t. O9 v- [$ O6 FFor k:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
无法证明，只能用具体值来代入验证。
" |# `8 ~8 o% f9 R" O: p) M
& ~" S$ l7 z' P" Q5 C& L/ ~

---

欢迎光临 数学建模社区-数学中国 (http://www.madio.net/)

Powered by Discuz! X2.5