窮舉搜尋法是編程中常用到的一種方法，通常在找不到解決問題的規律時對可能是解的眾多候選解按某種順序進行逐一枚舉和檢驗，並從中找出那些符合要求的候選解作為問題的解。
基本介紹
- 中文名：窮舉搜尋法
- 類別：方法
- 套用：編程
- 國家：中國
概述,窮舉式搜尋算法,廣度優先搜尋,深度優先搜尋,有界深度優先搜尋,一致代價搜尋,事例,範例,
概述
搜尋是人工智慧的一種問題求解方法，搜尋策略決定著問題求解的一個推理步驟中知識被使用的優先關係，可分為盲目搜尋和啟發式搜尋。通常把樹狀盲目搜尋稱為窮舉式搜尋，它通過把需要解決問題的所有可能情況逐一試驗來找出符合條件的解的方法，它包括廣度優先、深度優先、有界深度優先、一致代價四種搜尋算法。
窮舉式搜尋算法
廣度優先搜尋
廣度優先搜尋(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表，同時增大深度限制。
一致代價搜尋
在許多實際問題中，狀態空間搜尋樹中的各個邊的代價不是完全相同的，為此，需要在搜尋樹中考慮每條邊的代價，根據”代價最小”的原則，優先選用最小代價的搜尋路徑。寬度優先搜尋可被推廣用來解決尋找從起始狀態至目標狀態的具有最小代價的路徑問題，這種推廣了的寬度優先搜尋算法稱為一致代價搜尋算法。
事例
【問題】 將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數組；
}
}
}
