人工智能产生式系统的搜索策略

《人工智能产生式系统的搜索策略》由会员分享，可在线阅读，更多相关《人工智能产生式系统的搜索策略（69页珍藏版）》请在金锄头文库上搜索。

1、Artificial Intelligence第三章、产生式系统的搜索策略 3.1 状态空间搜索概述 3.2 回溯策略 3.3 图搜索策略 3.4 盲目的图搜索过程 3.5 启发式图搜索过程 Artificial Intelligence 有两种基本方式：盲目搜索的方法 、启发式搜索. 求任一解路： backtracking、 Hill Climbing、 Breadth-first、 Depth-first、Beam Search、 Best- first . 求最佳解路：British Museum、Branch and Bound 、 Dynamic Programming、A*. 求与

2、或图： AO*、 Minimax、Alpha-beta Pruning 、 Heuristic Pruning.图3-1 搜索空间 在人工智能中，问题求解的基本方法有搜索法、 归约法、归结法、推理法、约束满足法及规划等， 而状态空间搜索则是问题求解的主要方法之一.Artificial Intelligence31 状态空间搜索概述 3.1.1 图的概念 图是节点及连接它们的弧的集合，含两个集合: 节点和弧. 由方向性的弧连接的图是有向图. 节点深度的表示： dn+1=dn+1 路径： N个有序的节点序列中，若每对节点都表示一条 弧，则称该序列为图中长度为N的一条路径。 路径耗散值：令C（ni，

3、nj）为节点ni到节点nj这段路径（ 或弧线）的耗散值，一条路径的耗散值等于连接这条路 径各个节点间所有弧线耗散值的总和。路径耗散值可按 如下的递归公式计算： C（ni，t）=C（ni，nj）+C（nj，t） 节点的扩展：后裔节点的操作符（规则）作用到节点（ 对应于某一状态描述）上，生成出其所有的后继节点（ 新状态），并给出了解弧线的耗散值（相当于使用规则 的代价），这个过程叫做扩展一个节点。 Artificial Intelligence3.1.2 问题状态空间的图描述 问题的状态空间描述中，图是最直观的， 属于显式描述。图的节点表示问题的状态，图 的弧表示状态之间的关系，也就是求解问题的

4、步骤。初始状态对应于实际问题的已知信息， 是图中的根节点。问题的状态空间图描述中， 寻找从一种状态转换为另一种状态的某个操作 算子序列就等价于在一个图中寻找从一种状态 到另一种状态的一条路径。Artificial Intelligence3.1.3 将问题求解定义为状态空间搜索 搜索成为一种求解问题的一般机制，它构成了 AI系统的一种框架，其状态空间法构成了AI方法 的基础，其结构与问题的求解结构相对应： 状态空间法将一个问题形式地定义为用一个三元组中的 操作将某个给定的状态转换为所要求的状态。 状态空间法将一个待定问题的求解过程定义为若干算子 与搜索的有机结合体。一个算子则定义了问题空间的一

5、 个操作，搜索是考察一个问题的一般技术，其目的在于 要找出从当前状态到某个目标状态的一条路径或某些目 标状态的一组路径。Artificial Intelligence为提供对问题的形式描述，需要定义和规定： 1.定义一状态空间。它包含一个问题相关对象的各种 可能的排列。对空间的定义不必枚举其状态空间中 的所有状态。 2.规定一个或多个属于该空间的初始状态。该状态用 以描述问题求解过程开始时的状态。 3.规定一个或多个属于该空间的目标状态。该状态用 以描述问题的解。 4.规定一组规则。它们描述可使用的操作或算子。 将非形式的问题描述转换成状态空间形式描述后 ，便可利用状态空间的搜索方法。应用这一

6、组规则 和相应的控制策略，在问题状态的空间内进行搜索 ，直到找出从一开始状态到一目标状态的某条路径 或某些目标状态的一组路径。 Artificial Intelligence3.1.4 搜索的基本概念 在状态空间中，问题的求解就是搜索，即搜索某 个状态空间以求得由操作算子序列组成的一个解答的 过程，它对应于将一个隐式图的足够大的一部分变为 显式并包含目的节点的过程。这种搜索过程是状态空 间问题求解的主要基础。 搜索的基本问题是： 1）有解? 搜索过程是否一定能找到一个解。 2）终止?搜索过程是否能终止运行或是否会陷入一个死 循环。 3）最佳解? 当搜索过程找到解时，找到的是否是最佳解 。 4）

7、代价?搜索过程的时间与空间复杂性如何。 Artificial Intelligence搜索过程的要点是： 1)从初始或目的状态出发，并将它作为当前状态 。 2)扫描操作算子集合，将适用于当前状态的一些操 作算子作用在其上而得到新的状态，并建立与父 母节点的连接指针。 3)检查所生成的新状态是否满足结束状态，如果满 足，则得解，并可沿着有关指针从结束状态反向 到达开始状态，给出一解答路径；否则，将这新 状态作为当前状态，返回第（2）步再进行搜索 。Artificial Intelligence3.1.5 搜索的策略 通常搜索策略的任务是确定如何选择选取操作 算子的公式，有两种基本方式：盲目搜索和

8、启发 式搜索(无信息搜索和有信息搜索)。 所谓盲目搜索是指在不具有对特定问题的任何有 关信息的条件下，按固定的步骤（依次或随机调 用操作算子）进行搜索，它能很快地运用一个操 作算子； 而启发式搜索则是考虑特定问题领域可应用的知 识，动态地确定调用操作算子的步骤，优先选取 较合适的操作算子，尽量减少不必要的搜索，以 求尽快地到达结束状态，提高搜索效率。Artificial Intelligence 盲目搜索中，由于没有可参考的信息，因此 只要能匹配的操作算子都须运用，这会搜索 出更多的状态，生成较大的状态空间显示图 启发式搜索中，如果具有较多的甚至完整的 启发信息，那么只须运用少量的操作算子，

