窮舉搜索法

搜索是人工智能的一種問題求解方法，搜索策略決定着問題求解的一個推理步驟中知識被使用的優先關係，可分為盲目搜索和啓發式搜索。通常把樹狀盲目搜索稱為窮舉式搜索，它通過把需要解決問題的所有可能情況逐一試驗來找出符合條件的解的方法，它包括廣度優先、深度優先、有界深度優先、一致代價四種搜索算法。 ^[1] 

廣度優先搜索(Breadth- First- Search)也稱為寬度優先搜索，它是一種按”先產生的節點先擴展”的原則進行的搜索。搜索的過程是:從初始節點A開始，逐層地對節點進行擴展並考察它是否為目標節點，在第n層節點沒有全部擴展並考察之前，不對第n十1層節點進行擴展。

廣度搜索是逐層進行的。它把起始節點放到OPEN中(如果該起始節點為一目標節點，則求得一個解答);如果OPEN表是個空表，則沒有解，失敗退出;否則繼續;把第一個節點(節點n)從OPEN表移出，並把它放入CLOSED擴展節點表中;擴展節點n如果沒有後繼節點，則轉回;把n的所有後繼節點放到OPEN表的末端，並提供從這些後繼節點回到n指針;如果n的任一個後繼節點是個目標節點，則找到解，成功退出;否則轉回。

廣度優先搜索這種策略是完備的，即如果問題的解存在，用它則一定能找到解，且找到的解還是最優解(即最短的路徑)，但它的缺點是搜索效率低。

深度優先搜索(Depth- first- Search)亦稱為縱向搜索，它是從樹根開始一枝一枝逐漸生成，是一種後生成的節點先擴展的搜索方法。首先，擴展最深的節點的結果使得搜索沿着狀態空間某條單一的路徑從起始節點向下進行;只有當搜索到一個沒有後裔的狀態時，它才考慮另一條替代的路徑(替代路徑與前面已經試過的路徑不同之處僅僅在於改變最後n步，而且保持n儘可能小)。

深度優先搜索所遵循的搜索策略是儘可能”深”地搜索圖，它把起始節點放到未擴展節點OPEN表中，如果此節點為一目標節點，則得到一個解;如果OPEN為一空表，則失敗退出;把第一個節點(節點n)從OPEN表移到。,OSED表;如果節點n的深度等於最大深度，則轉回;擴展節點n，產生其全部後裔，並把它們放入OPEN表的前頭，如果沒有後裔，則轉回;如果後繼節點中有任一個為目標節點，則求得一個解，成功退出;否則轉回。深度優先搜索策略是不完備的，帶有一定的冒險性，並且應用此策略得到的解不一定是最優解(最短路徑)。

對於許多複雜問題，其狀態空間搜索樹的深度可能為無限深，或者可能至少要比某個可接受的解答序列的己知深度上限還要深。為了這種情況，常給出一個節點擴展的最大深度——深度界限，即在深度優先策略中引入深度限制，稱之為有界深度優先搜索。當從初始節點出發沿某一分枝擴展到限制深度，但還沒有找到目標時，就不能再繼續向下擴展，而只能改變方向繼續搜索。若在限度內沒有找到問題的解，且CLOSED表中仍有待擴展的節點，就將這些節點送回OPEN表，同時增大深度限制。

在許多實際問題中，狀態空間搜索樹中的各個邊的代價不是完全相同的，為此，需要在搜索樹中考慮每條邊的代價，根據”代價最小”的原則，優先選用最小代價的搜索路徑。寬度優先搜索可被推廣用來解決尋找從起始狀態至目標狀態的具有最小代價的路徑問題，這種推廣了的寬度優先搜索算法稱為一致代價搜索算法。 ^[1] 

【問題】 將A、B、C、D、E、F這六個變量排成三角形，這六個變量分別取[1，6]上的整數，且均不相同。求使三角形三條邊上的變量之和相等的全部解。

程序引入變量a、b、c、d、e、f，並讓它們分別順序取1至6的整數，在它們互不相同的條件下，測試由它們排成的三角形三條邊上的變量之和是否相等，如相等即為一種滿足要求的排列，把它們輸出。當這些變量取盡所有的組合後，程序就可得到全部可能的解。細節見下面的程序。

【程序1】

# include <stdio.h>

void main()

{ int a,b,c,d,e,f；

for (a=1；a<=6；a++)

for (b=1；b<=6；b++) {

if (b==a) continue；

for (c=1；c<=6；c++) {

if (c==a)||(c==b) continue；

for (d=1；d<=6；d++) {

if (d==a)||(d==b)||(d==c) continue；

for (e=1；e<=6；e++) {

if (e==a)||(e==b)||(e==c)||(e==d) continue；

f=21-(a+b+c+d+e)；

if ((a+b+c==c+d+e))&&(a+b+c==e+f+a)) {

printf(“%6d,a)；

printf(“%4d%4d”,b,f)；

printf(“%2d%4d%4d”,c,d,e)；

scanf(“%*c”)；

}

}

}

}

}

}

