算法(Algorithm)是一系列解決問題的清晰指令，也就是說，能

夠?qū)σ欢ㄒ?guī)范的輸入，在有限時間內(nèi)獲得所要求的輸出。如果一個算

法有缺陷，或不適合于某個問題，執(zhí)行這個算法將不會解決這個問題。

不同的算法可能用不同的時間、空間或效率來完成同樣的任務(wù)。一個

算法的優(yōu)劣可以用空間復(fù)雜度與時間復(fù)雜度來衡量。

算法可以理解為有基本運算及規(guī)定的運算順序所構(gòu)成的完整

的解題步驟。或者看成按照要求設(shè)計好的有限的確切的計算序列，并

且這樣的步驟和序列可以解決一類問題。

一個算法應(yīng)該具有以下五個重要的特征：

1、有窮性：一個算法必須保證執(zhí)行有限步之后結(jié)束；

2、確切性：算法的每一步驟必須有確切的定義；

3、輸入：一個算法有0個或多個輸入，以刻畫運算對象的初

始情況，所謂0個輸入是指算法本身定除了初始條件；

4、輸出：一個算法有一個或多個輸出，以反映對輸入數(shù)據(jù)加

工后的結(jié)果。沒有輸出的算法是毫無意義的；

5、可行性：算法原則上能夠精確地運行，而且人們用筆和

紙做有限次運算后即可完成。

計算機科學(xué)家尼克勞斯-沃思曾著過一本著名的書《數(shù)據(jù)結(jié)構(gòu)十

算法二程序》，可見算法在計算機科學(xué)界與計算機應(yīng)用界的地位。

常見的五種算法：

分治算法

在計算機科學(xué)中，分治法是一種很重要的算法。字面上的解釋

是“分而治之”，就是把一個復(fù)雜的問題分成兩個或更多的相同或相

似的子問題，再把子問題分成更小的子問題……直到最后子問題可以

簡單的直接求解，原問題的解即子問題的解的合并。這個技巧是很多

高效算法的基礎(chǔ)，如排序算法（快速排序，歸并排序），傅立葉變換（快

速傅立葉變換）……

任何一個可以用計算機求解的問題所需的計算時間都與其規(guī)

模有關(guān)。問題的規(guī)模越小，越容易直接求解，解題所需的計算時間也

越少。例如，對于二個元素的排序問題，當(dāng)n3時，不需任何計算。

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

而當(dāng)n較大時，問題就不那么容易處理了。要想直接解決一個規(guī)模較

大的問題，有時是相當(dāng)困難的。

分治法的設(shè)計思想是，將一個難以直接解決的大問題，分割

成一些規(guī)模較小的相同問題，以便各個擊破，分而治之。

分治策略是：對于一個規(guī)模為n的問題，若該問題可以容易

地解決（比如說規(guī)模n較?。﹦t直接解決，否則將其分解為k個規(guī)模

較小的子問題，這些子問題互相獨立且與原問題形式相同，遞歸地解

這些子問題，然后將各子問題的解合并得到原問題的解。這種算法設(shè)

計策略叫做分治法。

如果原問題可分割成k個子問題，,且這些子問題都

可解并可利用這些子問題的解求出原問題的解，那么這種分治法就是

可行的。由分治法產(chǎn)生的子問題往往是原問題的較小模式，這就為使

用遞歸技術(shù)提供了方便。在這種情況下，反復(fù)應(yīng)用分治手段，可以使

子問題與原問題類型一致而其規(guī)模卻不斷縮小，最終使子問題縮小到

很容易直接求出其解。這自然導(dǎo)致遞歸過程的產(chǎn)生。分治與遞歸像一

對李生兄弟，經(jīng)常同時應(yīng)用在算法設(shè)計之中，并由此產(chǎn)生許多高效算

法。

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

1）該問題的規(guī)?？s小到一定的程度就可以容易地解決

2）該問題可以分解為若干個規(guī)模較小的相同問題，即該問題

具有最優(yōu)子結(jié)構(gòu)性質(zhì)。

3）利用該問題分解出的子問題的解可以合并為該問題的解;

4）該問題所分解出的各個子問題是相互獨立的，即子問題之

間不包含公共的子子問題。

上述的第一條特征是絕大多數(shù)問題都可以滿足的，因為問題

