算法題計算機算法設計與分析期末試題套含答案

1、1)用計算機求解問題的步驟： 1、問題分析 2、數(shù)學模型建立 3、算法設計與選擇 4、算法指標 5、算法分析 6、算法實現(xiàn) 7、 程序調試 8、結果整理文檔編制(2) 算法定義：算法是指在解決問題時，按照某種機械步驟一定可以得到問題結果的處理 過程(3) 算法的三要素1、操作 2、控制結構 3、數(shù)據(jù)結構 算法具有以下 5 個屬性 ： 有窮性：一個算法必須總是在執(zhí)行有窮步之后結束，且每一步都在有窮時間內完成。 確定性：算法中每一條指令必須有確切的含義。不存在二義性。只有一個入口和一個出 口可行性：一個算法是可行的就是算法描述的操作是可以通過已經(jīng)實現(xiàn)的基本運算執(zhí)行有 限次來實現(xiàn)的。輸入：一個算法有

2、零個或多個輸入，這些輸入取自于某個特定對象的集合。 輸出：一個算法有一個或多個輸出，這些輸出同輸入有著某些特定關系的量。算法設計的質量指標： 正確性：算法應滿足具體問題的需求； 可讀性：算法應該好讀，以有利于讀者對程序的理解； 健壯性：算法應具有容錯處理，當輸入為非法數(shù)據(jù)時，算法應對其作出反應，而不是產(chǎn) 生莫名其妙的輸出結果。效率與存儲量需求： 效率指的是算法執(zhí)行的時間； 存儲量需求指算法執(zhí)行過程中所需要 的最大存儲空間。一般這兩者與問題的規(guī)模有關。經(jīng)常采用的算法主要有迭代法、分而治之法、貪婪法、動態(tài)規(guī)劃法、回溯法、分支限界法 迭代法 也稱“輾轉法”，是一種不斷用變量的舊值遞推出新值的解決問題

3、的方法。 利用迭代算法解決問題，需要做好以下三個方面的工作：一、確定迭代模型。在可以用迭代算法解決的問題中，至少存在一個直接或間接地不斷 由舊值遞推出新值的變量，這個變量就是迭代變量。二、建立迭代關系式。所謂迭代關系式，指如何從變量的前一個值推出其下一個值的公 式(或關系)。迭代關系式的建立是解決迭代問題的關鍵，通常可以使用遞推或倒推的方法三、對迭代過程進行控制。 在什么時候結束迭代過程？這是編寫迭代程序必須考慮的問 題。不能讓迭代過程無休止地重復執(zhí)行下去。迭代過程的控制通?？煞譃閮煞N情況：一種是 所需的迭代次數(shù)是個確定的值，可以計算出來；另一種是所需的迭代次數(shù)無法確定。對于前 一種情況，可以

4、構建一個固定次數(shù)的循環(huán)來實現(xiàn)對迭代過程的控制；對于后一種情況，需要 進一步分析出用來結束迭代過程的條件。編寫計算斐波那契( Fibonacci )數(shù)列的第 n 項函數(shù) fib (n)。斐波那契數(shù)列為：0、1、1、2、3、，即：fib(0)=0;fib(1)=1;fib(n)=fib(n-1)+fib(n-2) (當 n1 時)。寫成遞歸函數(shù)有：int fib(int n) if (n=0) return 0;if (n=1) return 1;if (n1) return fib(n-1)+fib(n-2);一個飼養(yǎng)場引進一只剛出生的新品種兔子， 這種兔子從出生的下一個月開始， 每月新生一只

