屬於分治演算法

⑴ 分治法的步驟

分治法在每一層遞歸上都有三個步驟：
分解：將原問題分解為若干個規模較小，相互獨立，與原問題形式相同的子問題；
解決：若子問題規模較小而容易被解決則直接解，否則遞歸地解各個子問題；
合並：將各個子問題的解合並為原問題的解。
它的一般的演算法設計模式如下：
Divide-and-Conquer(P)
1. if |P|≤n0
2. then return(ADHOC(P))
3. 將P分解為較小的子問題 P1 ,P2 ,...,Pk
4. for i←1 to k
5. do yi ← Divide-and-Conquer(Pi) △ 遞歸解決Pi
6. T ← MERGE(y1,y2,...,yk) △ 合並子問題
7. return(T)
其中|P|表示問題P的規模；n0為一閾值，表示當問題P的規模不超過n0時，問題已容易直接解出，不必再繼續分解。ADHOC(P)是該分治法中的基本子演算法，用於直接解小規模的問題P。因此，當P的規模不超過n0時直接用演算法ADHOC(P)求解。演算法MERGE(y1,y2,...,yk)是該分治法中的合並子演算法，用於將P的子問題P1 ,P2 ,...,Pk的相應的解y1,y2,...,yk合並為P的解。
根據分治法的分割原則，原問題應該分為多少個子問題才較適宜？
各個子問題的規模應該怎樣才為適當？
答: 但人們從大量實踐中發現，在用分治法設計演算法時，最好使子問題的規模大致相同。換句話說，將一個問題分成大小相等的k個子問題的處理方法是行之有效的。許多問題可以取 k = 2。這種使子問題規模大致相等的做法是出自一種平衡(balancing)子問題的思想，它幾乎總是比子問題規模不等的做法要好。
出處：網路
實踐題目：
給定一個順序表，編寫一個求出其最大值和最小值的分治演算法。
分析：
由於順序表的結構沒有給出，作為演示分治法這里從簡順序表取一整形數組數組大小由用戶定義，數據隨機生成。我們知道如果數組大小為 1 則可以直接給出結果，如果大小為 2則一次比較即可得出結果，於是我們找到求解該問題的子問題即: 數組大小 <= 2。到此我們就可以進行分治運算了，只要求解的問題數組長度比 2 大就繼續分治，否則求解子問題的解並更新全局解
以下是代碼。
*/
/*** 編譯環境TC ***/
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define M 40
/* 分治法獲取最優解 */
void PartionGet(int s,int e,int *meter,int *max,int *min){
/* 參數:
* s 當前分治段的開始下標
* e 當前分治段的結束下標
* meter 表的地址
* max 存儲當前搜索到的最大值
* min 存儲當前搜索到的最小值
*/
int i;
if(e-s <= 1){ /* 獲取局部解，並更新全局解 */
if(meter[s] > meter[e]){
if(meter[s] > *max)
*max = meter[s];
if(meter[e] < *min)
*min = meter[e];
}
else{
if(meter[e] > *max)
*max = meter[e];
if(meter[s] < *min)
*min = meter[s];
}
return ;
}
i = s + (e-s)/2; /* 不是子問題繼續分治,這里使用了二分，也可以是其它 */
PartionGet(s,i,meter,max,min);
PartionGet(i+1,e,meter,max,min);
}
int main(){
int i,meter[M];
int max = INT_MIN; /* 用最小值初始化 */
int min = INT_MAX; /* 用最大值初始化 */
printf(The array's element as followed: );
rand(); /* 初始化隨機數發生器 */
for(i = 0; i < M; i ++){ /* 隨機數據填充數組 */
meter[i] = rand()%10000;
if(!((i+1)%10)) /* 輸出表的隨機數據 */
printf(%-6d ,meter[i]);
else
printf(%-6d,meter[i]);
}
PartionGet(0,M - 1,meter,&max,&min); /* 分治法獲取最值 */
printf( Max : %d Min : %d ,max,min);
system(pause);
return 0;
}

⑵ 每天一個知識點：分治演算法：選擇問題

選擇問題的要求是找出含有 N 個元素的表 S 中的第 k 個最小的元素。

基本的演算法是簡單的遞歸策略。設 N 大於截止點(cutoff point)，在截止點後元素將進行簡單的排序，v 是選出的一個元素，叫做樞紐元(pivot)。其餘的元素被放在兩個集合 和 中。 含有那些不大於 v 的元素，而 則包含那些不小於 v 的元素。

為了得到一個線性演算法，必須保證子問題只是原問題的一部分，而不僅僅只是比原問題少幾個元素。這里要解決問題就是如何花費更少的時間來尋找樞紐元。

為得到一個好的最壞情形，關鍵想法是再用一個間接層。不是從隨機元素的樣本中找出中項，而是從中項的樣本中找出中項。

基本的樞紐元選擇演算法如下：

上面給出的樞紐元選擇法，有一個專業的術語，叫做「五分化中項的中項」。「五分化中項的中項」保證每個遞歸子問題的大小最多是原問題的大約 70%。對於整個選擇演算法，樞紐元可以足夠快的算出，以確保 的運行時間。

定理：使用「五分化中項的中項」的快速選擇演算法的運行時間為 。

分治演算法還可以用來降低演算法預計所需要的比較次數。

設有 N 個數的集合 S 並且要尋找其中第 k 個最小的數 X。我們選擇 S 的子集 S『，令 δ 是某個數，使得計算過程所用的平均比較次數最小化。

找出 S』 中第 ( ) 個和第 個最小的元素，幾乎可以肯定 S 中的第 k 個元素將落在 和 之間，此時，問題變成了 2δ 個元素的選擇問題。

經過分析，會發現，若 和 ，則期望的比較次數為 ，除低次項外它是最優的。（如果 k>N/2，那麼我們可以考慮查找第(N-k)個最大元素的對稱問題。）

最後一項代表進行兩次選擇以確定 和 的代價。假設採用合理聰明的策略，則劃分的平均代價等於 N 加上 在 S 中的期望階(expected rank)，即 。如果第 k 個元素在 S『 中出現，那麼代價就是 O(N)。然而，s 和 δ 已經被選取以保證這種情況以非常低的概率 o(1/N) 發生，因此該可能性的期望代價是 o(1)，當它的 N 越來越大時趨向於 0。

這個分析指出，找出中項平均大約需要 1.5N 次比較。當然，該演算法為計算 s 需要浮點運算，這在一些機器上可能使該演算法減慢速度。不過即使是這樣，若能正確實現，則該演算法完全能夠比得上快速選擇實現方法。

⑶ 如何理解分治演算法及相關例題

演算法步驟：
1 ：從左上角起，給棋盤編號（1，1），（1，2）（8，8），計為集合qp。tracks記錄走過的每個點. （可以想像為坐標（x,y））

2：設起點為（1，1），記為 當前位置 cp，

3：搜索所有可走的下一步，根據「馬行日」的走步規則，可行的點的坐標是x坐標加減1，y坐標加減2，

或是x加減2，y加減1； （例如起點（1，1），可計算出（1+1，1+2），（1+1，1-2），（1-1，1+2），（1-1，1-2），（1+2，1+1），（1+2，1-1），（1-2，1+1），（1-2，1-1） 共8個點）， 如果沒有搜到可行點，程序結束。

4：判斷計算出的點是否在棋盤內，即是否在集合qp中；判斷點是否已經走過，即是否在集合tracts中，不在才是合法的點。（在上面的舉例起點（1，1），則合法的下一步是（2，3）和 （3，2））

5：將前一步的位置記錄到集合tracts中，即tracts.add（cp）；選擇一個可行點，cp=所選擇點的坐標。

6：如果tracts里的點個數等於63，退出程序，否則回到步驟3繼續執行。

⑷ 分治演算法求數組中最大元素位置的演算法：

實質就是遞歸，思想是分治
max1=Max(a, low, mid);
max2=Max(a, mid+1, high);
以上把代碼就是把數組分成兩部分，然後這兩部分中再往下分，直至if(low==high)
時返回下標，然後在每一層進行比較max=a[max1]>a[max2]?max1: max2; 把最大值的下標賦給max。
最後返回。

⑸ 分治法是什麼

分治法可以通俗的解釋為:把一片領土分解，分解為若干塊小部分，然後一塊塊地佔領征服，被分解的可以是不同的政治派別或是其他什麼，然後讓他們彼此異化。

分治法的精髓：

分--將問題分解為規模更小的子問題。

治--將這些規模更小的子問題逐個擊破。

合--將已解決的子問題合並，最終得出"母"問題的解。

任何一個可以用計算機求解的問題所需的計算時間都與其規模有關。問題的規模越小，越容易直接求解，解題所需的計算時間也越少。例如，對於n個元素的排序問題，當n=1時，不需任何計算。

n=2時，只要作一次比較即可排好序。n=3時只要作3次比較即可，…。

而當n較大時，問題就不那麼容易處理了。要想直接解決一個規模較大的問題，有時是相當困難的。

分治法的設計思想是，將一個難以直接解決的大問題，分割成一些規模較小的相同問題，以便各個擊破，分而治之。

分治策略是：對於一個規模為n的問題，若該問題可以容易地解決（比如說規模n較小）則直接解決，否則將其分解為k個規模較小的子問題，這些子問題互相獨立且與原問題形式相同，遞歸地解這些子問題，然後將各子問題的解合並得到原問題的解。這種演算法設計策略叫做分治法。

⑹ 分治演算法

演算法步驟：
1 ：從左上角起，給棋盤編號（1，1），（1，2），。。。。。。（8，8），計為集合qp。tracks記錄走過的每個點. （可以想像為坐標（x,y））

2：設起點為（1，1），記為 當前位置 cp，

3：搜索所有可走的下一步，根據「馬行日」的走步規則，可行的點的坐標是x坐標加減1，y坐標加減2，

或是x加減2，y加減1； （例如起點（1，1），可計算出（1+1，1+2），（1+1，1-2），（1-1，1+2），（1-1，1-2），（1+2，1+1），（1+2，1-1），（1-2，1+1），（1-2，1-1） 共8個點）， 如果沒有搜到可行點，程序結束。

4：判斷計算出的點是否在棋盤內，即是否在集合qp中；判斷點是否已經走過，即是否在集合tracts中，不在才是合法的點。（在上面的舉例起點（1，1），則合法的下一步是（2，3）和 （3，2））

5：將前一步的位置記錄到集合tracts中，即tracts.add（cp）；選擇一個可行點，cp=所選擇點的坐標。

6：如果tracts里的點個數等於63，退出程序，否則回到步驟3繼續執行。

⑺ 使用分治演算法解決的問題具備什麼特徵

分治法能解決的問題一般具有以下幾個特徵：

1、該問題的規模縮小到一定的程度就可以容易的解決。

2、該問題可以分解為若干個規模較小的相同問題，即該問題具有最優子結構性質。

3、利用該問題分解出的子問題的解可以合並為該問題的解。

4、該問題所分解出的自問題是相互獨立的，即子問題之間不包含子子問題。

(7)屬於分治演算法擴展閱讀

思想及策略

分治演算法的設計思想是：將一個難以直接解決的大問題，分割成一些規模小的相同的問題，一邊各個擊破，分而治之。

分治演算法的策略是：對於一個規模為n的問題，若該問題可以容易地解決（比如規模n比較小）則直接解決，否則將其分解成k個規模較小的自問題，這些子問題相互獨立且與元問題形式相同，遞歸地解這些子問題，然後將各子問題的解合並得到原問題的解。

⑻ 選擇排序，插入排序和歸並排序算數法中，什麼演算法是分治演算法

歸並排序 用到了 分治 的思想

⑼ 分治演算法是什麼呢

分治演算法的基本思想是將一個規模為N的問題分解為K個規模較小的子問題，這些子問題相互獨立且與原問題性質相同。求出子問題的解，就可得到原問題的解。即一種分目標完成程序演算法，簡單問題可用二分法完成。

解題步驟

分治法解題的一般步驟：

（1）分解，將要解決的問題劃分成若干規模較小的同類問題；

（2）求解，當子問題劃分得足夠小時，用較簡單的方法解決；

（3）合並，按原問題的要求，將子問題的解逐層合並構成原問題的解。

⑽ 什麼是分治演算法貪婪演算法

貪婪演算法

雖然設計一個好的求解演算法更像是一門藝術，而不像是技術，但仍然存在一些行之有效的能夠用於解決許多問題的演算法設計方法，你可以使用這些方法來設計演算法，並觀察這些演算法是如何工作的。一般情況下，為了獲得較好的性能，必須對演算法進行細致的調整。但是在某些情況下，演算法經過調整之後性能仍無法達到要求，這時就必須尋求另外的方法來求解該問題。

分治演算法

就是把大問題分解成一些小問題，然後重小問題構造出大問題的解。