发信人: marong(黑洋洋), 信区: Algorithm
标 题: 这个匹配算法的实现有没有严格证明
发信站: 饮水思源 (2011年12月03日00:20:58 星期六)
二分匹配算法的原理明白，但是我希望得到一个基于归纳的严格证明，证明这个实现是无
懈可击的。
要证明实现正确就是要证明
find(u)=true iff 存在一条从u出发的增光路，反之则不存在
但是为何从u出发，可以任意选取v，并用tested标记，从此就可以不再搜索从v出发的增广
路呢？感觉从这里开始说不清楚了。当然可以用一些模棱两可的说法安慰自己这是没问题
的，但我还是希望为tested能够成为一个意义明确的不变量，从而干净地得到一个证明。
大家可以不用理会我的说明，如果感兴趣的话，直接把自己认为严格的证明贴出来就可以
了，谢谢。
--
我感觉你们网友呐，还是要提高自己的知识水平，我为你们捉急啊。不要总是想弄那么一个大新闻，就说我不行了。我告诉你们啊，我是身经百战的，见得多啦！西方的哪一家医院我没有去过？条件比三零一好的不知道多到哪里去了，我在里面和他们谈笑风生。你们呐，too simple, sometimes naive!
※ 来源:·饮水思源 bbs.sjtu.edu.cn·[FROM: 218.82.56.214]
标 题: 这个匹配算法的实现有没有严格证明
发信站: 饮水思源 (2011年12月03日00:20:58 星期六)
二分匹配算法的原理明白，但是我希望得到一个基于归纳的严格证明，证明这个实现是无
懈可击的。
要证明实现正确就是要证明
find(u)=true iff 存在一条从u出发的增光路，反之则不存在
但是为何从u出发，可以任意选取v，并用tested标记，从此就可以不再搜索从v出发的增广
路呢？感觉从这里开始说不清楚了。当然可以用一些模棱两可的说法安慰自己这是没问题
的，但我还是希望为tested能够成为一个意义明确的不变量，从而干净地得到一个证明。
大家可以不用理会我的说明，如果感兴趣的话，直接把自己认为严格的证明贴出来就可以
了，谢谢。
--
我感觉你们网友呐，还是要提高自己的知识水平，我为你们捉急啊。不要总是想弄那么一个大新闻，就说我不行了。我告诉你们啊，我是身经百战的，见得多啦！西方的哪一家医院我没有去过？条件比三零一好的不知道多到哪里去了，我在里面和他们谈笑风生。你们呐，too simple, sometimes naive!
※ 来源:·饮水思源 bbs.sjtu.edu.cn·[FROM: 218.82.56.214]
No comments:
Post a Comment