[理工] Algo. optimal substructure證明

看板Grad-ProbAsk作者 (自然捲)時間6年前 (2019/11/15 14:51), 6年前編輯推噓4(4推 0噓 15→)
留言19則, 5人參與, 6年前最新討論串1/1
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
→
11/15 15:03, 6年前 , 1F
題目原本長怎樣...這樣最好有人看的懂= =
11/15 15:03, 1F
→
11/15 15:58, 6年前 , 2F
11/15 15:58, 2F
→
11/15 15:59, 6年前 , 3F
抱歉 不知道這樣清楚嗎
11/15 15:59, 3F
推
11/15 17:22, 6年前 , 4F
畫圖應該沒有比較清楚，題目想證的就是P為
11/15 17:22, 4F
→
11/15 17:22, 6年前 , 5F
ShortestPath(SP）並且subPath皆為SP
11/15 17:22, 5F
→
11/15 17:22, 6年前 , 6F
所以它宣告了兩條subPath一條是SP一條不是
11/15 17:22, 6F
→
11/15 17:22, 6年前 , 7F
所以原來P含有P1（假設不是SP），然後剪下P1貼上（因
11/15 17:22, 7F
→
11/15 17:22, 6年前 , 8F
為皆為a起點b終點所以可以做這個操作）P2造出P’，如
11/15 17:22, 8F
→
11/15 17:22, 6年前 , 9F
此一來便可以說明P’比P還短（因為假設P1不是SP，P2是
11/15 17:22, 9F
→
11/15 17:22, 6年前 , 10F
此時與題目產生矛盾（P為SP），則P1必為SP
11/15 17:22, 10F
推
11/15 19:16, 6年前 , 11F
有個問題疑惑很久了，證明optimal substructure跟證明gre
11/15 19:16, 11F
→
11/15 19:16, 6年前 , 12F
edy choice property差在哪裡呢？
11/15 19:16, 12F
→
11/15 19:17, 6年前 , 13F
知道後者的定義是：若某個選擇是當前最佳選擇，則一定包
11/15 19:17, 13F
→
11/15 19:17, 6年前 , 14F
含在最佳解中，而前者的定義是，最佳解一定有子問題的最
11/15 19:17, 14F
→
11/15 19:17, 6年前 , 15F
佳解建構而成
11/15 19:17, 15F
→
11/15 19:17, 6年前 , 16F
但證明方法好像都是用矛盾證法...
11/15 19:17, 16F
推
11/15 19:45, 6年前 , 17F
11/15 19:45, 17F
非常感謝您！！
→
11/15 19:45, 6年前 , 18F
附一點圖小講解，希望看得懂。
11/15 19:45, 18F
推
11/15 23:30, 6年前 , 19F
11/15 23:30, 19F
也謝謝m大解釋 ※ 編輯: jean20157 (42.73.199.19 臺灣), 11/16/2019 12:04:44 ※ 編輯: jean20157 (42.73.199.19 臺灣), 11/16/2019 15:18:26
‣ 更多 jean20157 的文章
文章代碼(AID): #1Tpahfp3 (Grad-ProbAsk)