Python算法有哪些

本篇內(nèi)容主要講解“Python算法有哪些”，感興趣的朋友不妨來(lái)看看。本文介紹的方法操作簡(jiǎn)單快捷，實(shí)用性強(qiáng)。下面就讓小編來(lái)帶大家學(xué)習(xí)“Python算法有哪些”吧!

 1   枚 舉

首先，最為簡(jiǎn)單的思想，枚舉算法。枚舉也叫窮舉，顧名思義，就是窮盡列舉。枚舉思想的應(yīng)用場(chǎng)景十分廣泛，也非常容易理解。簡(jiǎn)單來(lái)說(shuō)，枚舉就是將問(wèn)題的可能解依次列舉出來(lái)，然后一一帶入問(wèn)題檢驗(yàn)，從而從一系列可能解中獲得能夠解決問(wèn)題的精確解。

枚舉雖然看起來(lái)簡(jiǎn)單，但是其實(shí)還是有一些容易被人忽視的考慮點(diǎn)。比方說(shuō)待解決問(wèn)題的「可能解/候選解」的篩選條件，「可能解」之間相互的影響，窮舉「可能解」的代價(jià)，「可能解」的窮舉方式等等。

很多時(shí)候?qū)嶋H上不必去追求高大上的復(fù)雜算法結(jié)構(gòu)，反而大道至簡(jiǎn)，采用枚舉法就能夠很好的規(guī)避系統(tǒng)復(fù)雜性帶來(lái)的冗余，同時(shí)或許在一定程度上還能夠?qū)臻g進(jìn)行縮減。

枚舉思想的流程可以用下圖來(lái)表示。通過(guò)實(shí)現(xiàn)事先確定好「可能解」，然后逐一在系統(tǒng)中進(jìn)行驗(yàn)證，根據(jù)驗(yàn)證結(jié)果來(lái)對(duì)「可能解」進(jìn)行分析和論證。這是一種很明顯的結(jié)果導(dǎo)向型的思想，簡(jiǎn)單粗暴地試圖從最終結(jié)果反向分析「可能解」的可行性。

不過(guò)，枚舉思想的劣勢(shì)當(dāng)然也很明顯。在實(shí)際的運(yùn)行程序中，能夠直接通過(guò)枚舉方法進(jìn)行求解的問(wèn)題少之又少。而當(dāng)「可能解」的篩選條件不清晰，導(dǎo)致「可能解」的數(shù)量和范圍無(wú)法準(zhǔn)確判斷時(shí)，枚舉就失去了意義。然而當(dāng)「可能解」的規(guī)模比較小，同時(shí)依次驗(yàn)證的過(guò)程容易實(shí)施時(shí)，枚舉思想不失為一種方便快捷的方式。只不過(guò)在具體使用時(shí)，還可以針對(duì)應(yīng)用場(chǎng)景對(duì)「可能解」的驗(yàn)證進(jìn)行優(yōu)化。這種優(yōu)化可以從兩個(gè)方向入手，一是問(wèn)題的簡(jiǎn)化，盡可能對(duì)需要處理的問(wèn)題進(jìn)行模型結(jié)構(gòu)上的精簡(jiǎn)。這種精簡(jiǎn)具體可體現(xiàn)在問(wèn)題中的變量數(shù)目，減少變量的數(shù)據(jù)，從而能夠從根本上降低「可能解」的組合。二是對(duì)篩選「可能解」的范圍和條件進(jìn)行嚴(yán)格判斷，盡可能的剔除大部分無(wú)效的「可能解」。雖說(shuō)如此，但是一般而言大部分枚舉不可用的場(chǎng)景都是由于「可能解」的數(shù)量過(guò)多，無(wú)法在有限空間或有限時(shí)間內(nèi)完成所有可能性的驗(yàn)證。不過(guò)實(shí)際上枚舉思想是最接近人的思維方式，在更多的時(shí)候是用來(lái)幫助我們?nèi)ァ咐斫鈫?wèn)題」，而不是「解決問(wèn)題」。

案例：百錢買百雞問(wèn)題。翻譯過(guò)來(lái)，意思是公雞一個(gè)五塊錢，母雞一個(gè)三塊錢，小雞三個(gè)一塊錢，現(xiàn)在要用一百塊錢買一百只雞，問(wèn)公雞、母雞、小雞各多少只？

 2   遞 推

遞推思想跟枚舉思想一樣，都是接近人類思維方式的思想，甚至在實(shí)際生活具有比枚舉思想更多的應(yīng)用場(chǎng)景。人腦在遇到未知的問(wèn)題時(shí)，大多數(shù)人第一直覺(jué)都會(huì)從積累的「先驗(yàn)知識(shí)」出發(fā)，試圖從「已知」推導(dǎo)「未知」，從而解決問(wèn)題，說(shuō)服自己。