5、兔子，新生的兔子也如此繁殖。 如果所有的兔子都不死去，問到第 12 個月時，該飼養(yǎng)場共 有兔子多少只？分析： 這是一個典型的遞推問題。 我們不妨假設第 1 個月時兔子的只數(shù)為 u 1 ，第 2 個月時兔子的只數(shù)為u 2 ，第3個月時兔子的只數(shù)為u 3,根據(jù)題意，“這種兔子從出生的下一個月開始，每月新生一只兔子”，則有u 1 = 1 , u 2 = u 1+ u 1 X 1 = 2 , u 3 = u 2+ u 2 X 1 = 4 ,根據(jù)這個規(guī)律，可以歸納出下面的遞x=1推公式：for i=2 to 12u n = u n 1 X 2 (n 2)y=x*2對應 u n 和 u n 1 ，定義兩x

6、=y個迭代變量 y 和 x ，可將上面的遞next i推公式轉換成如下迭代關系：print yy=x*2end x=y讓計算機對這個迭代關系重復執(zhí)行 11 次，就可以算出第 12 個月時的兔子數(shù)。參考程序如下：cls分而治之法1、分治法的基本思想任何一個可以用計算機求解的問題所需的計算時間都與其規(guī)模N 有關。問題的規(guī)模越小，越容易直接求解，解題所需的計算時間也越少。例 如，對于 n 個元素的排序問題，當 n=1 時，不需任何計算； n=2 時，只要作 一次比較即可排好序；n=3時只要作3次比較即可，。而當 n較大時，問題就不那么容易處理了。要想直接解決一個規(guī)模較大的問題，有時是相當 困難的。分

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

8、則直接解，否則遞歸地解各個子問題；（3）合并：將各個子問題的解合并為原問題的解。快速排序在這種方法中， n 個元素被分成三段（組） ：左段 l e f t ，右段 r i g h t 和 中段 m i d d l e 。中段僅包含一個元素。左段中各元素都小于等于中段元素， 右段中各元素都大于等于中段元素。因此 l e f t 和 r i g h t 中的元素可以獨 立排序，并且不必對 l e f t 和 r i g h t 的排序結果進行合并。 m i d d l e 中的元素被稱為支點 （ p i v o t ）。圖 1 4 - 9 中給出了快速排序的偽代碼。/ / 使用快速排序方法對 a

9、0 :n- 1 排序從 a 0 :n- 1 中選擇一個元素作為 m i d d l e ，該元素為支點 把余下的元素分割為兩段 left 和 r i g h t ，使得 l e f t 中的元素都小 于等于支點，而 right 中的元素都大于等于支點遞歸地使用快速排序方法對 left 進行排序 遞歸地使用快速排序方法對 right 進行排序 所得結果為 l e f t + m i d d l e + r i g h t考察元素序列 4 , 8 , 3 , 7 , 1 , 5 , 6 , 2 。假設選擇元素 6 作為支點，則 6 位于 m i d d l e ；4，3，1，5，2位于 l e f

10、 t ；8，7位于 r i g h t 。當 left 排好序后，所得結果為 1，2，3，4，5；當 r i g h t 排好序后，所 得結果為 7，8。把 right 中的元素放在支點元素之后， l e f t 中的元素放在 支點元素之前，即可得到最終的結果 1 , 2 , 3 , 4 , 5 , 6 , 7 , 8 。把元素序列劃分為 l e f t 、 m i d d l e 和 r i g h t可以就地進行（見程序 1 4 - 6 ）。在程序 1 4 - 6 中，支點總是取位置 1 中的元素。也可以采用 其他選擇方式來提高排序性能，本章稍后部分將給出這樣一種選擇。程序 14-6 快速

11、排序未發(fā)現(xiàn)對左對右templatevoid QuickSort(T*a, int n)/ 對 a0:n-1 進行快速排序/ 要求 an 必需有最大關鍵 值quickSort(a, 0, n-1);templatevoid quickSort(T a, int l, int r)/ 排序 a l : r ， ar+1 有 大值if (l = r) return;int i = l, /從左至右的游標j = r + 1; / 從右到左的游標T pivot = al;/ 把左側 = pivot 的元素與右側 = pivot 的元素i = i + 1; while (a pivot);do / 在右側

