如何理解分治思想

分治思想就是把復雜問題、拆分成諾干個相同的小問題，然后將問題逐步解決掉，合并到一起的過程，就是分治思想。簡單來說，分治思想就是“分而治之”，將復雜問題拆分成諾干個相同的小問題進行解決。

那么如何實現分治思維去解決問題呢？首先分解的問題要與整個問題的規則要一致，否則就無法使用分治去解決問題，總體可總結為：

分解：將原問題分解為若干個規模較小，相對獨立，與原問題形式相同的子問題。

解決：若子問題規模較小且易于解決時，則直接解。否則，遞歸地解決各子問題。

合并：將各子問題的解合并為原問題的解。

有哪些場景中使用到了分治去解決問題呢，在上文中我們講解了排序、當時我們只講解了冒牌排序、選擇排序，插入排序，高級一點的排序并沒有涉及到，因為像歸并排序、推排序、快速排序涉及到更多的知識點需要去講解和個人去了解堆概念和遞歸思想。今天應用的分治思想就是完全適用于歸并排序，歸并排序同時還要去理解遞歸思想。

如果對遞歸不理解的，需要去學習下，要不沒辦法繼續下去，分治思想最著名的體現就是漢諾塔。

相信大家都玩過漢諾塔吧，那么漢諾塔是如何來的呢？

傳說越南河內某間寺院有三根銀棒，上串 64 個金盤。寺院里的僧侶依照一個古老的預言，以上述規則移動這些盤子；預言說當這些盤子移動完畢，

世界就會滅亡。這個傳說叫做梵天寺之塔問題（Tower of Brahma puzzle）。但不知道是盧卡斯自創的這個傳說，還是他受他人啟發。

若傳說屬實，僧侶們需要二的64次方減去一步才能完成這個任務；若他們每秒可完成一個盤子的移動，就需要 5849 億年才能完成。整個宇宙現在也不過 137 億年。這就是漢諾塔的由來。

算法求解

解法的基本思想是遞歸。假設有 A、B、C 三個塔，A塔有N塊盤，目標是把這些盤全部移到 C 塔。那么先把 A 塔頂部的N-1塊盤移動到 B 塔，再把 A 塔剩下的大盤移到 C，最后把B塔的N-1塊盤移到 C。

漢諾塔問題

從左到右有A、B、C三根柱子，其中A柱子

上面有從小疊到大的n個圓盤，現要求將A柱子上的圓盤移到C柱子上去，期間只有一個原則：一次只能移到

一個盤子且大盤子不能在小盤子上面，求移動的步驟和移動的次數

移動的規則：

1.每次只能移動一個圓盤；

2.大盤不能疊在小盤上面。

def hanoi(n, a, b, c): if n == 1: print(a, '-->', c) else: hanoi(n - 1, a, c, b) hanoi(1, a, b, c) hanoi(n - 1, b, a, c) if __name__ == "__main__": print(hanoi(2, 'A', 'B', 'C'))

圖解解釋

可以用無向圖來表示漢諾塔, 在表示的時候會更加地直觀和清晰, 雖然說理解上有一點點小難度.

現在規定, 每一個節點表示盤子的位置一種可能性, 每一條邊表示一種移動的方法.

注: 這里不考慮在兩個柱子之間的, 沒有意義的, 來回移動的情況.

對于只有一個盤子的漢諾塔，可以表示為：

一個盤子的情況

對于有兩個盤子的漢諾塔, 可以表示為:

相互連接的三個三角形, 組成了一個較大三角形的三個角。

每一個節點的第二個字母表示更大的盤子, 且最初時沒有被移動。

對于每一個頂端的小三角形, 表示兩個盤子的一種移動的方法：

兩個盤子的漢諾塔

外圍的三角形的每一個節點, 表示在一個柱子上盤子的所有分布可能.。

對于 h+1 個盤子, 就可以”復制” h 個盤子時候的三角形圖, 然后拼成一個新的大三角形圖, 稍微改動一下,

這個大的三角形圖就可以用來表示 h+1 個盤子時的情況了.

所以當有三個盤子時, 圖形為：

三個盤子的漢諾塔

A, b 和 c 表示三個柱子

按照從小到大的順序, 從左到右地列出的盤子的位置.

