3.2产生式系统的搜索(控制)策略 3.2.1产生式系统控制策略分类 可分解的产生式系统 控制策略可划分为两大类 不可撤回方法r回溯方法 L试探性方法一1 图搜索方法 第3章产生式系统及其搜索方法
第3 章 产生式系统及其搜索方法 3.2 产生式系统的搜索(控制)策略 3 . 2 . 1 产生式系统控制策略分类 可分解的产生式系统 控制策略可划分为两大类: ┌不可撤回方法 ┌回溯方法 └试探性方法─ ┤ └图搜索方法
3.2产生式系统的搜索(控制)策略 3.2.2不可撤回方法 这种方法相当于沿着单独一条路搜索下去,利用问题给 出的局部知识决定如何选取规则,就是说根据当前可靠的局 部知识选一条可应用规则并作用于当前综合数据库。接着 再根据新状态继续选取规则,搜索过程一直进行,不必考虑 撤回用过的规则。这是由于在搜索过程中如能有效利用局 部知识,即使使用了一条不理想的规则,也不妨碍下一步选 得另一条更合适的规则。这样不撤消用过的规则,并不影响 求到解,只是解序列中可能多了一些不必要的规则。显然这 种策略具有控制简单的优点。 第3章产生式系统及其搜索方法
第3 章 产生式系统及其搜索方法 3.2 产生式系统的搜索(控制)策略 3 . 2 . 2 不可撤回方法 这种方法相当于沿着单独一条路搜索下去, 利用问题给 出的局部知识决定如何选取规则, 就是说根据当前可靠的局 部知识选一条可应用规则并作用于当前综合数据库。接着 再根据新状态继续选取规则, 搜索过程一直进行, 不必考虑 撤回用过的规则。这是由于在搜索过程中如能有效利用局 部知识, 即使使用了一条不理想的规则, 也不妨碍下一步选 得另一条更合适的规则。这样不撤消用过的规则, 并不影响 求到解, 只是解序列中可能多了一些不必要的规则。显然这 种策略具有控制简单的优点
3.2产生式系统的搜索(控制)策略 13.2.2不可撤回方法 爬山法不仅适用于爬山问题,那些目标为极大值,搜索 过程是不断接近目标的单值问题都可应用这一方法。使用不 可撤回策略,虽然不可能对任何状态总能选得最优的规则, 但是如果应用了一条不合适的规则之后,不去撤消它并不排 除下一步应用一条合适的规则,那么只是解序列有些多余的 规则而已,求得的解不是最优解,但控制较简单。此外还应当 指出,一般很难对给定问题构造出任何情况下都能通用的爬 山函数,因而不可撤回的方法具有一定的局限性。 第3章产生式系统及其搜索方法
第3 章 产生式系统及其搜索方法 3.2 产生式系统的搜索(控制)策略 3 . 2 . 2 不可撤回方法 爬山法不仅适用于爬山问题, 那些目标为极大值, 搜索 过程是不断接近目标的单值问题都可应用这一方法。使用不 可撤回策略, 虽然不可能对任何状态总能选得最优的规则, 但是如果应用了一条不合适的规则之后, 不去撤消它并不排 除下一步应用一条合适的规则, 那么只是解序列有些多余的 规则而已, 求得的解不是最优解, 但控制较简单。此外还应当 指出, 一般很难对给定问题构造出任何情况下都能通用的爬 山函数, 因而不 可撤回的方法具有一定的局限性
3.2产生式系统的搜索(控制)策略 323回溯方法 在问题求解过程中,有时会发现应用一条不合适的规则会阻扰或 拖延达到目标的过程。在这种情况下,需要有这样的控制策略:先试一试 某一条规则,如果以后发现这条规则不合适,则允许退回去,另选一条 规则来试。回溯方法不保留完整的搜索树结构,只记住当前工作的一条 路径,回溯就是对这条路径进行修正。 使用回溯策略首要的问题要研究在什么情况下应该回溯,即要确定 回溯条件的问题。其次就是如何利用有用知识进行规则排序,以减少回 溯次数。回溯应发生在以下三种情况: (1)新生成的状态在通向初始状态的路径上已出现过; 2)从初始状态开始,应用的规则数目达到所规定的数 目之后还未找到目标状态这一组规则的数目实际上就是 搜索深度范围所规定的) (3)对当前状态,再没有可应用的规则。 第3章产生式系统及其搜索方法
第3 章 产生式系统及其搜索方法 3.2 产生式系统的搜索(控制)策略 3.2.3 回溯方法 在问题求解过程中, 有时会发现应用一条不合适的规则会阻扰或 拖延达到目标的过程。在这种情况下, 需要有这样的控制策略: 先试一试 某一条规则, 如果以后发现这条规则不合适, 则允许退回去, 另选一条 规则来试。回溯方法不保留完整的搜索树结构, 只记住当前工作的一条 路径, 回溯就是对这条路径进行修正。 使用回溯策略首要的问题要研究在什么情况下应该回溯, 即要确定 回溯条件的问题。其次就是如何利用有用知识进行规则排序, 以减少回 溯次数。回溯应发生在以下三种情况: (1) 新生成的状态在通向初始状态的路径上已出现过; (2) 从初始状态开始, 应用的规则数目达到所规定的数 目之后还未找到目标状态(这一组规则的数目实际上就是 搜索深度范围所规定的); (3) 对当前状态, 再没有可应用的规则
3.2产生式系统的搜索(控制)策略 323回溯方法 搜索深度的设置是一个值得注意的问题,设置太浅,有 可能找不到解;设置太深,有可能导致回溯次数巨增。因而 应根据实际情况来规定搜索范围,先设置适中的深度搜索, 失败时再逐步加深。 回溯过程是一种可试探的方法,从形式上无论是否存 在对选择规则有用的知识,都可以采用这种策略。即如果没 有有用的知识来引导规则选取,那么规则可按任意方式固 定排序或随机选取;如果有好的选择规则的知识可用,那么 用这种知识来引导规则选取,就会减少盲目性,降低回溯次 数,甚至不回溯就能找到解,总之一般来说有利于提高效率 此外由于引入回溯机理,可以避免陷入局部极大值的情况, 继续寻找其他达到目标的路径。 第3章产生式系统及其搜索方法
第3 章 产生式系统及其搜索方法 3.2 产生式系统的搜索(控制)策略 3.2.3 回溯方法 搜索深度的设置是一个值得注意的问题, 设置太浅, 有 可能找不到解; 设置太深, 有可能导致回溯次数巨增。因而 应根据实际情况来规定搜索范围, 先设置适中的深度搜索, 失败时再逐步加深。 回溯过程是一种可试探的方法, 从形式上无论是否存 在对选择规则有用的知识, 都可以采用这种策略。即如果没 有有用的知识来引导规则选取, 那么规则可按任意方式(固 定排序或随机)选取; 如果有好的选择规则的知识可用, 那么 用这种知识来引导规则选取, 就会减少盲目性, 降低回溯次 数, 甚至不回溯就能找到解, 总之一般来说有利于提高效率。 此外由于引入回溯机理, 可以避免陷入局部极大值的情况, 继续寻找其他达到目标的路径