12、尋找 pivot);if (i = j) break; / 交換對象Swap(a, aj);/ 設置 p i v o tal = aj;aj = pivot;quickSort(a, l, j-1); / 段排序quickSort(a, j+1, r); / 段排序貪婪法它采用逐步構造最優(yōu)解的思想，在問題求解的每一個階段，都作出一個在一 定 標準下看上去最優(yōu)的決策； 決策一旦作出， 就不可再更改。 制定決策的依據(jù)稱為 貪婪準則。 貪婪法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。貪婪法一般可 以快速得到滿意的解， 因為它省去了為找最優(yōu)解要窮盡所有可能而必須耗費的大 量時間。貪婪法常以當前情

13、況為基礎作最優(yōu)選擇， 而不考慮各種可能的整體情況， 所以貪婪法不要回溯?！締栴}】 背包問題問題描述：有不同價值、不同重量的物品 n 件，求從這 n 件物品中選取一部分物品的選擇方案，使 選中物品的總重量不超過指定的限制重量，但選中物品的價值之和最大。#includevoid main()int m,n,i,j,w50,p50,pl50,b50 ,s=0,max;prin tf(輸入背包容量 m,物品種類 n :);scanf(%d %d,&m,&n); for(i=1;i=n;i=i+1)printf(輸入物品的重量 W和價值 P :);scanf(%d %d,&wi,&pi); pli=pi

14、; s=s+wi; if(s=m)動態(tài)規(guī)劃的基本思想printf(whole choosen);/return;for(i=1;i=n;i=i+1)max=1;for(j=2;jplmax/wmax) max=j; plmax=0; bi=max;for(i=1,s=0;sm&i=n;i=i+1)s=s+wbi;if(s!=m)wbi-1=m-wbi-1;for(j=1;j=i-1;j=j+1)printf(chooseweight %dn,wbj);前文主要介紹了動態(tài)規(guī)劃的一些理論依據(jù)， 我們將前文所說的具有明顯的階段劃 分和狀態(tài)轉移方程的動態(tài)規(guī)劃稱為 標準動態(tài)規(guī)劃 ，這種標準動態(tài)規(guī)劃是在研

15、究多 階段決策問題時推導出來的， 具有嚴格的數(shù)學形式， 適合用于理論上的分析。 在 實際應用中， 許多問題的階段劃分并不明顯， 這時如果刻意地劃分階段法反而麻 煩。一般來說， 只要該問題可以劃分成規(guī)模更小的子問題， 并且原問題的最優(yōu)解 中包含了子問題的最優(yōu)解 （即滿足最優(yōu)子化原理） ，則可以考慮用動態(tài)規(guī)劃解決。 動態(tài)規(guī)劃的實質是 分治思想和解決冗余，因此，動態(tài)規(guī)劃 是一種將問題實例分解 為更小的、相似的子問題， 并存儲子問題的解而避免計算重復的子問題， 以解決 最優(yōu)化問題的算法策略。由此可知， 動態(tài)規(guī)劃法與分治法和貪心法類似， 它們都是將問題實例歸納為更小 的、相似的子問題，并通過求解子問題產(chǎn)

16、生一個全局最優(yōu)解。貪心法的當前選擇可能要依賴已經(jīng)作出的所有選擇， 但不依賴于有待于做出的選 擇和子問題。因此貪心法自頂向下，一步一步地作出貪心選擇； 而分治法中的各個子問題是獨立的（即不包含公共的子問題） ，因此一旦遞歸地 求出各子問題的解后，便可自下而上地將子問題的解合并成問題的解。不足之處： 如果當前選擇可能要依賴子問題的解時， 則難以通過局部的貪心策略 達到全局最優(yōu)解；如果各子問題是不獨立的，則分治法要做許多不必要的工作， 重復地解公共的子問題。解決上述問題的辦法是利用動態(tài)規(guī)劃。 該方法主要應用于最優(yōu)化問題， 這類問題 會有多種可能的解， 每個解都有一個值， 而動態(tài)規(guī)劃找出其中最優(yōu) （最