的計算復(fù)雜性一般是隨著問題規(guī)模的增加而增加；第二條特征是應(yīng)用

分治法的前提它也是大多數(shù)問題可以滿足的，此特征反映了遞歸思想

的應(yīng)用；第三條特征是關(guān)鍵，能否利用分治法完全取決于問題是否具

有第三條特征，如果具備了第一條和第二條特征，而不具備第三條特

征，則可以考慮用貪心法或動態(tài)規(guī)劃法。第四條特征涉及到分治法的

效率，如果各子問題是不獨立的則分治法要做許多不必要的工作，重

復(fù)地解公共的子問題，此時雖然可用分治法，但一般用動態(tài)規(guī)劃法較

好。

分治法的基本步驟

分治法在每一層遞歸上都有三個步驟：

分解：將原問題分解為若干個規(guī)模較小，相互獨立，與原問

題形式相同的子問題；

解決：若子問題規(guī)模較小而容易被解決則直接解，否則遞歸

地解各個子問題

合并：將各個子問題的解合并為原問題的解。

它的一般的算法設(shè)計模式如下:

Divide-and-Conquer(P)

1.if|P|WnO

2.thenreturn(ADHOC(P))

3.將P分解為較小的子問題Pl,P2,...,Pk

4.fori+1tok

5.doyi-Divide-and-Conquer(Pi)△遞歸解決Pi

6.T-MERGE(yl,y2,...,yk)△合并子問題

7.return(T)

其中M表示問題P的規(guī)模；nO為一閾值，表示當(dāng)問題P的

規(guī)模不超過nO時，問題已容易直接解出，不必再繼續(xù)分解。ADHOC(P)

是該分治法中的基本子算法，用于直接解小規(guī)模的問題P。因此，當(dāng)

P的規(guī)模不超過nO時直接用算法ADHOC(P)求解。算法

MERGE(yl,y2,...,yk)是該分治法中的合并子算法，用于將P的子問

題Pl,P2,...,Pk的相應(yīng)的解yl,y2,...,yk合并為P的解。

分治法的復(fù)雜性分析

一個分治法將規(guī)模為n的問題分成k個規(guī)模為n/m的子問題

去解。設(shè)分解閥值nO=l,且adhoc解規(guī)模為1的問題耗費1個單位

時間。再設(shè)將原問題分解為k個子問題以及用merge將k個子問題的

解合并為原問題的解需用f(n)個單位時間。用T(n)表示該分治法解

規(guī)模為|P|二n的問題所需的計算時間，則有：

。⑴n=1

T(n)-*

kT(n/m)+f(n)n>1

通過迭代法求得方程的解：

六。

遞歸方程及其解只給出I】等于川的方暴時T(n)的值，但是如

果認為T(n)足夠平滑，那么由n等于m的方幕時T(n)的值可以估計

T(n)的增長速度。通常假定T(n)是單調(diào)上升的，從而當(dāng)miWn<mi+1

時，T(mi)^T(n)<T(mi+l)o

二.動態(tài)規(guī)劃算法

最優(yōu)化原理

1951年美國數(shù)學(xué)家R.Bellman等人，根據(jù)一類多階段問題

的特點，把多階段決策問題變換為一系列互相聯(lián)系的單階段問題，然

后逐個加以解決。一些靜態(tài)模型，只要人為地引進“時間”因素，分

成時段，就可以轉(zhuǎn)化成多階段的動態(tài)模型，用動態(tài)規(guī)劃方法去處理。

與此同時，他提出了解決這類問題的“最優(yōu)化原理"(Principleof

optimality)：

“一個過程的最優(yōu)決策具有這樣的性質(zhì)：即無論其初始狀態(tài)

和初始決策如何，其今后諸策略對以第一個決策所形成的狀態(tài)作為初

始狀態(tài)的過程而言，必須構(gòu)成最優(yōu)策略”C簡言之，一個最優(yōu)策略的

子策略，對于它的初態(tài)和終態(tài)而言也必是最優(yōu)的。

這個“最優(yōu)化原理”如果用數(shù)學(xué)化一點的語言來描述的話，

就是:假設(shè)為了解決某一?優(yōu)化問題,需要依次作出n個決策DLD2,…,

Dn,如若這個決策序列是最優(yōu)的，對于任何一個整數(shù)k,1<k<n,

