搜索策略.doc

搜索策略
搜索是人工智能中的一个基本问题,(计算机的50%工作)并与推理密切相关,一个智能系统搜索策略的优劣,将直接影响到该系统的性能与推理效率。(NP- (nondeterministic polynomial)旅行商问题:费用、落地时间、旅途与休息时间、路线安排、约束条件等)
搜索的基本概念
搜索的含义
人工智能所研究的对象大多是属于结构不良(指所需信息不完整)或非结构化(指没有现成的算法可依)的问题。对于这些问题,一般很难获得其全部信息,更没有现成的算法可供求解使用。因此,只能依靠经验,利用已有知识逐步摸索求解(仁者见仁,智者见智)。像这种根据问题的实际情况,不断寻找可利用知识,从而构造一条代价最小的推理路线,使问题得以解决的过程称为搜索。
另一方面,对那些结构性能较好,理论上有算法可依的问题,如果问题或算法的复杂性较高(如按指数形式增长),由于受计算机在时间和空间上的限制,也无法付诸实用。这就是人们常说的组合爆炸问题。例如,64阶梵塔问题有(所需要的存储空间为3,433,683,820,292,512,484,657,849,089,281 。另一个例子,几百年)状态,仅从空间上来看,这是一个任何计算机都无法存储的问题。可见,理论上有算法的问题实际上不一定可解。像这类问题,也需要采用搜索的方法来进行求解。
对于搜索的类型,可根据搜索过程是否使用启发式信息分为盲目搜索和启发式搜索,也可根据问题的表示方式分为状态空间搜索和与/或树搜索。
盲目搜索是按预定的控制策略进行搜索,在搜索过程中获得的中间信息并不改变控制策略。由于搜索总是按预先规定的路线进行,没有考虑到问题本身的特性,因此这种搜索具有盲目性,效率不高,不便于复杂问题的求解。
启发式搜索是在搜索中加入了与问题有关的启发性信息,用于指导搜索朝着最有希望的方向前进,加速问题的求解过程并找到最优解。
状态空间搜索是指用状态空间法来求解问题所进行的搜索。
与/或树搜索是指用问题归约法来求解问题所进行的搜索。
状态空间法和问题归约法是人工智能中最基本的两种问题求解方法,状态空间表示法和与/或树表示法则是人工智能中最基本的两种问题表示方法。
状态空间法
状态空间法是人工智能中最基本的问题求解方法,它所采用的问题表示方法称为状态空间表示法。状态空间法的基本思想是用“状态”和“操作”来表示并求解问题。
状态空间表示法
在状态空间表示法中,问题是用“状态”和“操作”来表示的,问题求解过程是用“状态空间”来表示的。
(1) 状态
状态(State)是表示问题求解过程中每一步问题状况的数据结构,它可形式地表示为:
Sk={Sk0, Sk1, …}
在这种表示方式中,当对每一个分量都给以确定的值时,就得到了一个具体的状态。实际上,任何一种类型的数据结构都可以用来描述状态,只要它有利于问题求解,就可以选用。
(2) 操作
操作(Operator)也称为算符,它是把问题从一种状态变换为另一种状态的手段。当对一个问题状态使用某个可用操作时,它将引起该状态中某些分量值的变化,从而使问题从一个具体状态变为另一个具体状态。操作可以是一个机械步骤,一个运算,一条规则或一个过程。操作可理解为状态集合上的一个函数,它描述了状态之间的关系。
(3) 状态空间
状态空间(State Space)用来描述一个问题的全部状态以及这些状态之间的相互关系。状态空间常用一个三元组
(S, F, G)
来表示。其中,S为问题的所有初始状态的集合;F为操作的集合;G为目标状态的集合。
状态空间也可用一个赋值的有向图来表示,该有向图称为状态空间图。在状态空间图中,节点表示问题的状态,有向边表示操作。
2. 状态空间问题求解
任何以状态和操作为基础的问题求解方法都可称为状态空间问题求解方法,简称状态空间法。用状态空间法求解问题的基本过程是:首先为问题选择适当的“状态”及“操作”的形式化描述方法;然后从某个初始状态出发,每次使用一个“操作”,递增地建立起操作序列,直到达到目标状态为止;最后,由初始状态到目标状态所使用的算符序列就是该问题的一个解。
上述问题求解过程实际上是一个搜索过程,至于具体的搜索方法我们将在后面详细讨论,这里仅是对状态空间法的一个一般描述。
3. 状态空间的例子
下面通过具体例子来说明状态空间法。
二阶梵塔问题。设有三根钢针,它们的编号分别是1号、2号和3号。在初始情况下,1号钢针上穿有A、B两个金片,A比B小,A位于B的上面。要求把这两个金片全部移到另一根钢针上,而且规定每次只能移动一个金片,任何时刻都不能使大的位于小的上面。
解:设用Sk={Sk0, Sk1}表示问题的状态,其中,Sk0表示金片A所在的钢针号,Sk1表示金片