3.2产生式系统的搜索(控制)策略 323回溯方法 可用递归算法描述回溯策略: YX0:选择一条新路径搜索; YⅪ1:搜索已超出规定指标(无新路径、超时超深度等),失败退出; 否则搜索继续; YX2:搜索的状态找不到可用规则,回溯到YX0; YX3:搜索的状态依某种原则(任意排列或按启发式准则)取有用规则; YX4:若规则用完未找到目标,回溯YX0; YX5:取头条可用规则Ri; YX6:删去头条规则减少搜索中规则集长度(注意,这不动原始规则 集) YX7:规则R作用于当前状态,生成新状态; YX8:若找到目标,成功退出;若生成的新状态已出现过回溯到 YXO YX9:记录新状态对新状态递规调用YX1~YX7; 第3章产生式系统及其搜索方法
第3 章 产生式系统及其搜索方法 3.2 产生式系统的搜索(控制)策略 3.2.3 回溯方法 可用递归算法描述回溯策略: YX0: 选择一条新路径搜索; YX1: 搜索已超出规定指标(无新路径、超时, 超深度等), 失败退出; 否则搜索继续; YX2: 搜索的状态找不到可用规则, 回溯到YX0; YX3: 搜索的状态依某种原则(任意排列或按启发式准则)取有用规则; YX4: 若规则用完未找到目标, 回溯YX0; YX5: 取头条可用规则Ri; YX6: 删去头条规则, 减少搜索中规则集长度(注意, 这不动原始规则 集); YX7: 规则Ri作用于当前状态, 生成新状态; YX8: 若找到目标, 成功退出; 若生成的"新状态"已出现过, 回溯到 YX0; YX9: 记录新状态, 对新状态递规调用YX1～YX7;
人3.3图搜索算法 产生式系统求解问题时,如果控制系统 保留所有规则应用后生成并链接起来的状态 记录图,则称工作在这种方式下的控制系统 使用了图搜索策略。实际上图搜索策略是实 现从一个隐含图中,生成一部分确实含有一个 目标节点的显式表示的子图搜索过程。 第3章产生式系统及其搜索方法
第3 章 产生式系统及其搜索方法 产生式系统求解问题时, 如果控制系统 保留所有规则应用后生成并链接起来的状态 记录图, 则称工作在这种方式下的控制系统 使用了图搜索策略。实际上图搜索策略是实 现从一个隐含图中, 生成一部分确实含有一个 目标节点的显式表示的子图搜索过程。 3 . 3 图搜索算法
人3.3图搜索算法 13.3.1一般性图搜索算法 步骤1G←S,OPEN←(S);建立一个搜索图G,它只含有 初始节点S,建立一个OPEN表(今后它用于存储生成的节点) 开始它只含有初始节点S 步骤2 CLOSED←(;建立一个 CLOSED表(今后它用 于存储已扩展节点或将要扩展的某个节点,它的初始状态 为空表 步骤3LOOP: if oPEn=() then return fall;进入循环。 如果OPEN表已空,说明没有节点可扩展,就返回FAI,即 失败 步骤4n← FIRST(OPEN, CLOSED←(n, CLOSED); 从OPEN表中取出一个节点n,将其放入 CLOSED表中。 第3章产生式系统及其搜索方法
第3 章 产生式系统及其搜索方法 3 . 3 图搜索算法 3. 3 . 1 一般性图搜索算法 步骤1 G←S,OPEN←(S); 建立一个搜索图G,它只含有 初始节点S, 建立一个OPEN表 (今后它用于存储生成的节点), 开始它只含有初始节点S。 步骤2 CLOSED←( ); 建立一个CLOSED表(今后它用 于存储已扩展节点或将要扩展的某个节点), 它的初始状态 为空表。 步骤3 LOOP: if OPEN=( ) then return FAIL; 进入循环。 如果OPEN表已空, 说明没有节点可扩展, 就返回FAIL, 即 失败。 步骤4 n←FIRST(OPEN), CLOSED←(n, CLOSED); 从OPEN表中取出一个节点n, 将其 放入CLOSED表中
人3.3图搜索算法 232典型的非启发式图搜索算法分析与改进 N广度优先搜索法 该方法从初始节点开始,序扩展生成下一级各子节点, OPEN表中已有的节点后面(实现先生成的子节点先扩展), 然后从OPEN表中提取最前的一个节点检查是否是目标节 点,否则再扩展,再重复上述操作。这种方法认为同一级 各节点对问题求解的价值是同等的,因而对全部节点沿广 度进行横向扫描,按各节点生成的先后次序先生成、先检 查、先扩展,沿广度遍历所有节点。 这种方法只要问题有解,即若树图上存在目标节点, 经搜索一定能找到。所以,广度优先搜索法是完备的,是 种推理算法。但是,在问题大节点多,且目标节点距离初 始节点较远时将会产生许多无用节点,搜索效率低,还可能 产生组合爆炸。因此,这种方法较适宜问题不大的环境中 第3章产生式系统及其搜索方法
第3 章 产生式系统及其搜索方法 3 . 3 图搜索算法 3.3.2 典型的非启发式图搜索算法分析与改进 广度优先搜索法 该方法从初始节点开始, 序扩展生成下一级各子节点, OPEN 表中已有的节点后面(实现先生成的子节点先扩展), 然后从OPEN 表中提取最前的一个节点检查是否是目标节 点, 否则再扩展, 再重复上述操作。 这种方法认为同一级 各节点对问题求解的价值是同等的, 因而对全部节点沿广 度进行横向扫描, 按各节点生成的先后次序,先生成、先检 查、先扩展, 沿广度遍历所有节点。 这种方法只要问题有解, 即若树图上存在目标节点, 经搜索一定能找到。所以, 广度优先搜索法是完备的, 是一 种推理算法。但是, 在问题大节点多, 且目标节点距离初 始节点较远时将会产生许多无用节点, 搜索效率低, 还可能 产生组合爆炸。因此, 这种方法较适宜问题不大的环境中
人3.3图搜索算法 332典型的非启发式图搜索算法分析与改进 深度优先搜索法 该方法从初始节点开始,顺序扩展生成下一级各子节点放在 OPEN表中已有的节点前面(实现后生成的子节点先扩展,然后从 OPEN表中提取最前的一个节点检查是否是目标节点,否则再扩 展,再重复上述操作。这种方法每一次扩展最晚生成的子节点, 沿着最晚生成的子节点分支,逐级纵向深入发展。 这种方法搜索一旦进入某个分支,就将沿着该分支一直向下搜 索。如果目标节点恰好在此分支上,则可较快地得到解。但是, 如果目标节点不在此分支上,不回溯就不可能得到解。所以,深 度优先搜索是不完备的,只是推理步骤。如果回溯,不难证明其平 均效率与广度优先搜索法相同。因此,深度优先搜索法如果没有 启发信息,很难有实用价值。 第3章产生式系统及其搜索方法
第3 章 产生式系统及其搜索方法 3 . 3 图搜索算法 3.3.2 典型的非启发式图搜索算法分析与改进 深度优先搜索法 该方法从初始节点开始, 顺序扩展生成下一级各子节点,放在 OPEN表中已有的节点前面(实现后生成的子节点先扩展), 然后从 OPEN 表中提取最前的一个节点检查是否是目标节点, 否则再扩 展, 再重复上述操作。这种方法每一次扩展最晚生成的子节点, 沿着最晚生成的子节点分支, 逐级纵向深入发展。 这种方法搜索一旦进入某个分支, 就将沿着该分支一直向下搜 索。 如果目标节点恰好在此分支上, 则可较快地得到解。但是, 如果目标节点不在此分支上, 不回溯就不可能得到解。所以, 深 度优先搜索是不完备的, 只是推理步骤。如果回溯, 不难证明其平 均效率与广度优先搜索法相同。因此, 深度优先搜索法如果没有 启发信息, 很难有实用价值