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

《人工智能产生式系统的搜索策略》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第三章、产生式系统的搜索策略3.1状态空间搜索概述3.2回溯策略3.3图搜索策略3.4盲目的图搜索过程3.5启发式图搜索过程有两种基本方式：盲目搜索的方法、启发式搜索.求任一解路：backtracking、HillClimbing、Breadth-first、Depth-first、BeamSearch、Best-first.求最佳解路：BritishMuseum、BranchandBound、DynamicProgramming、A*.求与或图：AO*、Minimax、Alpha-betaPrun

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

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

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

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

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

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

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