《《算法設(shè)計(jì)與分析》歷年期末試題整理-含答案-》由會(huì)員分享，可在線閱讀，更多相關(guān)《《算法設(shè)計(jì)與分析》歷年期末試題整理-含答案-（16頁珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、 《算法設(shè)計(jì)與分析》歷年期末試題整理 ( 含答案 ) （ 1）用計(jì)算機(jī)求解問題的步驟： 1、問題分析 2、數(shù)學(xué)模型建立 3、算法設(shè)計(jì)與選擇 4、算法指標(biāo) 5、算法分析 6、算法實(shí)現(xiàn) 7、程序調(diào)試 8、結(jié)果整理文檔編制 （ 2）算法定義：算法是指在解決問題時(shí)，按照某種機(jī)械步驟一定可以得到問題結(jié)果的處理過程 （ 3）算法的三要素 1、操作 2、控制結(jié)構(gòu) 3、數(shù)據(jù)結(jié)構(gòu)算法具有以 下 5 個(gè)屬性： 有窮性：一個(gè)算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時(shí)間內(nèi)完成。確定性：算法中每一條指令必須有確切的含義。不存在二義性。只有一個(gè)入口和一個(gè)

2、出口 可行性：一個(gè)算法是可行的就是算法描述的操作是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)的。 輸入：一個(gè)算法有零個(gè)或多個(gè)輸入，這些輸入取自于某個(gè)特定對(duì)象的集合。 輸出：一個(gè)算法有一個(gè)或多個(gè)輸出，這些輸出同輸入有著某些特定關(guān)系的量。 算法設(shè)計(jì)的質(zhì)量指標(biāo)： 正確性：算法應(yīng)滿足具體問題的需求； 可讀性：算法應(yīng)該好 讀，以有利于讀者對(duì)程序的理解； 健壯性：算法應(yīng)具有容錯(cuò)處理，當(dāng)輸入為非法數(shù)據(jù) 時(shí)，算法應(yīng)對(duì)其作出反應(yīng)，而不是產(chǎn)生莫名其妙的輸出結(jié)果。 效率與存儲(chǔ)量需求：效率指的是算法執(zhí)行的時(shí)間；存儲(chǔ)量需求指算法執(zhí)行過程中所需要的最大存儲(chǔ)空間。一般這兩者與問題的

3、規(guī)模有關(guān)。 經(jīng)常采用的算法主要有迭代法、分而治之法、貪婪法、動(dòng)態(tài)規(guī)劃法、回溯法、分支限界法 迭代法 也稱“輾轉(zhuǎn)法”，是一種不斷用變量的舊值遞推出新值的解決問題的方法。 利用迭代算法解決問題，需要做好以下三個(gè)方面的工作： 一、確定迭代模型。在可以用迭代算法解決的問題中，至少存在一個(gè)直接或間接地不斷由舊值遞推出新值的變量，這個(gè)變量就是迭代變量。 二、 建立迭代關(guān)系式。所謂迭代關(guān)系式，指如何從變量的前一個(gè)值推出其下一個(gè)值的公式（或關(guān)系）。迭代關(guān)系式的建立是解決迭代問題的關(guān)鍵，通?？梢允褂眠f推或倒推的方法來完成。 三、 對(duì)迭代過程進(jìn)行控制。在什

4、么時(shí)候結(jié)束迭代過程？這是編寫迭代程序必須考慮的問題。不能讓迭代過程無休止地重復(fù)執(zhí)行下去。迭代過程的控制通?？煞譃閮煞N情況：一種是所需的迭代次數(shù)是個(gè)確定的值，可以計(jì)算出來；另一種是所需的迭代次數(shù)無法確定。對(duì)于前一種情況，可以構(gòu)建一個(gè)固定次數(shù)的循環(huán)來實(shí)現(xiàn)對(duì)迭代過程的控制；對(duì)于后一種情況，需要進(jìn)一步分析出用來結(jié)束迭代過程的條件。 編寫計(jì)算斐波那契（ Fibonacci ）數(shù)列的第 n 項(xiàng)函數(shù) fib （ n）。 斐波那契數(shù)列 ： 0、1、1、2、3、??，即： fib(0)=0; fib(1)=1; fib(n)=fib(n-1)+fib(n-2

5、) （當(dāng) n>1 ）。 寫成 函數(shù)有： int fib(int n) { if (n==0) return 0; if (n==1) return 1; if (n>1) return fib(n-1)+fib(n-2); } 一個(gè) 養(yǎng) 引 一只 出生的新品種兔子， 種兔子從出生的下一個(gè)月開始，每月新生一只兔子，新生的兔子也如此繁殖。如果所有的兔子都不死去， 到第 12 個(gè)月 ， 養(yǎng) 共有兔子多少只？ 分析： 是一個(gè)典型的 推 。我 不妨假 第 1 個(gè)月 兔子的只數(shù) u 1 ，第 2 個(gè)月 兔子的只數(shù) u 2 ，

