資源簡介

(共18張PPT)
第13課
算法的設計
目錄
分治算法步驟
01
分治算法概念
02
分治算法策略
03
分治算法特征
04
分治算法概念
01
Part One
【分治法】
在計算機科學中，分治法是一種很重要的算法。字面上的解釋是“分而治之”，就是把一個復雜的問題分成兩個或更多的相同或相似的子問題，再把子問題分成更小的子問題……直到最后子問題可以簡單的直接求解，原問題的解即子問題的解的合并。這個技巧是很多高效算法的基礎，如排序算法(快速排序，歸并排序)，傅立葉變換(快速傅立葉變換)……等。任何一個可以用計算機求解的問題所需的計算時間都與其規模有關。問題的規模越小，越容易直接求解，解題所需的計算時間也越少。
例如
對于n個元素的排序問題，當n=1時，不需任何計算。n=2時，只要作一次比較即可排好序。n=3時只要作3次比較即可，…。而當n較大時，問題就不那么容易處理了。要想直接解決一個規模較大的問題，有時是相當困難的。分治法的設計思想是，將一個難以直接解決的大問題，分割成一些規模較小的相同問題，以便各個擊破，分而治之。
分治算法策略
02
分治策略是：
對于一個規模為n的問題，若該問題可以容易地解決（比如說規模n較小）則直接解決，否則將其分解為k個規模較小的子問題，這些子問題互相獨立且與原問題形式相同，遞歸地解這些子問題，然后將各子問題的解合并得到原問題的解。這種算法設計策略叫做分治法。
如果原問題可分割成k(1\u003Ck≤n)個子問題， 且這些子問題都可解并可利用這些子問題的解求出原問題的解，那么這種分治法就是可行的。由分治法產生的子問題往往是原問題的較小模式，這就為使用遞歸技術提供了方便。
在這種情況下，反復應用分治手段，可以使子問題與原問題類型一致而其規模卻不斷縮小，最終使子問題縮小到很容易直接求出其解，這自然導致遞歸過程的產生。"分治"與"遞歸"像一對孿生兄弟，經常同時應用在算法設計之中，并由此產生許多高效算法。
分治算法特征
03
分治法所能解決的問題一般具有以下幾個特征：
該問題的規模縮小到一定的程度就可以容易地解決
01
該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質。（前提）
02
利用該問題分解出的子問題的解可以合并為該問題的解；（最關鍵的一點）
03
該問題所分解出的各個子問題是相互獨立的，即子問題之間不包含公共的子子問題。
04
上述的第一條特征是絕大多數問題都可以滿足的，因為問題的計算復雜性一般是隨著問題規模的增加而增加；第二條特征是應用分治法的前提它也是大多數問題可以滿足的，此特征反映了遞歸思想的應用；第三條特征是關鍵，能否利用分治法完全取決于問題是否具有第三條特征。
如果具備了第一條和第二條特征，而不具備第三條特征，則可以考慮用貪心法或動態規劃法。第四條特征涉及到分治法的效率，如果各子問題是不獨立的則分治法要做許多不必要的工作，重復地解公共的子問題，此時雖然可用分治法，但一般用動態規劃法較好。
分治算法步驟
04
分治法的基本步驟分治法在每一層遞歸上都有
三個步驟：
分解將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題。
01
解決若子問題規模較小而容易被解決則直接解，否則遞歸地解各個子問題。
02
合并將各個子問題的解合并為原問題的解。
03
練習1
針對機器人畫正六邊形的問題,設計一個算法。
練習2
練習3
感謝聆聽

展開更多......

收起↑