算法設計與分析 課件 第六章 回溯法6.3.3 花草種植問題

計算機算法設計與分析第6章回溯法6.3.3花草種植問題在一大片農(nóng)田中有多個花草的種植區(qū)域，這些種植區(qū)域通過田埂連接，如下圖所示?，F(xiàn)需要將每個種植區(qū)域種上一種顏色的花草，但相鄰區(qū)域不能種植同一種顏色的花草。我們的目標是找到一種最優(yōu)的花草種植方案，使得各個種植區(qū)域使用最少的花草顏色區(qū)分開來。圖的著色問題12345圖的著色問題假設給定無向連通圖G=(V,E)和m種不同的顏色，其中V表示結點集合，E表示邊集合，用這些顏色為圖G的各頂點著色，每個頂點著一種顏色。若一個圖最少需要m種顏色才能使圖中每條邊連接的兩個頂點著不同顏色，則稱m為該圖的著色數(shù)。求一個圖的著色數(shù)m的問題稱為圖的m可著色優(yōu)化問題。第一步，定義解向量設圖G=(V,E),|V|=n,顏色數(shù)=m,圖G用鄰接矩陣g存儲表示，用整數(shù)1,2…m來表示m種不同的顏色。頂點i所著的顏色用x[i]表示。則可用一個n元組x[1],x[2],...x[n]表示花草種植問題的解，其中x[i]表第i塊區(qū)域種植花草的顏色種類，x[i]∈[1,m]。第二步，確定搜索結構：子集樹1-紅2-綠3-藍×××××x1=2x2=mx3=3x3=2x3=1x2=2x1=mx1=1x2=1x4=1x5=3x5=2x5=1............2345151234第三步確定：約束條件解空間樹為子集樹,是一棵n+1層的完全m叉樹，在解空間樹中做深度優(yōu)先搜索，約束條件:如果g[i][j]=1，x[i]≠x[j]，j∈[1,n]。剪枝函數(shù)代碼//剪枝函數(shù)intisColorValid(inti,intcolor){ for(intj=0;j<n;j++){ if(g[i][j]&&x[j]==color){ return0;//顏色沖突 } } return1;//顏色有效}i和j有邊相鄰，且i頂點著的顏色color與j頂點的顏色x[j]相同圖的m著色問題遞歸回溯代碼intbacktrack(inti){

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

printf("結點%d:顏色%d\n",i+1,x[i]); } return1;//所有結點都已著色 } for(intcolor=1;color<=m;color++){

x[i]=color;

if(isColorValid(i,color)){backtrack(i+1);return1;} } return0;//未找到有效的著色方案}考慮到葉子結點后，一個可行解出現(xiàn)，輸出結果對第i頂點著色color=1~m一一嘗試若滿足約束條件，則遞歸考慮下一個頂點時間復雜度分析花草種植問題即圖的m可著色問題，全部搜索的情況下其解空間樹中有

個結點。對于每一個結點，