最外面的三角形的邊, 表示了盤子從一個柱子移動到另一個柱子最快的方式. 最大的三角形可以沿著中線分成三個次小的三角形, 就是上面由二級的漢諾塔組成三級的漢諾塔的逆向操作, 次小三角形相互之間的連線, 表示著最大的盤子的移動方式.

同理, 在這次三角形的也可以沿其中線分割成為三個次次三角形, 一樣的, 次次小三角形相互之間的連線, 表示著次大的盤子的移動方式. 繼續下去, 也就可以表示出一個漢諾塔的移動方式.

通常，對于具有 n 個盤子的圖, 有3n個節點; 每個節點都有三條邊連接著其他節點, 但是在頂點的的節點只卻只有有兩條邊連接著其他節點.所以說總是下都可以將最小的盤子移動到另外兩個柱子中的一個, 對于多數情況, 是可以在兩個柱子間移動一個盤子, 除了所有的盤子都在一個柱子上. 邊角的節點表示著所有的盤子都在一個柱子的情況, 即可以在 a, b 或 c 柱上堆滿盤子, 顯然只要三種. 對于n+1個盤子的圖, 可以通過表示n給盤子的圖 “復制” 三份, 組合在一起的. 因此也就很方便地表示了每一層的漢諾塔移動方式, 每一個次小的三角形表示次小的盤子的所有可能的移動方式和放置狀態, 次小的三角形之間的連接表示了大盤子的三種可能的移動方式. 所以圖形有3n+1個節點, 基本都有三個與之相連接的邊,而頂點只有兩個.

在盤子數比較多的時候, 漢諾塔的圖像就會開始和分形圖比較相似了.

該圖較為清楚地表達了：

對于任意的全部盤子在一根柱子的情況下, 將所有盤子移動到另一個柱子的最短路徑只有一個.

對于任意的兩個盤子分布情況之間轉換的時候, 只有一個或者兩個不同的最短路徑.

對于任意的盤子分布情況, 都有一個或者兩個將所有盤子移動到任意一個柱子上的最長不相交路徑.

對于任意的兩個盤子分布情況之間轉換的時候, 只有一個或者兩個不同的最長不相交路徑.

設Nh是將有h個盤子的塔, 將所有盤子從一個柱子移動到另一個柱子的非相交路徑的數量(一開始盤子都在一個柱子上). 可以得出：

這里的

除了漢諾塔，還有其他的案例

歸并排序

二分搜索

大整數乘法

Strassen矩陣乘法

棋盤覆蓋

快速排序

線性時間選擇

最接近點對問題

循環賽日程表

青蛙跳臺階問題

分治法的復雜性分析

一個分治法將規模為n的問題分成k個規模為n／m的子問題去解。設分解閥值n0=1，且adhoc解規模為1的問題耗費1個單位時間。再設將原問題分解為k個子問題以及用merge將k個子問題的解合并為原問題的解需用f(n)個單位時間。用T(n)表示該分治法解規模為|P|=n的問題所需的計算時間，則有：

T（n）= k T(n/m)+f(n)

通過迭代法求得方程的解：

遞歸方程及其解只給出n等于m的方冪時T(n)的值，但是如果認為T(n)足夠平滑，那么由n等于m的方冪時T(n)的值可以估計T(n)的增長速度。通常假定T(n)是單調上升的，從而當 mi≤n

依據分治法設計程序時的思維過程

實際上就是類似于數學歸納法，找到解決本問題的求解方程公式，然后根據方程公式設計遞歸程序。

1、一定是先找到最小問題規模時的求解方法

2、然后考慮隨著問題規模增大時的求解方法

3、找到求解的遞歸函數式后（各種規模或因子），設計遞歸程序即可。

我們通常使用分治思想去解決大數據量問題，以及可以給我們一個思考，當我們遇到無法解決的問題，可以將問題拆分開來，逐步解決，這樣就可以實現賺它一個億的小目標。

版權聲明：本文內容由網絡用戶投稿，版權歸原作者所有，本站不擁有其著作權，亦不承擔相應法律責任。如果您發現本站中有涉嫌抄襲或描述失實的內容，請聯系我們jiasou666@gmail.com 處理，核實后本網站將在24小時內刪除侵權內容。