按窮舉法編寫的程序通常不能適應變化的情況。如問題改成有9個變量排成三角形，每條邊有4個變量的情況，程序的循環重數就要相應改變。

對一組數窮盡所有排列，還有更直接的方法。將一個排列看作一個長整數，則所有排列對應着一組整數。將這組整數按從小到大的順序排列排成一個整數，從對應最小的整數開始。按數列的遞增順序逐一列舉每個排列對應的每個整數，這能更有效地完成排列的窮舉。從一個排列找出對應數列的下一個排列可在當前排列的基礎上作部分調整來實現。倘若當前排列為1，2，4，6，5，3，並令其對應的長整數為124653。要尋找比長整數124653更大的排列，可從該排列的最後一個數字順序向前逐位考察，當發現排列中的某個數字比它前一個數字大時，如本例中的6比它的前一位數字4大，這説明還有對應更大整數的排列。但為了順序從小到大列舉出所有的排列，不能立即調整得太大，如本例中將數字6與數字4交換得到的排列126453就不是排列124653的下一個排列。為了得到排列124653的下一個排列，應從已經考察過的那部分數字中選出比數字大，但又是它們中最小的那一個數字，比如數字5，與數字4交換。該數字也是從後向前考察過程中第一個比4大的數字。5與4交換後，得到排列125643。在前面數字1，2，5固定的情況下，還應選擇對應最小整數的那個排列，為此還需將後面那部分數字的排列順序顛倒，如將數字6，4，3的排列順序顛倒，得到排列1，2，5，3，4，6，這才是排列1，2，4，6，5，3的下一個排列。按以上想法編寫的程序如下。

【程序2】

# include <stdio.h>

# define SIDE_N 3

# define LENGTH 3

# define VARIABLES 6

int A,B,C,D,E,F；

int *pt[]={&A,&B,&C,&D,&E,&F}；

int *side[SIDE_N][LENGTH]={&A,&B,&C,&C,&D,&E,&E,&F,&A}；

int side_total[SIDE_N]；

main{ }

{ int i,j,t,equal；

for (j=0；j<VARIABLES；j++)

*pt[j]=j+1；

while(1)

{ for (i=0；i<SIDE_N；i++)

{ for (t=j=0；j<LENGTH；j++)

t+=*side[j]；

side_total=t；

}

for (equal=1,i=0；equal&&i<SIDE_N-1；i++)

if (side_total!=side_total[i+1] equal=0；

if (equal)

{ for (i=1；i<VARIABLES；i++)

printf(“%4d”,*pt)；

printf(“\n”)；

scanf(“%*c”)；

}

for (j=VARIABLES-1；j>0；j--)

if (*pt[j]>*pt[j-1]) break；

if (j==0) break；

for (i=VARIABLES-1；i>=j；i--)

if (*pt>*pt[i-1]) break；

t=*pt[j-1]；* pt[j-1] =* pt； *pt=t；

for (i=VARIABLES-1；i>j；i--,j++)

{ t=*pt[j]； *pt[j] =* pt； *pt=t； }

}

}

從上述問題解決的方法中，最重要的因素就是確定某種方法來確定所有的候選解。下面再用一個示例來加以説明。

【問題】 揹包問題

問題描述：有不同價值、不同重量的物品n件，求從這n件物品中選取一部分物品的選擇方案，使選中物品的總重量不超過指定的限制重量，但選中物品的價值之和最大。

設n個物品的重量和價值分別存儲於數組w[ ]和v[ ]中，限制重量為tw。考慮一個n元組（x0，x1，…，xn-1），其中xi=0 表示第i個物品沒有選取，而xi=1則表示第i個物品被選取。顯然這個n元組等價於一個選擇方案。用枚舉法解決揹包問題，需要枚舉所有的選取方案，而根據上述方法，我們只要枚舉所有的n元組，就可以得到問題的解。

顯然，每個分量取值為0或1的n元組的個數共為2n個。而每個n元組其實對應了一個長度為n的二進制數，且這些二進制數的取值範圍為0～2n-1。因此，如果把0～2n-1分別轉化為相應的二進制數，則可以得到我們所需要的2n個n元組。

【算法】

maxv=0；

for (i=0；i<2n；i++)

{ B[0..n-1]=0；

把i轉化為二進制數，存儲於數組B中；

temp_w=0；

temp_v=0；

for (j=0；j<n；j++)

{ if (B[j]==1)

{ temp_w=temp_w+w[j]；

temp_v=temp_v+v[j]；

}

if ((temp_w<=tw)&&(temp_v>maxv))

{ maxv=temp_v；

保存該B數組；

}

}

}