6、第 3 個(gè)月 兔子的只數(shù) u 3 ，?? 根據(jù) 意，“ 種兔子從出生的下一個(gè)月開始，每月新生一只兔子”， 有 u 1 ＝ 1 ， u 2 ＝ u 1 ＋ u 1 1 ＝ 2 ， u 3 ＝ u 2 ＋ u 2 1 ＝ 4 ，?? 根據(jù) 個(gè) 律，可以 出下面的 推公式： u n ＝ u n － 1 2 (n ≥ 2) 對(duì)應(yīng) u n 和 u n － 1 ，定 兩個(gè)迭代 量 y 和 x ，可將上面的 推公式 成如下迭代關(guān)系： y=x*2 x=y 算機(jī) 個(gè)迭代關(guān)系重復(fù) 行 11 次，就可以算出第 1

7、2 個(gè)月 的兔子數(shù)。參考程序如下： cls  x=1 for i=2 to 12 y=x*2 x=y next i print y end 分而治之法 1、分治法的基本思想 任何一個(gè)可以用 算機(jī)求解的 所需的 算 都與其 模 N 有關(guān)。 的 模越 小，越容易直接求解，解 所需的 算 也越少。例如， 于 n 個(gè)元素的排序 ，當(dāng) n=1 ，不需任何 算； n=2 ，只要作一次比 即可排好序； n=3 只要作 3 次比 即可，?。而當(dāng) n 大 ， 就不那么容易 理了。要想直接解決一個(gè) 模 大的

8、， 有 是相當(dāng)困 的。 分治法的 思想是，將一個(gè) 以直接解決的大 ，分割成一些 模 小的相同 ，以便各個(gè) 破，分而治之。 分治法所能解決的問題一般具有以下幾個(gè)特征： （ 1）該問題的規(guī)?？s小到一定的程度就可以容易地解決； （2）該問題可以分解為若干個(gè)規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)； （ 3） 利用該問題分解出的子問題的解可以合并為該問題的解； （ 4） 該問題所分解出的各個(gè)子問題是相互獨(dú)立的，即子問題之間不包含公共的子子問題。 3 、分治法的基本步驟 分治法在每一層遞歸上都有三個(gè)步驟： （ 1） 分

9、解：將原問題分解為若干個(gè)規(guī)模較小，相互獨(dú)立，與原問題形式相同的子問題； （ 2） 解決：若子問題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個(gè)子問題； （ 3） 合并：將各個(gè)子問題的解合并為原問題的解。 快速排序 在這種方法中， n 個(gè)元素被分成三段（組）：左段 l e f t ，右段 r i g h t 和中段 m i d d l e 。中段僅包含一個(gè)元素。左段中各元素都小于等于中段元素，右段中各元素都大于等于中段元 素。 因此 l e f t 和 r i g h t 中的元素可以獨(dú)立排序，并且不必對(duì) l e f t 和 r i g h t 的排序結(jié)果進(jìn)行

10、 合并。 m i d d l e 中的元素被稱為支點(diǎn) ( p i v o t ) 。圖 1 4 - 9 中給出了快速排序的偽代碼。 / /使用快速排序方法對(duì) a[ 0 :n- 1 ] 排序 從 a[ 0 :n- 1 ] 中選擇一個(gè)元素作為 m i d d l e ，該元素為支點(diǎn) 把余下的元素分割為兩段 left 和 r i g h t ，使得 l e f t 中的元素都小于等于支點(diǎn)，而 right 中的元素都大于等于支點(diǎn) 遞歸地使用快速排序方法對(duì) left 進(jìn)行排序 遞歸地使用快速排序方法對(duì) right 進(jìn)行排序 所 得結(jié)果為 l e f

11、t + m i d d l e + r i g h t 考察元素序列 [ 4 , 8 , 3 , 7 , 1 , 5 , 6 , 2 ] 。假設(shè)選擇元素 6 作為支點(diǎn)，則 6 位于 m i d d l e； 4， 3， 1， 5，2 位于 l e f t； 8， 7 位于 r i g h t 。當(dāng) left 排好序后，所得結(jié)果為 1， 2， 3， 4， 5；當(dāng) r i g h t 排好序后，所得結(jié)果為 7， 8。把 right 中的元素放在支點(diǎn)元素之后， l e f t 中的元素放在支點(diǎn)元素之前，即可得到最終的結(jié)果 [ 1 , 2 , 3 , 4 , 5 , 6 ,

12、7 , 8 ] 。 把元素序列劃分為 l e f t 、 m i d d l e 和 r i g h t 可以就地進(jìn)行（見程序 1 4 - 6）。在程序 1 4 - 6 中，支點(diǎn)總是取位置 1 中的元素。也可以采用其他選擇方式來提高排序性能，本章 稍 后部分將給出這樣一種選擇。 程 序 14-6 快速排序 template void QuickSort(T*a, int n) {// 對(duì) a[0:n-1] 進(jìn)行快速排序 {// 要求 a[n] 必需有最大關(guān)鍵值  void quickSort(T

13、a[], int l, int r) {// 排 序 a [ l : r ] ， a[r+1] 有大值 if (l >= r) return; int i = l, // 從左至右的游標(biāo) j = r + 1; // 從右到左的游標(biāo) T pivot = a[l]; // 把左側(cè) >= pivot 的元素與右側(cè) <= quickSort(a, 0, n-1); pivot 的元素進(jìn)行交換 while (true) { template do {// 在左側(cè)尋找 >= pivot 的

14、元素 i = i + 1; } while (a < pivot); do {// 在右側(cè)尋找 <= pivot 的元素 Swap(a, a[j]); } // 設(shè)置 p i v o t a[l] = a[j];  j = j - 1; } while (a[j] > pivot); if (i >= j) break; // 未發(fā)現(xiàn)交換對(duì)象 a[j] = pivot; quickSort(a, l, j-1); // 對(duì)左段排序 quickSort(a, j+1, r); // 對(duì)右段排序 }

15、 貪婪法 它采用逐步構(gòu)造最優(yōu)解的思想，在問題求解的每一個(gè)階段，都作出一個(gè)在一 定標(biāo)準(zhǔn)下看上 去最優(yōu)的決策；決策一旦作出，就不可再更改。制定決策的依據(jù)稱為貪婪準(zhǔn)則。 貪婪法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到 滿意的解，因?yàn)樗∪チ藶檎易顑?yōu)解要窮盡所有可能而必須耗費(fèi)的大量時(shí)間。貪婪法常以當(dāng) 前情況為基礎(chǔ)作最優(yōu)選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯。 【問題】 背包問題 問題描述：有不同價(jià)值、不同重量的物品 n 件，求從這 n 件物品中選取一部分物 品的選擇方案，使選中物品的總重量不超過指定

