资源描述：
《基于搜索的问题求解之盲目搜索》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第二章基于搜索的问题求解——一种在图中寻找路径的方法。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.2831476581324765八数码魔方§2.1搜索与人工智能的关系初始节点S0目标节点SgEvaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004
2、-2011AsposePtyLtd.状态空间表示状态（State）的基本概念状态(state)是为描述某类不同事物间的差别而引入的一组最少变量q0，q1，…，qn的有序集合，其矢量形式如下：Q=[q0,q1,…,qn]T(1)式中每个元素qi(i=0,1，…，n)为集合的分量，称为状态变量。给定每个分量的一组值就得到一个具体的状态，如Qk=[q0k,q1k,…，qnk]T(2)Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.
3、0.Copyright2004-2011AsposePtyLtd.例如，八数码魔方中，一个具体的状态集合Q中，Q0是而Qk是2831476581324765Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.问题求解技术主要是两个方面：问题的表示求解的方法Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5Client
4、Profile5.2.0.0.Copyright2004-2011AsposePtyLtd.问题的状态空间(statespace)是一个表示该问题全部可能状态及其关系的图，它包含三种说明的集合，即所有可能的问题初始状态集合S、算符集合F以及目标状态集合G。因此，可把状态空间记为三元状态(S，F，G)。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.算符：使问题
5、从一种状态变化为另一种状态的手段称为操作符或算符。操作符可为走步、过程、规则、数学算子、运算符号或逻辑符号等。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.例如，例子中的八数码魔方问题就可以用三元状态空间表示为（S0，F，Sg）其中，S0代表初始状态，Sg代表目标状态，而F就是所有能将初始状态变化为目标状态的算符集合。Evaluationonly.Creat
6、edwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.举例：012x012y迷宫问题Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.整个迷宫问题的知识表示是如书上第10页的图2.3，这是一种状态图知识表示法。问题是：机器人位于迷宫入口(0，0)处，如何到
7、达迷宫的出口(2，2)。解：问题空间的初始状态是节点(0,0),而目标状态是节点(2,2)。从图2.3可见，从(0,0)到(2,2)需经过(U，R，R，U)算符集合的操作，因此本问题的解用三元状态集合表示为：{(0,0),(U,R,R,U),(2,2)}Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyLtd.与图有关的术语状态空间图——由节点(不一定是有限的节点)及连
8、接节点的分枝的集合构成。有限节点图——节点数目有限的图称为有限节点图。有向图——一对节点用分枝线连接起来，从一个节点指向另一个节点。这种图叫做有向图。始节点叫父节点或双亲节点，终节点叫子节点。Evaluationonly.CreatedwithAspose.Slidesfor.NET3.5ClientProfile5.2.0.0.Copyright2004-2011AsposePtyL
