當前位置:首頁 » 操作系統 » 分治演算法策略

分治演算法策略

發布時間: 2023-07-16 18:05:29

1. 程序員都應該精通的六種演算法,你會了嗎

對於一名優秀的程序員來說,面對一個項目的需求的時候,一定會在腦海里浮現出最適合解決這個問題的方法是什麼,選對了演算法,就會起到事半功倍的效果,反之,則可能會使程序運行效率低下,還容易出bug。因此,熟悉掌握常用的演算法,是對於一個優秀程序員最基本的要求。


那麼,常用的演算法都有哪些呢?一般來講,在我們日常工作中涉及到的演算法,通常分為以下幾個類型:分治、貪心、迭代、枚舉、回溯、動態規劃。下面我們來一一介紹這幾種演算法。


一、分治演算法


分治演算法,顧名思義,是將一個難以直接解決的大問題,分割成一些規模較小的相同問題,以便各個擊破,分而治之。


分治演算法一般分為三個部分:分解問題、解決問題、合並解。

分治演算法適用於那些問題的規模縮小到一定程度就可以解決、並且各子問題之間相互獨立,求出來的解可以合並為該問題的解的情況。


典型例子比如求解一個無序數組中的最大值,即可以採用分治演算法,示例如下:


def pidAndConquer(arr,leftIndex,rightIndex):

if(rightIndex==leftIndex+1 || rightIndex==leftIndex){

return Math.max(arr[leftIndex],arr[rightIndex]);

}

int mid=(leftIndex+rightIndex)/2;

int leftMax=pidAndConquer(arr,leftIndex,mid);

int rightMax=pidAndConquer(arr,mid,rightIndex);

return Math.max(leftMax,rightMax);


二、貪心演算法


貪心演算法是指在對問題求解時,總是做出在當前看來是最好的選擇。也就是說,不從整體最優上加以考慮,他所做出的僅是在某種意義上的局部最優解。


貪心演算法的基本思路是把問題分成若干個子問題,然後對每個子問題求解,得到子問題的局部最優解,最後再把子問題的最優解合並成原問題的一個解。這里要注意一點就是貪心演算法得到的不一定是全局最優解。這一缺陷導致了貪心演算法的適用范圍較少,更大的用途在於平衡演算法效率和最終結果應用,類似於:反正就走這么多步,肯定給你一個值,至於是不是最優的,那我就管不了了。就好像去菜市場買幾樣菜,可以經過反復比價之後再買,或者是看到有賣的不管三七二十一先買了,總之最終結果是菜能買回來,但搞不好多花了幾塊錢。


典型例子比如部分背包問題:有n個物體,第i個物體的重量為Wi,價值為Vi,在總重量不超過C的情況下讓總價值盡量高。每一個物體可以只取走一部分,價值和重量按比例計算。

貪心策略就是,每次都先拿性價比高的,判斷不超過C。


三、迭代演算法


迭代法也稱輾轉法,是一種不斷用變數的舊值遞推新值的過程。迭代演算法是用計算機解決問題的一種基本方法,它利用計算機運算速度快、適合做重復性操作的特點,讓計算機對一組指令(或一定步驟)進行重復執行,在每次執行這組指令(或這些步驟)時,都從變數的原值推出它的一個新值。最終得到問題的結果。


迭代演算法適用於那些每步輸入參數變數一定,前值可以作為下一步輸入參數的問題。


典型例子比如說,用迭代演算法計算斐波那契數列。


四、枚舉演算法


枚舉演算法是我們在日常中使用到的最多的一個演算法,它的核心思想就是:枚舉所有的可能。枚舉法的本質就是從所有候選答案中去搜索正確地解。

枚舉演算法適用於候選答案數量一定的情況。


典型例子包括雞錢問題,有公雞5,母雞3,三小雞1,求m錢n雞的所有可能解。可以採用一個三重循環將所有情況枚舉出來。代碼如下:



五、回溯演算法


回溯演算法是一個類似枚舉的搜索嘗試過程,主要是在搜索嘗試過程中尋找問題的解,當發現已不滿足求解條件時,就「回溯」返回,嘗試別的路徑。

許多復雜的,規模較大的問題都可以使用回溯法,有「通用解題方法」的美稱。