17、大或最?。?值的解。若存在若干個取最優(yōu)值的解的話，它只取其中的一個。在求解過程中， 該方法也是通過求解局部子問題的解達到全局最優(yōu)解， 但與分治法和貪心法不同 的是，動態(tài)規(guī)劃允許這些子問題不獨立， （亦即各子問題可包含公共的子問題） 也允許其通過自身子問題的解作出選擇， 該方法對每一個子問題只解一次， 并將 結果保存起來，避免每次碰到時都要重復計算。 因此，動態(tài)規(guī)劃法所針對的問題有一個顯著的特征， 即它所對應的子問題樹中的 子問題呈現(xiàn)大量的重復。 動態(tài)規(guī)劃法的關鍵就在于， 對于重復出現(xiàn)的子問題， 只 在第一次遇到時加以求解， 并把答案保存起來， 讓以后再遇到時直接引用， 不必 重新求解。3、動態(tài)

18、規(guī)劃算法的基本步驟 設計一個標準的動態(tài)規(guī)劃算法，通常可按以下幾個步驟進行：（1）劃分階段：按照問題的時間或空間特征，把問題分為若干個階段。注意這 若干個階段一定要是有序的或者是可排序的（即無后向性） ，否則問題就無法用 動態(tài)規(guī)劃求解。（2）選擇狀態(tài)：將問題發(fā)展到各個階段時所處于的各種客觀情況用不同的狀態(tài) 表示出來。當然，狀態(tài)的選擇要滿足無后效性。（3）確定決策并寫出狀態(tài)轉移方程：之所以把這兩步放在一起，是因為決策和 狀態(tài)轉移有著天然的聯(lián)系， 狀態(tài)轉移就是根據(jù)上一階段的狀態(tài)和決策來導出本階 段的狀態(tài)。 所以，如果我們確定了決策， 狀態(tài)轉移方程也就寫出來了。 但事實上， 我們常常是反過來做，根據(jù)相

19、鄰兩段的各狀態(tài)之間的關系來確定決策。（ 4）寫出規(guī)劃方程 （包括邊界條件）：動態(tài)規(guī)劃的基本方程是規(guī)劃方程的通用形 式化表達式。一般說來，只要階段、狀態(tài)、決策和狀態(tài)轉移確定了，這一步還是比較簡單的。 動態(tài)規(guī)劃的主要難點在于理論上的設計， 一旦設計完成，實現(xiàn)部分就會非常簡單。 根據(jù)動態(tài)規(guī)劃的基本方程可以直接遞歸計算最優(yōu)值，但是一般將其改為遞推計 算，實現(xiàn)的大體上的框架如下： 標準動態(tài)規(guī)劃的基本框架1.?對fn+1（Xn+1）初始化；? 邊界條件for k:=n downto 1 dofor 每一個 Xk Xk dofor 每一個 Uk Uk（x k） dobeginf k（X k）:= 一個極值;

20、？?？ %或xk+1:=T k（x k,u k）;? 狀態(tài)轉移方程 t:= （f k+i（x k+i）,v k（x k,u k）;? 基本方程（9）式if? t 比 f k（x k）更優(yōu) then f k（x k）:=t; 計算 fk（Xk）的最優(yōu)值end;t：= 一個極值;?？ x或x for 每一個 xi X doif f 1（x 1）比t更優(yōu)then t:=f 1（x 1）;? 按照10式求出最優(yōu)指標 輸出 t;但是，實際應用當中經(jīng)常不顯式地按照上面步驟設計動態(tài)規(guī)劃， 而是按以下幾個 步驟進行：（1）分析最優(yōu)解的性質，并刻劃其結構特征。（2）遞歸地定義最優(yōu)值。（3）以自底向上的方式或自頂

