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

点击打开微信,马上办理ETC
提示打开微信,请点击“允许/是”




人工智能: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)   LOOPIF NULL(RULES)RETURN FAIL ;若 RULES 为空集合,即 DATA


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


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


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


(7)  
RDATA:=GEN(RDATA); 调用规则 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) 为不合法状态 , 即不可能成 为 满足目标条件的中间势态。





文本框: 	Q	
		Q
Q		
	Q

文本框: 	Q	
Q		
		Q
	Q

文本框: Q		
Q

文本框: Q		
	Q

文本框: Q		
	Q	
Q		
	Q


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


 


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


 


综合数据库 DATA={ij | 1i j4} 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 1i4       且   LENGTH (
DATA)= i

点击打开微信,马上办理ETC


ETC注销ETC充值ETC客服ETC扣费查询


ETC发行合作

发表评论