事實(shí)上，這就是一種遞推的算法思想。遞推思想的核心就是從已知條件出發(fā)，逐步推算出問(wèn)題的解。實(shí)現(xiàn)方式很像是初高中時(shí)我們的數(shù)學(xué)考卷上一連串的「因?yàn)椤埂杆浴埂Ｄ莻€(gè)時(shí)候還是用三個(gè)點(diǎn)來(lái)表示的。

而對(duì)于計(jì)算機(jī)而言，復(fù)雜的推導(dǎo)其實(shí)很難實(shí)現(xiàn)。計(jì)算機(jī)擅長(zhǎng)的是執(zhí)行高密度重復(fù)性高的工作，對(duì)于隨機(jī)性高變化多端的問(wèn)題反而不好計(jì)算。相比之下，人腦在對(duì)不同維度的問(wèn)題進(jìn)行推導(dǎo)時(shí)具有更高的自由度。

比方說(shuō)，人腦可以很容易的從「太陽(yáng)從東邊升起」推出「太陽(yáng)從西邊落下」，然后大致推出「現(xiàn)在的時(shí)間」。但是對(duì)于計(jì)算機(jī)而言并沒(méi)有那么容易，你可能需要設(shè)置一系列的限制條件，才能避免計(jì)算機(jī)推出「太陽(yáng)/月亮/星星」從「南/北/東邊」「落下/飛走/掉落」的可能性。

我說(shuō)這個(gè)例子的用意是在說(shuō)明，計(jì)算機(jī)在運(yùn)用遞推思想時(shí)，大多都是重復(fù)性的推理。比方說(shuō)，從「今天是1號(hào)」推出「明天是2號(hào)」。這種推理的結(jié)構(gòu)十分類似，往往可以通過(guò)繼而往復(fù)的推理就可以得到最終的解。

遞推思想用圖解來(lái)表示可以參見(jiàn)下圖。每一次推導(dǎo)的結(jié)果可以作為下一次推導(dǎo)的的開(kāi)始，這似乎跟迭代、遞歸的思想有點(diǎn)類似，不過(guò)遞推的范疇要更廣一些。

案例：兔子問(wèn)題。 定一對(duì)大兔子每月能生一對(duì)小兔子，且每對(duì)新生的小兔子經(jīng)過(guò)一個(gè)月可以長(zhǎng)成一對(duì)大兔子,具備繁殖能力，如果不發(fā)生死亡，且每次均生下一雌一雄，問(wèn)一年后共有多少對(duì)兔子？

 3   遞 歸

說(shuō)完遞推，就不得不說(shuō)說(shuō)它的兄弟思想——遞歸算法。二者同樣都帶有一個(gè)「遞」字，可以看出二者還是具有一定的相似性的?！高f」的理解可以是逐次、逐步。在遞推中，是逐次對(duì)問(wèn)題進(jìn)行推導(dǎo)直到獲得最終解。而在遞歸中，則是逐次回歸迭代，直到跳出回歸。

遞歸算法實(shí)際上是把問(wèn)題轉(zhuǎn)化成規(guī)模更小的同類子問(wèn)題，先解決子問(wèn)題，再通過(guò)相同的求解過(guò)程逐步解決更高層次的問(wèn)題，最終獲得最終的解。所以相較于遞推而言，遞歸算法的范疇更小，要求子問(wèn)題跟父問(wèn)題的結(jié)構(gòu)相同。而遞推思想從概念上并沒(méi)有這樣的約束。

用一句話來(lái)形容遞歸算法的實(shí)現(xiàn)，就是在函數(shù)或者子過(guò)程的內(nèi)部，直接或間接的調(diào)用自己算法。所以在實(shí)現(xiàn)的過(guò)程中，最重要的是確定遞歸過(guò)程終止的條件，也就是迭代過(guò)程跳出的條件判斷。否則，程序會(huì)在自我調(diào)用中無(wú)限循環(huán)，最終導(dǎo)致內(nèi)存溢出而崩潰。

遞歸算法的圖解可如下圖。很明顯，遞歸思想其實(shí)就是一個(gè)套娃過(guò)程。一般官方都是嚴(yán)禁套娃行為的。所以在使用時(shí)一定要明確「套娃」舉動(dòng)的停止條件，及時(shí)止損。