21、向下的記憶化方法（備忘錄法）計算出最優(yōu)值。（4）根據(jù)計算最優(yōu)值時得到的信息，構造一個最優(yōu)解。步驟（1）（3）是動態(tài)規(guī)劃算法的基本步驟。在只需要求出最優(yōu)值的情形，步 驟（4）可以省略，若需要求出問題的一個最優(yōu)解，則必須執(zhí)行步驟（4）。此時，在步驟（ 3）中計算最優(yōu)值時，通常需記錄更多的信息，以便在步驟（ 4）中，根 據(jù)所記錄的信息，快速地構造出一個最優(yōu)解?？偨Y：動態(tài)規(guī)劃實際上就是最優(yōu)化的問題， 是指將原問題的大實例等價于同一最 優(yōu)化問題的較小實例， 自底向上的求解最小實例， 并將所求解存放起來， 存放的 結果就是為了準備數(shù)據(jù)。 與遞歸相比， 遞歸是不斷的調用子程序求解， 是自頂向 下的調用和求解

22、?；厮莘? 回溯法也稱為試探法， 該方法首先暫時放棄關于問題規(guī)模大小的限制， 并 將問題的候選解按某種順序逐一枚舉和檢驗。當發(fā)現(xiàn)當前候選解不可能是解時， 就選擇下一個候選解； 倘若當前候選解除了還不滿足問題規(guī)模要求外， 滿足所有 其他要求時， 繼續(xù)擴大當前候選解的規(guī)模， 并繼續(xù)試探。 如果當前候選解滿足包 括問題規(guī)模在內的所有要求時， 該候選解就是問題的一個解。 在回溯法中， 放棄 當前候選解， 尋找下一個候選解的過程稱為回溯。 擴大當前候選解的規(guī)模， 以繼 續(xù)試探的過程稱為向前試探。1、回溯法的一般描述可用回溯法求解的問題P,通常要能表達為：對于已知的由 n元組（X1, X2,， xj組成的

23、一個狀態(tài)空間 E= （X1, X2,，xjl Xi S , i=1 , 2,，n，給 定關于n元組中的一個分量的一個約束集 D,要求E中滿足D的全部約束條件的 所有n元組。其中S是分量Xi的定義域，且|Si|有限，i=1 , 2,，n。我們 稱E中滿足D的全部約束條件的任一 n元組為問題P的一個解。解問題P的最樸素的方法就是枚舉法，即對E中的所有n元組逐一地檢測其是否 滿足D的全部約束，若滿足，則為問題P的一個解。但顯然，其計算量是相當大 的。我們發(fā)現(xiàn)，對于許多問題，所給定的約束集D具有完備性，即i元組（X1, X2, Xi）滿足D中僅涉及到X1, X2,，Xi的所有約束意味著j （ji ）元

24、組（X1, X2, Xj） 定也滿足D中僅涉及到X1, X2,，Xj的所有約束，i=1 , 2,，n。換句 話說，只要存在OW j j。因 此，對于約束集D具有完備性的問題P, 旦檢測斷定某個j元組（Xi, X2,， Xj）違反D中僅涉及Xi, X2,，Xj的一個約束，就可以肯定，以（Xi, X2,， Xj）為前綴的任何n元組（Xi, X2,，Xj, Xj+i，Xn）都不會是問題P的解， 因而就不必去搜索它們、檢測它們。回溯法正是針對這類問題，利用這類問題的 上述性質而提出來的比枚舉法效率更高的算法?；厮莘ㄊ紫葘栴}P的n元組的狀態(tài)空間E表示成一棵高為n的帶權有序樹T, 把在E中求問題P的所有