不論前面k個決策是怎樣的，以后的最優(yōu)決策只取決于由前面決策所

確定的當(dāng)前狀態(tài)，即以后的決策Dk+1,Dk+2,…，Dn也是最優(yōu)的。

最優(yōu)化原理是動態(tài)規(guī)劃的基礎(chǔ)。任何一個問題，如果失去了

這個最優(yōu)化原理的支持，就不可能用動態(tài)規(guī)劃方法計算。能采用動態(tài)

規(guī)劃求解的問題都需要滿足一定的條件：

(1)問題中的狀態(tài)必須滿足最優(yōu)化原理；

(2)問題中的狀態(tài)必須滿足無后效性。

所謂的無后效性是指：“下一時刻的狀態(tài)只與當(dāng)前狀態(tài)有關(guān),

而和當(dāng)前狀態(tài)之前的狀態(tài)無關(guān)，當(dāng)前的狀態(tài)是對以往決策的總結(jié)”。

問題求解模式

動態(tài)規(guī)劃所處理的問題是一個多階段決策問題，一般由初始

狀態(tài)開始，通過對中間階段決策的選擇，達到結(jié)束狀態(tài)。這些決策形

成了一個決策序列，同時確定了完成整個過程的一條活動路線(通常

是求最優(yōu)的活動路線)。如圖所示。動態(tài)規(guī)劃的設(shè)計都有著一定的模

式，一般要經(jīng)歷以下幾個步驟。

初始狀態(tài)一I決策1IfI決策2|一…一|決策n|結(jié)

束狀態(tài)

圖1動態(tài)規(guī)劃決策過程示意圖

(1)劃分階段：按照問題的時間或空間特征，把問題分為若干

個階段。在劃分階段時，注意劃分后的階段一定要是有序的或者是可

排序的，否則問題就無法求解。

(2)確定狀態(tài)和狀態(tài)變量：將問題發(fā)展到各個階段時所處于的

各種客觀情況用不同的狀態(tài)表示出來。當(dāng)然，狀態(tài)的選擇要滿足無后

效性。

(3)確定決策并寫出狀態(tài)轉(zhuǎn)移方程：因為決策和狀態(tài)轉(zhuǎn)移有著

天然的聯(lián)系，狀態(tài)轉(zhuǎn)移就是根據(jù)上一階段的狀態(tài)和決策來導(dǎo)出本階段

的狀態(tài)。所以如果確定了決策，狀態(tài)轉(zhuǎn)移方程也就可寫出。但事實上

常常是反過來做，根據(jù)相鄰兩段各狀態(tài)之間的關(guān)系來確定決策。

(4)尋找邊界條件：給出的狀態(tài)轉(zhuǎn)移方程是一個遞推式，需要

一個遞推的終止條件或邊界條件。

算法實現(xiàn)

動態(tài)規(guī)劃的主要難點在于理論上的設(shè)計，也就是上面4個步

驟的確定，一旦設(shè)計完成，實現(xiàn)部分就會非常簡單。使用動態(tài)規(guī)劃求

解問題，最重要的就是確定動態(tài)規(guī)劃三要素：問題的階段，每個階段

的狀態(tài)以及從前一個階段轉(zhuǎn)化到后一個階段之間的遞推關(guān)系。遞推關(guān)

系必須是從次小的問題開始到較大的問題之間的轉(zhuǎn)化，從這個角度來

說，動態(tài)規(guī)劃往往可以用遞歸程序來實現(xiàn)，不過因為遞推可以充分利

用前面保存的子問題的解來減少重復(fù)計算，所以對于大規(guī)模問題來

說，有遞歸不可比擬的優(yōu)勢，這也是動態(tài)規(guī)劃算法的核心之處。確定

了動態(tài)規(guī)劃的這三要素，整個求解過程就可以用一個最優(yōu)決策表來描

述，最優(yōu)決策表是一個二維表，其中行表示決策的階段，列表示問題

狀態(tài)，表格需要填寫的數(shù)據(jù)一般對應(yīng)此問題的在某個階段某個狀態(tài)下

的最優(yōu)值（如最短路徑，最長公共子序列，最大價值等），填表的過

程就是根據(jù)遞推關(guān)系，從1行1列開始，以行或者列優(yōu)先的順序，依