16、的限制重量，但選中物品的價(jià)值之和最大。 #include void main() { int m,n,i,j,w[50],p[50],pl[50],b[50],s=0,max; printf(" 輸入背包容量 m,物品種類 n :"); scanf("%d %d",&m,&n); for(i=1;i<=n;i=i+1) { printf(" 輸入物品的重量 W 和價(jià)值 P :"); scanf("%d %d",&w[i],&p[i]); pl[i]=p[i]; s=s+w[

17、i]; } if(s<=m) { printf("whole choose\n");  //return; } for(i=1;i<=n;i=i+1) { max=1; for(j=2;j<=n;j=j+1) if(pl[j]/w[j]>pl[max]/w[max] ) max=j; pl[max]=0; b[i]=max; } for(i=1,s=0;s

18、-w[b[i-1]]; for(j=1;j<=i- 1;j=j+1) printf("choose weight %d\n",w[b[j]]); } 動(dòng)態(tài)規(guī)劃的基本思想 前文主要介紹了動(dòng)態(tài)規(guī)劃的一些理論依據(jù)，我們將前文所說的具有明顯的階段劃分和狀態(tài)轉(zhuǎn)移方程的動(dòng)態(tài)規(guī)劃稱為標(biāo)準(zhǔn)動(dòng)態(tài)規(guī)劃，這種標(biāo)準(zhǔn)動(dòng)態(tài)規(guī)劃是在研究多階段決策問題時(shí)推導(dǎo)出來的，具有嚴(yán)格的數(shù)學(xué)形式，適合用于理論上的分析。在實(shí)際應(yīng)用中，許多問題的階段劃分并不明顯，這時(shí)如果刻意地劃分階段法反而麻煩。一般來說，只要該問題可以劃分成規(guī)模更 小的子問題，并且原問題的最優(yōu)解中包含了子問題的最優(yōu)解（

19、即滿足最優(yōu)子化原理），則可以考慮用動(dòng)態(tài)規(guī)劃解決。動(dòng)態(tài)規(guī)劃的實(shí)質(zhì)是分治思想和解決冗余，因此，動(dòng)態(tài)規(guī)劃是一種將問題實(shí)例分解為更小的、相似的子問題，并存儲(chǔ)子問題的解而避免計(jì)算重復(fù)的子問題，以解決最優(yōu)化問題的算法策略。由此可知，動(dòng)態(tài)規(guī)劃法與分治法和貪心法類似，它們都是將問題實(shí)例歸納為更小的、相似的子問題，并通過求解子問題產(chǎn)生一個(gè)全局最優(yōu)解。 貪心法的當(dāng)前選擇可能要依賴已經(jīng)作出的所有選擇，但不依賴于有待于做出的選擇和子問題。因此貪心法自頂向下，一步一步地作出貪心選擇；而分治法中的各個(gè)子問題是獨(dú)立的（即不包含公共的子問題），因此一旦遞歸地求出各子問題的解后，便可自下而上地將子問題的解合并成問題的解。

20、 不足之處：如果當(dāng)前選擇可能要依賴子問題的解時(shí)，則難以通過局部的貪心策略達(dá)到全局最優(yōu)解；如果各子問題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題。解決上述問題的辦法是利用動(dòng)態(tài)規(guī)劃。該方法主要應(yīng)用于最優(yōu)化問題，這類問題會(huì)有多種可能的解，每個(gè)解都有一個(gè)值，而動(dòng)態(tài)規(guī)劃找出其中最優(yōu)（最大或最小）值的解。若存在若干個(gè)取最優(yōu)值的解的話，它只取其中的一個(gè)。在求解過程中，該方法也是通過求解局部子問題的解達(dá)到全局最優(yōu)解，但與分治法和貪心法不同的是，動(dòng)態(tài)規(guī)劃允許這些子問題不獨(dú)立，（亦即各子問題可包含公共的子問題）也允許其通過自身子問題的解作出選擇，該方法對(duì)每一個(gè)子問題只解一次，并將結(jié)果保存

