還不懂這八大算法思想，刷再多題也白搭！
掃描二維碼
隨時(shí)隨地手機(jī)看文章
各位朋友好久不見呢。最近由于剛?cè)肼?，作為職?chǎng)萌新，所以大部分時(shí)間都花在了工作上。因而也沒有太多時(shí)間來寫文章啦，這篇文章也是定題了許久，遲遲沒有落筆。等之后工作慢慢穩(wěn)定，業(yè)務(wù)熟練起來，文章更新頻率就會(huì)高起來的！還請(qǐng)朋友們持續(xù)關(guān)注哦～
算法和數(shù)據(jù)結(jié)構(gòu)一直以來都是程序員的基本內(nèi)功，可以說沒有數(shù)據(jù)結(jié)構(gòu)的基礎(chǔ)建設(shè)和算法加持，也就沒有這將近八十年的信息革命時(shí)代。數(shù)據(jù)結(jié)構(gòu)可以看作是算法實(shí)現(xiàn)的容器，通過一系列特殊結(jié)構(gòu)的數(shù)據(jù)集合，能夠?qū)⑺惴ǜ鼮楦咝Ф煽康貓?zhí)行起來。
算法的應(yīng)用不單只體現(xiàn)在編程中。狹義的來講，算法可看作是數(shù)據(jù)傳遞和處理的順序、方法和組成方式，就像是各種排序算法等。而廣義的來講，算法更像是一種事物運(yùn)行的邏輯和規(guī)則。太陽東升西落，海水潮汐潮流，月兒陰晴圓缺，這些或許都可以看似一種算法，只不過執(zhí)行者不是電子計(jì)算機(jī)，而是自然萬物。
聊遠(yuǎn)了。所以對(duì)于算法的理解，重要的是領(lǐng)悟其思想，感受其內(nèi)在。有同學(xué)或許就會(huì)說了，「算法不就是Leetcode，不就是刷題嘛 」。
片面了啊。題總是刷不完的，但是算法的思想就那么幾個(gè)。所以呢，刷了那么多題的你，還不了解這幾個(gè)常見的算法思想，想必是應(yīng)該好好反省反省下了。
1 枚 舉
首先，最為簡(jiǎn)單的思想，枚舉算法。枚舉也叫窮舉，顧名思義，就是窮盡列舉。枚舉思想的應(yīng)用場(chǎng)景十分廣泛，也非常容易理解。簡(jiǎn)單來說，枚舉就是將問題的可能解依次列舉出來，然后一一帶入問題檢驗(yàn)，從而從一系列可能解中獲得能夠解決問題的精確解。
枚舉雖然看起來簡(jiǎn)單，但是其實(shí)還是有一些容易被人忽視的考慮點(diǎn)。比方說待解決問題的「可能解/候選解」的篩選條件，「可能解」之間相互的影響，窮舉「可能解」的代價(jià)，「可能解」的窮舉方式等等。
很多時(shí)候?qū)嶋H上不必去追求高大上的復(fù)雜算法結(jié)構(gòu)，反而大道至簡(jiǎn)，采用枚舉法就能夠很好的規(guī)避系統(tǒng)復(fù)雜性帶來的冗余，同時(shí)或許在一定程度上還能夠?qū)臻g進(jìn)行縮減。
枚舉思想的流程可以用下圖來表示。通過實(shí)現(xiàn)事先確定好「可能解」，然后逐一在系統(tǒng)中進(jìn)行驗(yàn)證，根據(jù)驗(yàn)證結(jié)果來對(duì)「可能解」進(jìn)行分析和論證。這是一種很明顯的結(jié)果導(dǎo)向型的思想，簡(jiǎn)單粗暴地試圖從最終結(jié)果反向分析「可能解」的可行性。
不過，枚舉思想的劣勢(shì)當(dāng)然也很明顯。在實(shí)際的運(yùn)行程序中，能夠直接通過枚舉方法進(jìn)行求解的問題少之又少。而當(dāng)「可能解」的篩選條件不清晰，導(dǎo)致「可能解」的數(shù)量和范圍無法準(zhǔn)確判斷時(shí)，枚舉就失去了意義。
然而當(dāng)「可能解」的規(guī)模比較小，同時(shí)依次驗(yàn)證的過程容易實(shí)施時(shí)，枚舉思想不失為一種方便快捷的方式。只不過在具體使用時(shí)，還可以針對(duì)應(yīng)用場(chǎng)景對(duì)「可能解」的驗(yàn)證進(jìn)行優(yōu)化。
這種優(yōu)化可以從兩個(gè)方向入手，一是問題的簡(jiǎn)化，盡可能對(duì)需要處理的問題進(jìn)行模型結(jié)構(gòu)上的精簡(jiǎn)。這種精簡(jiǎn)具體可體現(xiàn)在問題中的變量數(shù)目，減少變量的數(shù)據(jù)，從而能夠從根本上降低「可能解」的組合。
二是對(duì)篩選「可能解」的范圍和條件進(jìn)行嚴(yán)格判斷，盡可能的剔除大部分無效的「可能解」。
雖說如此，但是一般而言大部分枚舉不可用的場(chǎng)景都是由于「可能解」的數(shù)量過多，無法在有限空間或有限時(shí)間內(nèi)完成所有可能性的驗(yàn)證。不過實(shí)際上枚舉思想是最接近人的思維方式，在更多的時(shí)候是用來幫助我們?nèi)ァ咐斫鈫栴}」，而不是「解決問題」。
案例
百錢買百雞問題。 該問題敘述如下：雞翁一，值錢五；雞母一，值錢三；雞雛三，值錢一；百錢買百雞，則翁、母、雛各幾何？
翻譯過來，意思是公雞一個(gè)五塊錢，母雞一個(gè)三塊錢，小雞三個(gè)一塊錢，現(xiàn)在要用一百塊錢買一百只雞，問公雞、母雞、小雞各多少只？
2 遞 推
遞推思想跟枚舉思想一樣，都是接近人類思維方式的思想，甚至在實(shí)際生活具有比枚舉思想更多的應(yīng)用場(chǎng)景。人腦在遇到未知的問題時(shí)，大多數(shù)人第一直覺都會(huì)從積累的「先驗(yàn)知識(shí)」出發(fā)，試圖從「已知」推導(dǎo)「未知」，從而解決問題，說服自己。
事實(shí)上，這就是一種遞推的算法思想。遞推思想的核心就是從已知條件出發(fā)，逐步推算出問題的解。實(shí)現(xiàn)方式很像是初高中時(shí)我們的數(shù)學(xué)考卷上一連串的「因?yàn)椤埂杆浴?。那個(gè)時(shí)候還是用三個(gè)點(diǎn)來表示的。
而對(duì)于計(jì)算機(jī)而言，復(fù)雜的推導(dǎo)其實(shí)很難實(shí)現(xiàn)。計(jì)算機(jī)擅長(zhǎng)的是執(zhí)行高密度重復(fù)性高的工作，對(duì)于隨機(jī)性高變化多端的問題反而不好計(jì)算。相比之下，人腦在對(duì)不同維度的問題進(jìn)行推導(dǎo)時(shí)具有更高的自由度。
比方說，人腦可以很容易的從「太陽從東邊升起」推出「太陽從西邊落下」，然后大致推出「現(xiàn)在的時(shí)間」。但是對(duì)于計(jì)算機(jī)而言并沒有那么容易，你可能需要設(shè)置一系列的限制條件，才能避免計(jì)算機(jī)推出「太陽/月亮/星星」從「南/北/東邊」「落下/飛走/掉落」的可能性。
我說這個(gè)例子的用意是在說明，計(jì)算機(jī)在運(yùn)用遞推思想時(shí)，大多都是重復(fù)性的推理。比方說，從「今天是1號(hào)」推出「明天是2號(hào)」。這種推理的結(jié)構(gòu)十分類似，往往可以通過繼而往復(fù)的推理就可以得到最終的解。
遞推思想用圖解來表示可以參見下圖。每一次推導(dǎo)的結(jié)果可以作為下一次推導(dǎo)的的開始，這似乎跟迭代、遞歸的思想有點(diǎn)類似，不過遞推的范疇要更廣一些。
案例
兔子問題。 定一對(duì)大兔子每月能生一對(duì)小兔子，且每對(duì)新生的小兔子經(jīng)過一個(gè)月可以長(zhǎng)成一對(duì)大兔子,具備繁殖能力，如果不發(fā)生死亡，且每次均生下一雌一雄，問一年后共有多少對(duì)兔子？
3 遞 歸
說完遞推，就不得不說說它的兄弟思想——遞歸算法。二者同樣都帶有一個(gè)「遞」字，可以看出二者還是具有一定的相似性的。「遞」的理解可以是逐次、逐步。在遞推中，是逐次對(duì)問題進(jìn)行推導(dǎo)直到獲得最終解。而在遞歸中，則是逐次回歸迭代，直到跳出回歸。
遞歸算法實(shí)際上是把問題轉(zhuǎn)化成規(guī)模更小的同類子問題，先解決子問題，再通過相同的求解過程逐步解決更高層次的問題，最終獲得最終的解。所以相較于遞推而言，遞歸算法的范疇更小，要求子問題跟父問題的結(jié)構(gòu)相同。而遞推思想從概念上并沒有這樣的約束。
用一句話來形容遞歸算法的實(shí)現(xiàn)，就是在函數(shù)或者子過程的內(nèi)部，直接或間接的調(diào)用自己算法。所以在實(shí)現(xiàn)的過程中，最重要的是確定遞歸過程終止的條件，也就是迭代過程跳出的條件判斷。否則，程序會(huì)在自我調(diào)用中無限循環(huán)，最終導(dǎo)致內(nèi)存溢出而崩潰。
遞歸算法的圖解可如下圖。很明顯，遞歸思想其實(shí)就是一個(gè)套娃過程。一般官方都是嚴(yán)禁套娃行為的。所以在使用時(shí)一定要明確「套娃」舉動(dòng)的停止條件，及時(shí)止損。
案例
漢諾塔問題。 源于印度傳說中，大梵天創(chuàng)造世界時(shí)造了三根金鋼石柱子，其中一根柱子自底向上疊著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動(dòng)一個(gè)圓盤。
4 分 治
分治，分而治之。
分治算法的核心步驟就是兩步，一是分，二是治。但這還引申出了一系列的問題，為什么分，怎么分，怎么治，治后如何。
分治算法很像是一種向下管理的思想，從最高級(jí)層層劃分，將子任務(wù)劃分給不同的子模塊，進(jìn)而可以進(jìn)行大問題的拆分，對(duì)系統(tǒng)問題的粒度進(jìn)行細(xì)化，尋求最底層的最基本的解。這樣的思路在很多領(lǐng)域都有運(yùn)用，比如幾何數(shù)學(xué)中的正交坐標(biāo)、單位坐標(biāo)、基的概念等，都是通過將復(fù)雜問題簡(jiǎn)化為基本的子問題，然后通過先解決子模塊再逐步解決主模塊。
在實(shí)際的運(yùn)用中，分治算法主要包括兩個(gè)維度的處理，一是自頂向下，將主要問題劃分逐層級(jí)劃分為子問題；二是自底向上，將子問題的解逐層遞增融入主問題的求解中。
那為什么要分？這個(gè)很好解釋，由于主要問題的規(guī)模過大，無法直接求解，所以需要對(duì)主要問題進(jìn)行粒度劃分。
那怎么分？遵循計(jì)算機(jī)的最擅長(zhǎng)的重復(fù)運(yùn)算，劃分出來的子問題需要相互獨(dú)立并且與原問題結(jié)構(gòu)特征相同，這樣能夠保證解決子問題后，主問題也就能夠順勢(shì)而解。
怎么治？這就涉及到最基本子問題的求解，我們約定最小的子問題是能夠輕易得到解決的，這樣的子問題劃分才具有意義，所以在治的環(huán)節(jié)就是需要對(duì)最基本子問題的簡(jiǎn)易求解。
治后如何？子問題的求解是為了主問題而服務(wù)的。當(dāng)最基本的子問題得到解后，需要層層向上遞增，逐步獲得更高層次問題的解，直到獲得原問題的最終解。
分治思想的圖解可見下圖。通過層層粒度上的劃分，將原問題劃分為最小的子問題，然后再向上依次得到更高粒度的解。從上而下，再?gòu)南露?。先分解，再求解，再合并?/strong>
案例
歸并排序。
5 動(dòng)態(tài)規(guī)劃
講完分治，我們知道分治思想最重要的一點(diǎn)是分解出的子問題是相互獨(dú)立且結(jié)構(gòu)特征相同的。這一點(diǎn)并不是所有問題都能滿足，許多問題的劃分的子問題往往都是相互重疊且互相影響的，那么就很難使用分治算法進(jìn)行有效而又干凈的子問題劃分。
于是乎，動(dòng)態(tài)規(guī)劃來了。動(dòng)態(tài)規(guī)劃同樣需要將問題劃分為多個(gè)子問題，但是子問題之間往往不是互相獨(dú)立的。當(dāng)前子問題的解可看作是前多個(gè)階段問題的完整總結(jié)。因此這就需要在在子問題求解的過程中進(jìn)行多階段的決策，同時(shí)當(dāng)前階段之前的決策都能夠構(gòu)成一種最優(yōu)的子結(jié)構(gòu)。這就是所謂的最優(yōu)化原理。
最優(yōu)化原理，一個(gè)最優(yōu)化策略具有這樣的性質(zhì)，不論過去狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。同時(shí)，這樣的最優(yōu)策略是針對(duì)有已作出決策的總結(jié)，對(duì)后來的決策沒有直接影響，只能借用目前最優(yōu)策略的狀態(tài)數(shù)據(jù)。這也被稱之為無后效性。
動(dòng)態(tài)規(guī)劃是在目前看來非常不接近人類思維方式一種算法，主要原因是在于人腦在演算的過程中很難對(duì)每一次決策的結(jié)果進(jìn)行記憶。動(dòng)態(tài)規(guī)劃在實(shí)際的操作中，往往需要額外的空間對(duì)每個(gè)階段的狀態(tài)數(shù)據(jù)進(jìn)行保存，以便下次決策的使用。
動(dòng)態(tài)規(guī)劃的求解思路如下圖解。動(dòng)歸的開始需要將問題按照一定順序劃分為各個(gè)階段，然后確定每個(gè)階段的狀態(tài)，如圖中節(jié)點(diǎn)的F0等。然后重點(diǎn)是根據(jù)決策的方法來確定狀態(tài)轉(zhuǎn)移方程。也就是需要根據(jù)當(dāng)前階段的狀態(tài)確定下一階段的狀態(tài)。
在這個(gè)過程中，下一狀態(tài)的確定往往需要參考之前的狀態(tài)。因此需要在每一次狀態(tài)轉(zhuǎn)移的過程中將當(dāng)前的狀態(tài)變量進(jìn)行記錄，方便之后的查找。
動(dòng)態(tài)規(guī)劃主要就是用來解決多階段決策的問題，但是實(shí)際問題中往往很難有統(tǒng)一的處理方法，必須結(jié)合問題的特點(diǎn)來進(jìn)行算法的設(shè)計(jì)，這也是這種算法很難真正掌握的原因。
案例
背包問題。 有 n 件物品和容量為 m 的背包，給出物品的重量以及價(jià)值。求解讓裝入背包的物品重量不超過背包容量且價(jià)值最大 。
6 貪 心
貪心算法，我愿稱之為最現(xiàn)實(shí)的算法思想。
人活在世上，不可能每一個(gè)選擇都那么恰到好處。那么多的問題，不可能所有問題都能找到最優(yōu)解。很多問題根本沒有準(zhǔn)確解，甚至于無解。所以在某些場(chǎng)景下，傻傻的去追求問題的最精確解是沒有意義的。
有人說，那還有最優(yōu)解呢。難道最優(yōu)解都不要了嗎？
沒錯(cuò)，許多問題雖然找不到最精確的解，但是的確會(huì)存在一個(gè)或者一些最優(yōu)解。但是一定要去追求這些最優(yōu)解嗎？我看不一定。
算法的存在不是單純的為了對(duì)問題求解，更多的是提供一種「策略」。何謂「策略」，解決問題的一種方式，一個(gè)角度，一條路。所以，貪心思想是有價(jià)值的。
說回貪心算法。從貪心二字就可得知，這個(gè)算法的目的就是為了「貪圖更多」。但是這種貪心是「目光短淺」的，這就導(dǎo)致貪心算法無法從長(zhǎng)遠(yuǎn)出發(fā)，只看重眼前的利益。
具體點(diǎn)說，貪心算法在執(zhí)行的過程中，每一次都會(huì)選擇最大的收益，但是總收益卻不一定最大。所以這樣傻白甜的思路帶來的好處就是選擇簡(jiǎn)單，不需要糾結(jié)，不需要考慮未來。
貪心算法的實(shí)現(xiàn)過程就是從問題的一個(gè)初始解出發(fā)，每一次都作出「當(dāng)前最優(yōu)」的選擇，直至遇到局部極值點(diǎn)。貪心所帶來的局限性很明顯，就是無法保證最后的解是最優(yōu)的，很容易陷入局部最優(yōu)的情況。
但是它每一次做選擇的速度很快，同時(shí)判斷條件簡(jiǎn)單，能夠比較快速的給出一種差不多的解決方案。這里的圖解我用下圖來表示。
這個(gè)圖表示的是求解對(duì)多條直線的交點(diǎn)。很顯然，下圖中的直線是不存在統(tǒng)一交點(diǎn)的，但是可以通過算法求得統(tǒng)一交點(diǎn)的最優(yōu)解。若是采用貪心算法，那么在進(jìn)行迭代時(shí)，每一次都會(huì)選擇離此時(shí)位置最近的直線進(jìn)行更新。這樣一來，在經(jīng)過多次迭代后，交點(diǎn)的位置就會(huì)在某一片區(qū)域無限輪回跳轉(zhuǎn)。而這片區(qū)域也就是能求得出的大致的最優(yōu)解區(qū)域。
案例
旅行推銷員問題。 給定一系列城市和每對(duì)城市之間的距離，求解訪問每一座城市一次并回到起始城市的最短回路。
7 回 溯
蒹葭蒼蒼，白露為霜。所謂伊人，在水一方。溯洄從之，道阻且長(zhǎng)。溯游從之，宛在水中央。
每每提及回溯，都會(huì)忍不住想到「蒹葭」里的這句詩。看到心中所懷念的心上人啊，忍不住逆流而上去追尋她，盡管追隨的道路險(xiǎn)阻又漫長(zhǎng)；又順流而下繼續(xù)尋覓，感覺她似乎就在河水中央。回溯算法的過程正如追逐愛情般的艱辛和反復(fù)，時(shí)而溯洄從之，時(shí)而溯游從之。
回溯算法也可稱作試探算法，是不是讓你回憶起了在女神面前的小心翼翼。簡(jiǎn)單來說，回溯的過程就是在做出下一步選擇之前，先對(duì)每一種可能進(jìn)行試探；只有當(dāng)可能性存在時(shí)才會(huì)向前邁進(jìn)，倘若所有選擇都不可能，那么則向后退回原來的位置，重新選擇。
這樣看起來，回溯算法很像是一種進(jìn)行中的枚舉算法，在行進(jìn)的過程中對(duì)所有可能性進(jìn)行枚舉并判斷。常用的應(yīng)用場(chǎng)景就在對(duì)樹結(jié)構(gòu)、圖結(jié)構(gòu)以及棋盤落子的遍歷上。
舉一個(gè)很簡(jiǎn)單的例子，看下面圖解。假設(shè)目的是從最O0到達(dá)O4，需要對(duì)所有節(jié)點(diǎn)進(jìn)行回溯遍歷路徑。那么回溯算法的過程則需要在前進(jìn)的每一步對(duì)所有可能的路徑進(jìn)行試探。
比方說，O0節(jié)點(diǎn)前進(jìn)的路徑有三條，分別是上中下條的O1。回溯過程的開始，先走上面的O1，然后能夠到達(dá)上面 O2，但是這時(shí)是一條死路。那么就需要從O2退回到O1，而此時(shí)O1的唯一選擇也走不通，所以還需要從O1退回到O0。然后繼續(xù)試探中間的O1。
回溯算法的過程就是不斷進(jìn)行這樣的試探、判斷、退回并重新試探，直至找到一條完整的前進(jìn)路徑。只不過在這個(gè)過程中，可以通過「剪枝」等限制條件降低試探搜索的空間，從而避免重復(fù)無效的試探。比方說上下的O2節(jié)點(diǎn)，在經(jīng)過O0-O1-O2的試探之后，就已經(jīng)驗(yàn)證了該節(jié)點(diǎn)不可行性，下次就無須從O1開始重復(fù)對(duì)O2的試探。
回溯思想在許多大規(guī)模的問題的求解上都能得到有效的運(yùn)用?；厮菽軌?qū)?fù)雜問題進(jìn)行分步調(diào)整，從而在中間的過程中可對(duì)所有可能運(yùn)用枚舉思想進(jìn)行遍歷。這樣往往能夠清地看到問題解決的層次，從而可以幫助更好地理解問題的最終解結(jié)構(gòu)。
案例
八皇后問題。 在8×8格的國(guó)際象棋上擺放8個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。
8 模 擬
模擬思想的理解相比上述思想應(yīng)該不是什么難事。
許多真實(shí)場(chǎng)景下，由于問題規(guī)模過大，變量過多等因素，很難將具體的問題抽象出來，也就無法針對(duì)抽象問題的特征來進(jìn)行算法的設(shè)計(jì)。這個(gè)時(shí)候，模擬思想或許是最佳的解題策略。
模擬的過程就是對(duì)真實(shí)場(chǎng)景盡可能的模擬，然后通過計(jì)算機(jī)強(qiáng)大的計(jì)算能力對(duì)結(jié)果進(jìn)行預(yù)測(cè)。這相較于上述的算法是一種更為宏大的思想。在進(jìn)行現(xiàn)實(shí)場(chǎng)景的模擬中，可能系統(tǒng)部件的實(shí)現(xiàn)都需要上述幾個(gè)算法思想的參與。
模擬說起來是一種很玄幻的思想，沒有具體的實(shí)現(xiàn)思路，也沒有具體的優(yōu)化策略。只能說，具體問題具體分析。
那應(yīng)該怎么樣來圖解呢。我的理解是自定義的，任意的輸入，不規(guī)則的系統(tǒng)響應(yīng)，但是只為了獲得一個(gè)可靠的理想的輸出。
9 總 結(jié)
算法思想這種東西，實(shí)際上是很玄幻的。同一種問題，或許在實(shí)現(xiàn)上可以采用不同的思想進(jìn)行。這八種思想也不是想象中那么高的獨(dú)立性，很多思想都是雜糅在一起的，只是角度和側(cè)重點(diǎn)不同。上面這些案例也不代表單只能用一種思想來解答，只是用來體會(huì)一下對(duì)應(yīng)的算法思想。
作為底層的程序員，雖說不需要每天刷題，但是基礎(chǔ)的算法思想還是需要有的。這種東西不是具體于某個(gè)算法，而是在于更高層次的對(duì)于系統(tǒng)或者需求的理解。
如獨(dú)立之精神，自由之思想般。
最后的最后，記得給我轉(zhuǎn)發(fā)、點(diǎn)贊、在看三連支持吧，這是我原創(chuàng)的動(dòng)力呢！
免責(zé)聲明：本文內(nèi)容由21ic獲得授權(quán)后發(fā)布，版權(quán)歸原作者所有，本平臺(tái)僅提供信息存儲(chǔ)服務(wù)。文章僅代表作者個(gè)人觀點(diǎn)，不代表本平臺(tái)立場(chǎng)，如有問題，請(qǐng)聯(lián)系我們，謝謝！
下載文檔
