作者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/m.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