Greedy strategy牽涉到三個步驟：
1. 如何做一個符合（假設存在）optimal solution的貪婪決定？（稱為safe move)
2. 如何把大問題劃成許多相同的較小問題 (稱為subproblem)
3. 如何持續不斷做1和2
怎樣加最少次的油？
以car-fueling problem為例，假設有從A到B路上有以下幾個加油站：
每次加滿油可以跑400 km，怎麼加油才會最少次呢？
1. 如果以greedy的含義來看的話，應該要往加最少次的方向去思考，則合理的一個greedy choice嘗試就是只在能跑得最遠能到達的加油站加油。
2. 假設採用1的greedy strategy在某個加油站G加油，則剩下的路程就變成一個subproblem，因為是一模一樣的問題，只是出發點不是A而是G。
3. 持續不斷把剩下的路程做1. 和 2.的步驟。
Safe Move需要證明！
我們要證明在每次能到達最遠距離的加油站加油是一個safe move。假設從A 到 B有最少次加油的optimal solution解決方案，而其中第一次選的加油站為G1, 而G為離A能到達的最遠的加油站。
第一種可能G和G1重合，則得證。
剩下一種可能必然是G1離A比較近，因為我們已經定義G是離A最遠能到達的加油站。
假設我們在G1加油之後，下一個在optimal solution中要加油的是G2。
此時又有三種可能：
1. G在G1和G2中間：
此時如果要在G2加油的話，我們可以不選G1為第一個加油站，而選G為第一個加油站，因為在G1加滿油可以抵達G2的話，代表在G加滿油一定可以抵達G2，因為G1到G2的路程比G到G2來得遠。
所以如果用G代替G1當作第一個加油站的話，也是一個optimal solution，因為此solution的總加油次數不變。得證。
2. 第二種可能是G2在G1和G中間：
但這是不可能的，因為如果真是這樣，那我們完全可以選G2為第一個加油站就好，這樣整體加油次數會比原本的optimal solution少一次，這違反假設，不成立。
另外我們甚至可以選G為第一個加油站，因為G2到下一個加油站G3的距離大於G到G3的距離，所以在G加滿油一定可以抵達G3，整體加油次數也比optimal solution少2，違反假設，不成立。
3. G2和G重和，一樣違反假設，不成立，原因與2.理由一樣。
所以我們證明了G一定是optimal solution的第一個加油站
我同樣上了coursera的這堂課
回覆刪除看了您的筆記後終於懂老師的證明
感謝 :)))
不客氣喔! 有空多交流 :D
回覆刪除不太明白証明safe move的點子2和3。例如為什麼G2在G1和G之間就是沒可能呢？重看了影片數次，依然不明白呢。
回覆刪除當中說到違反了假設，可否更詳細說明違反了什麼假設和如何違反。謝謝。
刪除我的理解是：
刪除sub-problem是從某出發點到終點。
而，最優解的定義是以最少refuel次數達成從某出發點到終點的目標。
如果，現在的subproblem是G1為出發點到終點B。這個假設包含了假設G1是上一個sub-problem的最優解。假設G2是從G1到B的最優解，而G2真的在G和G2之間。由於G2離A比較遠，而且在可駕駛範圍內，按道理G2是比G1更優秀的解。這跟以上解設出現矛盾因此這沒可能發生。同理，第三點也是如此。