人理解算法,神定義哲學(xué)

點(diǎn)擊藍(lán)字

關(guān)注我們

遞歸、分治、動(dòng)態(tài)規(guī)劃、貪心、回溯、分支限界這些算法，原本都是為了解決問題。

但了解算法，會(huì)發(fā)現(xiàn)古老的哲學(xué)。

無論是否跟產(chǎn)品經(jīng)理崗位，甚至IT行業(yè)打交道，都會(huì)被算法背后的智慧吸引。

?

1

遞歸算法

（recursion algorithm）

?

大師 L. Peter Deutsch 說過：To Iterate is Human, to Recurse, Divine。譯為：

人理解迭代，神理解遞歸。

在算法領(lǐng)域，直接或間接地調(diào)用自身的算法，就稱為遞歸算法。

?

典型代表：Fibonacci函數(shù)、Hanoi問題、數(shù)據(jù)結(jié)構(gòu)（二叉樹、廣義表）

案例：Fibonacci函數(shù)

即斐波那契數(shù)列，又稱黃金分割數(shù)列，因數(shù)學(xué)家萊昂納多·斐波那契（Leonardo Fibonacci）以兔子繁殖為例子而引入，故又稱為“兔子數(shù)列”。

我們都知道黃金分割，但是實(shí)際上和自然界的繁殖生息如此緊密。

?

一對兔子，每個(gè)月能生出一對小兔子來。如果所有兔子都不死，那么一年以后可以繁殖多少對兔子？

?

第一個(gè)月小兔子沒有繁殖能力，所以還是一對；兩個(gè)月后，生下一對小兔對數(shù)共有兩對；三個(gè)月以后，老兔子又生下一對，因?yàn)樾⊥米舆€沒有繁殖能力，所以一共是三對……

?

這個(gè)規(guī)律，就是生物學(xué)上著名的“魯?shù)戮S格定律”。

?

此外，觀察延齡草、野玫瑰、南美血根草、大波斯菊、金鳳花、耬斗菜、百合花、蝴蝶花的花瓣，可以發(fā)現(xiàn)它們花瓣數(shù)目具有斐波那契數(shù)：3、5、8、13、21……

?

2

分治法

（divide and conquer method）

?

將待求解的原問題劃分成k個(gè)較小規(guī)模的子問題，對這k個(gè)子問題分別求解。

如果子問題的規(guī)模仍然不夠小，則再將每個(gè)子問題劃分為k個(gè)規(guī)模更小的子問題，如此分解下去，直到問題規(guī)模足夠小.

再將子問題的解合并為一個(gè)更大規(guī)模的問題的解，自底向上逐步求出原問題的解。

?

典型代表：二分搜索、棋盤覆蓋、合并排序、最接近點(diǎn)對問題、循環(huán)賽日程表、漢諾塔、Fibonacci數(shù)列、階乘、快速排序......

?

案例：漢諾塔（Tower of Hanoi）

又稱河內(nèi)塔，是一個(gè)源于印度古老傳說的益智玩具。

?

大梵天創(chuàng)造世界的時(shí)候做了三根金剛石柱子，在一根柱子上從下往上按照大小順序摞著64片黃金圓盤。

?

大梵天命令婆羅門把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規(guī)定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動(dòng)一個(gè)圓盤。

?

有預(yù)言說，這件事完成時(shí)宇宙會(huì)在一瞬間閃電式毀滅。也有人相信婆羅門至今還在一刻不停地搬動(dòng)著圓盤。

上升到文化、宇宙、時(shí)間的話題，總是那么引人入勝！

如果移動(dòng)一個(gè)圓盤需要1秒鐘的話，等到64個(gè)圓盤全部重新落在一起，宇宙被毀滅是什么時(shí)候呢？

?

3

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

（dynamic programing method）

?

將待求解問題分解成若干個(gè)相互重疊的子問題，每個(gè)子問題對應(yīng)決策過程的一個(gè)階段。

一般來說，子問題的重疊關(guān)系表現(xiàn)在對給定問題求解的遞推關(guān)系（也就是動(dòng)態(tài)規(guī)劃函數(shù)）中，將子問題的解求解一次并填入表中，當(dāng)需要再次求解此子問題時(shí)，可以通過查表獲得該子問題的解而不用再次求解，從而避免了大量重復(fù)計(jì)算。

?

典型代表：最長公共子序列、最優(yōu)二叉查找樹、近似串匹配問題......?

?

4

貪心法

（greedy method）

?

貪心法在解決問題的策略上目光短淺，只根據(jù)當(dāng)前已有的信息就做出選擇，而且一旦做出了選擇，不管將來有什么結(jié)果，這個(gè)選擇都不會(huì)改變。

