历史研究记录

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

2018年12月9日历史地图研究

人工智能：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) 。