案例：漢諾塔問(wèn)題。 源于印度傳說(shuō)中，大梵天創(chuàng)造世界時(shí)造了三根金鋼石柱子，其中一根柱子自底向上疊著64片黃金圓盤。大梵天命令婆羅門把圓盤從下面開(kāi)始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動(dòng)一個(gè)圓盤。

 4   分 治

分治，分而治之。

分治算法的核心步驟就是兩步，一是分，二是治。但這還引申出了一系列的問(wèn)題，為什么分，怎么分，怎么治，治后如何。

分治算法很像是一種向下管理的思想，從最高級(jí)層層劃分，將子任務(wù)劃分給不同的子模塊，進(jìn)而可以進(jìn)行大問(wèn)題的拆分，對(duì)系統(tǒng)問(wèn)題的粒度進(jìn)行細(xì)化，尋求最底層的最基本的解。這樣的思路在很多領(lǐng)域都有運(yùn)用，比如幾何數(shù)學(xué)中的正交坐標(biāo)、單位坐標(biāo)、基的概念等，都是通過(guò)將復(fù)雜問(wèn)題簡(jiǎn)化為基本的子問(wèn)題，然后通過(guò)先解決子模塊再逐步解決主模塊。

在實(shí)際的運(yùn)用中，分治算法主要包括兩個(gè)維度的處理，一是自頂向下，將主要問(wèn)題劃分逐層級(jí)劃分為子問(wèn)題；二是自底向上，將子問(wèn)題的解逐層遞增融入主問(wèn)題的求解中。

那為什么要分？這個(gè)很好解釋，由于主要問(wèn)題的規(guī)模過(guò)大，無(wú)法直接求解，所以需要對(duì)主要問(wèn)題進(jìn)行粒度劃分。

那怎么分？遵循計(jì)算機(jī)的最擅長(zhǎng)的重復(fù)運(yùn)算，劃分出來(lái)的子問(wèn)題需要相互獨(dú)立并且與原問(wèn)題結(jié)構(gòu)特征相同，這樣能夠保證解決子問(wèn)題后，主問(wèn)題也就能夠順勢(shì)而解。

怎么治？這就涉及到最基本子問(wèn)題的求解，我們約定最小的子問(wèn)題是能夠輕易得到解決的，這樣的子問(wèn)題劃分才具有意義，所以在治的環(huán)節(jié)就是需要對(duì)最基本子問(wèn)題的簡(jiǎn)易求解。

治后如何？子問(wèn)題的求解是為了主問(wèn)題而服務(wù)的。當(dāng)最基本的子問(wèn)題得到解后，需要層層向上遞增，逐步獲得更高層次問(wèn)題的解，直到獲得原問(wèn)題的最終解。

分治思想的圖解可見(jiàn)下圖。通過(guò)層層粒度上的劃分，將原問(wèn)題劃分為最小的子問(wèn)題，然后再向上依次得到更高粒度的解。從上而下，再?gòu)南露?。先分解，再求解，再合并?/strong>

案例：歸并排序。

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

講完分治，我們知道分治思想最重要的一點(diǎn)是分解出的子問(wèn)題是相互獨(dú)立且結(jié)構(gòu)特征相同的。這一點(diǎn)并不是所有問(wèn)題都能滿足，許多問(wèn)題的劃分的子問(wèn)題往往都是相互重疊且互相影響的，那么就很難使用分治算法進(jìn)行有效而又干凈的子問(wèn)題劃分。

于是乎，動(dòng)態(tài)規(guī)劃來(lái)了。動(dòng)態(tài)規(guī)劃同樣需要將問(wèn)題劃分為多個(gè)子問(wèn)題，但是子問(wèn)題之間往往不是互相獨(dú)立的。當(dāng)前子問(wèn)題的解可看作是前多個(gè)階段問(wèn)題的完整總結(jié)。因此這就需要在在子問(wèn)題求解的過(guò)程中進(jìn)行多階段的決策，同時(shí)當(dāng)前階段之前的決策都能夠構(gòu)成一種最優(yōu)的子結(jié)構(gòu)。這就是所謂的最優(yōu)化原理。

最優(yōu)化原理，一個(gè)最優(yōu)化策略具有這樣的性質(zhì)，不論過(guò)去狀態(tài)和決策如何，對(duì)前面的決策所形成的狀態(tài)而言，余下的諸決策必須構(gòu)成最優(yōu)策略。同時(shí)，這樣的最優(yōu)策略是針對(duì)有已作出決策的總結(jié)，對(duì)后來(lái)的決策沒(méi)有直接影響，只能借用目前最優(yōu)策略的狀態(tài)數(shù)據(jù)。這也被稱之為無(wú)后效性。