典型例子是8皇後演算法。在8 8格的國際象棋上擺放八個皇後,使其不能互相攻擊,即任意兩個皇後都不能處於同一行、同一列或同一斜線上,問一共有多少種擺法。


回溯法是求解皇後問題最經典的方法。演算法的思想在於如果一個皇後選定了位置,那麼下一個皇後的位置便被限制住了,下一個皇後需要一直找直到找到安全位置,如果沒有找到,那麼便要回溯到上一個皇後,那麼上一個皇後的位置就要改變,這樣一直遞歸直到所有的情況都被舉出。


六、動態規劃演算法


動態規劃過程是:每次決策依賴於當前狀態,又隨即引起狀態的轉移。一個決策序列就是在變化的狀態中產生出來的,所以,這種多階段最優化決策解決問題的過程就稱為動態規劃。


動態規劃演算法適用於當某階段狀態給定以後,在這階段以後的過程的發展不受這段以前各段狀態的影響,即無後效性的問題。


典型例子比如說背包問題,給定背包容量及物品重量和價值,要求背包裝的物品價值最大。


2. 分治策略的分治策略的定義

這種演算法設計策略叫做分治法。 如果原問題可分割成k個子問題,1<k≤n ,且這些子問題都可解,並可利用這些子問題的解求出原問題的解,那麼這種分治法就是可行的。由分治法產生的子問題往往是原問題的較小模式,這就為使用遞歸技術提供了方便。在這種情況下,反復應用分治手段,可以使子問題與原問題類型一致而其規模卻不斷縮小,最終使子問題縮小到很容易直接求出其解。這自然導致遞歸過程的產生。分治與遞歸像一對孿生兄弟,經常同時應用在演算法設計之中,並由此產生許多高效演算法。 分治法所能解決的問題一般具有以下幾個特徵:
該問題的規模縮小到一定的程度就可以容易地解決;
該問題可以分解為若干個規模較小的相同問題,即該問題具有最優子結構性質。
利用該問題分解出的子問題的解可以合並為該問題的解;
該問題所分解出的各個子問題是相互獨立的,即子問題之間不包含公共的子子問題。
上述的第一條特徵是絕大多數問題都可以滿足的,因為問題的計算復雜性一般是隨著問題規模的增加而增加;第二條特徵是應用分治法的前提,它也是大多數問題可以滿足的,此特徵反映了遞歸思想的應用;第三條特徵是關鍵,能否利用分治法完全取決於問題是否具有第三條特徵,如果具備了第一條和第二條特徵,而不具備第三條特徵,則可以考慮用貪心法或動態規劃法。第四條特徵涉及到分治法的效率,如果各子問題是不獨立的,則分治法要做許多不必要的工作,重復地解公共的子問題,此時雖然可用分治法,但一般用動態規劃法較好。

3. 利用分治演算法求解、

對於這種已知不合格硬幣比正常銀幣偏重(或偏輕)的問題,可以用分治法。 以下演算法可以用數學歸納法證明:假設有3枚硬幣,則稱一次,如果a邊重則是a,……,平衡則是c。同理如果有N塊硬幣,我們可以把它分成三堆,稱一次後,這樣問題規模縮小至n/3。重復以上操作,直至稱出。需要次數為log3 n。這是典型的分治法,如果想了解更多,可參考《演算法導論》 謝謝採納我的答案

熱點內容
怎麼搭建linux伺服器ftp 發布:2025-03-16 07:07:38 瀏覽:987
晶元存儲原理 發布:2025-03-16 06:58:21 瀏覽:284
c語言中的整型 發布:2025-03-16 06:40:48 瀏覽:184
分部資料庫伺服器的IP地址有效 發布:2025-03-16 06:33:40 瀏覽:192
安卓項目如何配置tomacat 發布:2025-03-16 06:31:13 瀏覽:431
寫腳本測試 發布:2025-03-16 06:20:07 瀏覽:780
多個撥號寬頻如何配置 發布:2025-03-16 05:51:35 瀏覽:688
管理員c語言 發布:2025-03-16 05:40:17 瀏覽:342
安卓軟體上的圖案如何更改 發布:2025-03-16 05:35:57 瀏覽:748
2010編譯c中文亂碼 發布:2025-03-16 05:33:40 瀏覽:550