第二讲_知识表示_3.状态空间&问题归约表示法

《第二讲_知识表示_3.状态空间&问题归约表示法》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、2021/7/151人工智能原理第二讲知识表示之状态空间/问题归约表示主讲：王祖喜zuxiw@163.com华中科技大学图像所2021/7/152知识的表示方法谓词逻辑法状态空间法问题归约法语义网络法框架表示法面向对象表示剧本(script)表示过程(procedure)表示小结2021/7/153§状态空间法问题求解(problemsolving)是个大课题，它涉及归约、推断、决策、规划、常识推理、定理证明和相关过程的核心概念。在分析了人工智能研究中运用的问题求解方法之后，就会发现许多问题求解方法是采

2、用试探搜索方法的。也就是说，这些方法是通过在某个可能的解空间内寻找一个解来求解问题的。这种基于解答空间的问题表示和求解方法就是状态空间法，它是以状态和算符(operator)为基础来表示和求解问题的。2021/7/154问题求解技术两个主要的方面问题的表示：如果描述方法不对，对问题求解会带来很大的困难求解的方法：采用试探搜索方法。2021/7/155状态空间法三要点状态（state）：表示问题解法中每一步问题状况的数据结构；算符（operator）：把问题从一种状态变换为另一种状态的手段；状态空间方法：

3、基于解答空间的问题表示和求解方法，它是以状态和算符为基础来表示和求解问题的。2021/7/1561.问题状态描述要完成某个问题的状态描述，必须确定三件事：1.该状态描述方式，特别是初始状态描述；2.操作符集合及其对状态描述的作用；3.目标状态描述的特性。2021/7/157定义:状态(state)：为描述某类不同事物间的差别而引入的一组最少变量q0，q1，…，qn的有序集合，其矢量形式如下：式中每个元素qi(i=0,1，…，n)为集合的分量，称为状态变量。2021/7/158给定每个变量的一组值就得到一

4、个具体的状态，如Qk=[q0k，q1k，...，qnk]T它只是问题所有可能状态的罗列，还必须描述这些状态之间的可能变化。所谓操作，或称为算子是引起状态中的某分量发生改变，从而使问题由一个具体状态A变化为另一具体状态B的作用。2021/7/159算符：使问题从一种状态变化为另一种状态的手段称为操作符或算符。操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。问题的状态空间(statespace)：是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合S(初始

5、状态S0∈S)、操作符集合F以及目标状态集合G(GS)。可把状态空间记为三元状态(S，F，G)。状态空间可用有向图来表示2021/7/1510状态空间的一个解使一个有限的操作算子序列，它使初始状态转化为目标状态：S0-f1->S1-f2->...fk->G2021/7/1511状态空间表示详释让我们先用数码难题(puzzleproblem)来说明状态空间表示的概念。由15个编有1至15并放在4×4方格棋盘上的可走动的棋子组成。棋盘上总有一格是空的，以便可能让空格周围的棋子走进空格，这也可以理解为移动空

6、格。图中绘出了两种棋局，即初始棋局和目标棋局，它们对应于该下棋问题的初始状态和目标状态。如何把初始棋局变换为目标棋局呢？问题的解答就是某个合适的棋子走步序列，如"左移棋子12，下移棋子15，右移棋子4，…"等等。2021/7/1512（a）初始棋局（b）目标棋局十五数码难题1410213685712311549111514131211109876543212021/7/1513总状态为16!＝20922789888000由于棋盘的对称性，实际状态数减半上、下、左、右移动四种操作2021/7/1514十五

7、数码难题最直接的求解方法是尝试各种不同的走步，直到偶然得到该目标棋局为止。这种尝试本质上涉及某种试探搜索。从初始棋局开始，试探(对于一般问题实际上是由计算机进行计算和执行的)由每一合法走步得到的各种新棋局，然后计算再走一步而得到的下一组棋局。这样继续下去，直至达到目标棋局为止。把初始状态可达到的各状态所组成的空间设想为一幅由各种状态对应的节点组成的图。这种图称为状态图。图中每个节点标有它所代表的棋局。首先把适用的算符用于初始状态，以产生新的状态；然后，再把另一些适用算符用于这些新的状态；这样继续下去，直

8、至产生目标状态为止。部分状态图为：2021/7/15151410213685712311549111410213685712311549111410213685712431159111410213685712311549111410213657128311549111410213685712431159111410213685712431159111410213857612311549112021/7/1516我们一般用状态空间法这一术语来