動(dòng)態(tài)規(guī)劃是在目前看來(lá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)歸的開(kāi)始需要將問(wèn)題按照一定順序劃分為各個(gè)階段，然后確定每個(gè)階段的狀態(tài)，如圖中節(jié)點(diǎn)的F0等。然后重點(diǎn)是根據(jù)決策的方法來(lái)確定狀態(tài)轉(zhuǎn)移方程。也就是需要根據(jù)當(dāng)前階段的狀態(tài)確定下一階段的狀態(tài)。

在這個(gè)過(guò)程中，下一狀態(tài)的確定往往需要參考之前的狀態(tài)。因此需要在每一次狀態(tài)轉(zhuǎn)移的過(guò)程中將當(dāng)前的狀態(tài)變量進(jìn)行記錄，方便之后的查找。

動(dòng)態(tài)規(guī)劃主要就是用來(lái)解決多階段決策的問(wèn)題，但是實(shí)際問(wèn)題中往往很難有統(tǒng)一的處理方法，必須結(jié)合問(wèn)題的特點(diǎn)來(lái)進(jìn)行算法的設(shè)計(jì)，這也是這種算法很難真正掌握的原因。

案例

背包問(wèn)題。 有 n 件物品和容量為 m 的背包，給出物品的重量以及價(jià)值。求解讓裝入背包的物品重量不超過(guò)背包容量且價(jià)值最大 。

 6   貪 心

貪心算法，我愿稱之為最現(xiàn)實(shí)的算法思想。

人活在世上，不可能每一個(gè)選擇都那么恰到好處。那么多的問(wèn)題，不可能所有問(wèn)題都能找到最優(yōu)解。很多問(wèn)題根本沒(méi)有準(zhǔn)確解，甚至于無(wú)解。所以在某些場(chǎng)景下，傻傻的去追求問(wèn)題的最精確解是沒(méi)有意義的。

有人說(shuō)，那還有最優(yōu)解呢。難道最優(yōu)解都不要了嗎？

沒(méi)錯(cuò)，許多問(wèn)題雖然找不到最精確的解，但是的確會(huì)存在一個(gè)或者一些最優(yōu)解。但是一定要去追求這些最優(yōu)解嗎？我看不一定。

算法的存在不是單純的為了對(duì)問(wèn)題求解，更多的是提供一種「策略」。何謂「策略」，解決問(wèn)題的一種方式，一個(gè)角度，一條路。所以，貪心思想是有價(jià)值的。

說(shuō)回貪心算法。從貪心二字就可得知，這個(gè)算法的目的就是為了「貪圖更多」。但是這種貪心是「目光短淺」的，這就導(dǎo)致貪心算法無(wú)法從長(zhǎng)遠(yuǎn)出發(fā)，只看重眼前的利益。

具體點(diǎn)說(shuō)，貪心算法在執(zhí)行的過(guò)程中，每一次都會(huì)選擇最大的收益，但是總收益卻不一定最大。所以這樣傻白甜的思路帶來(lái)的好處就是選擇簡(jiǎn)單，不需要糾結(jié)，不需要考慮未來(lái)。

貪心算法的實(shí)現(xiàn)過(guò)程就是從問(wèn)題的一個(gè)初始解出發(fā)，每一次都作出「當(dāng)前最優(yōu)」的選擇，直至遇到局部極值點(diǎn)。貪心所帶來(lái)的局限性很明顯，就是無(wú)法保證最后的解是最優(yōu)的，很容易陷入局部最優(yōu)的情況。

但是它每一次做選擇的速度很快，同時(shí)判斷條件簡(jiǎn)單，能夠比較快速的給出一種差不多的解決方案。這里的圖解我用下圖來(lái)表示。

這個(gè)圖表示的是求解對(duì)多條直線的交點(diǎn)。很顯然，下圖中的直線是不存在統(tǒng)一交點(diǎn)的，但是可以通過(guò)算法求得統(tǒng)一交點(diǎn)的最優(yōu)解。若是采用貪心算法，那么在進(jìn)行迭代時(shí)，每一次都會(huì)選擇離此時(shí)位置最近的直線進(jìn)行更新。這樣一來(lái)，在經(jīng)過(guò)多次迭代后，交點(diǎn)的位置就會(huì)在某一片區(qū)域無(wú)限輪回跳轉(zhuǎn)。而這片區(qū)域也就是能求得出的大致的最優(yōu)解區(qū)域。

案例

旅行推銷員問(wèn)題。 給定一系列城市和每對(duì)城市之間的距離，求解訪問(wèn)每一座城市一次并回到起始城市的最短回路。

 7   回 溯

