《算法設(shè)計(jì)與分析》歷年期末試題整理-含答案-

算法設(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）算法定義：算法是指在解決問題時，按照某種機(jī)械步驟一定可以得到問題結(jié)果的處理過程（ 3）算法的三要素1、操作2、控制結(jié)構(gòu)3、數(shù)據(jù)結(jié)構(gòu)算法具有以下 5 個屬性：有窮性：一個算法必須總是在執(zhí)行有窮步之后結(jié)束，且每一步都在有窮時間內(nèi)完成。確定性：算法中每一條指令必須有確切的含義。不存在二義性。只有一個入口和一個出口可行性：一個算法是可行的就是算法描述的操作是可以通過已經(jīng)實(shí)現(xiàn)的基本運(yùn)算執(zhí)行有限次來實(shí)現(xiàn)的。輸入：一個算法有零個或多個輸入，這些輸入取自于某個特定對象的集合。輸出：一個算法有一個或多個輸出，這些輸出同輸入有著某些特定關(guān)系的量。算法設(shè)計(jì)的質(zhì)量指標(biāo)：正確性：算法應(yīng)滿足具體問題的需求；可讀性：算法應(yīng)該好讀，以有利于讀者對程序的理解；健壯性：算法應(yīng)具有容錯處理，當(dāng)輸入為非法數(shù)據(jù)時，算法應(yīng)對其作出反應(yīng)，而不是產(chǎn)生莫名其妙的輸出結(jié)果。效率與存儲量需求：效率指的是算法執(zhí)行的時間；存儲量需求指算法執(zhí)行過程中所需要的最大存儲空間。一般這兩者與問題的規(guī)模有關(guān)。經(jīng)常采用的算法主要有迭代法、分而治之法、貪婪法、動態(tài)規(guī)劃法、回溯法、分支限界法迭代法 也稱“輾轉(zhuǎn)法”，是一種不斷用變量的舊值遞推出新值的解決問題的方法。利用迭代算法解決問題，需要做好以下三個方面的工作： 一、確定迭代模型。在可以用迭代算法解決的問題中，至少存在一個直接或間接地不斷由舊值遞推出新值的變量，這個變量就是迭代變量。二、 建立迭代關(guān)系式。所謂迭代關(guān)系式，指如何從變量的前一個值推出其下一個值的公式（或關(guān)系）。迭代關(guān)系式的建立是解決迭代問題的關(guān)鍵，通常可以使用遞推或倒推的方法來完成。三、 對迭代過程進(jìn)行控制。在什么時候結(jié)束迭代過程？這是編寫迭代程序必須考慮的問題。不能讓迭代過程無休止地重復(fù)執(zhí)行下去。迭代過程的控制通?？煞譃閮煞N情況：一種是所需的迭代次數(shù)是個確定的值，可以計(jì)算出來；另一種是所需的迭代次數(shù)無法確定。對于前一種情況，可以構(gòu)建一個固定次數(shù)的循環(huán)來實(shí)現(xiàn)對迭代過程的控制；對于后一種情況，需要進(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)（當(dāng) n>1 ）。寫成 函數(shù)有：intfib(int n) if (n=0) return 0;if(n=1) return 1;if (n>1) return fib(n-1)+fib(n-2);一個 養(yǎng) 引 一只 出生的新品種兔子， 種兔子從出生的下一個月開始，每月新生一只兔子，新生的兔子也如此繁殖。如果所有的兔子都不死去， 到第12 個月 ， 養(yǎng) 共有兔子多少只？分析： 是一個典型的 推 。我 不妨假 第1個月 兔子的只數(shù) u1 ，第 2個月 兔子的只數(shù) u 2，第 3個月 兔子的只數(shù) u 3，根據(jù) 意，“ 種兔子從出生的下一個月開始，每月新生一只兔子”， 有u 1 1， u 2 u 1 u 1 1 2， u 3 u 2 u 2 1 4 ，根據(jù) 個 律，可以 出下面的 推公式：u n u n 1 2 (n 2)對應(yīng) u n 和 u n 1 ，定 兩個迭代 量 y 和 x ，可將上面的 推公式 成如下迭代關(guān)系：y=x*2x=y 算機(jī) 個迭代關(guān)系重復(fù) 行 11 次，就可以算出第 12 個月 的兔子數(shù)。參考程序如下：clsx=1for i=2to 12y=x*2x=ynext iprint yend分而治之法1、分治法的基本思想任何一個可以用 算機(jī)求解的 所需的 算 都與其 模N 有關(guān)。 的 模越小，越容易直接求解，解 所需的 算 也越少。例如， 于n 個元素的排序 ，當(dāng)n=1 ，不需任何 算； n=2 ，只要作一次比 即可排好序； n=3 只要作 3 次比 即可，。而當(dāng) n 大 ， 就不那么容易 理了。要想直接解決一個 模 大的 ，有 是相當(dāng)困 的。分治法的 思想是，將一個 以直接解決的大 ，分割成一些 模 小的相同 ，以便各個 破，分而治之。分治法所能解決的問題一般具有以下幾個特征：（ 1）該問題的規(guī)?？s小到一定的程度就可以容易地解決； （2）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)；（ 3） 利用該問題分解出的子問題的解可以合并為該問題的解；（ 4） 該問題所分解出的各個子問題是相互獨(dú)立的，即子問題之間不包含公共的子子問題。3 、分治法的基本步驟分治法在每一層遞歸上都有三個步驟：（ 1） 分解：將原問題分解為若干個規(guī)模較小，相互獨(dú)立，與原問題形式相同的子問題；（ 2） 解決：若子問題規(guī)模較小而容易被解決則直接解，否則遞歸地解各個子問題；（ 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 中的元素可以獨(dú)立排序，并且不必對l e f t 和 r i g h t 的排序結(jié)果進(jìn)行合并。 m i d d l e 中的元素被稱為支點(diǎn)( p i v o t ) 。圖1 4 - 9 中給出了快速排序的偽代碼。/ /使用快速排序方法對a 0 :n- 1 排序從 a 0 :n- 1 中選擇一個元素作為m i d d l e ，該元素為支點(diǎn)把余下的元素分割為兩段left 和 r i g h t ，使得l e f t 中的元素都小于等于支點(diǎn)，而right中的元素都大于等于支點(diǎn)遞歸地使用快速排序方法對left 進(jìn)行排序遞歸地使用快速排序方法對right 進(jìn)行排序所得結(jié)果為l e f 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 le； 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 , 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<class T>void QuickSort(T*a, int n)/ 對 a0:n-1 進(jìn)行快速排序 / 要求 an 必需有最大關(guān)鍵值void quickSort(T a, int l, int r)/ 排序 a l : r ， ar+1 有大值if (l >= r) return;int i = l, / 從左至右的游標(biāo)j = r+ 1; / 從右到左的游標(biāo) T pivot = al;/ 把左側(cè) >= pivot 的元素與右側(cè) <=quickSort(a, 0, n-1);pivot 的元素進(jìn)行交換while (true) template<class T>do / 在左側(cè)尋找 >= pivot 的元素i = i + 1; while (a < pivot);do / 在右側(cè)尋找 <= pivot 的元素Swap(a, aj);/ 設(shè)置p i v o tal= aj;j = j - 1; while (aj > pivot); if (i >= j) break; / 未發(fā)現(xiàn)交換對象aj = pivot;quickSort(a, l, j-1); /對左段排序quickSort(a, j+1, r); /對右段排序貪婪法它采用逐步構(gòu)造最優(yōu)解的思想，在問題求解的每一個階段，都作出一個在一定標(biāo)準(zhǔn)下看上去最優(yōu)的決策；決策一旦作出，就不可再更改。制定決策的依據(jù)稱為貪婪準(zhǔn)則。貪婪法是一種不追求最優(yōu)解，只希望得到較為滿意解的方法。貪婪法一般可以快速得到滿意的解，因?yàn)樗∪チ藶檎易顑?yōu)解要窮盡所有可能而必須耗費(fèi)的大量時間。貪婪法常以當(dāng)前情況為基礎(chǔ)作最優(yōu)選擇，而不考慮各種可能的整體情況，所以貪婪法不要回溯?！締栴}】背包問題問題描述：有不同價值、不同重量的物品n 件，求從這n 件物品中選取一部分物品的選擇方案，使選中物品的總重量不超過指定的限制重量，但選中物品的價值之和最大。#include<stdio.h> voidmain()intm,n,i,j,w50,p50,pl50,b50,s=0,max;printf(" 輸入背包容量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;s=s+wi;if(s<=m)printf("whole choosen");/return;for(i=1;i<=n;i=i+1)max=1;for(j=2;j<=n;j=j+1)if(plj/wj>plmax/wmax)max=j;plmax=0;bi=max;for(i=1,s=0;s<m && 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("choose weight %dn",wbj); 動態(tài)規(guī)劃的基本思想前文主要介紹了動態(tài)規(guī)劃的一些理論依據(jù)，我們將前文所說的具有明顯的階段劃分和狀態(tài)轉(zhuǎn)移方程的動態(tài)規(guī)劃稱為標(biāo)準(zhǔn)動態(tài)規(guī)劃，這種標(biāo)準(zhǔn)動態(tài)規(guī)劃是在研究多階段決策問題時推導(dǎo)出來的，具有嚴(yán)格的數(shù)學(xué)形式，適合用于理論上的分析。在實(shí)際應(yīng)用中，許多問題的階段劃分并不明顯，這時如果刻意地劃分階段法反而麻煩。一般來說，只要該問題可以劃分成規(guī)模更小的子問題，并且原問題的最優(yōu)解中包含了子問題的最優(yōu)解（即滿足最優(yōu)子化原理），則可以考慮用動態(tài)規(guī)劃解決。動態(tài)規(guī)劃的實(shí)質(zhì)是分治思想和解決冗余，因此，動態(tài)規(guī)劃是一種將問題實(shí)例分解為更小的、相似的子問題，并存儲子問題的解而避免計(jì)算重復(fù)的子問題，以解決最優(yōu)化問題的算法策略。由此可知，動態(tài)規(guī)劃法與分治法和貪心法類似，它們都是將問題實(shí)例歸納為更小的、相似的子問題，并通過求解子問題產(chǎn)生一個全局最優(yōu)解。貪心法的當(dāng)前選擇可能要依賴已經(jīng)作出的所有選擇，但不依賴于有待于做出的選擇和子問題。因此貪心法自頂向下，一步一步地作出貪心選擇；而分治法中的各個子問題是獨(dú)立的（即不包含公共的子問題），因此一旦遞歸地求出各子問題的解后，便可自下而上地將子問題的解合并成問題的解。不足之處：如果當(dāng)前選擇可能要依賴子問題的解時，則難以通過局部的貪心策略達(dá)到全局最優(yōu)解；如果各子問題是不獨(dú)立的，則分治法要做許多不必要的工作，重復(fù)地解公共的子問題。解決上述問題的辦法是利用動態(tài)規(guī)劃。該方法主要應(yīng)用于最優(yōu)化問題，這類問題會有多種可能的解，每個解都有一個值，而動態(tài)規(guī)劃找出其中最優(yōu)（最大或最小）值的解。若存在若干個取最優(yōu)值的解的話，它只取其中的一個。在求解過程中，該方法也是通過求解局部子問題的解達(dá)到全局最優(yōu)解，但與分治法和貪心法不同的是，動態(tài)規(guī)劃允許這些子問題不獨(dú)立，（亦即各子問題可包含公共的子問題）也允許其通過自身子問題的解作出選擇，該方法對每一個子問題只解一次，并將結(jié)果保存起來，避免每次碰到時都要重復(fù)計(jì)算。因此，動態(tài)規(guī)劃法所針對的問題有一個顯著的特征，即它所對應(yīng)的子問題樹中的子問題呈現(xiàn)大量的重復(fù)。動態(tài)規(guī)劃法的關(guān)鍵就在于，對于重復(fù)出現(xiàn)的子問題，只在第一次遇到時加以求解，并把答案保存起來，讓以后再遇到時直接引用，不必重新求解。3、動態(tài)規(guī)劃算法的基本步驟設(shè)計(jì)一個標(biāo)準(zhǔn)的動態(tài)規(guī)劃算法，通?？砂匆韵聨讉€步驟進(jìn)行：（ 1）劃分階段：按照問題的時間或空間特征，把問題分為若干個階段。注意這若干個階段一定要是有序的或者是可排序的（即無后向性），否則問題就無法用動態(tài)規(guī)劃求解。（ 2）選擇狀態(tài)：將問題發(fā)展到各個階段時所處于的各種客觀情況用不同的狀態(tài)表示出來。當(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ī)劃方程（包括邊界條件）：動態(tài)規(guī)劃的基本方程是規(guī)劃方程的通用形式化表達(dá)式。一般說來，只要階段、狀態(tài)、決策和狀態(tài)轉(zhuǎn)移確定了，這一步還是比較簡單的。動態(tài)規(guī)劃的主要難點(diǎn)在于理論上的設(shè)計(jì)，一旦設(shè)計(jì)完成，實(shí)現(xiàn)部分就會非常簡單。根據(jù)動態(tài)規(guī)劃的基本方程可以直接遞歸計(jì)算最優(yōu)值，但是一般將其改為遞推計(jì)算，實(shí)現(xiàn)的大體上的框架如下：標(biāo)準(zhǔn)動態(tài)規(guī)劃的基本框架1. 對 f n+1(xn+1 )初始化 ; 邊界條件 for k:=n downto 1 do for 每一個 xk X kdo for 每一個 ukU k(xk) do beginf 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 k)的最優(yōu)值 end;t:= 一個極 ; 或 for每一個 x1X 1 doif f 1(x 1)比 t 更 then t:=f 1(x1); 按照 10 式求出最 指 出t;但是， 用當(dāng)中 常不 式地按照上面步 劃，而是按以下幾個步 行：（ 1）分析最 解的性 ，并刻劃其 構(gòu)特征。（ 2） 地定 最 。（ 3）以自底向上的方式或自 向下的 化方法（ 忘 法） 算出最 。（ 4）根據(jù) 算最 得到的信息，構(gòu)造一個最 解。步 （ 1）（ 3）是 劃算法的基本步 。在只需要求出最 的情形，步 （ 4）可以省略，若需要求出 的一個最 解， 必 行步 （ 4）。此 ，在步 （ 3）中 算最 ，通常需 更多的信息，以便在步 （ 4）中，根據(jù)所 的信息，快速地構(gòu)造出一個最 解。 ： 劃 上就是最 化的 ，是指將原 的大 例等價于同一最 化 的 小 例，自底向上的求解最小 例，并將所求解存放起來，存放的 果就是 了準(zhǔn) 數(shù)據(jù)。與 相比， 是不斷的 用子程序求解，是自 向下的 用和求解?；厮莘ɑ厮莘ㄒ卜Q 探法， 方法首先 放棄關(guān)于 模大小的限制，并將 的候 解按某種 序逐一枚 和 。當(dāng) 當(dāng)前候 解不可能是解 ，就 下一個候 解；倘若當(dāng)前候 解除了 不 足 模要求外， 足所有其他要求 ， 大當(dāng)前候 解的 模，并 探。如果當(dāng)前候 解 足包括 模在內(nèi)的所有要求 ， 候 解就是 的一個解。在回溯法中，放棄當(dāng)前候 解， 找下一個候 解的 程稱 回溯。 大當(dāng)前候 解的 模，以 探的 程稱 向前 探。1、回溯法的一般描述可用回溯法求解的 P，通常要能表達(dá) ： 于已知的由n 元 （ x1， x2， xn） 成的一個狀 空 E= （ x1， x2， xn） xi Si ， i=1 ， 2， n ， 定關(guān)于n 元 中的一個分量的一個 束集D ，要求 E 中 足 D 的全部 束條件的所有n 元 。其中 Si是分量xi 的定 域，且|Si | 有限， i=1 ， 2， n。我 稱 E 中 足 D 的全部 束條件的任一n 元組為問題 P 的一個解。解 P 的最樸素的方法就是枚 法，即 E 中的所有n 元 逐一地 其是否 足D的全部 束，若 足， P 的一個解。但 然，其 算量是相當(dāng)大的。我 ， 于 多 ，所 定的 束集D 具有完 性，即i 元 （ x1，x2， xi） 足 D 中 涉及到 x1， x2， xi 的所有 束意味著j （j<i ）元 （ x1， x2， xj ）一定也 足D 中 涉及到 x ， x ， x的所有 束， i=1 ， 2， n。 句 ，只要存在0 j n-12j1，使得（ x ， x ， x） 反 D 中 涉及到 x ， x ， x的 束之一， 以（ x ，12j12j1x ，x） 前 的任何 n 元 （ x， x， x， xj+1， x ）一定也 反D 中 涉及2j12jn到 x1， x2， xi 的一個 束， n i>j 。因此， 于 束集D 具有完 性的 P，一旦 斷定某個 j 元 （ x1， x2， xj） 反 D 中 涉及 x1，x2， xj 的一個 束，就可以肯定，以（ x1， x2， xj） 前 的任何n 元 （ x1 ，x2， xj，xj+1 ， xn）都不會是問題 P 的解，因而就不必去搜索它 、 它 。回溯法正是 ，利用 的上述性 而提出來的比枚 法效率更高的算法?；厮莘ㄊ紫葘?P 的 n 元 的狀 空 E 表示成一棵高 n 的 有序 T，把在 E中求 P 的所有解 化 在T 中搜索 P 的所有解。 T 似于 索 ，它可以 構(gòu)造：設(shè) Si 中的元素可排成xi(1) ， xi(2) ， xi(mi-1) ， |Si| =m i， i=1 ， 2， n。從根開始， T的第 I 的每一個 點(diǎn)都有mi個兒子。 mi 個兒子到它 的雙 的 ，按從左到右的次序，分 xi+1(1) ，xi+1(2)， xi+1(mi)， i=0 ， 1，2， n-1。照 種構(gòu)造方式， E 中的一個 n 元 （ x1， x2， xn） 于 T 中的一個葉子 點(diǎn)，T 的根到 個葉子 點(diǎn)的路徑上依次的 n 條 的 分 x1，x2， xn，反之亦然。另外， 于任意的0 i n-1， E中 n 元 （ x1， x2， xn）的一個前 I 元 （ x1，x2 ， xi） 于 T 中的一個非葉子 點(diǎn)， T 的根到 個非葉子 點(diǎn)的路徑上依次的I 條 的 分 x1， x2， xi，反之亦然。特 ，E 中的任意一個n 元 的空前 （）， 于T 的根。因而，在 E 中 找 P 的一個解等價于在T 中搜索一個葉子 點(diǎn)，要求從T 的根到 葉子 點(diǎn)的路徑上依次的n 條 相 的n 個 x1， x2， xn 足 束集 D 的全部 束。在 T 中搜索所要求的葉子 點(diǎn)，很自然的一種方式是從根出 ，按深度 先的策略逐步深入，即依次搜索 足 束條件的前 1 元 （ x1i ）、前 2 元 （ x1，x2）、，前 I 元 （ x1， x2， xi），直到 i=n 止。在回溯法中，上述引入的 被稱 P 的狀 空 ； T 上任意一個 點(diǎn)被稱 問題P 的狀 點(diǎn)； T 上的任意一個葉子 點(diǎn)被稱 P 的一個解狀 點(diǎn)； T上 足 束集D 的全部 束的任意一個葉子 點(diǎn)被稱 P 的一個回答狀 點(diǎn)，它 于 P 的一個解?！?】n 皇后 描述：求出在一個n n 的棋 上，放置n 個不能互相捕捉的國 象棋“皇后”的所有布局。 是來源于國 象棋的一個 ?；屎罂梢匝刂?橫和兩條斜 4 個方向相互捕捉。如 所示，一個皇后放在棋 的第 4 行第 3 列位置上， 棋 上凡打“”的位置上的皇后就能與 個皇后相互捕捉。12345678 Q 從 中可以得到以下啟示：一個合適的解 是在每列、每行上只有一個皇后，且一條斜 上也只有一個皇后。求解 程從空配置開始。在第1 列至第m 列 合理配置的基 上，再配置第m+1 列，直至第n 列配置也是合理 ，就找到了一個解。接著改 第n 列配置，希望 得下一個解。另外，在任一列上，可能有n 種配置。開始 配置在第1 行，以后改 ， 次 第2行、第3 行、直到第n 行。當(dāng)?shù)趎 行配置也找不到一個合理的配置 ，就要回溯，去改 前一列的配置。得到求解皇后 的算法如下： 入棋 大小 n；m=0;good=1;if (good)doif(m=n) 出解；改 之，形成下一個候 解;else 展當(dāng)前候 接至下一列； else 改 之，形成下一個候 解；good= 當(dāng)前候 解的合理性； while (m!=0);在 寫程序之前，先確定 式棋 的數(shù)據(jù) 構(gòu)。比 直 的方法是采用一個二 數(shù) ，但仔 察就會 ， 種表示方法 整候 解及 其合理性 來困 。更好的方法乃是盡可能直接表示那些常用的信息。 于本 來 ，“常用信息”并不是皇后的具體位置，而是“一個皇后是否已 在某行和某條斜 合理地安置好了”。因在某一列上恰好放一個皇后，引入一個一 數(shù) （col ）， coli 表示在棋 第i 列、 coli 行有一個皇后。例如：col3=4 ，就表示在棋 的第 3 列、第 4 行上有一個皇后。另外， 了使程序在找完了全部解后回溯到最初位置， 定 col0 的初 0 當(dāng)回溯到第 0 列 ， 明程序已求得全部解， 束程序運(yùn)行。 使程序在 皇后配置的合理性方面 易方便，引入以下三個工作數(shù) ：（ 1）數(shù) a ， ak 表示第 k 行上 沒有皇后；（ 2）數(shù) b ， bk 表示第 k 列右高左低斜 上沒有皇后；（3）數(shù) c ， ck 表示第 k 列左高右低斜 上沒有皇后；棋 中同一右高左低斜 上的方格，他 的行號與列號之和相同；同一左高右低斜 上的方格，他 的行號與列號之差均相同。初始時，所有行和斜線上均沒有皇后，從第1 列的第1 行配置第一個皇后開始，在第m 列colm 行放置了一個合理的皇后后，準(zhǔn)備考察第m+1列時，在數(shù)組a、 b 和c 中為第m 列， colm 行的位置設(shè)定有皇后標(biāo)志；當(dāng)從第m 列回溯到第m-1列，并準(zhǔn)備調(diào)整第m-1列的皇后配置時，清除在數(shù)組a 、 b 和c 中設(shè)置的關(guān)于第m-1列， colm-1行有皇后的標(biāo)志。一個皇后在m 列，colm 行方格內(nèi)配置是合理的，由數(shù)組a 、 b 和c 對應(yīng)位置的值都為1 來確定。細(xì)節(jié)見以下程序：【程序】# include# include# defineMAXN20n,m,good;intint colMAXN+1,aMAXN+1,b2*MAXN+1,c2*MAXN+1;voidmain()int j;charawn;printf(“ Entern:“ );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(“ Enter a character (Q/qn” );scanf(“ %c” ,&awn);if (awn= Q |awn= q )exit(0);while (colm=n) m-;acolm=bm+colm=cn+m-colm=1;colm+;elseacolm=bm+colm=cn+m-colm=0;col+m=1;elsewhile (colm=n)m-;acolm=bm+colm=cn+m-colm=1;colm+;good=acolm&&bm+colm&&cn+m-colm; while (m!=0);試探法找解算法也常常被編寫成遞歸函數(shù)，下面兩程序中的函數(shù)queen_all() 和函數(shù)queen_one()能分別用來解皇后問題的全部解和一個解?！境绦颉? include# include# define MAXN 20 int 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-i=0;if (k=n)printf( “列 t 行” );for (j=1;j<=n;j+)printf(“ %3d n” ,j,colj);printf(“ Enter a character (Q/qn” );scanf(“ %c” ,&awn);if (awn= Q |awn= q )exit(0);queen_all(k+1,n);ai=bk+i=cn+k-i;采用遞歸方法找一個解與找全部解稍有不同，在找一個解的算法中，遞歸算法要對當(dāng)前候選解最終是否能成為解要有回答。當(dāng)它成為最終解時，遞歸函數(shù)就不再遞歸試探，立即返回；若不能成為解，就得繼續(xù)試探。設(shè)函數(shù)queen_one()返回1 表示找到解，返回0 表示當(dāng)前候選解不能成為解。細(xì)節(jié)見以下函數(shù)。【程序】# defineMAXN20int n;intcolMAXN+1,aMAXN+1,b2*MAXN+1,c2*MAXN+1;intqueen_one(int k,int n)int i,found;i=found=0;While (!found&&ii+;if (ai&&bk+i&&cn+k-i)colk=i;ai=bk+i=cn+k-i=0;if (k=n)return 1;elsefound=queen_one(k+1,n);ai=bk+i=cn+k-i=1;returnfound;分支定界法：分支限界法：這是一種用于求解組合優(yōu)化問題的排除非解的搜索算法。類似于回溯法，分枝定界法在搜索解空間時，也經(jīng)常使用樹形結(jié)構(gòu)來組織解空間。然而與回溯法不同的是，回溯算法使用深度優(yōu)先方法搜索樹結(jié)構(gòu)，而分枝定界一般用寬度優(yōu)先或最小耗費(fèi)方法來搜索這些樹。因此，可以很容易比較回溯法與分枝定界法的異同。相對而言，分枝定界算法的解空間比回溯法大得多，因此當(dāng)內(nèi)存容量有限時，回溯法成功的可能性更大。算法思想：分枝定界（branch and bound）是另一種系統(tǒng)地搜索解空間的方法，它與回溯法的主要區(qū)別在于對 E-節(jié)點(diǎn)的擴(kuò)充方式。每個活節(jié)點(diǎn)有且僅有一次機(jī)會變成 E-節(jié)點(diǎn)。當(dāng)一個節(jié)點(diǎn)變?yōu)?E-節(jié)點(diǎn)時，則生成從該節(jié)點(diǎn)移動一步即可到達(dá)的所有新節(jié)點(diǎn)。在生成的節(jié)點(diǎn)中，拋棄那些不可能導(dǎo)出（最優(yōu)）可行解的節(jié)點(diǎn)，其余節(jié)點(diǎn)加入活節(jié)點(diǎn)表，然后從表中選擇一個節(jié)點(diǎn)作為下一個 E-節(jié)點(diǎn)。從活節(jié)點(diǎn)表中取出所選擇的節(jié)點(diǎn)并進(jìn)行擴(kuò)充，直到找到解或活動表為空，擴(kuò)充過程才結(jié)束。有兩種常用的方法可用來選擇下一個E-節(jié)點(diǎn)（雖然也可能存在其他的方法）：1) 先進(jìn)先出（ F I F O ） 即從活節(jié)點(diǎn)表中取出節(jié)點(diǎn)的順序與加入節(jié)點(diǎn)的順序相同，因此活 節(jié)點(diǎn)表的性質(zhì)與隊(duì)列相同。2) 最小耗費(fèi)或最大收益法在這種模式中，每個節(jié)點(diǎn)都有一個對應(yīng)的耗費(fèi)或收益。如果查找一個具有最小耗費(fèi)的解，則活節(jié)點(diǎn)表可用最小堆來建立，下一個E-節(jié)點(diǎn)就是具有最小耗費(fèi) 的活節(jié)點(diǎn)；如果希望搜索一個具有最大收益的解，則可用最大堆來構(gòu)造活節(jié)點(diǎn)表，下一個E-節(jié)點(diǎn)是具有最大收益的活節(jié)點(diǎn) 裝載問題用一 個隊(duì)列 Q 來存放活結(jié) 點(diǎn)表， Q 中 weight 表示每個活結(jié)點(diǎn)所相應(yīng)的當(dāng)前載重量。當(dāng)weight 1 時，表示隊(duì)列已達(dá)到解空間樹同一層結(jié)點(diǎn)的尾部。算法首先檢測當(dāng)前擴(kuò)展結(jié)點(diǎn)的左兒子結(jié)點(diǎn)是否為可行結(jié)點(diǎn)。如果是則將其加入到活結(jié)點(diǎn)隊(duì)列中。然后將其右兒子結(jié)點(diǎn)加入到活結(jié)點(diǎn)隊(duì)列中 (右兒子結(jié)點(diǎn)一定是可行結(jié)點(diǎn) )。 2 個兒子結(jié)點(diǎn)都產(chǎn)生后，當(dāng)前擴(kuò)展結(jié)點(diǎn)被舍棄?；罱Y(jié)點(diǎn)隊(duì)列中的隊(duì)首元素被取出作為當(dāng)前擴(kuò)展結(jié)點(diǎn)，由于隊(duì)列中每一層結(jié)點(diǎn)之后都有一個尾部標(biāo)記-1 ，故在取隊(duì)首元素時，活結(jié)點(diǎn)隊(duì)列一定不空。當(dāng)取出的元素是 -1 時，再判斷當(dāng)前隊(duì)列是否為空。如果隊(duì)列非空，則將尾部標(biāo)記-1 加入活結(jié)點(diǎn)隊(duì)列，算法開始處理下一層的活結(jié)點(diǎn)。/* 該版本只算出最優(yōu)解*/#include<stdio.h>#include<malloc.h>struct Queue intweight ;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") ; return 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 ; intIsEmpty()if(Q->next=NULL)return 1 ; return0 ; intDelete(int&w) 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ì)列Qif (i = n) /葉 子if(wt>bestw)bestw = wt;elseAdd(wt); / 不是葉子if (IsEmpty()return bestw;if(i<n)Add(-1); /同層結(jié)點(diǎn)的尾部Delete(Ew); / 取下一擴(kuò)展結(jié)點(diǎn)i+; / 進(jìn)入下一層 int main() int n =0 ;int c = 0 ; int i = 0 ; int* w ;FILE *in , *out ; in =fopen("input.txt" , "r") ;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" , &wi) ; MaxLoading(w , c , int MaxLoading(int 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 + wi <= c) / xi = 1EnQueue(Ew + wi, bestw , i, n);/ 右孩子總是可行的EnQueue(Ew, bestw, i, n); / xi = 0 Delete(Ew); / 取下一個擴(kuò)展結(jié)點(diǎn) if (Ew = -1) / 到達(dá)層的尾部n) ; fprintf(out , "%dn" , bestw) ; return 0 ;