第8章 貪婪算法
8.1 教室排程問題
思路:①選取結束時間最早的課,它就是這件教室上的第一節課。
②選擇必須第1節課結束後才開始的課,選擇結束最早的為第二堂課。
③重複
貪婪算法很簡單:每步都采用最優的做法。
8.2 背包問題
8.3 集合覆寫問題
方法:
①列出每個可能的廣播台集合。
②在這個集合中選擇覆寫全美50個州的最小集合
近似算法
①選出這樣一個廣播台,即它覆寫了最多的為覆寫州。
②重複第一步,直到覆寫了所有州。
8.4 NP完全問題
8…4.1 旅行商問題詳解
近似求解法:随便選擇出發城市,然後每次選擇要去的下一個城市時,都選擇沒去的最近城市。
8.4.2 如何識别NP完全問題
8.5 小結