一、分治策略

分（Divide）
將規模為n的問題分解為 k 個規模較小的子問題
治（Conquer）
對k個子問題分別求解，然后將各個子問題的解合并得到原問題的解
分治策略是從下至上求解并將合并得到解

Begin輸入有序數組a[],查找元素x,數組最左邊下標i，最右邊下標ji->0,j->a.length1.while(i<=j)循環執行: 1.1 設置 m =(i+j)/2;1.2 if(x==a[m]) return m;1.3 if(x<a[m]) j=m-1; else i=m+1;2.return -1; End

二、動態規劃

動態規劃算法與分治法類似，其基本思想也是將待求解問題分解成若干個子問題，并且它能夠解決子問題不相互獨立時的某些情況
不同子問題的數目常常只有多項式量級，即在用分治法求解時，有些子問題被重復計算了有限多次。

• 基本要素
  最優子結構:問題的最優解包含著其子問題的最優解。這種性質稱為最優子結構性質
  重疊子問題:遞歸求解問題時，每次產生的子問題并不總是新問題，有些子問題被反復計算多次。這種性質稱為子問題的重疊性質
• 基本步驟
  找出最優解的性質，并刻劃其結構特征
  遞歸地定義最優值
  以自底向上的方式計算出最優值
  根據計算最優值時得到的信息，構造最優解

/*0-1背包問題*/ int knapSack(int W, int wt[], int val[], int n) {if (n == 0 || W == 0)return 0;if (wt[n-1] > W)return knapSack(W, wt, val, n-1); else return max( val[n-1] + knapSack(W-wt[n-1], wt, val, n-1),knapSack(W, wt, val, n-1)); }

三、貪心算法

顧名思義，貪心算法總是作出在當前看來最好的選擇。也就是說貪心算法并不從整體最優考慮，它所作出的選擇只是在某種意義上的局部最優選擇當然，希望貪心算法得到的最終結果也是整體最優的。雖然貪心算法不能對所有問題都得到整體最優解，但對許多問題它能產生整體最優解。如單源最短路經問題，最小生成樹問題等在一些情況下，即使貪心算法不能得到整體最優解，其最終結果卻是最優解的近似值。

貪心算法需考慮到的方面

候選集（C）問題可能解的集合

解集（S）滿足問題的完整解，S是C的一個子集

可行解函數用于檢驗S是否構成問題的一個可行解

選擇函數即貪心策略，也是貪心算法的關鍵

約束函數檢測解集S加入一個候選對象是否滿足約束

/*dijkstra算法單源最短路徑*/ Begin1 初始 s={1},v={2...n},dist[i]=c[i][j];22.1 u=min{dist[i][j]|i屬于v}2.2 s=sU{v},v=v-{u};2.3 對于 v 中頂點 iif(dist[u]+c[u][i]<dist[i][j]) dist[i]=dist[u]+c[u][j]3.輸出dist End

四、回溯法

回溯法的基本做法是搜索，或是一種組織得井井有條的，能避免不必要搜索的窮舉式搜索法。這種方法適用于解一些組合數相當大的問題?；厮莘ㄔ趩栴}的解空間樹中，按深度優先策略，從根結點出發搜索解空間樹。算法搜索至解空間樹的任意一點時，先判斷該結點是否包含問題的解。如果肯定不包含，則跳過對該結點為根的子樹的搜索，逐層向其祖先結點回溯；否則，進入該子樹，繼續按深度優先策略搜索

基本思想

針對所給問題，定義問題的解空間

確定易于搜索的解空間結構

以深度優先方式搜索解空間，并在搜索過程中用剪枝函數避免無效搜索

剪枝函數（Pruning Function）：約束條件或目標函數的界，即判定該節點是否包含問題的解。如果肯定不包含，則跳過對以該節點為根的子樹的搜索，這便是所謂的剪枝

/*0-1背包問題回溯算法*/ Begin設Backtrakc(i)表示對第i層結點的搜索1. if(i>n)則返回當前解bestp,結束算法2. if 當前背包重量 cw+w[i]<c,進入左子樹2.1 cw+=w[i];當前價值cp+=v[i];2.2 搜索下一層結點 Backtrack(i+1);2.3 回退,cw-=w[i],cp=v[i]];3. 如果Bound(i+1)>bestp,進入右子樹,即Backtrack(i+1) End

五、分支界限法

求解目標：回溯法的求解目標是找出解空間樹中滿足約束條件的所有解，而分支限界法的求解目標則是找出滿足約束條件的一個解，或是在滿足約束條件的解中找出在某種意義下的最優解
搜索方式的不同：回溯法以深度優先的方式搜索解空間樹，而分支限界法則以廣度優先或以最小耗費優先的方式搜索解空間樹
搜索方式的不同：回溯法以深度優先的方式搜索解空間樹，而分支限界法則以廣度優先或以最小耗費優先的方式搜索解空間樹

基本思想

在分支限界法中，每一個活結點只有一次機會成為擴展結點。活結點一旦成為擴展結點，就一次性產生其所有兒子結點。在這些兒子結點中，導致不可行解或導致非最優解的兒子結點被舍棄，其余兒子結點被加入活結點表中
此后，從活結點表中取下一結點成為當前擴展結點，并重復上述結點擴展過程。這個過程一直持續到找到所需的解或活結點表為空時為止

/*0-1背包問題回溯算法*/ /*任務分配問題分支界限法*/ Begin1 根據限界函數計算目標函數的下界down;采用貪心法得到上界up;2. 將待處理結點活結點表初始化為空；3. for(i=l;i<=n;i++)x[i]= 0;4. k=l;i=0; //為第k個人分配任務，i為第k-1個人分配的任務5. while (k>=l)5.1 x[k]=l;5.2 while (x[k]<=n)5.2.1 如果人員k分配任務x[k]不發生沖突，則5.2.1.1 計算目標函數值lb;5.2.1.2 若lb<=up,則將i，<x[k]，k>lb存儲在活結點表中;5.2.2 x[k]=x[k]+l;5.3 如果k==n且葉子結點的lb值在活結點表中最小,則輸出該葉子結點對應的最優解;5.4 否則，如果k==n且活結點表中的葉子結點的lb值不是最小,則5.4.1 up=活結點表中的葉子結點最小的lb值；5.4.2 將活結點表中超出目標函數界的結點刪除；5.5 i=活結點表中lb最小的結點的x丨k]值；5.6 k=活結點表中lb最小的結點的k值;k++; End

總結

以上是生活随笔為你收集整理的常用算法的伪代码的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。