21、起來，避免每次碰到時(shí)都要重復(fù)計(jì)算。 因此，動(dòng)態(tài)規(guī)劃法所針對(duì)的問題有一個(gè)顯著的特征，即它所對(duì)應(yīng)的子問題樹中的子問題呈現(xiàn)大量的重復(fù)。動(dòng)態(tài)規(guī)劃法的關(guān)鍵就在于，對(duì)于重復(fù)出現(xiàn)的子問題，只在第一次遇到時(shí)加以求解，并把答案保存起來，讓以后再遇到時(shí)直接引用，不必重新求解。 3、動(dòng)態(tài)規(guī)劃算法的基本步驟設(shè)計(jì)一個(gè)標(biāo)準(zhǔn)的動(dòng)態(tài)規(guī)劃算法，通?？砂匆韵聨讉€(gè)步驟進(jìn)行： （ 1）劃分階段：按照問題的時(shí)間或空間特征，把問題分為若干個(gè)階段。注意這若干個(gè)階段一定要是有序的或者是可排序的（即無后向性），否則問題就無法用動(dòng)態(tài)規(guī)劃求解。 （ 2）選擇狀態(tài)：將問題發(fā)展到各個(gè)階段時(shí)所處于的各種客觀情況用不同的狀態(tài)表示出

22、來。當(dāng)然，狀態(tài)的選擇要滿足無后效性。 （ 3）確定決策并寫出狀態(tài)轉(zhuǎn)移方程：之所以把這兩步放在一起，是因?yàn)闆Q策和狀態(tài)轉(zhuǎn)移有著天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段的狀態(tài)。所以，如果我們確定了決策，狀態(tài)轉(zhuǎn)移方程也就寫出來了。但事實(shí)上，我們常常是反過來做，根據(jù)相鄰兩段的各狀態(tài)之間的關(guān)系來確定決策。 （ 4）寫出規(guī)劃方程（包括邊界條件）：動(dòng)態(tài)規(guī)劃的基本方程是規(guī)劃方程的通用形式化表達(dá)式。一般說來，只要階段、狀態(tài)、決策和狀態(tài)轉(zhuǎn)移確定了，這一步還是比較簡單的。動(dòng)態(tài)規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì)，一旦設(shè)計(jì)完成，實(shí)現(xiàn)部分就會(huì)非常簡單。根 據(jù)動(dòng)態(tài)規(guī)劃的基本方程可以直接遞歸計(jì)

23、算最優(yōu)值，但是一般將其改為遞推計(jì)算，實(shí)現(xiàn)的大體上的框架如下：標(biāo)準(zhǔn)動(dòng)態(tài)規(guī)劃的基本框架 1. 對(duì) f n+1(xn+1 )初始化 ; { 邊界條件 } for k:=n downto 1 do for 每一個(gè) xk∈ X k do for 每一個(gè) uk∈U k(xk) do begin f k(xk):= ; { } xk+1 :=T k(xk,uk); { 狀態(tài)轉(zhuǎn)移方程 } t:= φk+1(f (xk+1),v k(x k,uk)); { 基本方程 (9) 式 } if t 比 f k(xk)更優(yōu) then fk(x k):=t; { 計(jì)算 fk(x

24、k)的最優(yōu)值 } end; t:= 一個(gè)極 ; { ∞或－∞ } for 每一個(gè) x1∈X 1 do if f 1(x 1)比 t 更 then t:=f 1(x1); { 按照 10 式求出最 指 } 出 t; 但是， 用當(dāng)中 常不 式地按照上面步 劃，而是按以下幾個(gè)步 行： （ 1）分析最 解的性 ，并刻劃其 構(gòu)特征。 （ 2） 地定 最 。 （ 3）以自底向上的方式或自 向下的 化方法（ 忘 法） 算出最 。 （ 4）根據(jù) 算最 得到的信息，構(gòu)造一個(gè)最 解。

25、 步 （ 1）～（ 3）是 劃算法的基本步 。在只需要求出最 的情形，步 （ 4）可以省略，若需要求出 的一個(gè)最 解， 必 行步 （ 4）。此 ，在步 （ 3）中 算最 ，通常需 更多的信息，以便在步 （ 4）中，根據(jù)所 的信息，快速地構(gòu)造出一個(gè)最 解。 ： 劃 上就是最 化的 ，是指將原 的大 例等價(jià)于同一最 化 的 小 例，自底向上的求解最小 例，并將所求解存放起來，存放的 果就是 了準(zhǔn) 數(shù)據(jù)。 與 相比， 是不斷的 用子程序求解，是自 向下的 用和求解。 回溯法 回溯法也稱 探法， 方法首先