25、解轉化為在T中搜索問題P的所有解。樹T類似于檢索 樹，它可以這樣構造：?設 S 中的元素可排成 Xi,Xi，Xi（mi-i） , |Si| =mi , i=i , 2,， n。從根開始，讓T的第I層的每一個結點都有m個兒子。這m個兒子到它們的 雙親的邊,按從左到右的次序,分別帶權 Xi+i（i） ,Xi+i（2） , , Xi+i（mi） ,i=0,i, 2,，n-i。照這種構造方式，E中的一個n元組（Xi, X2,，Xn）對應于T 中的一個葉子結點，T的根到這個葉子結點的路徑上依次的 n條邊的權分別為Xi, X2,，Xn,反之亦然。另外，對于任意的 Ow i n-i , E中n元組（Xi,

26、X2,， Xn）的一個前綴I元組（Xi, X2，Xi）對應于T中的一個非葉子結點，T的根 到這個非葉子結點的路徑上依次的I條邊的權分別為Xi, X2,，Xi，反之亦然。 特別，E中的任意一個n元組的空前綴（），對應于T的根。? ?因而，在E中尋找問題P的一個解等價于在T中搜索一個葉子結點，要求 從T的根到該葉子結點的路徑上依次的 n條邊相應帶的n個權Xi, X2,，Xn滿 足約束集D的全部約束。在T中搜索所要求的葉子結點，很自然的一種方式是從 根出發(fā)，按深度優(yōu)先的策略逐步深入，即依次搜索滿足約束條件的前綴 i 元組（xii）、前綴2元組（Xi, X2）、，前綴I元組（Xi, X2,，Xi）,，

27、直到i=n 為止。?在回溯法中，上述引入的樹被稱為問題 P的狀態(tài)空間樹；樹T上任意一個 結點被稱為問題P的狀態(tài)結點；樹T上的任意一個葉子結點被稱為問題 P的一個 解狀態(tài)結點；樹T上滿足約束集D的全部約束的任意一個葉子結點被稱為問題 P 的一個回答狀態(tài)結點，它對應于問題 P的一個解?！締栴}】 n 皇后問題問題描述：求出在一個nxn的棋盤上，放置n個不能互相捕捉的國際象 棋“皇后”的所有布局。這是來源于國際象棋的一個問題?；屎罂梢匝刂v橫和兩條斜線 4 個方向 相互捕捉。如圖所示，一個皇后放在棋盤的第 4 行第 3列位置上，則棋盤上凡打 “X”的位置上的皇后就能與這個皇后相互捕捉。i 23 4 5

28、 67 8XXXXXXXXXX QXXXXXXXXXXXXXxX從圖中可以得到以下啟示： 一個合適的解應是在每列、 每行上只有一個皇 后，且一條斜線上也只有一個皇后。求解過程從空配置開始。在第1列至第m列為合理配置的基礎上，再配置 第m+1列，直至第n列配置也是合理時，就找到了一個解。接著改變第n列配置， 希望獲得下一個解。另外，在任一列上，可能有 n 種配置。開始時配置在第 1 行，以后改變時，順次選擇第2行、第3行、直到第n行。當?shù)趎行配置也 找不到一個合理的配置時， 就要回溯， 去改變前一列的配置。 得到求解皇后問題 的算法如下：輸入棋盤大小值 n；m=0;good=1;do if (g

29、ood)if (m=n)輸出解；改變之，形成下一個候選解 ;else擴展當前候選接至下一列；else改變之，形成下一個候選解；good=檢查當前候選解的合理性； while (m!=0);在編寫程序之前， 先確定邊式棋盤的數(shù)據(jù)結構。 比較直觀的方法是采用一 個二維數(shù)組， 但仔細觀察就會發(fā)現(xiàn)， 這種表示方法給調整候選解及檢查其合理性 帶來困難。更好的方法乃是盡可能直接表示那些常用的信息。 對于本題來說，“常 用信息”并不是皇后的具體位置， 而是“一個皇后是否已經(jīng)在某行和某條斜線合 理地安置好了”。因在某一列上恰好放一個皇后，引入一個一維數(shù)組( col)，值coli表示在棋盤第i列、coli行有一