次填寫表格，最后根據(jù)整個表格的數(shù)據(jù)通過簡單的取舍或者運算求得

問題的最優(yōu)解。下面分別以求解最大化投資回報問題和最長公共子序

列問題為例闡述用動態(tài)規(guī)劃算法求解問題的一般思路。

三.貪心算法

所謂貪心算法是指，在對問題求解時，總是做出在當(dāng)前看來是

最好的選擇。也就是說，不從整體最優(yōu)上加以考慮，他所做出的僅是

在某種意義上的局部最優(yōu)解。

貪心算法不是對所有問題都能得到整體最優(yōu)解，但對范圍相

當(dāng)廣泛的許多問題他能產(chǎn)生整體最優(yōu)解或者是整體最優(yōu)解的近似解。

貪心算法的基本思路如下：

1.建立數(shù)學(xué)模型來描述問題。

2.把求解的問題分成若干個子問題。

3.對每一子問題求解，得到子問題的局部最優(yōu)解。

4.把子問題的解局部最優(yōu)解合成原來解問題的一個解。

實現(xiàn)該算法的過程：

從問題的某一初始解出發(fā)；

while能朝給定總目標(biāo)前進一步do

求出可行解的一個解元素；

由所有解元素組合成問題的一個可行解；

下面是一個可以試用貪心算法解的題目，貪心解的確不錯，

可惜不是最優(yōu)解。

例題分析

［背包問題］有一個背包，背包容量是后150。有7個物品，

物品可以分割成任意大小。

要求盡可能讓裝入背包中的物品總價值最大，但不能超過總

容量。

物品ABCDEFG

重量35306050401025

價值10403050354030

分析：

目標(biāo)函數(shù)：Epi最大

約束條件是裝入的物品總重量不超過背包容量：

Lwi<=M(M=150)

(1)根據(jù)貪心的策略，每次挑選價值最大的物品裝入背包,

得到的結(jié)果是否最優(yōu)？

(2)每次挑選所占重量最小的物品裝入是否能得到最優(yōu)解？

(3)每次選取單位重量價值最大的物品，成為解本題的策

略。？

值得注意的是，貪心算法并不是完全不可以使用，貪心策略

一旦經(jīng)過證明成立后，它就是一種高效的算法。

貪心算法還是很常見的算法之一，這是由于它簡單易行，構(gòu)

造貪心策略不是很困難。

可惜的是，它需要證明后才能真正運用到題目的算法中。

一般來說，貪心算法的證明圍繞著：整個問題的最優(yōu)解一定

由在貪心策略中存在的子問題的最優(yōu)解得來的。

對于例題中的3種貪心策略，都是無法成立（無法被證明）

的，解釋如下：

（1）貪心策略：選取價值最大者。反例：

W=30

物品：ABC

重量：281212

價值：302020

根據(jù)策略，首先選取物品A,接下來就無法再選取了，可是,

選取B、C則更好。

（2）貪心策略：選取重量最小。它的反例與第一種策略的反

例差不多。

（3）貪心策略：選取單位重量價，直最大的物品。反例：

W=30

物品：ABC

重量：282010

價值：282010

根據(jù)策略，三種物品單位重量價值一樣，程序無法依據(jù)現(xiàn)有策略

作出判斷，如果選擇A,則答案錯誤。

（-）問題描述

一輛汽車加滿油后可以行駛N千米。旅途中有若干個加油站。

指出若要使沿途的加油次數(shù)最少，設(shè)計一個有效的算法，指出應(yīng)在那

些加油站?？考佑汀?/p>

給出N,并以數(shù)組的形式給出加油站的個數(shù)及相鄰距離，指

出若要使沿途的加油次數(shù)最少，設(shè)計一個有效的算法，指出應(yīng)在那些

加油站停靠加油。要求：算法執(zhí)行的速度越快越好。

（-）問題分析（前提行駛前車?yán)锛訚M油）

對于這個問題我們有以下幾種情況：設(shè)加油次數(shù)為k,每個

加油站間距離為a[i]；i=0,1,2,3……n

1.始點到終點的距離小于N,則加油次數(shù)k=0；

2.始點到終點的距離大于N,

A加油站間的距離相等，即a[i]=a[j]=L=N,則加油次數(shù)