26、放棄關(guān)于 模大小的限制，并將 的候 解按某種 序逐一枚 和 。當(dāng) 當(dāng)前候 解不可能是解 ，就 下一個(gè)候 解；倘若當(dāng)前候 解除了 不 足 模要求外， 足所有其他要求 ， 大當(dāng)前候 解的 模，并 探。如果當(dāng)前候 解 足包括 模在內(nèi)的所有要求 ， 候 解就是 的一個(gè)解。在回溯法中，放棄當(dāng)前候 解， 找下一個(gè)候 解的 程稱 回溯。 大當(dāng)前候 解的 模，以 探的 程稱 向前 探。 1、回溯法的一般描述 可用回溯法求解的 P，通常要能表達(dá) ： 于已知的由 n 元 （ x1， x2，?， xn） 成

27、 的一個(gè)狀 空 E={ （ x1， x2，?， xn）∣ xi∈ Si ， i=1 ， 2，?， n} ， 定關(guān)于 n 元 中的 一個(gè)分量的一個(gè) 束集 D ，要求 E 中 足 D 的全部 束條件的所有 n 元 。其中 Si 是分量 xi 的定 域，且 |Si | 有限， i=1 ， 2，?， n。我 稱 E 中 足 D 的全部 束條件的任一 n 元 組為問題 P 的一個(gè)解。 解 P 的最樸素的方法就是枚 法，即 E 中的所有 n 元 逐一地 其是否 足 D 的全部 束，

28、若 足， P 的一個(gè)解。但 然，其 算量是相當(dāng)大的。 我 ， 于 多 ，所 定的 束集 D 具有完 性，即 i 元 （ x1，x2，?， xi） 足 D 中 涉及到 x1， x2，?， xi 的所有 束意味著 j （j

29、 1，使得（ x ， x ，?， x ） 反 D 中 涉及到 x ， x ，?， x 的 束之一， 以（ x ， 1 2 j 1 2 j 1 x ，?， x ） 前 的任何 n 元 （ x ， x ，?， x ， x j+1 ，?， x ）一定也 反 D 中 涉及 2 j 1 2 j n 到 x1， x2，?， xi 的一個(gè) 束， n≥ i>j 。因此， 于 束集 D 具有完 性的 P，一旦 斷定某個(gè) j 元

30、 （ x1， x2 ，?， xj） 反 D 中 涉及 x1 ，x 2，?， xj 的一個(gè) 束，就可以 肯定，以（ x1， x2，?， xj） 前 的任何 n 元 （ x1 ，x2，?， xj，xj+1 ，?， xn）都不會(huì)是 問題 P 的解，因而就不必去搜索它 、 它 ?；厮莘ㄕ? ，利用 的上述性 而提出來的比枚 法效率更高的算法。 回溯法首先將 P 的 n 元 的狀 空 E 表示成一棵高 n 的 有序 T，把在 E 中求 P 的所有解 化 在 T 中搜索 P 的所有解。 T 似

31、于 索 ，它可以 構(gòu)造： 設(shè) Si 中的元素可排成 xi (1) ， xi (2) ，?， xi(mi-1) ， |Si| =m i， i=1 ， 2，?， n。從根開始， T 的第 I 的每一個(gè) 點(diǎn)都有 mi 個(gè)兒子。 mi 個(gè)兒子到它 的雙 的 ，按從左到右的次 序，分 xi+1 (1) ，xi+1 (2) ，?， xi+1 (mi) ， i=0 ， 1，2，?， n-1。照 種構(gòu)造方式， E 中的 一個(gè) n 元 （ x1， x2，?， xn） 于 T 中

32、的一個(gè)葉子 點(diǎn)， T 的根到 個(gè)葉子 點(diǎn)的路徑 上依次的 n 條 的 分 x1 ，x2，?， xn，反之亦然。另外， 于任意的 0≤ i≤ n-1， E 中 n 元 （ x1， x2，?， xn）的一個(gè)前 I 元 （ x1，x2 ，?， xi） 于 T 中的一個(gè)非葉子 點(diǎn)， T 的根到 個(gè)非葉子 點(diǎn)的路徑上依次的 I 條 的 分 x1， x2，?， xi，反之亦 然。特 ， E 中的任意一個(gè) n 元 的空前 （）， 于 T 的根。 因而，在 E 中 找

33、P 的一個(gè)解等價(jià)于在 T 中搜索一個(gè)葉子 點(diǎn)，要求從 T 的根到 葉子 點(diǎn)的路徑上依次的 n 條 相 的 n 個(gè) x1， x2，?， xn 足 束集 D 的全部 束。 在 T 中搜索所要求的葉子 點(diǎn)，很自然的一種方式是從根出 ，按深度 先的策略逐步深 入，即依次搜索 足 束條件的前 1 元 （ x1i ）、前 2 元 （ x1，x2）、?，前 I 元 （ x1， x2，?， xi），?，直到 i=n 止。 在回溯法中，上述引入的 被稱 P 的狀 空 ； T 上任意一個(gè) 點(diǎn)被稱 問題 P 的狀 點(diǎn)； T 上的任意一個(gè)葉子