9、生成较小的状态空间显示图，便可将搜索引 向一个解答，但是每使用一个操作算子要做 更多的计算与判断。 启发式搜索一般要优于盲目搜索，但不可过 于追求更多的甚至完整的启发信息，应综合 考虑，尽量使搜索系统的总开销较小。下图 可说明这个问题。 图3-2、搜索系统的开销 Artificial Intelligence3.2 回溯策略 回溯策略是一种系统地尝试状态空间中各种不 同路径的技术。 带回溯策略的搜索是从初始状态出发，不停地 、试探地寻找路径直到它到达目的或“不可解节 点”“死胡同”。如它遇到不可解节点就回溯 到路径中最近的父节点上，查看该节点是否还 有其他的子节点未被扩展，如有，则沿这些子 节

10、点继续搜索；如果找到目标，就成功退出搜 索，返回解题路径。 可以看出，这种求解过程呈现出递归过程的性 质。求解过程在每个节点上的检查遵循着递归 方式。 Artificial Intelligence递归过程示例：-阶乘函数的递归int factorial (int n) if (n = 1) return 1; else return n * factorial (n - 1); 只要初始值大于零，这个函数就能够终止。停止的位置称 为 基线条件（base case）。基线条件是递归程序的最底 层位置，在此位置时没有必要再进行操作，可以直接返回 一个结果。所有递归程序都必须至少拥有一个基线条件，

11、 而且必须确保它们最终会达到某个基线条件；否则，程序 将永远运行下去，直到程序缺少内存或者栈空间。 Artificial Intelligence一些符号的含义： 变量：DATA=当前状态；RULES=规则集合序列表； R=当前调用规则； RDATA=新生成的状态；PATH= 当前解路径表。 常量： NIL=空表； FAIL=回溯点标记； LOOP=循 环标号； 谓词：TERM(DATA)；DEADEND(DATA)； NULL(RULES)； 函数： APPRULES 求可应用的规则表；FIRST从表 中取表头的一个元素,TAIL除去表头的一个元素后 得到新表； GEN 调用规则生成新状态；

12、CONS 在 表头插入新元素，构造新表；Artificial Intelligence递归过程BACKTRACK(DATA)1. if TERM (DATA), return NIL; 当DATA满足终止条件时， TERM(DATA)为真即找到目标，此时，过程返回空表NIL. 2. if DEADEND (DATA), renturn FAIL 当已知DATA不在解的路 径上时，DEADEND(DATA)为真，即该状态不合法。必须回溯 3. RULES APPRULES(DATA) 可应用的规则表。 4. LOOP: if NULL(RULES), return FAIL; 如果已经没有了可应

13、 用的规则，则回答FAIL, 必须回溯. 5. R FIRST(RULES); 选出头条（最好的）可应用规则。 6. RULES TAIL(RULES); 把刚才选出的规则从规则表中删除， 减少可应用规则表的长度。 7. RDATA GEN（R，DATA）; 把R作用于当前状态。 8. PATHBACKTRACK(RDATA) 对新状态递归调用本过程 9. if PATH =FAIL, go LOOP; 如果递归失败，则用另一条规则 10. return CONS(R,PATH); 否则把R加在规则表中，向上传递成 功的规则表，过程返回解路径规则表（或局部解路径子表）.Artificial I

14、ntelligence举例综合数据库：DATA=L（表），L元素用ij表示，i，j的值域为 1，2，3，4。即L表的元素表示棋子所在的行和列。图3-3 中状态分别记为（12 24 31 43）、（13 21 34 42）、（11 21）、（11 22）、（11 23 31）。四皇后问题：在一个4*4的国际象棋棋盘上，一次一个地摆 布四枚皇后棋子，摆好后要满足每行、每列和对角线上只允 许出现一枚棋子，即棋子间不能相互俘获。图3-3、棋盘的几种状态 Artificial Intelligence共16个规则，每条规则 Rij 表示满足前提条件下 ，在ij处放一个棋子。当规则序列以R11、R12、R

15、13、 R14、R21、R44这种固定的排序方式调用 BACKTRACK时，四皇后问题的搜索示意图如3-4 所示，共回溯22次，主过程结束时返回规则表（ R12、R24、R31、R43）。规则集：Artificial Intelligence图3-4、四皇后问题的固定排序搜索树 Artificial Intelligence作业1： 当规则序列以R11、R21、R31、R41、R12、 R22 、 R32 、 、R44这种固定排序方式调用 BACKTRACK函数时，画出四皇后问题的搜索 树，并标出所有回溯的先后顺序。Artificial Intelligence如果要利用问题有关信息对规则进行

16、动态排序 ，则可定义一个对角线函数Maxdiag（i，j）。该 函数可计算棋盘上ij单元的最长的对角线长度，通 过比较不同单元的Maxdiag（i，j）函数值来决定 Rij的排序。如Maxdiag（i，k）Maxdiag（i，j） ，则为（Rik，Rij），即对角线短的单元，相应的 规则排在前头，若相同，则维持原顺序。按此知 识排列的序列为R12、R13、R11、R14、R21、R24、R22、 R23、R31、 R34、R32、 R33、R42、R43、R41、R44（3 、3、4、4）。这样搜索示意图如图所示，只 回溯2次找到目标。图3-5、四皇后问题的动态排序搜索树 Artificial Intelligence对于可能出现重复状态且搜索深度无限的问题，必须设置深 度范围限制及防止出现重复状态引起的死循环这两个回溯点。 改进的算法如下 BACKTRACK1(DATALIST):： 1 DATA