1.貪心算法
1.1 簡介
- 貪心算法（又稱貪婪算法），在求解問題時，總是做出在當前看來是最好的選擇。也就是說，不從整體最優(yōu)解進行考慮，而是得到某種意義上的局部最優(yōu)解。
- 貪心算法采用自頂向下，以迭代的方法做出貪心選擇，每做一次貪心選擇，就將所求問題簡化為一個規(guī)模更小的問題。
- 每一次的貪心選擇可得到問題的一個最優(yōu)解，雖然能夠保證每一步所獲得的是局部最優(yōu)解，但是不能保證全局解是最優(yōu)的。
- 適用貪心算法解決問題的前提是：局部最優(yōu)策略能夠得到全局最優(yōu)解
2.2 例題
- 錢幣找零問題
- 活動選擇問題
- 多機調(diào)度問題
- 小船過河問題
2.分治算法
2.1 簡介
- 分值算法是將一個規(guī)模為N的問題分解為K個規(guī)模較小的子問題
- 這些子問題相互獨立且與原問題性質(zhì)相同
- 求出子問題的解，就可以得到原問題的解
2.2 解題步驟
- 分解：將要解決的問題分解成若干個子問題
- 求解：求解子問題
- 合并：合并子問題的解組成原問題的解
2.3 例題
- 二分搜索
- 大整數(shù)乘法
- Strassen矩陣乘法
- 棋盤覆蓋
- 合并排序
- 快速排序
- 線性時間選擇
- 最接近點對問題
- 漢諾塔
2.4 分治與遞歸的關(guān)系
- 分治是一種處理問題的思想，遞歸則是一種編程技巧
- 實際情況中，分治算法大都采用遞歸來實現(xiàn)
3.回溯算法
3.1 簡介
- 是一個類似枚舉的搜索嘗試過程，主要是在搜索嘗試中求解，當不滿足條件時就“回溯”返回，嘗試別的路徑
3.2 解題步驟
- 確定了解空間的組織結(jié)構(gòu)后，回溯法就從開始結(jié)點（根節(jié)點）出發(fā)，以深度優(yōu)先（DFS）的方式遍歷搜索整個空間
- 這個開始的結(jié)點就成為一個活結(jié)點，同時也成為當前的拓展結(jié)點
- 依次移動，當結(jié)點不能夠再移動的時候，則當前拓展結(jié)點就成為死結(jié)點，此時應(yīng)該往回移動（回溯）到最近的一個活結(jié)點處
- 直到?jīng)]有活結(jié)點時
3.3 例題
- 八皇后問題
- 裝載問題
- 批量作業(yè)調(diào)度問題
4.動態(tài)規(guī)劃算法
4.1 簡介
- DP是求解決策過程最優(yōu)化的過程，能獲得全局最優(yōu)解
- 動態(tài)規(guī)劃算法與分治法類似，其基本思想也是將待求解問題分成若干個子問題，先求解子問題，然后再從這些子問題中的解得到原問題的解
- 不同之處：
- 1.分治法分解的子問題相互獨立，而動態(tài)規(guī)劃發(fā)分解的子問題不是相互獨立的
- 2.分治自頂向下，動態(tài)規(guī)劃自底向上
- 需要在給定約束條件下優(yōu)化某種指標時，動態(tài)規(guī)劃很有用
- 每種動態(tài)規(guī)劃解決方案都涉及網(wǎng)格，單元格中的值通常就是要優(yōu)化的值
4.2 應(yīng)用場景
- 具有最優(yōu)子結(jié)構(gòu)性質(zhì)：問題的最優(yōu)解包含子問題的最優(yōu)解，反過來說就是，我們可以通過子問題的最優(yōu)解推導(dǎo)出問題的最優(yōu)解
- 無后效性：只關(guān)心前面階段的狀態(tài)值，而不關(guān)心這個狀態(tài)是怎么一步一步推導(dǎo)出來的
- 具有重疊子問題的問題：子問題不是相互獨立的
4.3 例題
- 游艇租聘
- 0-1背包問題
- 跳臺階問題
- 強盜搶劫問題
文章來源地址http://www.zghlxwxcb.cn/news/detail-611955.html
文章來源：http://www.zghlxwxcb.cn/news/detail-611955.html
到了這里，關(guān)于四大算法：貪心、分治、回溯、動態(tài)規(guī)劃的文章就介紹完了。如果您還想了解更多內(nèi)容，請在右上角搜索TOY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