30、個皇后。例如：col3=4 ， 就表示在棋盤的第 3列、第 4行上有一個皇后。 另外，為了使程序在找完了全部 解后回溯到最初位置，設定 col0 的初值為 0 當回溯到第 0列時，說明程序已 求得全部解，結束程序運行。為使程序在檢查皇后配置的合理性方面簡易方便，引入以下三個工作 數(shù)組：(1)數(shù)組a ，ak表示第k行上還沒有皇后；( 2)數(shù)組 b ， bk 表示第 k 列右高左低斜線上沒有皇后；( 3)數(shù)組 c ， ck 表示第 k 列左高右低斜線上沒有皇后；棋盤中同一右高左低斜線上的方格， 他們的行號與列號之和相同； 同一左 高右低斜線上的方格，他們的行號與列號之差均相同。初始時，所有行和斜線

31、上均沒有皇后， 從第 1 列的第 1 行配置第一個皇后 開始，在第m列colm行放置了一個合理的皇后后，準備考察第 m+1列時，在 數(shù)組 a、b和c中為第m列，colm行的位置設定有皇后標志；當從第 m 列回溯到第 m-1 列，并準備調整第 m-1 列的皇后配置時，清除在數(shù)組 a、 b 和 c 中設置的關于第 m-1 列， colm-1 行有皇后的標志。一個皇后在m列，colm行方格內配置是合理的，由數(shù)組 a 、b和c 置的值都為 1 來確定。細節(jié)見以下程序：【程序】# include# include# define MAXN 20int n,m,good;int colMAXN+1,aMA

32、XN+1,b2*MAXN+1,c2*MAXN+1;void main() int j;char awn;printf( “Enter n:“); scanf(“%d”,&n);for (j=0;j=n;j+) aj=1;for (j=0;j=2*n;j+) cbj=cj=1;m=1; col1=1; good=1; col0=0;do if (good)if (m=n) printf(“列 t 行” );for (j=1;j=n;j+)printf( “%3dn”,j,colj);printf( “Entera character (Q/q” n”);scanf( “%c”,&awn);if

33、(awn= Q|awn= q) exit(0);while (colm=n) m-;acolm=bm+colm=cn+m-colm=1;colm+;else acolm=bm+colm=cn+m-colm=0;col+m=1;else while (colm=n) m-;acolm=bm+colm=cn+m-colm=1;colm+;good=acolm&bm+colm&cn+m-colm;對應位for while (m!=0);試探法找解算法也常常被編寫成遞歸函數(shù)，下面兩程序中的函數(shù) queen_all() 和函數(shù) queen_one() 能分別用來解皇后問題的全部解和一個解?！境绦颉? i

34、nclude# include# define MAXN 20int n;int colMAXN+1,aMAXN+1,b2*MAXN+1,c2*MAXN+1;void main() int j;printf( “Enter n:“); scanf( “%d”,&n);for (j=0;j=n;j+) aj=1;for (j=0;j=2*n;j+) cbj=cj=1;queen_all(1,n);void queen_all(int k,int n) int i,j;char awn;for (i=1;i=n;i+)if (ai&bk+i&cn+k-i) colk=i;ai=bk+i=cn+k-

35、i=0;if (k=n) printf(“列 t 行”);for (j=1;j=n;j+)printf( “%3dn”,j,colj);printf( “Entera character (Q/q for” n”);scanf( “%c”,&awn);if (awn= Q|awn= q) exit(0);queen_all(k+1,n);ai=bk+i=cn+k-i;采用遞歸方法找一個解與找全部解稍有不同， 在找一個解的算法中， 遞歸 算法要對當前候選解最終是否能成為解要有回答。 當它成為最終解時， 遞歸函數(shù) 就不再遞歸試探， 立即返回；若不能成為解，就得繼續(xù)試探。 設函數(shù) queen_one

36、() 返回 1 表示找到解，返回 0 表示當前候選解不能成為解。細節(jié)見以下函數(shù)?！境绦颉? define MAXN 20int n;int colMAXN+1,aMAXN+1,b2*MAXN+1,c2*MAXN+1;int queen_one(int k,int n) int i,found; i=found=0; While (!found&i i+;if (ai&bk+i&cn+k-i) colk=i; ai=bk+i=cn+k-i=0; if (k=n) return 1; else found=queen_one(k+1,n);ai=bk+i=cn+k-i=1; return foun

37、d; 分支定界法： 分支限界法： 這是一種用于求解組合優(yōu)化問題的排除非解的搜索算法。 類似于回溯法， 分枝定 界法在搜索解空間時， 也經(jīng)常使用樹形結構來組織解空間。 然而與回溯法不同的 是，回溯算法使用深度優(yōu)先方法搜索樹結構， 而分枝定界一般用寬度優(yōu)先或最小 耗費方法來搜索這些樹。 因此，可以很容易比較回溯法與分枝定界法的異同。 相 對而言，分枝定界算法的解空間比回溯法大得多， 因此當內存容量有限時， 回溯 法成功的可能性更大。算法思想：分枝定界( branch and bound )是另一種系統(tǒng)地搜索解空間的方法， 它與回溯法的主要區(qū)別在于對 E-節(jié)點的擴充方式。每個活節(jié)點有且僅有一次機 會

38、變成E-節(jié)點。當一個節(jié)點變?yōu)镋-節(jié)點時，則生成從該節(jié)點移動一步即可到達 的所有新節(jié)點。在生成的節(jié)點中，拋棄那些不可能導出(最優(yōu))可行解的節(jié)點， 其余節(jié)點加入活節(jié)點表，然后從表中選擇一個節(jié)點作為下一個E-節(jié)點。從活節(jié)點表中取出所選擇的節(jié)點并進行擴充， 直到找到解或活動表為空， 擴充過程才結 束。有兩種常用的方法可用來選擇下一個 E-節(jié)點(雖然也可能存在其他的方法)：1) 先進先出( F I F O ) 即從活節(jié)點表中取出節(jié)點的順序與加入節(jié)點的順序相 同，因此活節(jié)點表的性質與隊列相同。2) 最小耗費或最大收益法在這種模式中， 每個節(jié)點都有一個對應的耗費或收益。 如果查找一個具有最小耗費的解，則活節(jié)