34、 點(diǎn)被稱 P 的一個(gè)解狀 點(diǎn)； T 上 足 束集 D 的全部 束的任意一個(gè)葉子 點(diǎn)被稱 P 的一個(gè)回答狀 點(diǎn)，它 于 P 的一個(gè)解。 【 】 n 皇后 描述：求出在一個(gè) n n 的棋 上，放置 n 個(gè)不能互相捕捉 的國 象棋“皇后” 的所有布局。 是來源于國 象棋的一個(gè) ?；屎罂梢匝刂?橫和兩條斜 4 個(gè)方向相互捕捉。如 所示，一個(gè)皇后放在棋 的第 4 行第 3 列位置上， 棋 上凡打“”的位置上的皇后就能與 個(gè)皇后相互捕捉。 1 2 3 4 5 6 7 8

35、 Q  從 中可以得到以下啟示：一個(gè)合適的解 是在每列、每行上只有一個(gè)皇后，且一條斜 上也只有一個(gè)皇后。 求解 程從空配置開始。在第 1 列至第 m 列 合理配置的基 上，再配置第 m+1 列， 直至第 n 列配置也是合理 ，就找到了一個(gè)解。接著改 第 n 列配置，希望 得下一個(gè)解。 另外，在任一列上，可能有 n 種配置。開始 配置在第 1 行，以后改 ， 次 第 2 行、第 3 行、?、直到第 n 行。當(dāng)?shù)?n 行配置也找不到一個(gè)合理的配置 ，就要

36、回溯，去 改 前一列的配置。得到求解皇后 的算法如下： {  入棋 大小  n； m=0; {  good=1; if (good)  do if (m==n) {  出解； 改 之，形成下一個(gè)候 解 ; } else 展當(dāng)前候 接至下一列； else 改 之，形成下一個(gè)候 解； good= 當(dāng)前候 解的合理性； } while (m!=0); } 在 寫程序之前，先確定 式棋 的數(shù)

37、據(jù) 構(gòu)。比 直 的方法是采用一個(gè)二 數(shù) ，但仔 察就會(huì) ， 種表示方法 整候 解及 其合理性 來困 。更好的方法乃是盡可能直接表示那些常用的信息。 于本 來 ，“常用信息”并不是皇后的具體位置，而是“一個(gè)皇后是否已 在某行和某條斜 合理地安置好了”。因在某一列上恰好放一個(gè)皇 后，引入一個(gè)一 數(shù) （ col[ ] ）， col[i] 表示在棋 第 i 列、 col[i] 行有一個(gè)皇后。例如： col[3]=4 ，就表示在棋 的第 3 列、第 4 行上有一個(gè)皇后。另外， 了使程序在找完了全部解后回溯到最初位置， 定 col[0] 的初 0 當(dāng)回溯到第 0 列 ，

38、明程序已求得全部解， 束程序運(yùn)行。 使程序在 皇后配置的合理性方面 易方便，引入以下三個(gè)工作數(shù) ： （ 1） 數(shù) a[ ]， a[k] 表示第 k 行上 沒有皇后； （ 2） 數(shù) b[ ] ， b[k] 表示第 k 列右高左低斜 上沒有皇后； （3） 數(shù) c[ ] ， c[k] 表示第 k 列左高右低斜 上沒有皇后； 棋 中同一右高左低斜 上的方格，他 的行號(hào)與列號(hào)之和相同；同一左高右低斜 上的方格，他 的行號(hào)與列號(hào)之差均相同。 初始時(shí)，所有行和斜線上均沒有皇后，從第 

39、 1 列的第  1 行配置第一個(gè)皇后開始，在第 m 列  col[m] 行放置了一個(gè)合理的皇后后，準(zhǔn)備考察第  m+1  列時(shí)，在數(shù)組  a[  ]  、 b[ ] 和 c[ ] 中為第  m 列， col[m] 行的位置設(shè)定有皇后標(biāo)志；當(dāng)從第  m 列回溯到第  m-1  列，并準(zhǔn)備 調(diào)整第  m-1  列的皇后配置時(shí)，清除在數(shù)組  a[ ] 、 b[ ]  和  c

40、[ ]  中設(shè)置的關(guān)于第  m-1  列， col[m-1]  行有皇后的標(biāo)志。一個(gè)皇后在  m 列， col[m] 行方格內(nèi)配置是合理的，由數(shù)組  a[ ] 、 b[ ] 和  c[ ] 對(duì)應(yīng)位置的值都為  1 來確定。細(xì)節(jié) 見以下程序： 【程序】 # include # include # define MAXN 20 n,m,good;  int int col[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*M

