人工智能：5.2 盲目搜索策略

 

盲目搜索是不利用问题的有关信息，而 是 根据事先确定好的某种固定的搜索方法进行搜索。典型的盲目搜索方法是深度优先搜索方法
和宽度优先搜索  方法

(
亦 称 广 度 优 先 搜 索 方法 )
， 这 是 两 种 基 本 搜 索 方 法 。 我 们 先 讨 论 回 溯 策 略

(Backtracking 
Strategies) 和图搜索策略(Graph  Search) 的一般策略，然后再介绍深

 

・91 ・

人工智能技术与方法

度优先搜索(Depth-first Search) 和宽度优先搜索(Breath-first
Search) 。

 

5.2.1    回溯策略

当 求解过程呈现出递归过程的性质 时 ， 使用 递归算法简单有效。下面定义一个递归过程 BACKTRACK ，输入参数为状态变量 DATA ，若算法成功结束，则返回一张规则表作为解输出 ； 若找不到解，则算法返回 FAIL ，失败退出。下面给出一个具有两个回溯
点( 即设 置两个回溯条件) 的简单算法，并通过四皇后问题说明算法的运行过程。

1．递归过程 BACKTRACK

递归过程 BACKTRACK(DATA) 的步骤如下。

(1)   
IF TERM(DATA)RETURN NIL ； 若当前状态 DATA 即为目标，则过程返回空表 NIL 。

(2)   IF DEADEND(DATA)RETURN
FAIL
；若 DATA 为不合法状态，则过程返

回 FAIL ，必须回溯。

(3)   
RULES:=APPRULES(DATA)； 得到 DATA 的可应用规则集， 并依某种原则( 任意排列或按某种启发式准则) 排列后赋给规则集变量 RULES。

(4)   LOOP：IF NULL(RULES)RETURN FAIL ；若 RULES 为空集合，即 DATA

没有任何规则可用， 规则用完却未找到目标， 则过程返回 FAIL ，必须回溯。

(5)   R:=FIRST(RULES)；取 DATA 的头条可应用规则 R 作为当前调用的规则 。

(6)    
RULES:=TAIL(RULES)； 从 RULES 中删去头条规则，减少可应用规则表的长度。

(7)  
RDATA:=GEN(R，DATA)； 调用规则 R 作用于当前状态 DATA ，生成新状态 RDATA 。

(8)  
PATH:=BACKTRACK(RDATA)； 对新状态递归调用本过程，得到当前解路径表 PATH 。

(9)     IF PATH=FAIL      GO LOOP ； 当 PATH=FAIL 时，递归调用失败，即从

RDATA 出发不能到达目标，则转移调用另一规则进行测试。

(10)     
RETURN CONS(R ，PATH)； 过程返回解路径规则表( 或局部解路径子表) ，CONSCONS(X ，Y) 返回将状态 X 加到一个表
Y 的前头而得到的表。

这个简单的 BACKTRACK
过程只设置两个回溯点 ， 第(2)
步是处理不合法状态的回溯点，而第(4)
步是处理全部规则应用均失败时的回溯点。若处在递归调用过程期间

・92 ・

第 5 章   搜索原理

失败，过程会回溯到上一层继续运行， 而在最高层失败则整个过程宣告失败退出。构造成功结束时的规则表在第(10) 步完成。算法第(3)步实现可应用规则的排序，可以是固定排序或根据启发信息排序。下面以四皇后问题为例来说明算法的运行过程。

2. BACKTRACK 举例――四皇后问题

在一个 4×4 
的国际象棋棋盘上，一次一个 棋子 地摆布四枚皇后棋子，摆好后要满足每行、每列和对 角 线上只允许出现一枚棋子，即棋子间不许相互俘获。图

5.2  给出棋盘的几个势态，其中(a) 、(b) 满足目 标条件 ，(c) 、(d) 和(e) 为不合法状态 ， 即不可能成 为 满足目标条件的中间势态。

(
a )                          (b )                       (c )                        (d )                        (e )

 

图 5.3 四皇后问题棋盘的几个势态

 

综合数据库 ： DATA={ij | 1≤i ， j≤4} 。DATA 非空时， 其表元素表示棋子所在的行和列。因只有 4 个棋子，
所以 表元素个数最多为 4 。
如图 5.3 所示 ，(a) ，(b) 分别记为(12 ， 24 ， 31 ， 43) 和(13 ， 21 ， 34 ， 42) ，(c) ，(d) ，(e) 分别记为(11 ，21) ， (11 ， 22) ，(11 ， 23 ， 31) 。

规则集： IF 1≤i≤4       且   LENGTH (
DATA)= i