39、點表可用最小堆來建立，下一個E-節(jié)點就是具有最小耗費的活節(jié)點；如果希望搜索一個具有最大收益的解， 則可用最大堆來構造活節(jié)點表， 下一個E-節(jié)點是具有最大收益的活節(jié)點 裝載問題 用一個隊列Q來存放活結點表，Q中 weight表示每個活結點所相應的當前載重量。當weight = 1時，表示隊 列已達到解空間樹同一層結點的尾 部。算法首先檢測當前擴展結點的左 兒子結點是否為可行結點。如果是則 將其加入到活結點隊列中。然后將其 右兒子結點加入到活結點隊列中 ( 右 兒子結點一定是可行結點 )。 2 個兒子 結點都產(chǎn)生后，當前擴展結點被舍棄?；罱Y點隊列中的隊首元素被取出 作為當前擴展結點，由于隊列中每一

40、 層結點之后都有一個尾部標記 -1 ，故 在取隊首元素時，活結點隊列一定不 空。當取出的元素是 -1 時，再判斷當 前隊列是否為空。如果隊列非空，則 將尾部標記 -1 加入活結點隊列，算法 開始處理下一層的活結點。 /* 該版本只算出最優(yōu)解 */ #include #include struct Queue int weight ; struct Queue* next ;int bestw = 0 ; / 目前的最優(yōu)值 Queue* Q; / 活結點隊列 Queue* lq = NULL ; Queue* fq = NULL ; int Add(int w) Queue* q ; q = (Queue*)malloc(sizeof(Queue) ; if(q =NULL)printf( 沒有足夠的空間分配 n) ;return 1