第三章知识的状态空间表示法

第三章 知识的状态空间表示法 1 课前思考： 人类的思维过程，可以看作是一个搜索的过程。 某个方案所用的步骤是否最少？也就是说它是最优的吗？如果不是，如何才能找到最优的方案？在计算机上又如何实现这样的搜索？这些问题实际上就是本章我们要介绍的搜索问题。 2 学习目标： 掌握回溯搜索算法、深度优先搜索算法、宽度优先搜索算法和 A 搜索算法，对典型问题，掌握启发式函数的定义方法。 3 学习指南： 了解算法的每一个过程和细节问题，掌握一些重要的定理和结论，在有条件的情况下，程序实现每一个算法，求解一些典型的问题。 4 难重点： 回溯搜索算法、 算法及其性质、改进的Ａ＊算法。 5 知识点： 本章所要的讨论的问题如下： 有哪些常用的搜索算法。 问题有解时能否找到解。 找到的解是最佳的吗？ 什么情况下可以找到最佳解？ 求解的效率如何。 3.1 状态空间表示知识 一、状态空间表示知识要点 1．状态 状态（State）用于描述叙述性知识的一组变量或数组，也可以说成是描述问题求解过程中任意时刻的数据结构。通常表示成： Q={q1，q2，……，qn} 当给每一个分量以确定的值时，就得到一个具体的状态，每一个状态都是一个结点（节点）。实际上任何一种类型的数据结构都可以用来描述状态，只要它有利于问题求解，就可以选用。 2．操作（规则或算符） 操作（Operator）是把问题从一种状态变成为另一种状态的手段。当对一个问题状态使用某个可用操作时，它将引起该状态中某一些分量发生变化，从而使问题由一个具体状态变成另一个具体状态。操作可以是一个机械步骤、一个运算、一条规则或一个过程。操作可理解为状态集合上的一个函数，它描述了状态之间的关系。通常可表示为： F={ f1 , f2,……… fm} 3．状态空间 状态空间（State Space）是由问题的全部及一切可用算符（操作）所构成的集合称为问题的状态空间。用三元组表示为： （{Qs}，{F}，{Qg}） Qs：初始状态，Qg：目标状态，F：操作（或规则）。 4．状态空间（转换）图 状态空间也可以用一个赋值的有向图来表示，该有向图称为状态空间图，在状态空间图中包含了操作和状态之间的转换关系，节点表示问题的状态，有向边表示操作。 二、状态图搜索 1.搜索方式 用计算机来实现状态图的搜索，有两种最基本的方式：树式搜索和线式搜索。 2.搜索策略 大体可分为盲目搜索和启发式（heuristic）搜索两大类。 搜索空间示意图 例 3.1 钱币翻...