最少k=n；

B加油站間的距離相等，即a=L>N,則不可能到

達終點；

C加油站間的距離相等，即a[i]=a[j]=L〈N,則加油次數(shù)

k=n/N(n%N==O)或k=[n/N]+1(n%N!=0)；

D加油站間的距離不相等，即則加油次數(shù)k通

過以下算法求解。

(三)算法描述

貪心算法的基本思想

該題目求加油最少次數(shù)，即求最優(yōu)解的問題，可分成幾個步

驟，一般來說，每個步驟的最優(yōu)解不一定是整個問題的最優(yōu)解，然而

對于有些問題，局部貪心可以得到全局的最優(yōu)解。貪心算法將問題的

求解過程看作是一系列選擇，從問題的某一個初始解出發(fā)，向給定目

標(biāo)推進。推進的每一階段不是依據(jù)某一個固定的遞推式，而是在每一

個階段都看上去是一個最優(yōu)的決策（在一定的標(biāo)準(zhǔn)下）。不斷地將問

題實例歸納為更小的相似的子問題，并期望做出的局部最優(yōu)的選擇產(chǎn)

生一個全局得最優(yōu)解。

貪心算法的適用的問題

貪心算法適用的問題必須滿足兩個屬性：

（1）貪心性質(zhì)：整體的最優(yōu)解可通過一系列局部最優(yōu)

解達到，并且每次的選擇可以依賴以前做出的選擇，但不能依賴于以

后的選擇。

（2）最優(yōu)子結(jié)構(gòu)：問題的整體最優(yōu)解包含著它的子問

題的最優(yōu)解。

貪心算法的基本步驟

（1）分解：將原問題分解為若干相互獨立的階段。

（2）解決：對于每一個階段求局部的最優(yōu)解。

（3）合并：將各個階段的解合并為原問題的解。

［問題分析］

由于汽車是由始向終點方向開的，我們最大的麻煩就是不知

道在哪個加油站加油可以使我們既可以到達終點又可以使我們加油

次數(shù)最少。

提出問題是解決的開始.為了著手解決遇到的困難,取得最優(yōu)

方案。我們可以假設(shè)不到萬不得已我們不加油，即除非我們油箱里的

油不足以開到下一個加油站，我們才加一次油。在局部找到一個最優(yōu)

的解。卻每加一次油我們可以看作是一個新的起點，用相同的遞歸方

法進行下去。最終將各個階段的最優(yōu)解合并為原問題的解得到我們原

問題的求解。

加油站貪心算法設(shè)計(C)：

include<math.h>

include<studio.h>

intadd(intb[],intin,intn)

{〃求一個從m到n的數(shù)列的和

intsb;

for(inti=m;i<n;i++)sb+=b[i];

returnsb;

)

intTanxin(inta[n],intN)//a[n]表示加油站的個數(shù)，N

為加滿油能行駛的最遠距離

intb[n];〃若在a[i]加油站加油，則b[i]為1,否則為

0

intm=0;

if(a[i]>N)returnERROR;〃如果某相鄰的兩個加油站間的

距離大于N,則不能到達終點

if(add(a[i],0,n)<N)

{〃如果這段距離小于N,則不需要加油

b[i]=0;

returnadd(b[i],0,n);

)

if(a[i]==a[j]&&a[i]==N)

{〃如果每相鄰的兩個加油站間的距離都是N,則每個加油站都

需要加油

returnadd(b[i],0,n);

)

if(a[i]==a[j]&&a[i]<N)

