Python算法有哪些

本篇內容主要講解“Python算法有哪些”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“Python算法有哪些”吧!

 1   枚 舉

首先，最為簡單的思想，枚舉算法。枚舉也叫窮舉，顧名思義，就是窮盡列舉。枚舉思想的應用場景十分廣泛，也非常容易理解。簡單來說，枚舉就是將問題的可能解依次列舉出來，然后一一帶入問題檢驗，從而從一系列可能解中獲得能夠解決問題的精確解。

枚舉雖然看起來簡單，但是其實還是有一些容易被人忽視的考慮點。比方說待解決問題的「可能解/候選解」的篩選條件，「可能解」之間相互的影響，窮舉「可能解」的代價，「可能解」的窮舉方式等等。

很多時候實際上不必去追求高大上的復雜算法結構，反而大道至簡，采用枚舉法就能夠很好的規避系統復雜性帶來的冗余，同時或許在一定程度上還能夠對空間進行縮減。

枚舉思想的流程可以用下圖來表示。通過實現事先確定好「可能解」，然后逐一在系統中進行驗證，根據驗證結果來對「可能解」進行分析和論證。這是一種很明顯的結果導向型的思想，簡單粗暴地試圖從最終結果反向分析「可能解」的可行性。

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

案例：百錢買百雞問題。翻譯過來，意思是公雞一個五塊錢，母雞一個三塊錢，小雞三個一塊錢，現在要用一百塊錢買一百只雞，問公雞、母雞、小雞各多少只？

 2   遞 推

遞推思想跟枚舉思想一樣，都是接近人類思維方式的思想，甚至在實際生活具有比枚舉思想更多的應用場景。人腦在遇到未知的問題時，大多數人第一直覺都會從積累的「先驗知識」出發，試圖從「已知」推導「未知」，從而解決問題，說服自己。

事實上，這就是一種遞推的算法思想。遞推思想的核心就是從已知條件出發，逐步推算出問題的解。實現方式很像是初高中時我們的數學考卷上一連串的「因為」「所以」。那個時候還是用三個點來表示的。

而對于計算機而言，復雜的推導其實很難實現。計算機擅長的是執行高密度重復性高的工作，對于隨機性高變化多端的問題反而不好計算。相比之下，人腦在對不同維度的問題進行推導時具有更高的自由度。

比方說，人腦可以很容易的從「太陽從東邊升起」推出「太陽從西邊落下」，然后大致推出「現在的時間」。但是對于計算機而言并沒有那么容易，你可能需要設置一系列的限制條件，才能避免計算機推出「太陽/月亮/星星」從「南/北/東邊」「落下/飛走/掉落」的可能性。

我說這個例子的用意是在說明，計算機在運用遞推思想時，大多都是重復性的推理。比方說，從「今天是1號」推出「明天是2號」。這種推理的結構十分類似，往往可以通過繼而往復的推理就可以得到最終的解。

遞推思想用圖解來表示可以參見下圖。每一次推導的結果可以作為下一次推導的的開始，這似乎跟迭代、遞歸的思想有點類似，不過遞推的范疇要更廣一些。

案例：兔子問題。 定一對大兔子每月能生一對小兔子，且每對新生的小兔子經過一個月可以長成一對大兔子,具備繁殖能力，如果不發生死亡，且每次均生下一雌一雄，問一年后共有多少對兔子？

 3   遞 歸

說完遞推，就不得不說說它的兄弟思想——遞歸算法。二者同樣都帶有一個「遞」字，可以看出二者還是具有一定的相似性的。「遞」的理解可以是逐次、逐步。在遞推中，是逐次對問題進行推導直到獲得最終解。而在遞歸中，則是逐次回歸迭代，直到跳出回歸。

遞歸算法實際上是把問題轉化成規模更小的同類子問題，先解決子問題，再通過相同的求解過程逐步解決更高層次的問題，最終獲得最終的解。所以相較于遞推而言，遞歸算法的范疇更小，要求子問題跟父問題的結構相同。而遞推思想從概念上并沒有這樣的約束。

用一句話來形容遞歸算法的實現，就是在函數或者子過程的內部，直接或間接的調用自己算法。所以在實現的過程中，最重要的是確定遞歸過程終止的條件，也就是迭代過程跳出的條件判斷。否則，程序會在自我調用中無限循環，最終導致內存溢出而崩潰。

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

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

 4   分 治

分治，分而治之。

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

分治算法很像是一種向下管理的思想，從最高級層層劃分，將子任務劃分給不同的子模塊，進而可以進行大問題的拆分，對系統問題的粒度進行細化，尋求最底層的最基本的解。這樣的思路在很多領域都有運用，比如幾何數學中的正交坐標、單位坐標、基的概念等，都是通過將復雜問題簡化為基本的子問題，然后通過先解決子模塊再逐步解決主模塊。

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

那為什么要分？這個很好解釋，由于主要問題的規模過大，無法直接求解，所以需要對主要問題進行粒度劃分。

那怎么分？遵循計算機的最擅長的重復運算，劃分出來的子問題需要相互獨立并且與原問題結構特征相同，這樣能夠保證解決子問題后，主問題也就能夠順勢而解。

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

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

分治思想的圖解可見下圖。通過層層粒度上的劃分，將原問題劃分為最小的子問題，然后再向上依次得到更高粒度的解。從上而下，再從下而上。先分解，再求解，再合并。

案例：歸并排序。

 5   動態規劃

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

于是乎，動態規劃來了。動態規劃同樣需要將問題劃分為多個子問題，但是子問題之間往往不是互相獨立的。當前子問題的解可看作是前多個階段問題的完整總結。因此這就需要在在子問題求解的過程中進行多階段的決策，同時當前階段之前的決策都能夠構成一種最優的子結構。這就是所謂的最優化原理。

