《人工智能第三章讲解》由会员分享，可在线阅读，更多相关《人工智能第三章讲解（85页珍藏版）》请在金锄头文库上搜索。
1、 第三章 产生式系统的搜索策略 回溯策略 图搜索策略：无信息的图搜索 启发式的图搜索 *1 产生式系统的费用 信息（知识 ） 完备信息0 无信息 计算费用 控制费用 规则应用费用 产生式系统费用 Date2 3.1 回溯策略 Date3 一、回溯算法BACKTRACK 算法中用到的部分变量、常量、谓词、函数： 变量： DATA，RDATA：状态变量 RULES, PATH ： 表变量 常量： NIL: 空表 -LISP语言中的常量，也可用（） 谓词： TERM(DATA): DATA满足结束条件时，为真 DEADEND(DATA):DATA不在解路上，为真（往下到达目标的可能性来定义这个谓词：
2、若 从 DATA当前状态往下走到达目标的可能性很小时，则放弃这个状态 ） NULL(X): 表X为空表时，为真 函数： APPRULES(DATA): 将DATA所有可用规则进行排序所得到的表 FIRST(X): 取表的头 TAIL(X): 取表的尾 CONS(E, X):将加入表前 Date4 BACKTRACK过程 Recursive Procedure BACKTRACK（DATA） 1if TERM（DATA），return NIL； 2if DEADEND（DATA），return FAIL； 3RULESAPPRULES（DATA）； 4 LOOP：if NULL（RULES），r
3、eturn FAIL； 5 RFIRST（RULES）； 6 RULESTAIL（RULES）； 7 RDATAR（DATA）； 8 PATHBACKTRACK（RDATA）； 9 if PATHFAIL，go LOOP； 10. return CONS（R，PATH）. Date5 带来的问题及解决方案 若DEADEND定义不好，则无限产生新的非终止的状态描述。 （既不成功又不失败的节点） 解决方案：设置门槛数，即搜索深度BOUND，当递归调用超 过这个深度时return FAIL，引起回溯。 程序中只有DATA和RDATA，回溯过程中将生成的状态都丢 弃了，有可能陷入循环，重复地产生一系列
4、非终止状态。 （实质属于情况(1)） 解决方案： 在过程中保存一个状态描述表DATALIST：记录从初始状态到 当前状态路径上的所有状态-递归变量变成DATALIST，取表 头为DATA 。 加比较：当产生新状态RDATA时，比较是否为DATALIST中 的一个状态（在这个表中），若是，则return FAIL，引起回溯 ，选择其它的Rule。 Date6 四皇后问题：4枚皇后放在44的国际象棋棋盘上，如何放置使 得它们不能相互俘获。 俘获：同行；同列；同对角线 二、回溯策略例四皇后问题 其中a，b满足目标条件， c，d，e为不可能构成满足目标条件的中间状态 。 Date7 综合数据库：以状态
5、为节点的有向图 状态：44矩阵 初始状态： 空矩阵 规则：Rij:if i=1时，矩阵中无皇后标志，或4 i 1时，矩阵的i-1 行有一个皇后标志，then在矩阵的第i行第j列放一个皇后标记 结束条件：TERM为真矩阵中有4个皇后标志，且不能相互俘获 控制策略：回溯 DEADEND(DATA): DATA中存在1对皇后相互俘获，为真 APPRULES(RULES): Rij排在Rik之前jk Date8 1 2 43 5 6789 10 11 12 1314 1516 1718 19 2021 22 23 24 252627 28 NIL Date9 四皇后问题 存在的问题：回溯的次数很多，2
6、2次回溯。 原因：没有关于问题的探索性信息指导规则排序。 解决方法之一：在规则排序过程中使用一些探索性信 息，减少回溯次数，提高算法效率 例：使用函数 diag(i, j)来修改APPRULES(RULES) diag(i, j)：通过单元（i，j）的最长对角线的长度 修改后的 APPRULES(RULES): if diag（i，j）diag（i，k）,then Rij排在Rik前 if diag（i，j）= diag（i，k），then与以前相同 Rij排在Pik之前jk Date10 课堂练习： l请请用回溯搜索策略BACKTRACK求解四皇 后问题问题 ，要求规则规则 排序使用对对角函
7、数diag(i, j)。如果diag(i, j)diag(i, k)，则则在排序中把 Rij放在Rik的前面；如果diag(i, j)=diag(i, k) ，jBOUND, return FAIL； s7 RDATALISTCONS(RDATA,DATALIST）； s8 PATHBACKTRACK1（RDATALIST） Date12 两层以上的回溯 Date13 3.2 图搜索策略 Date14 一、相关概念 有向图 ：G=(P,A)，P:点集 A:弧集 弧:两点间有方向的线。 如果有一条弧从节点ni出发指向nj；则节点nj称为节 点ni的子节点，节点ni称为节点nj的父亲节点 对于产生
8、式系统， 节点：用状态描述标记 弧：用规则标记 假定图中的每一个节点只有有限个子节点。 Date15 路：节点序列(ni0, ni1,，nik)称为从节点ni0到节点 nik的一条长度为k的路径，其中，对于j=1，k ，每一个nij都是nij-1的子节点。 如果存在一条从节点ni到节点nj的路径，则节点nj称 做是从节点ni出发可达到的，节点nj称做节点ni的后 裔，节点ni称做是节点nj的祖先。 解路径： 从初始节点到一个满足终止条件节点 的路径。 图搜索策略把寻找从初始状态描述到目标描述 的规则序列问题转化成寻找有向图的解路径问 题 Date16 有向树：每一个节点最多只有一个父亲的有向图
9、 根节点：有向树中没有父节点的节点 叶节点：有向树中没有子节点的节点 有向树中节点的深度: 1) 根节点的深度是0， 2)其它节点的深度等于它父节点的深度加1。 Date17 加权有向图（权图）： 每条弧线上都有使用费用（正数）的图。 例：从节点ni到节点nj的有向孤的费用：C(ni, nj) 路径的费用:路径上所有弧费用的和 两节点间具有最小费用的路径：是此两节点 间所有弧费用的费用总和最小的一条路。 最佳解路径：费用最小的解路径。 Date18 隐含图：由部分节点和一组其它节点生成规则所确 定的图 图搜索控制策略的目标：从隐含图出发生成一个部 分明确的图，使该明确图中含有目标节点 l图搜索
10、非形式定义 假定：所有隐含图中有向弧的费用大于某一个小的 正数 问题：求隐含图中初始节点s到目标节点集ti中任 意成员的一条具有最小费用的解路径。 Date19 二、一般的图搜索过程GRAPHSEARCH lOPEN表：未扩展的节点 lCLOSED表：已扩展或正在扩展的节点 lG：搜索图，动态变化，部分明确的图 Date20 1Gs， OPEN （s） 2CLOSED NIL 3LOOP：IF OPEN=NIL,THEN FAIL 4 n FIRST(OPEN)，OPEN TAIL(OPEN),CONS(n, CLOSED) 5 IF TERM(n)，THEN 成功结束 （解路径可通过追溯G中
11、从n到s的指针获得）。 6 扩展节点n， 令M=m m是n的子节点，且m不是n的祖先 ， G G M 7 （设置指针，调整指针）对于mM, (1)若mCLOSED, mOPEN, 建立m到n的指针，并CONS(m, OPEN). (2)(a)mOPEN, 考虑是否修改m的指针. (b)mCLOSED,考虑是否修改m及在G中后裔的指针。 8 重排OPEN表中的节点（按某一任意确定的方式或者根据探索信息） 。 9 GO LOOP Procedure GRAPHSEARCH Date21 lNote1:算法结束时， OPEN:树的叶节点 CLOSED:1)非叶节点 2)被选来扩展但无后裔的叶节点 l
12、Note2:如果搜索的隐含图是一棵树， 步骤6和步骤7得以简化： step 6:扩展节点n， 令M=m m是n的子节点 ， G G M step 7:建立m到n的指针，并CONS(m, OPEN). lNote3:如果搜索的隐含图不是树，则需确定是否需要指针修改 。 Date22 3.3 无信息的图搜索过程 若在GRAPHSEARCH的步骤8中对OPEN表 中节点的排序不使用关于问题的探索性信息， 则必须任意规定一种排序方式，所得到的搜索 过程叫作无信息的。 一般有两种无信息的图搜索过程：深度优先 搜索与宽度优先搜索 在人工智能中，一般说来人们对无信息的过 程不感兴趣 Date23 无信息的图
13、搜索过程 l深度优先搜索：排列OPEN表中的节点时按 它们在搜索树中的深度递减排序 。深度最大 的节点放在表的前面，深度相等的节点以任 意方式排序。 l宽度优先搜索：在排列OPEN表中节点时按 它们在搜索图中的深度递增顺序，深度最小 的节点放在表的前面 。 l 8-数码问题例子 Date24 A B F C GED HIJ K L M N O A B F C GED HIJ K L M N OO A B F C GED HIJ K L M N A B F C GED HIJ K L M N O A B F C GED HIJ K L M N O A B F C GED HIJ K L M N
14、O Date25 一个简单二叉树的宽度优先搜索过程 A B F C GED A B F C GED A B F C GED A B F C GED 在每一个阶段，下一个要扩展的节点由箭头指示 出来。 Date26 3.4 启发式图搜索过程 无信息的搜索方式需要产生大量的节点才能 找到解路径。这些节点都需要在内存中保存 起来。由此可见无信息搜索方式所需存储空 间是相当大的。而实际上计算机所能提供的 存储总是有限的，因此我们必须寻找效率更 高的搜索方法。 Date27 启发式搜索 l启发式信息：用于帮助减少搜索量的与问题 有关的信息或知识。 启发式信息用在GRAPHSEARCH的步骤8 中对OPEN表中的节点进行排序，把最有希 望的节点排在最前面，使搜索图沿着有利于 获得解的方向扩展。 l启发式搜索：使用启发信息指导的搜索过程 叫做启发式搜索。 Date28 启发信息强，可以降低搜索的工作量，但可能导致 找不到最优解； 启发信息弱，一般会导致搜索的工作量加大，极端 情况下演变为盲目搜索，但有可能找到最优解。 我们希望，通过引