回溯算法也可稱作試探算法，是不是讓你回憶起了在女神面前的小心翼翼。簡(jiǎn)單來(lái)說(shuō)，回溯的過(guò)程就是在做出下一步選擇之前，先對(duì)每一種可能進(jìn)行試探；只有當(dāng)可能性存在時(shí)才會(huì)向前邁進(jìn)，倘若所有選擇都不可能，那么則向后退回原來(lái)的位置，重新選擇。

這樣看起來(lái)，回溯算法很像是一種進(jìn)行中的枚舉算法，在行進(jìn)的過(guò)程中對(duì)所有可能性進(jìn)行枚舉并判斷。常用的應(yīng)用場(chǎng)景就在對(duì)樹(shù)結(jié)構(gòu)、圖結(jié)構(gòu)以及棋盤落子的遍歷上。

舉一個(gè)很簡(jiǎn)單的例子，看下面圖解。假設(shè)目的是從最O0到達(dá)O4，需要對(duì)所有節(jié)點(diǎn)進(jìn)行回溯遍歷路徑。那么回溯算法的過(guò)程則需要在前進(jìn)的每一步對(duì)所有可能的路徑進(jìn)行試探。

比方說(shuō)，O0節(jié)點(diǎn)前進(jìn)的路徑有三條，分別是上中下條的O1?；厮葸^(guò)程的開(kāi)始，先走上面的O1，然后能夠到達(dá)上面 O2，但是這時(shí)是一條死路。那么就需要從O2退回到O1，而此時(shí)O1的唯一選擇也走不通，所以還需要從O1退回到O0。然后繼續(xù)試探中間的O1。

回溯算法的過(guò)程就是不斷進(jìn)行這樣的試探、判斷、退回并重新試探，直至找到一條完整的前進(jìn)路徑。只不過(guò)在這個(gè)過(guò)程中，可以通過(guò)「剪枝」等限制條件降低試探搜索的空間，從而避免重復(fù)無(wú)效的試探。比方說(shuō)上下的O2節(jié)點(diǎn)，在經(jīng)過(guò)O0-O1-O2的試探之后，就已經(jīng)驗(yàn)證了該節(jié)點(diǎn)不可行性，下次就無(wú)須從O1開(kāi)始重復(fù)對(duì)O2的試探。

回溯思想在許多大規(guī)模的問(wèn)題的求解上都能得到有效的運(yùn)用。回溯能夠?qū)?fù)雜問(wèn)題進(jìn)行分步調(diào)整，從而在中間的過(guò)程中可對(duì)所有可能運(yùn)用枚舉思想進(jìn)行遍歷。這樣往往能夠清地看到問(wèn)題解決的層次，從而可以幫助更好地理解問(wèn)題的最終解結(jié)構(gòu)。

案例

八皇后問(wèn)題。 在8×8格的國(guó)際象棋上擺放8個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問(wèn)有多少種擺法。

 8   模 擬

模擬思想的理解相比上述思想應(yīng)該不是什么難事。

許多真實(shí)場(chǎng)景下，由于問(wèn)題規(guī)模過(guò)大，變量過(guò)多等因素，很難將具體的問(wèn)題抽象出來(lái)，也就無(wú)法針對(duì)抽象問(wèn)題的特征來(lái)進(jìn)行算法的設(shè)計(jì)。這個(gè)時(shí)候，模擬思想或許是最佳的解題策略。

模擬的過(guò)程就是對(duì)真實(shí)場(chǎng)景盡可能的模擬，然后通過(guò)計(jì)算機(jī)強(qiáng)大的計(jì)算能力對(duì)結(jié)果進(jìn)行預(yù)測(cè)。這相較于上述的算法是一種更為宏大的思想。在進(jìn)行現(xiàn)實(shí)場(chǎng)景的模擬中，可能系統(tǒng)部件的實(shí)現(xiàn)都需要上述幾個(gè)算法思想的參與。

模擬說(shuō)起來(lái)是一種很玄幻的思想，沒(méi)有具體的實(shí)現(xiàn)思路，也沒(méi)有具體的優(yōu)化策略。只能說(shuō)，具體問(wèn)題具體分析。

那應(yīng)該怎么樣來(lái)圖解呢。我的理解是自定義的，任意的輸入，不規(guī)則的系統(tǒng)響應(yīng)，但是只為了獲得一個(gè)可靠的理想的輸出。

到此，相信大家對(duì)“Python算法有哪些”有了更深的了解，不妨來(lái)實(shí)際操作一番吧！這里是億速云網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！