[理工] Algo. optimal substructure證明

[jean20157 (自然捲)]

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://www.ptt.cc/bbs/Grad-ProbAsk/M.1573800681.A.CC3.html
→ mathtsai: 題目原本長怎樣...這樣最好有人看的懂= =
→ jean20157: https://i.imgur.com/i1MfKM0.jpg
→ jean20157: 抱歉 不知道這樣清楚嗎
推 b10007034: 畫圖應該沒有比較清楚，題目想證的就是P為
→ b10007034: ShortestPath(SP）並且subPath皆為SP
→ b10007034: 所以它宣告了兩條subPath一條是SP一條不是
→ b10007034: 所以原來P含有P1（假設不是SP），然後剪下P1貼上（因
→ b10007034: 為皆為a起點b終點所以可以做這個操作）P2造出P’，如
→ b10007034: 此一來便可以說明P’比P還短（因為假設P1不是SP，P2是
→ b10007034: 此時與題目產生矛盾（P為SP），則P1必為SP
推 mistel: 有個問題疑惑很久了，證明optimal substructure跟證明gre
→ mistel: edy choice property差在哪裡呢？
→ mistel: 知道後者的定義是：若某個選擇是當前最佳選擇，則一定包
→ mistel: 含在最佳解中，而前者的定義是，最佳解一定有子問題的最
→ mistel: 佳解建構而成
→ mistel: 但證明方法好像都是用矛盾證法...
推 b10007034: https://i.imgur.com/SoZC4km.jpg
非常感謝您！！
→ b10007034: 附一點圖小講解，希望看得懂。
推 mi981027: https://i.imgur.com/1p8fpKc.jpg
也謝謝m大解釋
※ 編輯: jean20157 (42.73.199.19 臺灣), 11/16/2019 12:04:44
※ 編輯: jean20157 (42.73.199.19 臺灣), 11/16/2019 15:18:26