上文講到算法的概念、復(fù)雜度，本文給大家介紹具體的算法思想，讓大家對(duì)算法設(shè)計(jì)理念有個(gè)認(rèn)識(shí)，后續(xù)再分別介紹各種算法。

算法思想

算法是解決問(wèn)題的一種思想和方法，其基本思想是將一個(gè)復(fù)雜問(wèn)題分解為多個(gè)簡(jiǎn)單的子問(wèn)題，然后通過(guò)一定的邏輯和操作方法將這些子問(wèn)題的解組合成原問(wèn)題的解。

分而治之

把一個(gè)復(fù)雜的問(wèn)題分成兩個(gè)或更多的相同或相似的子問(wèn)題，再把子問(wèn)題分成更小的子問(wèn)題，直到最后子問(wèn)題小到可以簡(jiǎn)單的直接求解，原問(wèn)題的解即子問(wèn)題的解的合并。這個(gè)技巧是很多高效算法的基礎(chǔ)，如排序算法(快速排序，歸并排序)，傅立葉變換(快速傅立葉變換)，大數(shù)據(jù)中的MR，現(xiàn)實(shí)中如漢諾塔游戲。

分治法對(duì)問(wèn)題有一定的要求：

• 該問(wèn)題縮小到一定程度后，就可以輕松解決
• 問(wèn)題具有可拆解性，不是一團(tuán)無(wú)法拆分的亂麻
• 拆解后的答案具有可合并性。能組裝成最終結(jié)果
• 拆解的子問(wèn)題要相互獨(dú)立，互相之間不存在或者很少有依賴關(guān)系

動(dòng)態(tài)規(guī)劃

基本思想與分治法類似，也是將待求解的問(wèn)題分解為若干個(gè)子問(wèn)題（階段），按順序求解子階段，前一子問(wèn)題的解，為后一子問(wèn)題的求解提供了有用的信息。在求解任一子問(wèn)題時(shí)，列出各種可能的局部解，通過(guò)決策保留那些有可能達(dá)到最優(yōu)的局部解，丟棄其他。依次解決各子問(wèn)題，最后一個(gè)子問(wèn)題就是初始問(wèn)題的解。

與分治法最大的不同在于，分治法的思想是并發(fā)，動(dòng)態(tài)規(guī)劃的思想是分步。該方法經(jīng)分解后得到的子問(wèn)題往往不是互相獨(dú)立的，其下一個(gè)子階段的求解往往是建立在上一個(gè)子階段的解的基礎(chǔ)上。動(dòng)態(tài)規(guī)劃算法同樣有一定的適用性場(chǎng)景要求：

• 最優(yōu)化解：拆解后的子階段具備最優(yōu)化解，且該最優(yōu)化解與追蹤答案方向一致
• 流程向前，無(wú)后效性：上一階段的解決方案一旦確定，狀態(tài)就確定，只會(huì)影響下一步，而不會(huì)反向影響
• 階段關(guān)聯(lián)：上下階段不是獨(dú)立的，上一階段會(huì)對(duì)下一階段的行動(dòng)提供決策性指導(dǎo)。這不是必須的，但是如果具備該特征，動(dòng)態(tài)規(guī)劃算法的意義才能更大的得到體現(xiàn)

貪心算法

同樣對(duì)問(wèn)題要求作出拆解，但是每一步，以當(dāng)前局部為目標(biāo)，求得該局部的最優(yōu)解。那么最終問(wèn)題解決時(shí)，得到完整的最優(yōu)解。也就是說(shuō)，在對(duì)問(wèn)題求解時(shí)，總是做出在當(dāng)前看來(lái)是最好的選擇，而不去從整體最優(yōu)上加以考慮。從這一角度來(lái)講，該算法具有一定的場(chǎng)景局限性。

• 要求問(wèn)題可拆解，并且拆解后每一步的狀態(tài)無(wú)后效性（與動(dòng)態(tài)規(guī)劃算法類似）
• 要求問(wèn)題每一步的局部最優(yōu)，與整體最優(yōu)解方向一致。至少會(huì)導(dǎo)向正確的主方向。

回溯算法

回溯算法實(shí)際上是一個(gè)類似枚舉的搜索嘗試過(guò)程，在每一步的問(wèn)題下，列舉可能的解決方式。選擇某個(gè)方案往深度探究，尋找問(wèn)題的解，當(dāng)發(fā)現(xiàn)已不滿足求解條件，或深度達(dá)到一定數(shù)量時(shí)，就返回，嘗試別的路徑?；厮莘ㄒ话氵m用于比較復(fù)雜的，規(guī)模較大的問(wèn)題。有“通用解題法”之稱。

• 問(wèn)題的解決方案具備可列舉性，數(shù)量有限
• 界定回溯點(diǎn)的深度。達(dá)到一定程度后，折返

分支限界

與回溯法類似，也是一種在空間上枚舉尋找最優(yōu)解的方式。但是回溯法策略為深度優(yōu)先。分支法為廣度優(yōu)先。分支法一般找到所有相鄰結(jié)點(diǎn)，先采取淘汰策略，拋棄不滿足約束條件的結(jié)點(diǎn)，其余結(jié)點(diǎn)加入活結(jié)點(diǎn)表。然后從存活表中選擇一個(gè)結(jié)點(diǎn)作為下一個(gè)操作對(duì)象