搜索基于状态空间的搜索课件.ppt

《搜索基于状态空间的搜索课件.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章用以搜索状态空间的结构与策略用以搜索状态空间的结构与策略1内容2.0简介2.1图论2.2问题状态空间的表示2.3状态空间搜索的方向2.4一般图搜索2.5常见的盲目式搜索技术2.0简介什么是问题？283710514115964111412123487659101112151413?2.0简介问题（现代认知心理学）：在给定信息和目标状态之间有某些障碍需要加以克服的情境。①给定：有关问题条件的描述，即问题的起始状态；②目标：有关构成问题结论的描述，即问题的目标状态；③障碍：无法直接到达目标，必须通过一定的思维活动才能找到答案，达到目标状态。问题解决（信息

2、加工观点）：就是搜索问题空间，寻找一条从起始状态通向目标状态的通路，或使用算子使起始状态逐步过渡到目标状态。按解决问题所需的领域特有知识的多寡，问题求解系统可以划分为两大类：①知识贫乏系统：依靠搜索技术去解决问题。②知识丰富系统：依靠推理的识别技术解决问题。2.0简介搜索人工智能所研究的对象大多是属于结构不良或非结构化的问题。对于这些问题，一般很难获得其全部信息，更没有现成的算法可供求解使用。只能依靠经验，利用已有知识逐步摸索求解。根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程——搜索。对那些结构性能较好，理

3、论上有算法可依的问题，如果问题或算法的复杂性较高（如按指数形式增长），由于受计算机在时间和空间上的限制，也无法付诸实用。——组合爆炸问题。2.0简介搜索的分类①根据搜索过程是否使用启发式信息盲目搜索：按预定的控制策略进行搜索，在搜索过程中获得的中间信息并不改变控制策略。由于搜索总是按预先规定的路线进行，没有考虑到问题本身的特性，因此这种搜索具有盲目性。启发式搜索：搜索过程中加入与问题有关的启发性信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解过程并找到最优解。②根据问题的表示方式状态空间搜索：基于问题到状态空间表示求解问题所进行的搜索。与／或树搜

4、索：基于问题的与／或树表示利用问题归约法来求解问题时所进行的搜索。第六章内容2.0简介2.1图论2.2问题状态空间的表示2.3状态空间搜索的方向2.4一般图搜索2.5常见的盲目式搜索技术2.1图论例1：从某王姓家族的四代中找王A的后代且其寿命为X的人王A：寿命47，有儿子王B1、王B3、王B2王B1：寿命77，有儿子王C1、王C2王B3：寿命52，有儿子王D1王B2：寿命65，有儿子王E1、王E2王F1：寿命32王G1：寿命96王C2：寿命87，有儿子王F1王D1：寿命77，没有儿子王E1：寿命57，有儿子王G1王E2：寿命92，有儿子王H1王C1：寿命

5、27，没有儿子王H1：寿命512.1图论例1：从某王姓家族的四代中找王A的后代且其寿命为X的人2.1图论例2：哥尼斯堡七桥问题（瑞士数学家-欧拉）2.1图论图节点和连接这些节点的弧的集合。带标签的有向图2.1图论有根图具有一个唯一节点（根），从这个节点到图中所有节点都存在一条路径。2.1图论树两个节点之间最多有一条路径的图。内容2.0简介2.1图论2.2问题状态空间的表示2.3状态空间搜索的方向2.4一般图搜索2.5常见的盲目式搜索技术2.2问题状态空间的表示状态空间表示法用来表示问题及其搜索过程的一种形式化方法。①状态②操作③状态空间⑴什么是状态？状态

6、（State）是表示问题求解过程中每一步问题状况的数据结构：Sk＝｛Sk0，Sk1，…｝对每一个分量给予确定的值时，得到一个具体的状态。任何一种类型的数据结构都可以用来描述状态，只要它有利于问题求解，就可以选用。2.2问题状态空间的表示⑵什么是操作？操作（Operator）——算符当对一个问题状态使用某个可用操作时，它将引起该状态中某些分量值的变化，从而使问题从一个具体状态变为另一个具体状态。操作可以是一个机械步骤、一个运算、一条规则或一个过程。操作可理解为状态集合上的一个函数，它描述了状态之间的关系。State1State2Operator2.2问题状

7、态空间的表示⑶什么是状态空间？状态空间（Statespace）用来描述一个问题的全部状态以及这些状态之间的相互关系。状态空间常用一个三元组表示：（S，F，G）S：为问题的所有初始状态的集合；F：为操作的集合；G：为目标状态的集合。InitialStateMediumState1MediumState2TargetState问题求解过程实际上是一个搜索过程2.2问题状态空间的表示【例2.1】二阶Hanoi问题设有三根钢针，它们的编号分别是1号、2号和3号;在初始情况下，l号钢针上穿有A、B两个金片;A比B小，A位于B的上面;要求把这两个金片全部移到另一根钢

8、针上，而且规定每次只能移动一个金片，任何时刻都不能使大片位于小片的上面。如何将A