2.4 状态空间表示法 课件

状态空间表示法 假设有三枚钱币，开始时，朝上的一面为“正、正、正”状态，规定每次只许翻动一枚钱币，在操作中不能出现相同状态，怎样才能得到“反、反、反”朝上状态？1状态及操作1.状态 描述某类事物在不同时刻所处的信息状况。如三枚钱币朝上的一面有“正、反、正”，“正、正、正”，“反、反、反”等状态。 问题的状态包括三个方面：初始状态、中间状态、目标状态。 （1）初始状态：描述问题求解过程中开始的可能情况的状态。如上述问题的初始状态：“正、正、正”状态。 （2）中间状态：求解问题过程中从开始状态到目标状态之间的状态。 如上述问题的中间状态有如下六种： “正、正、反” “正、反、反” “正、反、正” “反、正、正” “反、正、反” “反、反、正” （3）目标状态：问题解的状态。 如上述问题的目标状态：“反、反、反”状态。2.操作 引起状态中的某些分量发生改变，从而使问题由一个具体状态变化到另一个具体状态的手段称为操作。操作可以用过程、规则、数学式子、运算符号或逻辑符号等表示。上述钱币翻转问题包括以下三个操作：第一个钱币翻转、第二个钱币翻转、第三个钱币翻转。2状态空间表示知识实例 设钱币正面为0，反面为1，则描述这三枚钱币的全部状态有8种：（0，0，0）、（0，0，1）、（0，1，0）、（0，1，1）、（1，0，0）、（1，0，1）、（1，1，0）、（1，1，1）翻钱币有三种操作a：将第一个钱币翻转一次c：将第三个钱币翻转一次b：将第二个钱币翻转一次钱币翻转问题，可简单地用下图表示。（0，0，0）初始状态经过多次操作a、b、c（1，1，1）目标状态 状态空间是利用状态变量和操作符号表示知识的符号系统。本例中，状态用数组（x，y，z）表示，其中状态变量x、y、z取值为“0”（表示钱币正面）或“1”（表示钱币反面）；操作符号用a、b、c表示，它们分别表示对三个钱币的翻转操作。1.三元状态表示钱币翻转问题的状态空间可表示为如下两种形式： 三元状态表示实际上是用规定的符号来表示，如上述钱币翻转问题，可表示为： <{（0，0，0）}，{a，b，c}，{（1，1，1）}> 其中{（0，0，0）}是初始状态，{a，b，c}是全体操作，{（1，1，1）}是目标状态。状态空间表示法可把问题简单地表示为： <初始状态，所有操作，目标状态>2.状态图表示 上述钱币翻转问题可用下图表示，其中圆圈表示状态，连线表示操作。初始状态中间状态目标状态 从上面的图可以看到，可以将第一个、第二个、第三个钱币依次翻转一次，得到目标状态（1，1，1），也可以采取其他顺序，如：先将第二个钱币翻一次，再将第一个钱币翻一次，最后将第三个钱币翻一次，得到目标状态（1，1，1）等等过程，得到目标状态。 状态空间表示法也很直观，而且方便用程序设计语言表达和计算机存储处理，能很方便地通过状态转换表示过程性知识。练习（1）状态空间有_____、_____、_____三种状态。（2）状态空间中的操作是指____________________。