最優化原理，一個最優化策略具有這樣的性質，不論過去狀態和決策如何，對前面的決策所形成的狀態而言，余下的諸決策必須構成最優策略。同時，這樣的最優策略是針對有已作出決策的總結，對后來的決策沒有直接影響，只能借用目前最優策略的狀態數據。這也被稱之為無后效性。

動態規劃是在目前看來非常不接近人類思維方式一種算法，主要原因是在于人腦在演算的過程中很難對每一次決策的結果進行記憶。動態規劃在實際的操作中，往往需要額外的空間對每個階段的狀態數據進行保存，以便下次決策的使用。

動態規劃的求解思路如下圖解。動歸的開始需要將問題按照一定順序劃分為各個階段，然后確定每個階段的狀態，如圖中節點的F0等。然后重點是根據決策的方法來確定狀態轉移方程。也就是需要根據當前階段的狀態確定下一階段的狀態。

在這個過程中，下一狀態的確定往往需要參考之前的狀態。因此需要在每一次狀態轉移的過程中將當前的狀態變量進行記錄，方便之后的查找。

動態規劃主要就是用來解決多階段決策的問題，但是實際問題中往往很難有統一的處理方法，必須結合問題的特點來進行算法的設計，這也是這種算法很難真正掌握的原因。

案例

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

 6   貪 心

貪心算法，我愿稱之為最現實的算法思想。

人活在世上，不可能每一個選擇都那么恰到好處。那么多的問題，不可能所有問題都能找到最優解。很多問題根本沒有準確解，甚至于無解。所以在某些場景下，傻傻的去追求問題的最精確解是沒有意義的。

有人說，那還有最優解呢。難道最優解都不要了嗎？

沒錯，許多問題雖然找不到最精確的解，但是的確會存在一個或者一些最優解。但是一定要去追求這些最優解嗎？我看不一定。

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

說回貪心算法。從貪心二字就可得知，這個算法的目的就是為了「貪圖更多」。但是這種貪心是「目光短淺」的，這就導致貪心算法無法從長遠出發，只看重眼前的利益。

具體點說，貪心算法在執行的過程中，每一次都會選擇最大的收益，但是總收益卻不一定最大。所以這樣傻白甜的思路帶來的好處就是選擇簡單，不需要糾結，不需要考慮未來。

貪心算法的實現過程就是從問題的一個初始解出發，每一次都作出「當前最優」的選擇，直至遇到局部極值點。貪心所帶來的局限性很明顯，就是無法保證最后的解是最優的，很容易陷入局部最優的情況。

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

這個圖表示的是求解對多條直線的交點。很顯然，下圖中的直線是不存在統一交點的，但是可以通過算法求得統一交點的最優解。若是采用貪心算法，那么在進行迭代時，每一次都會選擇離此時位置最近的直線進行更新。這樣一來，在經過多次迭代后，交點的位置就會在某一片區域無限輪回跳轉。而這片區域也就是能求得出的大致的最優解區域。

案例

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

 7   回 溯

回溯算法也可稱作試探算法，是不是讓你回憶起了在女神面前的小心翼翼。簡單來說，回溯的過程就是在做出下一步選擇之前，先對每一種可能進行試探；只有當可能性存在時才會向前邁進，倘若所有選擇都不可能，那么則向后退回原來的位置，重新選擇。

這樣看起來，回溯算法很像是一種進行中的枚舉算法，在行進的過程中對所有可能性進行枚舉并判斷。常用的應用場景就在對樹結構、圖結構以及棋盤落子的遍歷上。

舉一個很簡單的例子，看下面圖解。假設目的是從最O0到達O4，需要對所有節點進行回溯遍歷路徑。那么回溯算法的過程則需要在前進的每一步對所有可能的路徑進行試探。

比方說，O0節點前進的路徑有三條，分別是上中下條的O1。回溯過程的開始，先走上面的O1，然后能夠到達上面 O2，但是這時是一條死路。那么就需要從O2退回到O1，而此時O1的唯一選擇也走不通，所以還需要從O1退回到O0。然后繼續試探中間的O1。

回溯算法的過程就是不斷進行這樣的試探、判斷、退回并重新試探，直至找到一條完整的前進路徑。只不過在這個過程中，可以通過「剪枝」等限制條件降低試探搜索的空間，從而避免重復無效的試探。比方說上下的O2節點，在經過O0-O1-O2的試探之后，就已經驗證了該節點不可行性，下次就無須從O1開始重復對O2的試探。

回溯思想在許多大規模的問題的求解上都能得到有效的運用。回溯能夠將復雜問題進行分步調整，從而在中間的過程中可對所有可能運用枚舉思想進行遍歷。這樣往往能夠清地看到問題解決的層次，從而可以幫助更好地理解問題的最終解結構。

案例

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

 8   模 擬

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

許多真實場景下，由于問題規模過大，變量過多等因素，很難將具體的問題抽象出來，也就無法針對抽象問題的特征來進行算法的設計。這個時候，模擬思想或許是最佳的解題策略。

模擬的過程就是對真實場景盡可能的模擬，然后通過計算機強大的計算能力對結果進行預測。這相較于上述的算法是一種更為宏大的思想。在進行現實場景的模擬中，可能系統部件的實現都需要上述幾個算法思想的參與。

模擬說起來是一種很玄幻的思想，沒有具體的實現思路，也沒有具體的優化策略。只能說，具體問題具體分析。

那應該怎么樣來圖解呢。我的理解是自定義的，任意的輸入，不規則的系統響應，但是只為了獲得一個可靠的理想的輸出。

到此，相信大家對“Python算法有哪些”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！