41、AXN+1]; void main() { int j; char awn; printf( “ Entern: “ ); scanf( “ %d” ,&n); for (j=0;j<=n;j++) a[j]=1; for (j=0;j<=2*n;j++) cb[j]=c[j]=1; m=1; col[1]=1; good=1; col[0]=0; do { if (good) if (m==n) { printf( “列 \t 行” ); for (j=

42、1;j<=n;j++) printf( “ %3d n” ,j,col[j]); printf( “ Enter a character (Q/q n” ); scanf( “ %c” ,&awn); if (awn== ’ Q’ ||awn== ’ q’ ) exit(0); while (col[m]==n) { m--; a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1; col[m]++; } }

43、 else { a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=0; col[++m]=1; }else { while (col[m]==n) { m--; a[col[m]]=b[m+col[m]]=c[n+m-col[m]]=1; } col[m]++; } good=a[col[m]]&&b[m+col[m]]&&c[n+m-col[m]]; } while (m!=0); } 試探法找解算法也常常被編寫成遞歸函數(shù)，下面兩程序中的函數(shù)

44、queen_all() 和函數(shù) queen_one()能分別用來解皇后問題的全部解和一個(gè)解。 【程序】 # include # include # define MAXN 20 int n; int col[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1]; void main() { int j; printf( “ Enter “n: ); scanf( “ %d” ,&n); for (j=0;j<=n;j++) a[j]=1; for (j=0;j<=2*n;j++) cb[j

45、]=c[j]=1; queen_all(1,n); } void queen_all(int k,int n) { int i,j; char awn; for (i=1;i<=n;i++) if (a[i]&&b[k+i]&&c[n+k-i]) { col[k]=i; a[i]=b[k+i]=c[n+k-i]=0; if (k==n) { printf( “列 \t 行” ); for (j=1;j<=n;j++) printf( “ %3d n” ,j,col[j]); printf( “ Enter a character

46、(Q/q n” ); scanf( “ %c” ,&awn); if (awn== ’ Q’ ||awn== ’ q’ ) exit(0); } queen_all(k+1,n); a[i]=b[k+i]=c[n+k-i]; } } 采用遞歸方法找一個(gè)解與找全部解稍有不同，在找一個(gè)解的算法中，遞歸算法要對(duì)當(dāng)前候選解最終是否能成為解要有回答。當(dāng)它成為最終解時(shí)，遞歸函數(shù)就不再遞歸試探，立即返 回；若不能成為解，就得繼續(xù)試探。設(shè)函數(shù) queen_one()返回 1 表示找到解，返回 0 表示當(dāng) 前候選解不能成為解。細(xì)節(jié)見以下函數(shù)。

47、 【程序】 # define MAXN 20 int n; int col[MAXN+1],a[MAXN+1],b[2*MAXN+1],c[2*MAXN+1]; int queen_one(int k,int n) { int i,found; i=found=0; While (!found&&i { i++; if (a[i]&&b[k+i]&&c[n+k-i]) { col[k]=i; a[i]=b[k+i]=c[n+k-i]=0; if (k==n) return 1; else found=queen_one(k+

48、1,n); a[i]=b[k+i]=c[n+k-i]=1; } } return found; } 分支定界法： 分支限界法： 這是一種用于求解組合優(yōu)化問題的排除非解的搜索算法。類似于回溯法，分枝定界法在搜索解空間時(shí)，也經(jīng)常使用樹形結(jié)構(gòu)來組織解空間。然而與回溯法不同的是，回溯算法使用深度優(yōu)先方法搜索樹結(jié)構(gòu)，而分枝定界一般用寬度優(yōu)先或最小耗費(fèi)方法來搜索這些樹。因此，可以很容易比較回溯法與分枝定界法的異同。相對(duì)而言，分枝定界算法的解空間比回溯法大得多，因此當(dāng)內(nèi)存容量有限時(shí)，回溯法成功的可能性更大。 算法思想：分枝定界（

49、branch and bound）是另一種系統(tǒng)地搜索解空間的方法，它與回溯法 的主要區(qū)別在于對(duì) E-節(jié)點(diǎn)的擴(kuò)充方式。每個(gè)活節(jié)點(diǎn)有且僅有一次機(jī)會(huì)變成 E-節(jié)點(diǎn)。當(dāng)一個(gè)節(jié)點(diǎn)變?yōu)?E-節(jié)點(diǎn)時(shí)，則生成從該節(jié)點(diǎn)移動(dòng)一步即可到達(dá)的所有新節(jié)點(diǎn)。在生成的節(jié)點(diǎn)中，拋棄那些不可能導(dǎo)出（最優(yōu)）可行解的節(jié)點(diǎn)，其余節(jié)點(diǎn)加入活節(jié)點(diǎn)表，然后從表中選擇一 個(gè)節(jié)點(diǎn)作為下一個(gè) E-節(jié)點(diǎn)。從活節(jié)點(diǎn)表中取出所選擇的節(jié)點(diǎn)并進(jìn)行擴(kuò)充，直到找到解或活動(dòng)表為空，擴(kuò)充過程才結(jié)束。 有兩種常用的方法可用來選擇下一個(gè) E-節(jié)點(diǎn)（雖然也可能存在其他的方法）： 1) 先進(jìn)先出（ F I F O ） 即從活節(jié)點(diǎn)表中取出節(jié)點(diǎn)的順