?

換言之，貪心法并不是從整體最優(yōu)考慮，它所做出的選擇只是在某種意義上的局部最優(yōu)。

這種局部最優(yōu)選擇并不總能獲得整體最優(yōu)解（Optimal Solution），但通常能獲得近似最優(yōu)解（Near-Optimal Solution）。

?

典型代表：TSP問題（最近鄰點(diǎn)）、TSP問題（最短鏈接）、圖著色、背包問題、多極度調(diào)度問題、霍夫曼編碼、單源最短路徑（Dijkstra算法）、最小生成樹（Prim和Kruskal算法）

案例：背包問題(Knapsack problem)?

?

可追溯到1897年數(shù)學(xué)家托比亞斯·丹齊格（Tobias Dantzig，1884-1956），指的是包裝你最有價(jià)值或有用的物品，而不會(huì)超載你的行李的常見問題。

問題可以描述為：給定一組物品，每種物品都有自己的重量和價(jià)格，在限定的總重量內(nèi)，我們?nèi)绾芜x擇，才能使得物品的總價(jià)格最高。

?

如何選擇最合適的物品放置于給定背包中。相似問題經(jīng)常出現(xiàn)在商業(yè)、組合數(shù)學(xué)，計(jì)算復(fù)雜性理論、密碼學(xué)和應(yīng)用數(shù)學(xué)等領(lǐng)域中。

?

5

回溯法

（back track method）

?

回溯法就是一種有組織的系統(tǒng)化搜索技術(shù)，可以看作是蠻力法窮舉搜索的改進(jìn)。

回溯法每次只構(gòu)建可能解的一部分，然后評估這個(gè)部分解，如果這個(gè)部分有可能導(dǎo)致一個(gè)完全解，對其進(jìn)一步搜索，否則，就不必繼續(xù)構(gòu)造這部分的解了，回溯法常常可以避免搜索所有可能的解.

所以，它往往比滿立法效率更高，適用于求解組合數(shù)組較大的問題。

?

回溯法是以深度優(yōu)先方式搜索問題解的算法，它適用于組合數(shù)較大的問題，能系統(tǒng)地搜索到一個(gè)問題的所有解惑任一解。

?

典型代表：哈密頓回路問題、八皇后問題、批處理作業(yè)調(diào)度......

?

案例：八皇后問題（Eight queens）

八皇后問題是國際象棋棋手馬克斯·貝瑟爾于1848年提出的問題，是回溯算法的典型案例。

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

?

高斯認(rèn)為有76種方案。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解，后來有人用圖論的方法解出92種結(jié)果。計(jì)算機(jī)發(fā)明后，有多種計(jì)算機(jī)語言可以編程解決此問題。

?

?

分支限界法按廣度優(yōu)先策略遍歷問題的解空間，在遍歷過程種，對已經(jīng)處理的每一個(gè)結(jié)點(diǎn)根據(jù)限界函數(shù)估算目標(biāo)函數(shù)的可能值，從中選取使目標(biāo)函數(shù)取得極值（極大或極?。┑慕Y(jié)點(diǎn)優(yōu)先進(jìn)行廣度優(yōu)先搜索，從而不斷調(diào)整搜索方向，盡快找到問題的解。

因?yàn)榻缦藓瘮?shù)常常是基于問題的目標(biāo)函數(shù)而確定的，所以，分支限界法適用于求解最優(yōu)化問題。

?

分支界限法的求解目標(biāo)是找出滿足約束條件的一個(gè)解，或是在滿足約束條件的解中找出使某一目標(biāo)函數(shù)值達(dá)到極大或極小的解，即在某種意義下的最優(yōu)解。（分支界限法與回溯法求解目標(biāo)不同）.

?

典型代表：任務(wù)分配問題、多段圖的最短路徑問題、批處理作業(yè)調(diào)度問題、電路布線問題......

?

案例：任務(wù)分配問題

問題描述：N個(gè)人分配N項(xiàng)任務(wù)，一個(gè)人只能分配一項(xiàng)任務(wù)，一項(xiàng)任務(wù)只能分配給一個(gè)人，將一項(xiàng)任務(wù)分配給一個(gè)人是需要支付報(bào)酬，如何分配任務(wù)，保證支付的報(bào)酬總數(shù)最小。

總結(jié)：

產(chǎn)品、代碼、算法等，在文化面前是短淺的。

只有探索、思考，超出人類所知的，并在歷史中沉淀下來的難題，才可以直指宇宙、時(shí)空、哲學(xué)域。

感受到這種永恒的魅力了嘛！

? ?END??

第二步：在公眾號"唧唧歪歪PM"回復(fù)：1