算法習(xí)題答案第5章回溯法

1、1算法設(shè)計(jì)與分析習(xí)題第五章 回溯法高興宇25.1 用回溯法解決圖的m著色問題，并分析它的算法的時(shí)間復(fù)雜度。（圖的m著色問題是指：給定連通圖G，問是否存在只需要m種不同的顏色給每個(gè)頂點(diǎn)著色，使得任意相鄰的兩個(gè)頂點(diǎn)所著的顏色不同）。3用圖的鄰接矩陣a來表示一個(gè)無向連通圖G=(V,E)。若(i,j)屬于圖G=(V,E)的邊集E，則aij=1，否則aij=0。用整數(shù)1，2 ,.,m來表示m種不同的顏色。頂點(diǎn)i所著的顏色用xi來表示。因此，該問題的解向量可以表示為n元組xn。問題的解空間可表示為一棵高度為n+1的完全m叉樹。解空間樹的第i(1=i n )sum+; /合理方案計(jì)數(shù)器； for ( int

2、 i=1; i=n; i+ ) coutxi ; coutendl;elsefor ( int i=1; i 12 ) sum +;if ( Ok( x ) ) /是否問題可行解；for ( int i=0; i12; i+ )coutxi0 xi1endl;else for ( int i=0; i6; i+ )for ( int j=0; j6; j+ ) xnum_chessman0 = i; xnum_chessman1 = j; if ( suitable(i,j) ) / (i,j)放下棋子是否違反規(guī)則 Backtrack( num_chessman+1 ); 105.3 老鼠走迷

3、宮也是一個(gè)經(jīng)典的問題，用一個(gè)二維數(shù)組Amn表示迷宮，數(shù)組元素為0表示通路，為1表示墻壁。老鼠在除邊角外的任意位置都可以試探8個(gè)方向。請(qǐng)用回溯法求出從入口A00到出口Am-1n-1的通路。11bool Backtrack( int x, int y )if ( 到達(dá)出口 ) coutpathendl;return true; else if ( 越界 )return false; else / 依次探測位置P(x,y)的剩余7個(gè)方向P1，P2.，P7； for ( int k=1; k path; return true; return false;125.4 任意給定4張牌面值從113的撲克，

4、只能用，以及括號(hào)進(jìn)行運(yùn)算，每張撲克用且只能用一次，要求得到結(jié)果為24。請(qǐng)用回溯法解決此問題。13void Backtrack(int result )if ( 四張牌都參與了運(yùn)算 ) if (result= =24) 輸出運(yùn)算序列；else for (int k=0; k4; k+ ) if ( cardk = 0 )/第k張牌還沒有參與運(yùn)算 for ( int m=0; m4; m+) 將cardk與result用運(yùn)算符operator m 進(jìn)行運(yùn)算，結(jié)果保存到result； 記錄運(yùn)算； cardk = 1; Backtrack( result ); cardk = 0; 145.5 有一個(gè)集合A，它有n個(gè)元素，請(qǐng)用回溯法輸出它所有的子集，并分析算法的時(shí)間復(fù)雜度。15void Backtrack( int t )if ( t 64 ) 輸出path；else 將(x,y)加入path； for ( int k=0; k8; k+ ) /position里存放了(x,y)可走的八個(gè)方向； if ( OK(postionk) ) /下一個(gè)位置沒有走過； Backtr