《算法分析理論及應(yīng)用》課程實(shí)驗(yàn)報(bào)告

一、實(shí)驗(yàn)題目

1.圖著色問(wèn)題：給定無(wú)向連通圖G和m種不司的顏色。用這些顏色為圖G的各

頂點(diǎn)著色，每個(gè)頂點(diǎn)著一種顏色。如果有一種著色法使G中短條邊的兩個(gè)頂點(diǎn)著不

同顏色，則稱(chēng)這個(gè)圖是m可著色的。圖的m著色問(wèn)題是對(duì)于給定圖G和m種顏色，

找出所有不同的著色法。

【輸入格式】第1行有3個(gè)正整數(shù)n、k和m,表示給定的圖G有n個(gè)頂點(diǎn)和k

條邊，m種顏色。頂點(diǎn)編號(hào)為1,2,…，n。接下來(lái)的k行中，每行有兩個(gè)正整數(shù)u、

v,表示圖G的一條邊（u,v）o

【輸出格式】程序運(yùn)行結(jié)束時(shí)，將計(jì)算出的不同的著色方案數(shù)輸出。如果不能著

色，程序輸出-1。

【輸入樣例】

443

12

13

14

24

【輸出樣例】

12

請(qǐng)寫(xiě)出算法時(shí)間復(fù)雜度、算法策略（基于回溯法），算法偽代碼以及代碼實(shí)現(xiàn)。

2.0/1背包問(wèn)題。有n個(gè)重量分別為｛wl,w2,…，wn｝的物品，它們的價(jià)值分

別為｛vl,v2,…，vn｝,給定一個(gè)容量為Q的背包。

設(shè)計(jì)從這些物品中選取一部分物品放入該背包的方案，每個(gè)物品要么選中要么不

選中，要求選中的物品不僅能夠放到背包中，而且重量和恰好為Q具有最大的價(jià)值。

0/1背包問(wèn)題（Q=6）：

物品編號(hào)重量?jī)r(jià)值

154

234

323

411

請(qǐng)寫(xiě)出算法時(shí)間復(fù)雜度、算法策略（基于回溯法），算法偽代碼以及代碼實(shí)現(xiàn)。

3.（選做題）八皇后問(wèn)題：八皇后問(wèn)題是十九世紀(jì)著名的數(shù)學(xué)家高斯于1850年

提出的。問(wèn)題是：在8X8的棋盤(pán)上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)

皇后都不能處于同一行、同一列或同一斜線上。可以把八皇后問(wèn)題擴(kuò)展到n皇后問(wèn)題,

即在nXn的棋盤(pán)上擺放n個(gè)皇后，使任意兩個(gè)皇后都不能處于同一行、同一列或同

一斜線上。

請(qǐng)寫(xiě)出算法時(shí)間復(fù)雜度、算法策略(基于回溯法)，算法偽代碼以及代碼實(shí)現(xiàn)。

二、實(shí)驗(yàn)內(nèi)容

1.圖著色問(wèn)題：給定無(wú)向連通圖G和m種不司的顏色.用這些顏色為圖G的各

頂點(diǎn)著色，每個(gè)頂點(diǎn)著一種顏色。如果有一種著色法使G中每條邊的兩個(gè)頂點(diǎn)著不

同顏色，則稱(chēng)這個(gè)圖是m可著色的。圖的m著色問(wèn)題是對(duì)于給定圖G和m種顏色，

找出所有不同的著色法。

【輸入格式】第1行有3個(gè)正整數(shù)n、k和m,表示給定的圖G有n個(gè)頂點(diǎn)和k

條邊，m種顏色。頂點(diǎn)編號(hào)為1,2,…，n。接下來(lái)的k行中，每行有兩個(gè)正整數(shù)u、

v,表示圖G的一條邊(u,v)o

【輸出格式】程序運(yùn)行結(jié)束時(shí)，將計(jì)算出的不同的著色方案數(shù)輸出。如果不能著

