穷举搜索法

编程中常用方法

穷举搜索法是编程中常用到的一种方法，通常在找不到解决问题的规律时对可能是解的众多候选解按某种顺序进行逐一枚举和检验，并从中找出那些符合要求的候选解作为问题的解。

基本介绍

搜索是人工智能的一种问题求解方法，搜索策略决定着问题求解的一个推理步骤中知识被使用的优先关系，可分为盲目搜索和启发式搜索。通常把树状盲目搜索称为穷举式搜索，它通过把需要解决问题的所有可能情况逐一试验来找出符合条件的解的方法，它包括广度优先、深度优先、有界深度优先、一致代价四种搜索算法。

穷举式搜索算法

广度优先搜索

广度优先搜索(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

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

# 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

*pt[j]=j+1；

while(1)

{ for (i=0；i

{ for (t=j=0；j

t+=*side[j]；

side_total=t；

}

for (equal=1,i=0；equal&&i

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

if (equal)

{ for (i=1；i

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

printf(“ ”)；

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

{ if (B[j]==1)

{ temp_w=temp_w+w[j]；

temp_v=temp_v+v[j]；