您好、欢迎来到现金彩票网!
当前位置:彩之网 > 状态空间 >

用状态空间表示表示问题的一般步骤

发布时间:2019-06-12 09:14 来源:未知 编辑:admin

  基本搜索,是一种没有任何经验和知识起作用的、由某种规则所确定的非智能性的搜索;

  启发式搜索(Heuristic Search):其特点在于是一种有准备的、追求效率而有的放矢的智能搜索,它要求依据某种知识及信息的指导,通过逐一状态比较而找到符合规定条件的目标状态解。

  问题的状态空间可用有向图来表达,又常称其为状态树(State Tree)。图中,节点Sk表示状态,状态之间的连接采用有向弧(Arc),弧上标以操作数OK来表示状态之间的转换关系。

  状态空间图在计算机中有两种存储方式:一种是图的显式存储,另一种是图的隐式存储。

  (5)当状态数量不是很大时,按问题的有序元组画出状态空间图,依照状态空间图搜索求解。

  在河的左岸有三个传教士、一条船和三个野人,传教士们想用这条船将所有的成员都运过河去,但是受到以下条件的限制:

  ② ②在任何岸边野人数目都不得超过传教士,否则传教士就会遭遇危险:被野人攻击甚至被吃掉。

  此外,假定野人会服从任何一种过河安排,试规划出一个确保全部成员安全过河的计划。

  对应右岸野人数为3-c;左岸船数为b,故又有b={0,1},右岸的船数为1-b.

  初始状态一个: S0 =(3,3,1),初始状态表示全部成员在河的左岸;

  目标状态也只一个: Sg =(0,0,0),表示全部成员从河左岸渡河完毕。

  仍然以河的左岸为基点来考虑,把船从左岸划向右岸定义为Pij操作。其中,第一下标i表示船载的传教士数, 第二下标j表示船载的野人数;同理,从右岸将船划回左岸称之为Qij操作,下标的定义同前。则共有10种操作,操作集为

  在这个问题世界中,S0 =(3,3,1)为初始状态,S31 = Sg =(0,0,0)为目标状态。全部的可能状态共有32个,如表所示。

  1)首先可以划去左岸边野人数目超过传教士的情况,即S4、S8、S9、S20、S24、S25等6种状态是不合法的;

  2)应划去右岸边野人数目超过修道士的情况,即S6、S7、S11、S22、S23、S27等情况;

  3)应划去4种不可能出现状态:划去S15和S16——船不可能停靠在无人的岸边;划去S3——传教士不可能在数量占优势的野人眼皮底下把船安全地划回来;划去S28——传教士也不可能在数量占优势的野人眼皮底下把船安全地划向对岸。可见,在状态空间中,真正符合题目规定条件的只有16个合理状态。

  (5)当状态数量不是很大时,按问题的有序元组画出状态空间图,依照状态空间图搜索求解。

  根据上述分析,共有16个合法状态和允许的操作,可以划出传教士和食人者问题的状态空间图,如图所示。

  2. 用所定义的状态描述形式把问题所有可能的状态都表示出来,并确定初始状态和目标状态集合描述。

  3. 定义一组算符,使得利用这些算符可以把问题由一个状态转为另一个状态。

  2、 用所定义的状态描述形式把问题所有可能的状态都表示出来,并确定初始状态和目标状态集合描述

http://pepdeco.com/zhuangtaikongjian/11.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有