数学建模社区-数学中国

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

---

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

我在用实际顶点代入验证的基础上证实如下现象，无法用理论解释，个人感到弗洛伊德算法象哥德巴赫猜想一样，无法证明的。
2 d  Z  y% o' ?* W0 g* w0 `原来的弗洛伊德算法是：
For k:=1 to n
/ x: Z, D3 V$ }4 _" [For i:=1 to n
8 {. l1 J/ |) i- }7 [2 @0 u0 UFor j:=1 to n
# K& Y( [. Z8 U* _# M$ ?# qIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
我改成下面的形式，结果具体值代入仍是正确的，当然无法证明：
0 B: B2 E9 e  F: |7 k$ |" XFor j:=1 to n
For i:=1 to n
# s2 C4 D% }+ g- a" pFor k:=1 to n
/ E/ P6 ~/ w# M9 Z" W" E1 m! ]If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
我再改成如下形式，结果仍是正确的：
For j:=1 to n
% r# S, x* l! x1 \& }) OFor i:=1 to j-1
2 v; @, v8 E2 O. h, ZFor k:=1 to n
If D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
如果我改成如下形式，结果出错，不行了：
For j:=1 to n
, ~7 }# C; u) E/ u2 w. U8 _  z/ QFor i:=j+1 to n
! q  R/ J1 K9 ^, M. mFor k:=1 to n
) c1 q2 e0 K$ Q4 j: I0 y& c9 @/ ?8 xIf D[i,j]>D[i,k]+D[k,j] Then  D[i,j]:=D[i,k]+D[k,j];
无法证明，只能用具体值来代入验证。
' G6 W, W2 j) m* j4 c

; x2 ?# |, b! R; y# A" S

---

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

Powered by Discuz! X2.5