分而治之思想 -开发者知识库

分而治之思想 -开发者知识库,第1张

        當一個問題的規模很大時,直接求解往往比較困難。對於這類問題,很大一部分是可以采取分而治之的思想來處理的。

        分治法是把問題划分成多個子問題來進行處理。這些子問題,在結構上跟原來的問題一樣,但是規模比原來的問題要小。如果得到的子問題還是比較大,那么可以接着細分,一直細分到可以接受的程度為止。這樣就可以用迭代的方法,分別求解這些子問題,最后再將子問題的解組合起來,就可以得到原問題的解。

分治法的設計原理

        對於一個規模為n的問題P(n),可以將它分解成k個規模較小的子問題,這些子問題互相獨立,且結構跟原問題的結構相同。在解這些問題的時候,又可以對每一個子問題進行進一步的分解,直到某一個閾值n0時為止。遞歸地解這些子問題,再把各個子問題的解結合起來,就得到原問題的解。這就是分而治之的思想。

        分治法的設計步驟:

        分而治之思想 -开发者知识库,image,第2张

        其中n0是一個閾值,當問題規模小於等於n0時,就不需要再對問題進行分解,而直接調用adhoc求解。adhoc是用來直接求解規模最小問題p的子算法。merge用來把所有子問題的解合並成原問題的真正解。

        從上面的圖中可以看出,分支思想的實現有三個步驟:

        (1)划分步:把輸入的問題划分成k個子問題。一般使這k個問題的規模大致相同。

        (2)治理步:當問題的規模大於預定義的n0時,治理步由k個遞歸調用組成。

        (3)組合步:組合步主要用來將各子問題的解合並成原問題的解。這一步對分治法的實際性能很重要。

最佳答案:

本文经用户投稿或网站收集转载,如有侵权请联系本站。

发表评论

0条回复