作者jean20157 (自然卷)
看板Grad-ProbAsk
标题[理工] Algo. optimal substructure证明
时间Fri Nov 15 14:51:19 2019
https://i.imgur.com/Yc7cexk.jpg
不太懂为什麽「令P’为P中去掉P1之所有边, 再加上P2之路径 」
这样就可以证明P1必为shortest path
P1与P2的起终点都是a, b
这样不就代表两边一样长吗？
这样又与P’有什麽关系？
还有想再请教，这个证明是否能用画图来理解？
总觉得用文字好像比较难明白解答的意思
-----
Sent from JPTT on my iPhone
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 42.72.48.46 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Grad-ProbAsk/M.1573800681.A.CC3.html
1F：→ mathtsai: 题目原本长怎样...这样最好有人看的懂= = 11/15 15:03
3F：→ jean20157: 抱歉 不知道这样清楚吗 11/15 15:59
4F：推 b10007034: 画图应该没有比较清楚，题目想证的就是P为 11/15 17:22
5F：→ b10007034: ShortestPath(SP）并且subPath皆为SP 11/15 17:22
6F：→ b10007034: 所以它宣告了两条subPath一条是SP一条不是 11/15 17:22
7F：→ b10007034: 所以原来P含有P1（假设不是SP），然後剪下P1贴上（因 11/15 17:22
8F：→ b10007034: 为皆为a起点b终点所以可以做这个操作）P2造出P’，如 11/15 17:22
9F：→ b10007034: 此一来便可以说明P’比P还短（因为假设P1不是SP，P2是 11/15 17:22
10F：→ b10007034: 此时与题目产生矛盾（P为SP），则P1必为SP 11/15 17:22
11F：推 mistel: 有个问题疑惑很久了，证明optimal substructure跟证明gre 11/15 19:16
12F：→ mistel: edy choice property差在哪里呢？ 11/15 19:16
13F：→ mistel: 知道後者的定义是：若某个选择是当前最佳选择，则一定包 11/15 19:17
14F：→ mistel: 含在最佳解中，而前者的定义是，最佳解一定有子问题的最 11/15 19:17
15F：→ mistel: 佳解建构而成 11/15 19:17
16F：→ mistel: 但证明方法好像都是用矛盾证法... 11/15 19:17
非常感谢您！！
18F：→ b10007034: 附一点图小讲解，希望看得懂。 11/15 19:45
也谢谢m大解释
※ 编辑: jean20157 (42.73.199.19 台湾), 11/16/2019 12:04:44
※ 编辑: jean20157 (42.73.199.19 台湾), 11/16/2019 15:18:26