色，程序輸出

【輸入樣例】

443

12

13

14

24

【輸出樣例】

12

請(qǐng)寫(xiě)出算法時(shí)間復(fù)雜度、算法策略(基于回溯法)，算法偽代碼以及代碼實(shí)現(xiàn)。

時(shí)間復(fù)雜度：O(nAi)

算法策略：

首先定義解向量，由于用機(jī)種顏色為無(wú)向圖G=(KE)著色，其中，V的頂點(diǎn)個(gè)數(shù)

為〃，可以用一個(gè)九元組X=Ql,X2,…，向)描述圖的一種可能著色,其中，Xi^(1,2,...,

表示賦予頂點(diǎn)i的顏色。再設(shè)計(jì)剪枝函數(shù)，如果在〃元組x中，所有相鄰頂

點(diǎn)都不會(huì)著相同顏色，就稱(chēng)此〃元組為答案解，否則為無(wú)效解。隨后構(gòu)建解空間樹(shù)，

圖中的頂點(diǎn)編號(hào)為1?〃，著色編號(hào)為1?〃?。對(duì)于圖G中的每一個(gè)頂點(diǎn)，可能的著色為I?

機(jī)，所以對(duì)應(yīng)的解空間是一棵〃?叉樹(shù)，高度為〃，層次，?從1開(kāi)始。回溯法求解圖著色問(wèn)題,

首先把所有頂點(diǎn)的顏色初始化為0,然后依次為每個(gè)頂點(diǎn)著色。在圖著色問(wèn)題的解空間

樹(shù)中，如果從根結(jié)點(diǎn)到當(dāng)前結(jié)點(diǎn)對(duì)應(yīng)一個(gè)部分解，也就是所有的顏色指派都沒(méi)有沖突，則在

當(dāng)前結(jié)點(diǎn)處選擇第一-棵子樹(shù)繼續(xù)搜索，也就是為下一個(gè)頂點(diǎn)著顏色1,否則，對(duì)當(dāng)前子樹(shù)的

兄弟子樹(shù)繼續(xù)搜索，也就是為當(dāng)前頂點(diǎn)著下一個(gè)顏色，如果所有，〃種顏色都已嘗試過(guò)并且都

發(fā)生沖突，則回溯到當(dāng)前結(jié)點(diǎn)的父結(jié)點(diǎn)處，上一個(gè)頂點(diǎn)的顏色被改變，依此類(lèi)推.

偽代碼：

graphColor(inti)

ifi>n

count++

else

forj=l;j<=m;j++

x[i]=j；

ifsame(i)

graphColor(i+l)

x[i]=0

代碼：

#include<stdio.h>

#includc<stdlib.h>

#includc<string.h>

#defineMAXN20

intn,k,m;

inta[MAXN][MAXN];

intcount=0;

intx[MAXN];

boolSame(inti)

(

for(intj=1;j<=n;i++)

&&x[i]=x|jj)

returnfalse;

returntrue;

)

voiddispasolution()

{

printf("第％d個(gè)著色方案:H,count);

fbr(intj=l;j<=n;j++)

printf("%d",x|j|);

printfCVn");

)

voidGraphColor(inti)

if(i>n)

{count++;

dispasolutionO;

)

else

{for(intj=l;j<=m;j++)

(

if(Same(i))

GraphColor(i+l);

x[i]=0；

1

)

)

intmain()

{

memsel(a,0,sizeof(a));

memset(x,0,sizeof(x));

intx,y;

scanf("%d%d%d",&n,&k,&m);

for(intj=l;j<=k;j4-+)

{scanf("%d%d",&x,&y);

a[x][y]=l;

a[y][x]=l;

)

GraphColor(1);

if(count>0)

prinlf("%d\n",count);

else

printfC'-lXn");

return0;

)

2.0/1背包問(wèn)題。有n個(gè)重量分別為｛wl,w2,…，wn｝的物品，它們的價(jià)值分

別為｛vl,v2,…,vn),給定一個(gè)容量為Q的背包。