50、序與加入節(jié)點(diǎn)的順序相同，因此 活 節(jié)點(diǎn)表的性質(zhì)與隊(duì)列相同。 2) 最小耗費(fèi)或最大收益法在這種模式中，每個(gè)節(jié)點(diǎn)都有一個(gè)對(duì)應(yīng)的耗費(fèi)或收益。如果 查找 一個(gè)具有最小耗費(fèi)的解，則活節(jié)點(diǎn)表可用最小堆來建立，下一個(gè) E-節(jié)點(diǎn)就是具有最 小耗費(fèi) 的活節(jié)點(diǎn)；如果希望搜索一個(gè)具有最大收益的解，則可用最大堆來構(gòu)造活節(jié)點(diǎn)表，下一個(gè) E-節(jié)點(diǎn)是具有最大收益的活節(jié)點(diǎn) 裝載問題用一 個(gè)隊(duì)列 Q 來存放活結(jié) 點(diǎn)表， Q 中 weight 表示每個(gè)活結(jié)點(diǎn)所相應(yīng)的當(dāng)前載重 量。當(dāng) weight ＝－ 1 時(shí)，表示隊(duì)列已達(dá)到解 空間樹同一層結(jié)點(diǎn)的尾部。 算法首先檢測(cè)當(dāng)前擴(kuò)展結(jié)點(diǎn)

51、的左兒子結(jié)點(diǎn)是否為可行結(jié)點(diǎn)。如果是則將其加入到活結(jié)點(diǎn)隊(duì)列中。然后將其右兒子結(jié)點(diǎn)加入到活結(jié)點(diǎn)隊(duì)列中 (右兒子結(jié)點(diǎn)一定是可行結(jié) 點(diǎn) )。 2 個(gè)兒子結(jié)點(diǎn)都產(chǎn)生后，當(dāng)前擴(kuò)展結(jié)點(diǎn)被舍棄。 活結(jié)點(diǎn)隊(duì)列中的隊(duì)首元素被取出作為當(dāng)前擴(kuò)展結(jié)點(diǎn)，由于隊(duì)列中每一層結(jié)點(diǎn)之后 都有一個(gè)尾部標(biāo)記 -1 ，故在取隊(duì)首元素時(shí)， 活結(jié)點(diǎn)隊(duì)列一定不空。當(dāng)取出的元素是 -1 時(shí)，再判斷當(dāng)前隊(duì)列是否為空。如果隊(duì)列 非空，則將尾部標(biāo)記 -1 加入活結(jié)點(diǎn)隊(duì)列， 算法 開始處理下一層的活結(jié)點(diǎn)。 /* 該版本只算出最優(yōu)解 */ #include  #inclu

52、de struct Queue{ int weight ; struct Queue* next ; }; int bestw = 0 ; // 目前的最優(yōu)值 Queue* Q; // 活結(jié)點(diǎn)隊(duì)列 Queue* lq = NULL ; Queue* fq = NULL ; int Add(int w) { Queue* q ; q = (Queue*)malloc(sizeof(Queue)) ; if(q ==NULL) { printf(" 沒有足夠的空間分配 \n") ; retur

53、n 1 ; } q->next = NULL ; q->weight = w ; if(Q->next == NULL) { Q->next = q ; fq = lq = Q->next ; // 一定要使元素放到鏈中 } else { lq->next = q ; lq = q ; // lq = q->next ; } return 0 ; } int IsEmpty() { if(Q->next==NULL) return 1 ; return 0 ; } int Delete(int&w)

54、 { Queue* tmp = NULL ; // fq = Q->next ; tmp = fq ; w = fq->weight ; Q->next = fq->next ; /* 一定不能丟了鏈表頭 */ fq = fq->next ; free(tmp) ; return 0 ; } void EnQueue(int wt, int& bestw, int i, int n) // 該函數(shù)負(fù)責(zé)加入 活結(jié)點(diǎn) { // 如果不是葉結(jié)點(diǎn)，則將結(jié)點(diǎn)權(quán)值 wt 加 入隊(duì)列 Q if (i == n) { // 葉 子 if

55、 (wt>bestw) bestw = wt; } else Add(wt); // 不是葉子 if (IsEmpty()) return bestw; if(i

56、 out = fopen("output.txt" , "w") ; if(in==NULL||out==NULL){ printf(" 沒有輸入輸出文件 \n") ; return 1 ; } fscanf(in , "%d" , &n) ; fscanf(in , "%d" , &c) ; w = (int*)malloc(sizeof(int)*(n+1)) ; for(i =1 ; i<=n ; i++) fscanf(in , "%d" , &w[i]) ; MaxLoading(w , c ,  } int MaxLoading(int

57、 w[], int c, int n) { // 返回最優(yōu)裝載值 // 為層次 1 初始化 int err ; // 返回值 int i = 1; // 當(dāng)前擴(kuò)展結(jié)點(diǎn)的層 int Ew = 0; // 當(dāng)前擴(kuò)展結(jié)點(diǎn)的權(quán)值 bestw = 0; // 目前的最優(yōu)值 Q = (Queue*)malloc(sizeof(Queue)) ; Q->next = NULL ; Q->weight = -1 ; err = Add(-1) ; // 標(biāo)記本層的尾部 if(err) { return 0 ; } while (true) { // 檢查左孩子結(jié)點(diǎn) if (Ew + w[i] <= c) // x[i] = 1 EnQueue(Ew + w[i], bestw , i, n); // 右孩子總是可行的 EnQueue(Ew, bestw, i, n); // x[i] = 0 Delete(Ew); // 取下一個(gè)擴(kuò)展結(jié)點(diǎn) if (Ew == -1) { // 到達(dá)層的尾部 n) ; fprintf(out , "%d\n" , bestw) ; return 0 ; }