[科普中国]-穷举搜索法

概述

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

void main()

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

for (a=1；a