最近在刷演算法題目，突然重新思考一下大二時學習的演算法分析與設計課程，發現當時沒有學習明白，只是記住了幾個特定的幾個題型；現在重新回歸的時候，上升到了方法學上了；感覺到了溫故知新的感覺；以下總結自童詠昕老師的演算法設計與分析課程和韓軍老師的演算法分析與設計課程；當我們遇到一個問題的時候，我們先想出一個簡單的方法，可以之后再在這個方法的基礎上進行優化；
分而治之思路：(存在獨立子問題，三個步驟都很重要）
- 分解原問題；（存在子問題，可以遞回求解，子問題不重疊，子問題比原問題規模小）
- 解決子問題；
- 合并問題解；
- 經典問題：
- 歸并排序，最大子陣列問題；逆序計數問題；（簡化了分解的程序，聚焦于合并求解程序）
- 快速排序，次序選擇問題；（聚焦于分解問題程序，簡化了合并問題解）
動態規劃思路：（存在重疊子問題）
- 問題結構分析；（存在子問題，可以遞回求解，子問題重疊，帶有memo的遞回求解，動態規劃自底向上）
- 遞推關系建立；
- 自底向上計算；（可以先用小規模資料找到求解規律，編程）
- 最優方案追蹤；（根據求解的順序，判斷當前問題規模的解，來自于那個子問題）
- 經典問題：
- 0-1背包問題（物品不可分割）；最大子陣列問題；最長公共子序列問題；最長公共子串問題；最小編輯距離問題；（有限的情況的選擇）
- 鋼條切割問題；矩陣鏈乘法問題；（區間型的動態規劃，需要列舉一個區間）
貪心策略思路：（存在單一子問題，需要證明貪心策略正確性）
- 貪心演算法是指，在求解問題時，總是做出在當前最好的選擇，不從整體最優上考慮，選擇當前區域最優解；貪心演算法不是對所有問題都能得到整體最優解，關鍵是貪心策略的選擇；選擇貪心策略必須具備無后效性，即某個狀態以前的程序不會影響以后的狀態，只與當前狀態有關，
- 提出貪心策略；
- 證明貪心策略正確；（數學歸納法或反證法）
- 經典問題：
- 部分背包問題（物品可分割，可以按照價值和重量比來進行排序）；
- 霍夫曼編碼問題；活動選擇問題；
求解思路：
經典問題：
回溯法：一種優先搜索法，試探法；總體思想就是，在搜索空間樹中，按照選擇條件向前搜索（深度優先搜索），以達到目標（找到解空間樹中滿足約束條件的所有解）；當搜索到某一步時，發現搜索選擇并不優或達不到目標，就回退一步，重新選擇（常常使用遞回實作）；遞回實作有三個核心要點：遞回出口，函式引數，處理程序，回溯法在求解0/1背包問題的時候，雖然回溯程序中的剪枝，減少了搜索空間；但是整個搜索按深度優先機械進行，是盲目搜索（不可預測本節點以下的節點如何進行）；
分支限界法：即在搜索空間樹中進行搜索（廣度優先，最小耗費優先，最大效益優先方式搜索），以達到求解目標（在滿足約束條件的解中，找出在某種意義下的最優解或者找出滿足約束條件的解，剪枝的原因），分支限界演算法，首先是確定一個合理的限界函式，然后根據函式確定目標函式的上下界（該屆在最優解情況下可更新）；然后按照廣度優先的策略遍歷問題的解空間樹，在某一分支上，依次搜索該結點的所有孩子結點，分別估算這些孩子結點的目標函式的可能取值（對于最小化問題估算結點的下界，對于最大化問題，估算該結點的上界）；如果某個孩子結點的目標函式值超出了目標函式的界，則將其丟棄（限界），否則加入佇列中；
其他演算法思想：近似演算法，隨機演算法和啟發式演算法；
保持更新，轉載請注明出處；更多內容請關注cnblogs.com/xuyaowen；
回溯法參考鏈接：https://zhuanlan.zhihu.com/p/51882471
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/71909.html
標籤：其他
上一篇：資料庫在docker重啟時丟失了
下一篇：找大佬