人工智能之状态空间搜索

《人工智能之状态空间搜索》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、人工智能原理(符号计算科学)PrinciplesofArtificialIntelligence第四章：状态空间搜索Chapter04SearchinStateSpaces§01Three-S的基本思想Section01theEssentialsofThree-S§01Three-S的基本思想1.1所谓状态空间搜索：机器的一种思维方式模拟人的问题球解过程，模拟人的思维或逻辑推理，是人工智能，特别是符号计算学的重要任务。人工智能的问题求解方法，是人的思维和逻辑推理的形式化，是机器或计算机的思维和逻辑推理。状态空间搜索(TheSea

2、rchinStateSpaces,Three-S)是一种问题求解策略，是一种模拟人的问题球解过程的人工智能方法，是机器的一种思维方式或逻辑推理方式。§01Three-S的基本思想1.2事物的特性变化的和运动的事物有事物的特性。事物既有内在特性又有外在特性，内在特性通常表现为事物固有的和本质的特征，而外在特性通常表现为事物与环境的关系。事物的特性是在不断地变化的，或不断地运动的，因而，被称为动态特性。事物特性的变化或运动必定是在一定的时间和空间中发生的。§01Three-S的基本思想1.3事物特性的可操作性事物特性问题性质在问题

3、求解活动中，事物的特性代表着问题的性质，事物特性的变化意味着问题性质的变化。在状态空间搜索策略中，事物的特性称为事物的状态，状态随时间变化或运动，而状态运动的空间，就是状态空间。因此，状态空间中状态的运动，意味着事物特性的变化，意味着问题性质的变化。重要的是，这种运动是可以通过对事物进行操作来控制的。§01Three-S的基本思想1.4状态是问题的性质问题求解过程搜索过程关于状态空间搜索(Three-S)：状态(State)：状态空间中的点，代表问题的性质；问题原态对应的状态称为初始状态，问题终态所对应的状态称为目标状态。状态

4、空间(StateSpace)：所有可能的状态的集合。状态空间搜索(SearchinStateSpace)：在状态空间中搜寻一条由初始状态到目标状态的路径的过程，即问题求解的过程。§01Three-S的基本思想1.4状态是问题的性质问题求解过程搜索过程关于状态空间搜索(Three-S)：状态空间问题原态问题终态过渡状态操作：改变问题状态的措施问题的解：一条由初始状态至目标状态的路径。问题求解的过程：搜索由初始状态至目标状态的路径的过程。§02Three-S问题的描述Section02RepresentationsofProble

5、msinThree-S§02Three-S问题的描述2.1Three-S问题的形式化定义：状态空间搜索中的问题被定义为一个四元组：其中：S,O,s(o),s(g)(4.1)(1)S={s}：状态空间(状态的集合)(2)O={O}：算子空间(操作的集合)(3)s(o)S：初始状态(4)s(g)S：目标状态应用O中的算子(操作)对s(o)进行操作(运算)，使其运动至目标状态s(g)的过程称为问题(4.1)的求解。§02Three-S问题的描述2.2Three-S问题的三要素s(o)和s(g)以及O(1)初始状态

6、(OriginalState)：s(o)=(s1,s2,…,sn)(o)S(问题原态的描述)(2)目标状态(GoalState)：s(g)=(s1,s2,…,sn)(g)S(问题终态的描述)(3)操作(又称算子，Operator)：O:SS或：s(j)=O(s(i))(s(i),s(j)S;OO)§02Three-S问题的描述2.3Three-S问题描述示例八数码问题：一个如图所示的33棋格中放置有八个数码：12345678，其中，有一个棋格是空格，邻近的数码可以通过左移、右移、上移、下移，移动进入空棋格

7、。八数码问题就是将给定的八数码初始棋谱变换为要求的八数码目标棋谱的问题。§02Three-S问题的描述2.3Three-S问题描述示例八数码问题：一个如图所示的33棋格上，将给定的八数码初始棋谱变换为要求的八数码目标棋谱，例如：初始状态so目标状态sg§02Three-S问题的描述2.3Three-S问题描述示例八数码问题：状态(State)八数码问题状态空间S中可能的状态数：9!状态的编码或表达方法：(1)向量编码s=(s1,s2,s3,s4,s5,s6,s7,s8,s9)S初始状态：s(o)=(1,2,3,4,0,5

8、,6,7,8)目标状态：s(g)=(0,1,2,4,5,3,6,7,8)§02Three-S问题的描述2.3Three-S问题描述示例八数码问题：状态(State)状态的编码或表达方法：(2)矩阵编码：初始状态目标状态§02Three-S问题的描述2.3Thre