設(shè)計(jì)從這些物品中選取一部分物品放入該背包的方案，每個(gè)物品要么選中要么不

選中，要求選中的物品不僅能夠放到背包中，而且重量和恰好為Q具有最大的價(jià)值。

0/1背包問(wèn)題(Q=6)：

物品編號(hào)重量?jī)r(jià)值

154

234

323

411

請(qǐng)寫(xiě)出算法時(shí)間復(fù)雜度、算法策略(基于回溯法)，算法偽代碼以及代碼實(shí)現(xiàn)。

時(shí)間復(fù)雜度：0(2An)

算法策略：

(1)選擇第i個(gè)物業(yè)放入背包中：op[i]=l,tw=lw+w[i],tv=tv+v[i],轉(zhuǎn)向下一個(gè)狀態(tài)

dfs=(i+l,lw,tv,op).該對(duì)策對(duì)應(yīng)左分枝

(2)不選擇第i個(gè)物品放入背包：op[i]=0,tw=tw不變，tv不變，轉(zhuǎn)向下一個(gè)狀態(tài)

dfs=(i+1,tw,tv,op).該對(duì)策對(duì)應(yīng)右分枝

葉子結(jié)點(diǎn)表示已經(jīng)對(duì)n個(gè)物品做了決策，對(duì)應(yīng)一個(gè)解。對(duì)所有葉子結(jié)點(diǎn)進(jìn)行比較

求出滿足tw=W的最大tv(用maxw表示)?將對(duì)應(yīng)的最優(yōu)解op存放至ljx中

只對(duì)左子樹(shù)進(jìn)行剪枝，沒(méi)有對(duì)右子樹(shù)進(jìn)行剪枝，實(shí)際也可以進(jìn)行對(duì)右子樹(shù)進(jìn)行剪

枝。用rw表示考慮第i個(gè)物品時(shí)剩余的物品重量，即rw=w[i]+…+w[n](初始時(shí)rw

是所有物品的重量和)，對(duì)于第i層上的某個(gè)分枝結(jié)點(diǎn)，將對(duì)應(yīng)的狀態(tài)改為

dfs(i,tw,tv,rw,op),對(duì)應(yīng)兩種擴(kuò)展如下。

(1)選擇第i個(gè)物品放入背包中：op[i]=l,如果放入物品i不超重嗎，則

tw=tw+w|i],tv=tv+v|i],rw=rw-w|iI,轉(zhuǎn)向卜一個(gè)狀態(tài)dfs=(i+1,tw,tv,rw,op).該對(duì)策對(duì)應(yīng)左

分枝

(2)不選擇第i個(gè)物品放入背包：op[i]=0,lw不變，tv不變,rw=rw-w[i](無(wú)論是否選

擇物品i,rw都是剩余沒(méi)有考慮的物品重量和)轉(zhuǎn)向下一個(gè)狀態(tài)(1?=6+1,1亞,1丫,(^).該對(duì)

策對(duì)應(yīng)右分枝。

當(dāng)不選擇物品i時(shí)，若tw+rw<W(tw中包含w[i]),也就是說(shuō)即使選擇后面的所有

物品，重量也不會(huì)達(dá)到W,因此可以不考慮擴(kuò)展這樣的結(jié)點(diǎn)，從而產(chǎn)生進(jìn)一步剪枝

的解空間，如圖，有9個(gè)結(jié)點(diǎn)，對(duì)于圖中第2層的(0,0)結(jié)點(diǎn)，此時(shí)tw=0,rw=6(物品2、

物品3、物品4的重量利)，tw+rw=6,不大于W(此時(shí)又不選擇物品2)所以不必?cái)U(kuò)展其右孩

子。

偽代碼：

dfs(int1,inttw,inttv,intop|])

ifi>n

iftw-k&&tv>maxv