{//如果每相鄰的兩個加油站間的距離相等且都小于N

if(add(a[i],m,k)<N&&add(a[i],m,k+1)>N)

(

b[k]=l;

m+=k;

)

returnadd(b[i],0,n);

if(a[i]!=a[j])

(〃如果每相鄰的兩個加油站間的距離不相等且都小于N

if(add(a[i],m,k)<N&&add(a[i],m,k+1)>N)

(

b[k]=l;

m+=k;

)

returnadd(b[i],0,n);

)

viodmain()

(

inta[];

scanfa);

scanf(〃/n〃)；

scanf(〃/d",&N);

Tanxin(a[],0,n);

貪心算法正確性證明:

貪心選擇性質(zhì)

所謂貪心選擇性質(zhì)是指所求問題的整體最優(yōu)解可以通過一系

列局部最優(yōu)的選擇，即貪心選擇來達到。對于一個具體的問題，要確

定它是否具有貪心性質(zhì)，我們必須證明每一步所作的貪心選擇最終導(dǎo)

致問題的一個整體最優(yōu)解。該題設(shè)在加滿油后可行駛的N千米這段路

程上任取兩個加油站A、B,且A距離始點比B距離始點近，則若在

B加油不能到達終點那么在A加油一定不能到達終點，因為m+N〈n+N,

即在B點加油可行駛的路程比在A點加油可行駛的路程要長n-m千

米，所以只要終點不在B、C之間且在C的右邊的話，根據(jù)貪心選擇,

為使加油次數(shù)最少就會選擇距離加滿油得點遠一些的加油站去加油，

因此，加油次數(shù)最少滿足貪心選擇性質(zhì)。

最優(yōu)子結(jié)構(gòu)性質(zhì)：

當(dāng)一個問題大的最優(yōu)解包含著它的子問題的最優(yōu)解時，稱該

問題具有最優(yōu)子結(jié)構(gòu)性質(zhì)。由于(b[l],b[2],……b[n])是這段路程

加油次數(shù)最少的一個滿足貪心選擇性質(zhì)的最優(yōu)解，則易知若在第一個

加油站加油時,b[l]二1,則(b[2],b[3],...b[n])是從a⑵到a[n]

這段路程上加油次數(shù)最少且這段路程上的加油站個數(shù)為

(a[2],a[3],……a[n])的最優(yōu)解，即每次汽車中剩下的油不能在行

駛到下一個加油站時我們才在這個加油站加一次油，每個過程從加油

開始行駛到再次加油滿足貪心且每一次加油后相當(dāng)于與起點具有相

同的條件，每個過程都是相同且獨立，也就是說加油次數(shù)最少具有最

優(yōu)子結(jié)構(gòu)性質(zhì)。

貪心算法時間復(fù)雜度分析

由于若想知道該在哪個加油站加油就必須遍歷所有的加油

站，且不需要重復(fù)遍歷，所以時間復(fù)雜度為0(n)。

四.回溯法

回溯法是一種選優(yōu)搜索法，按選優(yōu)條件向前搜索，以達到目標(biāo)。

但當(dāng)探索到某一步時，發(fā)現(xiàn)原先選擇并不優(yōu)或達不到目標(biāo)，就退回一

步重新選擇，這種走不通就退回再走的技術(shù)為回溯法，而滿足回溯條

件的某個狀態(tài)的點稱為“回溯點”。

1、回溯法的一般描述

可用回溯法求解的問題P,通常要能表達為：對于已知的由n

元組(xl,x2,???,xn)組成的一個狀態(tài)空間E={(xl,x2,…,xn)

IxieSi,i=l,2,-??,n},給定關(guān)于n元組中的一個分量的一個

約束集D,要求E中滿足D的全部約束條件的所有n元組。其中Si

是分量Xi的定義域，且|Si|有限，i=l,2,no我們稱E中滿

足D的全部約束條件的任一n元組為問題P的一個解。

解問題P的最樸素的方法就是枚舉法，即對E中的所有n元

組逐一地檢測其是否滿足D的全部約束，若滿足，則為問題P的一個

解。但顯然，其計算量是相當(dāng)大的。

我們發(fā)現(xiàn)，對于許多問題，所給定的約束集D具有完備性，

即i元組(xl,x2,???,xi)滿足D中僅涉及到xl,x2,--?,xi的

所有約束意味著j(j〈i)元組(xl,x2,xj)一定也滿足D中

僅涉及到xl,x2,…，xj的所有約束，i=l,2,…，no換句話說，

只要存在OWjWnT,使得(xl,x2,…，xj)違反D中僅涉及到xl,

x2,…,xj的約束之一,則以(xi,x2,…，xj)為前綴的任何n

元組(xl,x2,…,xj,xj+1,…,xn)一定也違反D中僅涉及到

xl,x2,…，xi的一個約束，n^i>jo因此，對于約束集D具有完

備性的問題P,一旦檢測斷定某個j元組(xl,x2,…，xj)違反D

中僅涉及xl,x2,…，xj的一個約束，就可以肯定，以(xl,x2,…,

xj)為前綴的任何n元組(xl,x2,???,xj,xj+1,???,xn)都不會

是問題P的解，因而就不必去搜索它們、檢測它們。回溯法正是針對

這類問題，利用這類問題的上述性質(zhì)而提出來的比枚舉法效率更高的

算法。

回溯法首先將問題P的n元組的狀態(tài)空間E表示成一棵高為

n的帶權(quán)有序樹T,把在E中求問題P的所有解轉(zhuǎn)化為在T中搜索問

題P的所有解。樹T類似于檢索樹，它可以這樣構(gòu)造：設(shè)Si中的元

素可排成xi(l),xi(2)，…,xi(mi-1),|Si|=mi,i=l,2,…,

no從根開始，讓T的第I層的每一個結(jié)點都有mi個兒子。這mi個

兒子到它們的雙親的邊，按從左到右的次序，分別帶權(quán)xi+l(l),

xi+1(2)，…，xi+1(mi),i=0,1,2,…,n-lo照這種構(gòu)造方式,

E中的一個n元組(xl,x2,???,xn)對應(yīng)于T中的一個葉子結(jié)點，

T的根到這個葉子結(jié)點的路徑上依次的n條邊的權(quán)分別為xl,x2,…,

xn,反之亦然。另外,對于任意的OWiWnT,E中n元組(xl,x2,…,

xn)的一個前綴I元組(xl,x2,-??,xi)對應(yīng)于T中的一個非葉子

結(jié)點,T的根到這個非葉子結(jié)點的路徑上依次的I條邊的權(quán)分別為xl,

x2,…，xi,反之亦然。特別，E中的任意一個n元組的空前綴(),

對應(yīng)于T的根。

因而，在E中尋找問題P的一個解等價于在T中搜索一個葉

子結(jié)點，要求從T的根到該葉子結(jié)點的路徑上依次的n條邊相應(yīng)帶的

n個權(quán)xl,x2,…，xn滿足約束集D的全部約束。在T中搜索所要

求的葉子結(jié)點，很自然的一種方式是從根出發(fā)，按深度優(yōu)先的策略逐

步深入，即依次搜索滿足約束條件的前綴1元組(xli)、前綴2元

組(xl,x2)、…，前綴I元組(xl,x2,???,xi),??-,直到i二n

為止。

在回溯法中，上述引入的樹被稱為問題P的狀態(tài)空間樹；樹

T上任意一個結(jié)點被稱為問題P的狀態(tài)結(jié)點；樹T上的任意一個葉子

結(jié)點被稱為問題P的一個解狀態(tài)結(jié)點；樹T上滿足約束集D的全部約

束的任意一個葉子結(jié)點被稱為問題P的一個回答狀態(tài)結(jié)點，它對應(yīng)于

問題P的一個解

用回溯法解題的一般步驟：

（1）針對所給問題，定義問題的解空間；

（2）確定易于搜索的解空間結(jié)構(gòu)：

（3）以深度優(yōu)先方式搜索解空間，并在搜索過程中用剪枝函數(shù)

避免無效搜索。

例子：

運動員最佳配問題，羽毛球隊有男女運動員各N人給定兩個N*?1矩

陣P和Q.P[I][J]是男運動員I和女運動員J配對組成混合雙打的

競賽優(yōu)勢；是女運動員I和男運動員J配合的競賽優(yōu)勢。由

于配合和心理狀態(tài)等各種因素影響，P[I][J]不一定等于Q[J][I].設(shè)

計一個算法計算男女運動員最佳配對法，使各組男女雙方競賽優(yōu)勢乘

積的總和達到最大。

ttinclude“stdafx.h〃

ftinclude<iostream>

#include<fstream>

#include<iomanip>

ttinclude<vector>

usingnamespacestd;

vector<int>Re;〃全局變量,Re用來記靈配對情況

vector<vector<int?P;

vector<vector<int>>Q;

classQueen

(

friendintPairUp(int);

private:

boolPlace(intk);

voidBacktrack(intk);

intn;

intsum;

vector<int>x;

public:

Queen(intm,intc,intb)

!

x.resize(m+1);

Re.resize(m+1);

n二c;

sum=b;

}

'Queen(){}

}；

boolQueen::Place(intk)

for(intj=l;j<k;j+