QQ登录

只需要一步,快速开始

 注册地址  找回密码
查看: 5412|回复: 12
打印 上一主题 下一主题

[问题求助] 最短路径中的Floyd算法(弗洛伊德算法)的较为严格的冥想证明过程

[复制链接]
字体大小: 正常 放大
释永思        

23

主题

13

听众

146

积分

升级  23%

  • TA的每日心情
    难过
    2016-5-14 14:04
  • 签到天数: 18 天

    [LV.4]偶尔看看III

    自我介绍
    软件开发工程师

    社区QQ达人

    跳转到指定楼层
    1#
    发表于 2015-10-31 13:45 |只看该作者 |倒序浏览
    |招呼Ta 关注Ta
    =========================================
    ' C: Y' y0 v# J/ L9 t! W最短路径中的Floyd算法(弗洛伊德算法)的较为严格的冥想证明过程:
    / O  N$ n( ]0 c6 f7 k6 @仍用数学归纳法,
    - D/ H6 s6 q# h1 `7 h9 {; |7 H假设N<=n时,弗法正确。具体值我就不验证了。
    5 J! E7 o  r) T" ]/ h3 S4 T6 |$ h8 o当N=n+1时,假设最新一点最后一点为K,此时K=n+1,+ ?9 M! O9 i+ U) X+ F7 u; [' l5 }
    三重循环中,我们都把K排在循环中的最后一位。
    / k7 z9 J/ v" F( K: R3 a, j现在我们要证明的是,加上新点K点后,经过弗法的三重循环,原来的n点之间仍是最短距离,但是n点与K点之间的短离是不是最短的就不知的。
    ; ]; G9 C* s  K' e5 w" s& f+ B如果原来的n点的某两点之间最短距是与K点无关的,显然经过三重循环后,就是最短距了。
    7 W2 x4 u- _$ K: w, x; D( V如果原来的n点的某两点之间最短距是经过K点的,假设P1,P2,P3,,,Pk-1,Pk,Pk+1,,,Pm本应是实边最短距,不是虚边最短距。+ }7 @+ M. b" @% i/ C
    那么由弗法知,P1,P2,P3,,,Pk-1与PK+1,,,,Pm已是连通的最短路了。且Pk-1Pk与PKPK+1是原始实边,不是虚边。
    5 E8 e3 }, t2 U3 @8 y6 t' h6 S经过最外层最后一次循环的松驰操作,必能连通P1,P2,P3,,,Pk-1,Pk,Pk+1,,,Pm。
    $ u6 `- F" F; j2 Z0 o& F4 u9 l所以得证:加上新点K点后,经过弗法的三重循环,原来的n点之间仍是最短距离,但是n点与K点之间的短离是不是最短的就不知的。
    # ?# F2 A- g% T3 l. _5 l+ ~由于对称性,将K点置入内部,把P1点放到最后一点,原来的循环结果不会变的,
    # T5 u) a4 C% m$ q* C0 p4 _所以三重循环后,K点与原来的点(除P1外)的最短距,就可以求出来了。
      N' x9 ]; Y1 F; i) q由于对称性,将K点置入内部,把P2点放到最后一点,原来的循环结果不会变的,6 ~6 e% g5 ^7 G) \5 ^
    所以三重循环后,K点与原来的点(除P2外,但P1不除外)的最短距,就可以求出来了。+ f% K3 w5 j6 {; Y0 H" X! [
    所以K点与原来的n个点的最短距,也就已经求出来的了,仍是原来的三重循环也。2 q, C; u) g# b. J% M- b
    这样,弗法就可以较为严格的证明了。. g! ]. l7 T; I# ~) n2 k5 n
    =========================================6 @* [+ T6 X2 w2 O2 F
    为何假设P1,P2,P3,,,Pk-1,Pk,Pk+1,,,Pm本应是实边最短距,不是虚边最短距???
    5 @. O2 L. |0 G# o! m8 p" n& A如果是虚边最短距,也可以转化成实边最短距,然后结果一样的。
    ) U: t% ], V# G4 E% s=========================================% g* J8 e1 \- b+ p& ^2 i, ?, s+ c) _

    ) q3 A* V9 k- D5 Q3 G5 R
    1 E; u  E, U, e- F8 y. G* q4 H7 f7 b$ Y
    zan
    转播转播0 分享淘帖0 分享分享0 收藏收藏0 支持支持0 反对反对0 微信微信
    释永思        

    23

    主题

    13

    听众

    146

    积分

    升级  23%

  • TA的每日心情
    难过
    2016-5-14 14:04
  • 签到天数: 18 天

    [LV.4]偶尔看看III

    自我介绍
    软件开发工程师

    社区QQ达人

    忽然想到,上面的证明中有一点未严格证明,就是,要证明弗法的三重循环与N个顶点的排序次序无关,例如for i=1 to n 与  for i=n to 1等次序无关,我没能证明这点。现在十分疲劳,没有余力思考这点。
    3 f- t, ~! j7 |* d9 W; x  F( E1 i
    回复

    使用道具 举报

    释永思        

    23

    主题

    13

    听众

    146

    积分

    升级  23%

  • TA的每日心情
    难过
    2016-5-14 14:04
  • 签到天数: 18 天

    [LV.4]偶尔看看III

    自我介绍
    软件开发工程师

    社区QQ达人

    谁人能证明弗洛伊德算法的三重循环与循环中的次序无关?我没有余力思考,我太疲劳了,我也不知如何证明,求助了。 例如要证明弗法中,for i=1 to n 与for i=n to 1或次序混乱也是无关的。这个我无法证明,用数学归纳法也一时想不出 来。求助,我太疲劳了,要休息,一时没有余力思考研究。这个也是我一时想到的,弗法无边,永思不尽。9 y' Q9 [3 V; j  M* J7 B

    ( b) {0 i) e  x7 _. h  c+ z
    回复

    使用道具 举报

    释永思        

    23

    主题

    13

    听众

    146

    积分

    升级  23%

  • TA的每日心情
    难过
    2016-5-14 14:04
  • 签到天数: 18 天

    [LV.4]偶尔看看III

    自我介绍
    软件开发工程师

    社区QQ达人

    弗法:数归法:7 e% h# Q8 S7 d. s
    对于N<=n的任一个混排序,K点替换其中一个点,必也是成立的。这样,就证明了弗法的混排序?, Y  u! O7 X" D. Y( E) G' i8 `
    这能叫证明吗???这与没有证明有何区别???
    + a$ i" T! U* e1 |9 p( {/ R2 q# z. z7 y& ]6 n; l; V. f
    弗法中,必然殊途同归,归于最后唯一的最短距离,这是唯一值,不会有多个值的。所以与顶点混排序无关乎???1 e- p( A5 c0 N8 d0 ~
    回复

    使用道具 举报

    361

    主题

    13

    听众

    2078

    积分

    风靡全球

  • TA的每日心情
    开心
    2016-11-15 12:14
  • 签到天数: 102 天

    [LV.6]常住居民II

    网络挑战赛参赛者

    新人进步奖 发帖功臣 最具活力勋章

    回复

    使用道具 举报

    361

    主题

    13

    听众

    2078

    积分

    风靡全球

  • TA的每日心情
    开心
    2016-11-15 12:14
  • 签到天数: 102 天

    [LV.6]常住居民II

    网络挑战赛参赛者

    新人进步奖 发帖功臣 最具活力勋章

    回复

    使用道具 举报

    361

    主题

    13

    听众

    2078

    积分

    风靡全球

  • TA的每日心情
    开心
    2016-11-15 12:14
  • 签到天数: 102 天

    [LV.6]常住居民II

    网络挑战赛参赛者

    新人进步奖 发帖功臣 最具活力勋章

    回复

    使用道具 举报

    361

    主题

    13

    听众

    2078

    积分

    风靡全球

  • TA的每日心情
    开心
    2016-11-15 12:14
  • 签到天数: 102 天

    [LV.6]常住居民II

    网络挑战赛参赛者

    新人进步奖 发帖功臣 最具活力勋章

    回复

    使用道具 举报

    361

    主题

    13

    听众

    2078

    积分

    风靡全球

  • TA的每日心情
    开心
    2016-11-15 12:14
  • 签到天数: 102 天

    [LV.6]常住居民II

    网络挑战赛参赛者

    新人进步奖 发帖功臣 最具活力勋章

    回复

    使用道具 举报

    361

    主题

    13

    听众

    2078

    积分

    风靡全球

  • TA的每日心情
    开心
    2016-11-15 12:14
  • 签到天数: 102 天

    [LV.6]常住居民II

    网络挑战赛参赛者

    新人进步奖 发帖功臣 最具活力勋章

    回复

    使用道具 举报

    您需要登录后才可以回帖 登录 | 注册地址

    qq
    收缩
    • 电话咨询

    • 04714969085
    fastpost

    关于我们| 联系我们| 诚征英才| 对外合作| 产品服务| QQ

    手机版|Archiver| |繁體中文 手机客户端  

    蒙公网安备 15010502000194号

    Powered by Discuz! X2.5   © 2001-2013 数学建模网-数学中国 ( 蒙ICP备14002410号-3 蒙BBS备-0002号 )     论坛法律顾问:王兆丰

    GMT+8, 2026-4-18 01:48 , Processed in 1.796969 second(s), 96 queries .

    回顶部