maxv=tv

forj=l;j<=n;j++

x[j]=op[i]

else

iftw+\v[i]<=k

op|i)=l

dfs(i+l,tw,op)

代碼：

#include<stdio.h>

#dcfmeMAXN20

intn=4;

intW=6;

int={0,5,3,2,1};

intv[]={0,4,4,3,l};

intx[MAXN];

intmaxv;

voiddfs(inti,inttw,inttv,intop[])

if(i>n)

if(tw==W&&tv>maxv)

(

maxv=tv;

for(intj=l;j<=n;j++)

x|jl=op|j|;

)

}

else

(

if(tw+w[i]<=W){

op|i]=l；

dfs(i+l,lw+w|i],tv+v|i],op);

I

op[i]=0;

dfs(i+l,tw,tv,op);

}

)

voiddispsolution()

(

inti;

printf("最優(yōu)解:\n");

for(i=l;i<=n;i++)

if(x[i]==l)

printf(H選取第％d個(gè)物品\n”,i);

printf("總重量=%&總價(jià)值二%d\n",W,maxv);

)

intmain(){

intop[MAXN];

dfs(1,0,0,op);

dispsolution():

return0;

)

3.(選做題)八皇后問(wèn)題：八皇后問(wèn)題是十九世紀(jì)著名的數(shù)學(xué)家高斯于1850年

提出的。問(wèn)題是：在8X8的棋盤(pán)上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)

皇后都不能處于同一行、同一列或同一斜線上。可以把八皇后問(wèn)題擴(kuò)展到n皇后問(wèn)題,

即在nXn的棋盤(pán)上擺放n個(gè)皇后，使任意兩個(gè)皇后都不能處于同一行、同一列或同

一斜線上。

請(qǐng)寫(xiě)出算法時(shí)間復(fù)雜度、算法策略(基于回溯法)，算法偽代碼以及代碼實(shí)現(xiàn)。

時(shí)間復(fù)雜度：0(n!)

算法策略：

1、這里的八個(gè)皇后用k=0,1,2,3,4,5,6,7來(lái)表示。

2、第一個(gè)皇后放在8x8矩陣的(0,0)位置，也就是k=0,x[k]=0,這

里的k表示行和皇后k,x[k]表示列。

3、放完第一個(gè)皇后之后，就要放置第二個(gè)皇后，因?yàn)椴荒茉谕恍校缘诙€(gè)

皇后肯定在第一行放，這個(gè)時(shí)候到底在哪一列還沒(méi)有確定.

4、在確定第二個(gè)皇后到底在哪一列的時(shí)候，就要用到一個(gè)判斷函數(shù)，這個(gè)函數(shù)主

要是確定皇后不在同一列和同一斜線上。

5、若發(fā)生了沖突【即皇后在同一列或同一斜線上】，就x[k]++,一直找到不發(fā)生

沖突的位置或越界。

6、在找到皇后的位置之后，要先判斷一下是否皇后都找到了合適的位置。

7、若還有剩余的皇后或發(fā)生越界，則分情況處理，若是還有剩余的皇后，則k二

k+1,擺放下一個(gè)皇后，若是發(fā)生越界，則說(shuō)明需要回溯，則x[k]=-1,k=k-1

偽代碼：

queen(intn)

whi1ek>=0

x[k]+-

whilex[k]<n&&check(k)==l

x[k]++

ifx[k]<n&&k==n-l

fori=0;i<n;i++

printx[i]+l

sum++

ifx[k]<n&&k<n-l

k++

else

x[k]=-l

k-

代碼：

#include<iostream>

usingnamespacestd;

#include<stdlib.h>

staticint*x;

staticintsum;

intcheck(intk){

for(inti=0;i<k;i++)

if(x[i]==x[k]||abs(x[i]-x[k])==abs(i-k))

return1;

return0;

}

