数学建模社区-数学中国

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

作者: 释永思    时间: 2016-4-21 17:00
标题: 关于弗洛伊德算法发现的怪现象
关于弗洛伊德算法发现的怪现象:; v* s5 x3 g( {- D

' k+ l, Y% Y8 c- @5 F# A: M! @/ A我在用实际顶点代入验证的基础上证实如下现象,无法用理论解释,个人感到弗洛伊德算法象哥德巴赫猜想一样,无法证明的。
8 f2 W/ S$ K3 M1 W3 N5 j9 Y原来的弗洛伊德算法是:
* v& ?% ^& B: s3 U9 K, EFor k:=1 to n- _; K$ c7 o% Y# \. A
For i:=1 to n0 g: l5 z! i: @
For j:=1 to n
3 |/ h* b: `- l( ZIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];. j6 S( x+ W0 W, ?
我改成下面的形式,结果具体值代入仍是正确的,当然无法证明:
* z  Q. J  j8 {' }/ s6 XFor j:=1 to n
; P6 x1 D5 X' X9 g, ]. `# E! L% JFor i:=1 to n
0 S7 [" K% L0 ?' F; _* yFor k:=1 to n
6 o  n8 g8 q% _3 V, q' |If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];- ]2 g. D4 D, i2 I0 S
我再改成如下形式,结果仍是正确的:
; x7 n" n8 g# x. ?) x  k4 `For j:=1 to n
* o5 O) X6 L3 ]0 [: W7 r" ^9 {For i:=1 to j-1% ]* o# h* m. d2 [$ _4 ]! V" H
For k:=1 to n
: o: v6 f  @* `, I& n/ cIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];, W: Q/ J( g0 |$ T3 y
如果我改成如下形式,结果出错,不行了:- r$ ]4 d9 d( U6 E; `
For j:=1 to n
% t% y/ _; r% t& n: R% M8 f1 `For i:=j+1 to n
% i! m" H! O% {8 E* A8 `6 R; p  xFor k:=1 to n
+ S  p4 ]4 o  |3 Q9 e! xIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
: ~6 C9 Y3 i0 Y6 A2 ~$ Y/ R2 w无法证明,只能用具体值来代入验证。
& O6 ^) g  q6 ?3 l8 `, k/ M1 B2 f
  I; n9 Y7 d6 I5 N
# _' |6 N% `8 n/ O; f9 C




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