voidqueen(intn)(

intk=0;

sum=0;

while(k>=0){

x[k]++;

while(x[k]<n&&check(k)==1)

x[k]++;

if(x[k]<n&&k==n-1)

for(inti=0;i<n;i++)

cout<<endl;

sum++;

}

if(x[k]<n&&k<n-l)

k++;

else

{

x[k]—1;

k一;

}

)

if(sum==0)

cout?"無(wú)解"<<endl;

intmain(){

intn=8;

x=newint[n-1];

for(inti=O;i<n;i++){

x[i]=-1:

)

queen(n);

cout<<”一共解的個(gè)數(shù)為："<<sum?endl;

return0;

}

三、實(shí)驗(yàn)?zāi)康?/p>

1.理解回溯問(wèn)題的思想，算法策略。

2.掌握利用回溯解決問(wèn)題的基本思想，會(huì)用高級(jí)語(yǔ)言對(duì)算法進(jìn)行描述，并對(duì)算法復(fù)雜度

(時(shí)間和空間)進(jìn)行分析。

四、實(shí)驗(yàn)代碼

1.

#include<stdio.h>

#include<stdlib.h>

#includc<string.h>

#defineMAXN20

intn,k,m;

inta[MAXN][MAXN];

intcount=0;

intxlMAXNJ;

boolSame(inti)

(

for(intj=l;j<=n;j++)

if(a[i]U]==l&&x[i]==xUJ)

returnfalse;

returntrue;

I

voiddispasolutionO

(

prinlf("第％d個(gè)著色方案:n,count);

for(intj=l;j<=n;j++)

printf("%d",x|j])；

printf("\n");

)

voidGraphColor(inti)

if(i>n)

{count++;

dispasolution();

)

else

{for(intj=l;j<=m;j++)

(

x[i]=j；

if(Samc(i))

GraphColor(i+I);

x[i]=0;

)

)

I

intmain()

(

mcmset(a,0,sizeof(a));

memset(x,0,sizeof(x));

intx,y;

scanf("%d%d%d',,&n,&k,&m);

for(intj=l;j<=k;j-i-+)

{scanf(H%d%d",&x,&y);

a[x][y]=l;

a|y|[x]=l;

)

GraphColor(l);

if(count>0)

printf("%d\n",count);

else

printfC-l\n");

return0;

)

2.

#include<stdio.h>

#defineMAXN20

intn=4;

intW=6;

intw[]={0,5,3,2J}；

intv[]={0,4,4,3,l)；

intx[MAXN];

intmaxv;

voiddfs(inti,inttw,inttv,intop[])

(

if(i>n)

if(tw==W&&tv>maxv)

maxv=tv;

for(intj=1;j<=n;j++)

x昨。pLH；

)

)

else

(

if(tw+w[i]<=W){

op(i]=l；

dfs(i+l,tw+w[i],tv+v[i],op);

I

op[i]=0;

dfs(i+l,tw,tv,op);

)

)

voiddispsolution()

(

inti;

prinlf("最優(yōu)解：\n");

for(i=l;i<=n;i++)

if(x[i]==D

printfC1選取第％d個(gè)物品\n”,i);

printf("總重量=%由總價(jià)值=%d\n",W,maxv);

intmain(){

intop[MAXN];

dfs(1,0,0,op);

dispsolution():

return0;

)

3.

#include<iostream>

usingnamespacestd;

#include<stdlib.h>

staticint*x;

staticintsum;

intcheck(intk){

for(inti=0;i<k;i++)

if(x[i]==x[k]||abs(x[i]-x[k])==abs(i-k))

return1;

return0;

}

voidqueen(intn)(

intk=0;

sum=0;

while(k>=0){

x[k]++;

while(x[k]<n&&check(k)==1)

x[k]++;

if(x[k]<n&&k==n-1)

for(inti=0：i<n;i++)

cout<<x[i]+l<<z，z，;

cout<<endl;

sum++;

)

if(x[k]<n&&k<n-l)

k++;

els