智能搜索技术

1

搜索是人工智能中的一个基本问题，并与推理密切相关，搜索策略的优劣，将直接影响到智能系统的性能与推理效率。

4.1搜索概述

4.1.1搜索的含义4.1.2状态空间问题求解方法4.1.3问题归约求解方法4.1.4进化搜索法概述4.2状态空间的启发式搜索4.3与/或树的启发式搜索4.4博弈树的启发式搜索4.5遗传算法第4章智能搜索技术智能搜索技术全文共106页，当前为第1页。2基于搜索空间类型A算法A*算法基于随机算法演化机制遗传算法种群寻优蚁群算法粒群算法蒙特卡罗算法其它方法爬山搜索算法模拟退火算法4.1.1搜索的含义搜索：依靠经验，利用已有知识，根据问题的实际情况，不断寻找可利用知识，从而构造一条代价最小的推理路线，使问题得以解决的过程称为搜索智能搜索：是指可以利用搜索过程得到的中间信息来引导搜索项最优方向发展的算法。状态空间与/或树博弈树问题归约法极大/极小算法α-β剪枝统计模型免疫算法免疫优化智能搜索技术全文共106页，当前为第2页。34.1.2状态空间问题求解方法1.状态空间问题表示状态(State)

是表示问题求解过程中每一步问题状况的数据结构，它可形式地表示为：

Sk={Sk0,Sk1,…}当对每一个分量都给以确定的值时，就得到了一个具体的状态。操作(Operator)

也称为算符，它是把问题从一种状态变换为另一种状态的手段。操作可以是一个机械步骤，一个运算，一条规则或一个过程。操作可理解为状态集合上的一个函数，它描述了状态之间的关系。状态空间(Statespace)

用来描述一个问题的全部状态以及这些状态之间的相互关系。常用一个三元组表示为：

(S,F,G)其中，S为问题的所有初始状态集合；F为操作的集合；G为目标状态的集合。状态空间也可用一个赋值的有向图来表示，该有向图称为状态空间图。在状态空间图中，节点表示问题的状态，有向边表示操作。智能搜索技术全文共106页，当前为第3页。4状态空间法求解问题的基本过程：首先，为问题选择适当的“状态”及“操作”的形式化描述方法；然后，从某个初始状态出发，每次使用一个“操作”，递增地建立起操作序列，直到达到目标状态为止；最后，由初始状态到目标状态所使用的算符序列就是该问题的一个解。

4.1.2状态空间问题求解方法2.状态空间问题求解智能搜索技术全文共106页，当前为第4页。5

例4.1二阶梵塔问题

设有三根钢针，它们的编号分别是1号、2号和3号。在初始情况下，1号钢针上穿有A、B两个金片，A比B小，A位于B的上面。要求把这两个金片全部移到另一根钢针上，而且规定每次只能移动一个金片，任何时刻都不能使大的位于小的上面。

解：设用Sk=(SkA,SkB)表示问题的状态，其中，SkA表示金片A所在的钢针号，SkB表示金片B所在的钢针号。全部可能的问题状态共有以下9种：

S0=(1,1)S1=(1,2)S2=(1,3)S3=(2,1)S4=(2,2)S5=(2,3)S6=(3,1)S7=(3,2)S8=(3,3)4.1.2状态空间问题求解方法3.状态空间的例子(1/11)智能搜索技术全文共106页，当前为第5页。6

ABABAB123123123图4.1二阶梵塔问题的初始状态和目标状态初始状态集合

S={S0}目标状态集合

G={S4,S8}

初始状态S0和目标状态S4、S8如下图

S0=(1,1)S4=(2,2)S8=(3,3)4.1.2状态空间问题求解方法3.状态空间的例子(2/11)智能搜索技术全文共106页，当前为第6页。7操作

Aij

表示把金片A从第i号钢针移到j号钢针上；

Bij

表示把金片B从第i号钢针一到第j号钢针上。共有12种操作，它们分别是：

A12A13A21A23A31A32

B12B13B21B23B31B32

根据上述9种可能的状态和12种操作，可构成二阶梵塔问题的状态空间图，如下图所示。4.1.2状态空间问题求解方法3.状态空间的例子(3/11)智能搜索技术全文共106页，当前为第7页。8

从初始节点(1,1)到目标节点(2,2)及(3,3)的任何一条路径都是问题的一个解。其中，最短的路径长度是3，它由3个操作组成。例如，从(1,1)开始，通过使用操作A13、B12及A32，可到达(3,3)。(1,1)B12A13(2,1)(3,2)(2,3)(3,3)(1,3)(3,1)(1,2)(2,2)A32A12B13A234.1.2状态空间问题求解方法3.状态空间的例子(4/11)图4.2二阶梵塔的状态空间图ABABABAB智能搜索技术全文共106页，当前为第8页。9

例4.2修道士(Missionaries)和野人(Cannibals)问题(简称M-C问题)。

设在河的一岸有3个野人、3个修道士和1条船，修道士想用这条船把所有的人运到河对岸，但受以下条件的约束：第一，修道士和野人都会划船，但每次船上至多可载2个人；第二，在河的任一岸，如果野人数目超过修道士数，修道士会被野人吃掉。如果野人会服从任何一次过河安排，请规划一个确保修道士和野人都能过河，且没有修道士被野人吃掉的安全过河计划。

解：先选取描述问题状态的方法。这里，需要考虑两岸的修道士人数和野人数，还需要考虑船在左岸还是在右岸，故可用如下三元组来表示状态

S=(m,c,b)其中，m表示左岸的修道士人数，c表示左岸的野人数，b表示左岸的船数。而右岸的状态可由下式确定：右岸修道士数m'=3-m

右岸野人数c'=3-c

右岸船数b'=1-b

在这种表示方式下，m和c都可取0、1、2、3中之一，b可取0和1中之一。因此，共有4×4×2=32种状态。

4.1.2状态空间问题求解方法3.状态空间的例子(5/11)智能搜索技术全文共106页，当前为第9页。初始状态目标状态左岸右岸(3,3,1)(0,0,0)104.1.2状态空间问题求解方法3.状态空间的例子(6/11)智能搜索技术全文共106页，当前为第10页。11有效状态在32种状中，除去不合法和修道士被野人吃掉的状态，有效状态只16种：

S0=(3,3,1)S1=(3,2,1)S2=(3,1,1)S3=(2,2,1)S4=(1,1,1)S5=(0,3,1)S6=(0,2,1)S7=(0,1,1)S8=(3,2,0)S9=(3,1,0)S10=(3,0,0)S11=(2,2,0)S12=(1,1,0)S13=(0,2,0)S14=(0,1,0)S15=(0,0,0)过河操作过河操作是指用船把修道士或野人从河的左岸运到右岸，或从右岸运到左岸的动作。每个操作都应当满足如下条件：第一，船上至少有一个人（m或c）操作，离开岸边的m和c的减少数目应该等于到达岸边的m和c的增加数目；第二，每次操作船上人数不得超过2个；第三，操作应保证不产生非法状态。操作的结构条件：只有当其条件具备时才能使用动作：刻划了应用此操作所产生的结果。

4.1.2状态空间问题求解方法3.状态空间的例子(7/11)智能搜索技术全文共106页，当前为第11页。12操作的表示

Lij

表示有i个修道士和j个野人，从左岸到右岸的操作

Rij

表示有i个修道士和j个野人，从右岸到左岸的操作操作集本问题有10种操作可供选择，他们的集合称为操作集，即

A={L01,L10,L11,L02,L20,R01,R10,R11,R02,R20}操作的例子下面以L01和R01为例来说明这些操作的条件和动作。操作符号条件动作

L01b=1,m=0或3,c≥1b=0,c=c-1R01b=0,m=0或3，c≤2b=1,c=c+1

4.1.2状态空间问题求解方法3.状态空间的例子(8/11)智能搜索技术全文共106页，当前为第12页。13abc

例4.3猴子摘香蕉问题。在讨论谓词逻辑知识表示时，我们曾提到过这一问题，现在用状态空间法来解决这一问题。

解：问题的状态可用4元组（w,x,y,z）表示。其中：

w

表示猴子的水平位置；

x

表示箱子的水平位置；

y

表示猴子是否在箱子上，当猴子在箱子上时，y取1；否则y取0；

z

表示猴子是否拿到香蕉，当拿到香蕉时z取1，否则z取0。4.1.2状态空间问题求解方法3.状态空间的例子(9/11)智能搜索技术全文共106页，当前为第13页。14所有可能的状态

S0:(a,b,0,0)初始状态

S1:(b,b,0,0)S2:(c,c,0,0)S3:(c,c,1,0)S4:(c,c,1,1)目标状态允许的操作为

Goto(u)：猴子走到位置u，即

(w,x,0,0)→(u,x,0,0)Pushbox(v):猴子推着箱子到水平位置v，即

(x,x,0,0)→(v,v,0,0)Climbbox:猴子爬上箱子，即

(x,x,0,0)→(x,x,1,0)Grasp；猴子拿到香蕉，即

(c,c,1,0)→(c,c,1,1)问题的状态空间图如下图所示。可见，由初始状态到目标状态的操作序列为：

{Goto(b),Pushbox(c),Climbbox,Grasp}4.1.2状态空间问题求解方法3.状态空间的例子(10/11)智能搜索技术全文共106页，当前为第14页。15猴子摘香蕉问题的状态空间图(a,b,0,0)(b,b,0,0)(c,c,0,0)(b,b,1,0)(c,c,1,0)(a,a,0,0)(c,c,1,1)Goto(b)Pushbox(c)Grasp初始状态图4.3猴子摘香蕉问题的状态空间图Pushbox(c)ClimbboxClimbboxPushbox(c)Pushbox(a)Pushbox(a)4.1.2状态空间问题求解方法3.状态空间的例子(11/11)Goto(b)目标状态智能搜索技术全文共106页，当前为第15页。16基本思想当一问题较复杂时，可通过分解或变换，将其转化为一系列较简单的子问题，然后通过对这些子问题的求解来实现对原问题的求解。分解如果一个问题P可以归约为一组子问题P1,P2,…,Pn，并且只有当所有子问题Pi都有解时原问题P才有解，任何一个子问题Pi无解都会导致原问题P无解，则称此种归约为问题的分解。即分解所得到的子问题的“与”与原问题P等价。等价变换如果一个问题P可以归约为一组子问题P1,P2,…,Pn，并且子问题Pi中只要有一个有解则原问题P就有解，只有当所有子问题Pi都无解时原问题P才无解，称此种归约为问题的等价变换，简称变换。即变换所得到的子问题的“或”与原问题P等价。

4.1.3问题归约求解方法1.问题的分解与等价变换智能搜索技术全文共106页，当前为第16页。17PP1P2P3P1P2P3PPP1P2P3P11P12P31P32P33(1)与树分解(2)或树等价变换(3)与/或树4.1.3问题归约求解方法2.问题归约的与/或树表示(1/3)与树或树与/或树智能搜索技术全文共106页，当前为第17页。18(4)端节点与终止节点在与/或树中，没有子节点的节点称为端节点；本原问题所对应的节点称为终止节点。可见，终止节点一定是端节点，但端节点却不一定是终止节点。(5)可解节点与不可解节点在与/或树中，满足以下三个条件之一的节点为可解节点：①任何终止节点都是可解节点。②对“或”节点，当其子节点中至少有一个为可解节点时，则该或节点就是可解节点。③对“与”节点，只有当其子节点全部为可解节点时，该与节点才是可解节点。同样，可用类似的方法定义不可解节点：

①不为终止节点的端节点是不可解节点。②对“或”节点，若其全部子节点都为不可解节点，则该或节点是不可解节点。③对“与”节点，只要其子节点中有一个为不可解节点，则该与节点是不可解节点。4.1.3问题归约求解方法2.问题归约的与/或树表示(2/3)智能搜索技术全文共106页，当前为第18页。19Pttt

(6)解树由可解节点构成，并且由这些可解节点可以推出初始节点（它对应着原始问题）为可解节点的子树为解树。在解树中一定包含初始节点。

例如，右图给出的与或树中，用红线表示的子树是一个解树。在该图中，节点P为原始问题节点，用t标出的节点是终止节点。根据可解节点的定义，很容易推出原始问题P为可解节点。问题归约求解过程就实际上就是生成解树，即证明原始节点是可解节点的过程。这一过程涉及到搜索的问题，对于与/或树的搜索将在后面详细讨论。4.1.3问题归约求解方法2.问题归约的与/或树表示(3/3)智能搜索技术全文共106页，当前为第19页。20

解：这个问题也可用状态空间法来解，不过本例主要用它来说明如何用归约法来解决问题。为了能够解决这一问题，首先需要定义该问题的形式化表示方法。设用三元组

(i,j,k)表示问题在任一时刻的状态，用“→”表示状态的转换。上述三元组中

i代表金片A所在的钢针号

j代表金片B所在的钢针号

k代表金片C所在的钢针号1231234.1.3问题归约求解方法3.问题归约的例子(1/2)ABCABC

例4.4

三阶梵塔问题。要求把1号钢针上的3个金片全部移到3号钢针上，如下图所示。智能搜索技术全文共106页，当前为第20页。21

(1,1,1)→(3,3,3)

(1,1,1)→(2,2,1)(2,2,1)→(2,2,3)(2,2,3)→(3,3,3)(1,1,1)→(3,1,1)(3,1,1)→(3,2,1)(3,2,1)→(2,2,1)(2,2,3)→(1,2,3)(1,2,3)→(1,3,3)(1,3,3)→(3,3,3)

在该与/或树中，有7个终止节点，它们分别对应着7个本原问题。如果把这些本原问题从左至右排列起来，即得到了原始问题的解：

(1,1,1)→(3,1,1)(3,1,1)→(3,2,1)(3,2,1)→(2,2,1)(2,2,1)→(2,2,3)(2,2,3)→(1,2,3)(1,2,3)→(1,3,3)(1,3,3)→(3,3,3)

利用问题归约方法，原问题可分解为以下三个子问题：

(1)把金片A及B移到2号钢针上的双金片移动问题。即(1,1,1)→(2,2,1)(2)把金片C移到3号钢针上的单金片移动问题。即(2,2,1)→(2,2,3)(3)把金片A及B移到3号钢针的双金片移动问题。即(2,2,3)→((3,3,3)其中，子问题(1)和(3)都是一个二阶梵塔问题，它们都还可以再继续进行分解；子问题(2)是本原问题，它已不需要再分解。三阶梵塔问题的分解过程可用如下图与/或树来表示

4.1.3问题归约求解方法3.问题归约的例子(2/2)智能搜索技术全文共106页，当前为第21页。22

进化搜索以达尔文进化论的“物竟天择、适者生存”作为算法的进化规则，并结合孟德尔的遗传变异理论，将生物进化过程中的繁殖（Reproduction）变异（Mutation）竞争（Competition）选择（Selection）引入到了算法中。(1)什么是进化搜索4.1.4进化搜索法概述1、进化搜索的概念及其生物学基础(1/3)进化搜索算法也称为模拟进化优化算法或进化计算（EvolutionaryComputation,EC），是在达尔文进化论和孟德尔遗传变异理论的基础上产生的一种在基因和种群层次上模拟自然界生物进化过程与机制进行问题求解的自组织、自适应的随机搜索技术。主要包括遗传算法（GeneticAlgorithm，GA）进化策略（EvolutionaryStrategy,ES）进化规划（EvolutionaryProgramming,EP）遗传规划（GeneticProgramming,GP）四大分支。智能搜索技术全文共106页，当前为第22页。23(2)进化计算的生物学基础

自然界生物进化过程是进化计算的生物学基础，它主要包括遗传(Heredity)、变异(Mutation)和进化(Evolution)理论。①遗传理论

遗传是指父代（或亲代）利用遗传基因将自身的基因信息传递给下一代（或子代），使子代能够继承其父代的特征或性状的这种生命现象。正是由于遗传的作用，自然界才能有稳定的物种。在自然界，构成生物基本结构与功能的单位是细胞（Cell）。细胞中含有一种包含着所有遗传信息的复杂而又微小的丝状化合物，人们称其为染色体（Chromosome）。在染色体中，遗传信息由基因（Gene）所组成，基因决定着生物的性状，是遗传的基本单位。染色体的形状是一种双螺旋结构，构成染色体的主要物质叫做脱氧核糖核酸(DNA)，每个基因都在DNA长链中占有一定的位置。一个细胞中的所有染色体所携带的遗传信息的全体称为一个基因组(Genome)。

细胞在分裂过程中，其遗传物质DNA通过复制转移到新生细胞中，从而实现了生物的遗传功能。4.1.4进化搜索法概述1.进化搜索的概念及其生物学基础(2/3)智能搜索技术全文共106页，当前为第23页。24②变异理论

变异是指子代和父代之间，以及子代的各个不同个体之间产生差异的现象。变异是一种随机、不可逆现象，是生物多样性的基础。引起变异的主要原因：杂交，是指有性生殖生物在繁殖下一代时两个同源染色体之间的交配重组，即两个染色体在某一相同处的DNA被切断后再进行交配重组，形成两个新的染色体。复制差错，是指在细胞复制过程中因DNA上某些基因结构的随机改变而产生出新的染色体。③进化论

进化是指在生物延续生存过程中，逐渐适应其生存环境，使得其品质不断得到改良的这种生命现象。遗传和变异是生物进化的两种基本现象，优胜劣汰、适者生存是生物进化的基本规律。

达尔文的自然选择学说：在生物进化中，一种基因有可能发生变异而产生出另一种新的基因。这种新基因将依据其与生存环境的适应性而决定其增殖能力。通常，适应性强的基因会不断增多，而适应性差的基因则会逐渐减少。通过这种自然选择，物种将逐渐向适应于生存环境的方向进化，甚至会演变成为另一个新的物种，而那些不适应于环境的物种将会逐渐被淘汰。4.1.4进化搜索法概述1.进化搜索的概念及其生物学基础(3/3)智能搜索技术全文共106页，当前为第24页。25

进化搜索自20世纪50年代以来，其发展过程大致可分为三个阶段。

(1)萌芽阶段这一阶段是从20世纪50年代后期到70年代中期。20世纪50年代后期，一些生物学家在研究如何用计算机模拟生物遗传系统中，产生了遗传算法的基本思想，并于1962年由美国密执安（Michigan）大学霍兰德（Holland）提出。1965年德国数学家雷切伯格（Rechenberg）等人提出了一种只有单个个体参与进化，并且仅有变异这一种进化操作的进化策略。同年，美国学者弗格尔（Fogel）提出了一种具有多个个体和仅有变异一种进化操作的进化规划。1969年美国密执安（Michigan）大学的霍兰德（Holland）提出了系统本身和外部环境相互协调的遗传算法。至此，进化计算的三大分支基本形成。

(2)成长阶段这一阶段是从20世纪70年代中期到80年代后期。1975年，霍兰德出版专著《自然和人工系统的适应性（AdaptationinNaturalandArtificialSystem）》，全面介绍了遗传算法。同年，德国学者施韦费尔（Schwefel）在其博士论文中提出了一种由多个个体组成的群体参与进化的，并且包括了变异和重组这两种进化操作的进化策略。1989年，霍兰德的学生戈尔德伯格（Goldberg）博士出版专著《遗传算法----搜索、优化及机器学习（GeneticAlgorithm----inSearchOptimizationandMachineLearning）》，使遗传算法得到了普及与推广。4.1.4进化搜索法概述2.进化搜索的产生与发展(1/2)智能搜索技术全文共106页，当前为第25页。26(3)发展阶段

这一阶段是从20世纪90年代至今。1989年，美国斯坦福（Stanford）大学的科扎（Koza）提出了遗传规划的新概念，并于1992年出版了专著《遗传规划----应用自然选择法则的计算机程序设计（GeneticProgramming:ontheProgrammingofComputerbyMeansofNaturalSelection）》该书全面介绍了遗传规划的基本原理及应用实例，标志着遗传规划作为计算智能的一个分支已基本形成。进入20世纪90年代以来，进化计算得到了众多研究机构和学者的高度重视，新的研究成果不断出现、应用领域不断扩大。目前，进化计算已成为人工智能领域的又一个新的研究热点。

4.1.4进化搜索法概述2.进化搜索的产生与发展(2/2)智能搜索技术全文共106页，当前为第26页。27

进化计算尽管有多个重要分支，并且不同分支的编码方案、选择策略和进化操作也有可能不同，但它们却有着共同的进化框架。若假设P为种群(Population，或称为群体)，t为进化代数，P(t)为第t代种群,则进化计算的基本结构可粗略描述如下：

{确定编码形式并生成搜索空间；初始化各个进化参数，并设置进化代数t=0；初始化种群P(0);

对初始种群进行评价（即适应度计算）；

while（不满足终止条件）do{t=t+1;

利用选择操作从P(t-1)代中选出P(t)代群体；对P(t)代种群执行进化操作；对执行完进化操作后的种群进行评价（即适应度计算）；

}}

可以看出，上述基本结构包含了生物进化中所必需的选择操作、进化操作和适应度评价等过程。4.1.4进化搜索法概述3.进化搜索的基本过程智能搜索技术全文共106页，当前为第27页。284.1搜索概述4.2状态空间的启发式搜索4.2.1启发信息和估价函数4.2.2A算法4.2.3A*算法4.2.4A*算法应用举例4.3与/或树的启发式搜索4.4博弈树的启发式搜索4.5遗传算法第4章智能搜索技术智能搜索技术全文共106页，当前为第28页。29启发性信息

启发性信息是指那种与具体问题求解过程有关的，并可指导搜索过程朝着最有希望方向前进的控制信息。启发信息的启发能力越强，扩展的无用结点越少。包括以下3种：①有效地帮助确定扩展节点的信息；②有效的帮助决定哪些后继节点应被生成的信息；③能决定在扩展一个节点时哪些节点应从搜索树上删除的信息。估价函数

用来估计节点重要性，定义为从初始节点S0出发，约束经过节点n到达目标节点Sg的所有路径中最小路径代价的估计值。一般形式：

f(n)=g(n)+h(n)其中，g(n)是从初始节点S0到节点n的实际代价；h(n)是从节点n到目标节点Sg的最优路径的估计代价。

4.2.1启发性信息和估价函数1.概念智能搜索技术全文共106页，当前为第29页。30

解：即g(n)=d(n)，h(n)=W(n)。d(n)说明用从S0到n的路径上的单位代价表示实际代价；W(n)说明用结点n中“不在位”的数码个数作为启发信息。可见，某节点中的“不在位”的数码个数越多，说明它离目标节点越远。对初始节点S0，由于d(S0)=0，W(S0)=3，因此有

f(S0)=0+3=32

831476512384765S0Sg

例4.5八数码难题。设问题的初始状态S0和目标状态Sg如下图所示，且估价函数为

f(n)=d(n)+W(n)其中：d(n)表示节点n在搜索树中的深度

W(n)表示节点n中“不在位”的数码个数。请计算初始状态S0的估价函数值f(S0)4.2.1启发性信息和估价函数2.例子智能搜索技术全文共106页，当前为第30页。31

在状态空间搜索中，如果每一步都利用估价函数f(n)=g(n)+h(n)对Open表中的节点进行排序，则称A算法。它是一种为启发式搜索算法。类型：全局择优：从Open表的所有节点中选择一个估价函数值最小的进行扩展。局部择优：仅从刚生成的子节点中选择一个估价函数值最小的进行扩展。全局择优搜索A算法描述：

(1)把初始节点S0放入Open表中，f(S0)=g(S0)+h(S0)；

(2)如果Open表为空，则问题无解，失败退出；

(3)把Open表的第一个节点取出放入Closed表，并记该节点为n；

(4)考察节点n是否为目标节点。若是，则找到了问题的解，成功退出；

(5)若节点n不可扩展，则转第(2)步；

(6)扩展节点n，生成其子节点ni(i=1,2,…)，计算每一个子节点的估价值f(ni)(i=1,2,…)，并为每一个子节点设置指向父节点的指针，然后将这些子节点放入Open表中；

(7)根据各节点的估价函数值，对Open表中的全部节点按从小到大的顺序重新进行排序；

(8)转第(2)步。4.2.2A算法1.概念和算法描述智能搜索技术全文共106页，当前为第31页。32

例4.6八数码难题。设问题的初始状态S0和目标状态Sg如图所示，估价函数与例4.5相同。请用全局择优搜索解决该问题。解：该问题的全局择优搜索树如下图所示。在该图中，每个节点旁边的数字是该节点的估价函数值。例如，对节点S2，其估价函数值的计算为：f(S2)=d(S2)+W(S2)=1+3=4

2831476512384765S0Sg4.2.2A算法2.例子（1/2)智能搜索技术全文共106页，当前为第32页。332831476528314765231

847652831476528316475S0

832147652837146523184765231847651238476512378465123

847654455564644SgS1S2八数码难题的全局择优搜索树该问题的解为：

S0→S1→S2→S3→SgS364.2.2A算法2.例子(2/2)f(n)=d(n)+W(n)智能搜索技术全文共106页，当前为第33页。34

4.2.3A*算法1.概念A*算法是对A算法的估价函数f(n)=g(n)+h(n)加上某些限制后得到的一种启发式搜索算法假设f*(n)是从初始节点S0出发，约束经过节点n到达目标节点Sg的最小代价，估价函数f(n)是对f*(n)的估计值。记

f*(n)=g*(n)+h*(n)其中，g*(n)是从S0出发到达n的最小代价,h*(n)是n到Sg的最小代价如果对A算法（全局择优）中的g(n)和h(n)分别提出如下限制：第一，g(n)是对最小代价g*(n)的估计，且g(n)>0；第二，h(n)是最小代价h*(n)的下界，即对任意节点n均有h(n)≤h*(n)。则称满足上述两条限制的A算法为A*算法。智能搜索技术全文共106页，当前为第34页。35

4.2.3A*算法1.A*算法的可纳性(1/6)可纳性的含义：

对任一状态空间图，当从初始节点到目标节点有路经存在时，如果搜索算法总能在有限步骤内找到一条从初始节点到目标节点的最佳路径，并在此路径上结束，则称该搜索算法是可采纳的。A*算法可纳性的证明过程：第一步，对有限图，A*算法一定能够成功结束。定理4.1

第二步，对无限图，A*算法也一定能够成功结束。引理4.1、4.2和推论4.1,定理4.2

第三步，A*算法一定能够结束在最佳路径上。定理4.3和推论4.2

定理4.1

对有限图，如果从初始节点S0到目标节点Sg有路径存在，则算法A*一定成功结束。

证明：首先证明算法必然会结束。

由于搜索图为有限图，如果算法能找到解，则成功结束；如果算法找不到解，则必然会由于Open表变空而结束。因此，A*算法必然会结束。

智能搜索技术全文共106页，当前为第35页。36

然后证明算法一定会成功结束。

由于至少存在一条由初始节点到目标节点的路径，设此路径为

S0=n0,n1,…,nk=Sg算法开始时，节点n0在Open表中，且路径中任一节点ni离开Open表后，其后继节点ni+1必然进入Open表，这样，在Open表变为空之前，目标节点必然出现在Open表中。因此，算法一定会成功结束。引理4.1

对无限图，如果从初始节点S0到目标节点Sg有路径存在，则算法A*算法不终止的话，则从Open表中选出的节点必将具有任意大的f值。证明：设d*(n)是A*生成的从初始节点S0到节点n的最短路经长度，由于搜索图中每条边的代价都是一个正数，令其中的最小的一个数是e，则有

g*(n)≥d*(n)×e因为g*(n)是最佳路径的代价，故有

g(n)≥g*(n)≥d*(n)×e又因为h(n)≥0，故有

f(n)=g(n)+h(n)≥g(n)≥d*(n)×e

如果A*算法不终止的话，从Open表中选出的节点必将具有任意大的d*(n)值，因此，也将具有任意大的f值。

4.2.3A*算法1.A*算法的可纳性(2/6)智能搜索技术全文共106页，当前为第36页。37

引理4.2

在A*算法终止前的任何时刻，Open表中总存在节点n’，它是从初始节点S0到目标节点的最佳路径上的一个节点，且满足f(n’)≤f*(S0)。证明：设从初始节点S0到目标节点t的一条最佳路径序列为

S0=n0,n1,…,nk=Sg算法开始时，节点S0在Open表中，当节点S0离开Open表进入Closed表时，节点n1进入Open表。因此，A*没有结束以前，在Open表中必存在最佳路径上的节点。设这些节点中排在最前面的节点为n'，则有

f(n')=g(n')+h(n')由于n'在最佳路径上，故有g(n')=g*(n')，从而

f(n')=g*(n')+h(n')又由于A*算法满足h(n')≤h*(n')，故有

f(n')≤g*(n')+h*(n')=f*(n')因为在最佳路径上的所有节点的f*值都应相等，因此有

f(n')≤f*(S0)4.2.3A*算法1.A*算法的可纳性(3/6)智能搜索技术全文共106页，当前为第37页。38

定理4.2

对无限图，若从初始节点S0到目标节点Sg有路径存在，则A*算法必然会结束。证明：（反证法）假设A*不结束，由引理4.1知Open表中的节点有任意大的f值，这与引理3.2的结论相矛盾，因此，A*算法只能成功结束。推论4.1

Open表中任一具有f(n)<f*(S0)的节点n，最终都被A*算法选作为扩展的节点。

(证明略)

下面给出A*算法的可纳性4.2.3A*算法1.A*算法的可纳性(4/6)智能搜索技术全文共106页，当前为第38页。394.2.3A*算法1.A*算法的可纳性(5/6)

定理4.3

A*算法是可采纳的，即若存在从初始节点S0到目标节点Sg的路径，则A*算法必能结束在最佳路径上。证明：证明过程分以下两步进行：

先证明A*算法一定能够终止在某个目标节点上。由定理4.1和定理4.2可知，无论是对有限图还是无限图，A*算法都能够找到某个目标节点而结束。

再证明A*算法只能终止在最佳路径上。（反证法）假设A*算法未能终止在最佳路径上，而是终止在某个目标节点t处，则有

f(t)=g(t)>f*(S0)但由引理4.2可知，在A*算法结束前，必有最佳路径上的一个节点n'在Open表中，且有

f(n’)≤f*(S0)<f(t)这时，A*算法一定会选择n'来扩展，而不可能选择t，从而也不会去测试目标节点t，这就与假设A*算法终止在目标节点t相矛盾。因此，A*算法只能终止在最佳路径上。智能搜索技术全文共106页，当前为第39页。40

推论4.2

在A*算法中，对任何被扩展的节点n，都有f(n)≤f*(S0)。

证明：令n是由A*选作扩展的任一节点，因此n不会是目标节点，且搜索没有结束。由引理4.2可知，在Open表中有满足

f(n')≤f*(S0)的节点n'。若n=n'，则有f(n)≤f*(S0)；否则，选择n扩展，必有

f(n)≤f(n')所以有

f(n)≤f*(S0)4.2.3A*算法1.A*算法的可纳性(6/6)智能搜索技术全文共106页，当前为第40页。41

A*算法的搜索效率很大程度上取决于启发函数h(n)。一般来说，在满足h(n)≤h*(n)的前提下，h(n)的值越大越好。h(n)的值越大，说明它携带的启发性信息越多，A*算法搜索时扩展的节点就越少，搜索效率就越高。A*算法的这一特性被称为最优性。下面通过一个定理来描述这一特性。定理4.4

设有两个A*算法A1*和A2*，它们有

A1*:f1(n)=g1(n)+h1(n)A2*:f2(n)=g2(n)+h2(n)如果A2*比A1*有更多的启发性信息，即对所有非目标节点均有

h2(n)>h1(n)则在搜索过程中，被A2*扩展的节点也必然被A1*扩展，即A1*扩展的节点不会比A2*扩展的节点少，亦即A2*扩展的节点集是A1*扩展的节点集的子集。4.2.3A*算法2.A*算法的最优性(1/2)智能搜索技术全文共106页，当前为第41页。42

4.2.3A*算法2.A*算法的最优性(2/2)证明：（用数学归纳法）

(1)对深度d(n)=0的节点，即n为初始节点S0，如n为目标节点，则A1*和A2*都不扩展n；如果n不是目标节点，则A1*和A2*都要扩展n。

(2)假设对A2*中d(n)=k的任意节点n结论成立，即A1*也扩展了这些节点。

(3)证明A2*中d(n)=k+1的任意节点n，也要由A1*扩展。（用反证法）假设A2搜索树上有一个满足d(n)=k+1的节点n，A2*扩展了该节点，但A1*没有扩展它。根据第(2)条的假设，知道A1*扩展了节点n的父节点。因此，n必定在A1*的Open表中。既然节点n没有被A1*扩展，则有

f1(n)≥f*(S0)即g1(n)+h1(n)≥f*(S0)。但由于d=k时，A2*扩展的节点A1*也一定扩展，故有

g1(n)≤g2(n)因此有h1(n)≥f*(S0)-g2(n)

另一方面，由于A2*扩展了n，因此有

f2(n)≤f*(0)即g2(n)+h2(n)≤f*(S0)，亦即h2(n)≤f*(S0)-g2(n)，所以有h1(n)≥h2(n)

这与我们最初假设的h1(n)<h2(n)矛盾，因此反证法的假设不成立。智能搜索技术全文共106页，当前为第42页。43

在A*算法中，每当扩展一个节点n时，都需要检查其子节点是否已在Open表或Closed表中。对已在Open表中的子节点，需要决定是否调整指向其父节点的指针；对已在Closed表中的子节点，除需要决定是否调整其指向父节点的指针外，还需要决定是否调整其子节点的后继节点的父指针。如果能够保证，每当扩展一个节点时就已经找到了通往这个节点的最佳路径，就没有必要再去作上述检查为满足这一要求，我们需要对启发函数h(n)增加单调性限制。定义4.1

如果启发函数满足以下两个条件:(1)h(Sg)=0;(2)对任意节点ni及其任一子节点nj，都有

0≤h(ni)-h(nj)≤c(ni,nj)其中c(ni,nj)是ni到其子节点nj的边代价，则称h(n)满足单调限制。4.2.3A*算法3.h(n)的单调限制(1/3)智能搜索技术全文共106页，当前为第43页。44

定理4.5

如果h满足单调条件，则当A*算法扩展节点n时，该节点就已经找到了通往它的最佳路径，即g(n)=g*(n)。证明：设A*正要扩展节点n，而节点序列

S0=n0,n1,…,nk=n是由初始节点S0到节点n的最佳路径。其中，ni是这个序列中最后一个位于Closed表中的节点，则上述节点序列中的ni+1节点必定在Open表中，则有

g*(ni)+h(ni)≤g*(ni)+c(ni,ni+1)+h(ni+1)由于节点ni和ni+1都在最佳路径上，故有

g*(ni+1)=g*(ni)+c(ni,ni+1)所以g*(ni)+h(ni)≤g*(ni+1)+h(ni+1)一直推导下去可得g*(ni+1)+h(ni+1)≤g*(nk)+h(nk)由于节点ni+1在最佳路径上，故有f(ni+1)≤g*(n)+h(n)因为这时A*扩展节点n而不扩展节点ni+1，则有

f(n)=g(n)+h(n)≤f(ni+1)≤g*(n)+h(n)即g(n)≤g*(n)但是g*(n)是最小代价值，应当有

g(n)≥g*(n)所以有g(n)=g*(n)4.2.3A*算法3.h(n)的单调限制(2/3)智能搜索技术全文共106页，当前为第44页。45

定理4.6

如果h(n)满足单调限制，则A*算法扩展的节点序列的f值是非递减的，即f(ni)≤f(ni+1)。证明：假设节点ni+1在节点ni之后立即扩展，由单调限制条件可知

h(ni)-h(ni+1)≤c(ni,ni+1)即

f(ni)-g(ni)-f(ni+1)+g(ni+1)≤c(ni,ni+1)亦即

f(ni)-g(ni)-f(ni+1)+g(ni)+c(ni,ni+1)≤c(ni,ni+1)所以

f(ni)-f(ni+1)≤0即

f(ni)≤f(ni+1)

以上两个定理都是在h(n)满足单调性限制的前提下才成立的。如果h(n)不满足单调性限制，则它们不一定成立。在h(n)满足单调性限制下的A*算法常被称为改进的A*算法。4.2.3A*算法3.h(n)的单调限制(3/3)智能搜索技术全文共106页，当前为第45页。46例4.7

八数码难题。

28314765283147652318476528314765283164752318476523184765123847651237846512384765S0f=6g*=1h*=3f=6f=6g*=2h*=2f=6f=4g*=3h*=1f=4g*=4h*=0f=4f=6Sg八数码难题h(n)=P(n)的搜索树f(n)=d(n)+P(n)d(n)深度P(n)与目标距离显然满足P(n)≤h*(n)即f*=g*+h*f=44.2.4A*算法应用举例八数码难题h*=4f=4智能搜索技术全文共106页，当前为第46页。47例4.8修道士和野人问题解：用m表示左岸的修道士人数，c表示左岸的野人数，b表示左岸的船数，用三元组(m,c,b)表示问题的状态。对A*算法，首先需要确定估价函数。设g(n)=d(n)，h(n)=m+c-2b，则有

f(n)=g(n)+h(n)=d(n)+m+c-2b其中，d(n)为节点的深度。通过分析可知h(n)≤h*(n)，满足A*算法的限制条件。

M-C问题的搜索过程如下图所示。

4.2.4A*算法应用举例修道士和野人过河问题（1/6）智能搜索技术全文共106页，当前为第47页。48h=4f=4问题状态：(m,c,b)估价函数：k(n)=g(n)+h(n)g(n)=d(n)h(n)=m+c-2bf(n)=d(n)+m+c-2b(3,2,0)(3,1,0)(3,3,1)h=5f=6h=4f=5(2,2,0)h=2f=7L01L11R01L02h=4f=5R10(3,0,0)(3,2,1)h=3f=5(3,1,1)R01L02h=3f=6(1,1,0)L20h=2f=6(2,2,1)R11h=2f=9(0,2,0)L20h=2f=8R01h=1f=9(0,3,1)(0,2,1)L02h=1f=10(0,1,0)R01h=1f=11(0,0,0)L02h=0f=114.2.4A*算法应用举例修道士和野人过河问题（2/6）智能搜索技术全文共106页，当前为第48页。初始状态左岸左岸右岸右岸(3,0,0)(3,2,1)(3,1,0)(3,3,1)L02R01L02R01R01494.2.4A*算法应用举例修道士和野人过河问题（3/6）智能搜索技术全文共106页，当前为第49页。右岸左岸右岸(0,2,0)(2,2,1)(1,1,0)(3,1,1)L20R11左岸R01R11L20R01504.2.4A*算法应用举例修道士和野人过河问题（4/6）智能搜索技术全文共106页，当前为第50页。左岸右岸左岸右岸(0,0,0)(0,2,1)(0,1,0)(0,3,1)R01L02R01R01L02514.2.4A*算法应用举例修道士和野人过河问题（5/6）智能搜索技术全文共106页，当前为第51页。右岸目标状态(0,0,0)操作序列：L02→R01→L02→R01→L20→R11→L20→R01→L02524.2.4A*算法应用举例修道士和野人过河问题（6/6）智能搜索技术全文共106页，当前为第52页。534.1搜索概述4.2状态空间的启发式搜索4.3与/或树的启发式搜索

4.3.1解树的代价和希望树

4.3.2与/或树的启发式搜索过程4.4博弈树的启发式搜索4.5遗传算法第4章智能搜索技术智能搜索技术全文共106页，当前为第53页。544.3与/或树的启发式搜索

与/或树的启发式搜索过程实际上是一种利用搜索过程所得到的启发性信息寻找最优解树的过程。算法的每一步都试图找到一个最有希望成为最优解树的子树。最优解树是指代价最小的那棵解树。它涉及到解树的代价与希望树。智能搜索技术全文共106页，当前为第54页。55解树的代价可按如下方法计算：

(1)若n为终止节点，则其代价h(n)=0；

(2)若n为或节点，且子节点为n1,n2,…,nk，则n的代价为：其中，c(n,ni)是节点n到其子节点ni的边代价。

(3)若n为与节点，且子节点为n1,n2,…,nk，则n的代价可用和代价法或最大代价法。若用和代价法，则其计算公式为：若用最大代价法，则其计算公式为：

(4)若n是端节点，但又不是终止节点，则n不可扩展，其代价定义为h(n)=∝。

(5)根节点的代价即为解树的代价。4.3.1解树的代价与希望树1.解树的代价（1/2）智能搜索技术全文共106页，当前为第55页。56

例4.11

设下图是一棵与/或树，它包括两棵解树，左边的解树由S0、A、t1、C及t2组成；右边的解树由S0、B、t2、D及t4组成。在该树中，t1、t2、t3、t4为终止节点；E、F是端节点；边上的数字是该边的代价。请计算解树的代价。解：先计算左边的解树按和代价：h(S0)=2+4+6+2=14按最大代价：h(S0)=(2+6)+2=10再计算右边的解树按和代价：h(S0)=1+5+3+2=11按最大代价：h(S0)=(1+5)+2=8

S02At1

Ct2

Dt3Et4F

与/或树的代价24623154.3.1解树的代价与希望树1.解树的代价（2/2）B智能搜索技术全文共106页，当前为第56页。57

希望树是指搜索过程中最有可能成为最优解树的那棵树。

与/或树的启发式搜索过程就是不断地选择、修正希望树的过程，在该过程中，希望树是不断变化的。定义4.2

希望解树

(1)初始节点S0在希望树T(2)如果n是具有子节点n1,n2,…,nk的或节点，则n的某个子节点ni在希望树T中的充分必要条件是4.3.1解树的代价与希望树2.希望树

(3)如果n是与节点，则n的全部子节点都在希望树T中。智能搜索技术全文共106页，当前为第57页。58

与/或树的启发式搜索过程如下：

(1)把初始节点S0放入Open表中，计算h(S0)；

(2)计算希望树T；

(3)依次在Open表中取出T的端节点放入Closed表，并记该节点为n；

(4)如果节点n为终止节点，则做下列工作：①标记节点n为可解节点；②在T上应用可解标记过程，对n的先辈节点中的所有可解解节点进行标记；

③如果初始解节点S0能够被标记为可解节点，则T就是最优解树，成功退出；④否则，从Open表中删去具有可解先辈的所有节点。⑤转第(2)步。4.3.2与/或树的启发式搜索过程1.算法描述(1/2)智能搜索技术全文共106页，当前为第58页。59

(5)如果节点n不是终止节点，但可扩展，则做下列工作：①扩展节点n，生成n的所有子节点；②把这些子节点都放入Open表中，并为每一个子节点设置指向父节点n的指针③计算这些子节点及其先辈节点的h值；④转第(2)步。

(6)如果节点n不是终止节点，且不可扩展，则做下列工作：①标记节点n为不可解节点；②在T上应用不可解标记过程，对n的先辈节点中的所有不可解解节点进行标记；③如果初始节点S0能够被标记为不可解，则问题无解，失败退出；④否则，从Open表中删去具有不可解先辈的所有节点。⑤转第(2)步。4.3.2与/或树的启发式搜索过程1.算法描述(2/2)智能搜索技术全文共106页，当前为第59页。60例子要求搜索过程每次扩展节点时都同时扩展两层，且按一层或节点、一层与节点的间隔方式进行扩展。它实际上就是下一节将要讨论的博弈树的结构。设初始节点为S0，对S0扩展后得到的与/或树如右图所示。其中，端节点B、C、E、F，下面的数字是用启发函数估算出的h值，节点S0、A、D旁边的数字是按和代价法计算出来的节点代价。此时，S0的右子树是当前的希望树。S08A8D7BCEF3332按和代价法：例:：节点S0的值=3+1+2+1+1=8扩展S0后得到的与/或树4.3.2与/或树的启发式搜索过程2.例子(1/4)或结点与结点智能搜索技术全文共106页，当前为第60页。61扩展节点E，得到如右图所示的与/或树。此时，由右子树求出的h(S0)=12。但是，由左子树求出的h(S0)=9。显然，左子树的代价小。因此，当前的希望树应改为左子树。S09A8D11BCEF3372322276扩展节点E后得到的与/或树4.3.2与/或树的启发式搜索过程2.例子(2/4)或结点与结点或结点与结点智能搜索技术全文共106页，当前为第61页。62

对节点B进行扩展，扩展两层后得到的与/或树如下图所示。由于节点H和I是可解节点，故调用可解标记过程，得节点G、B也为可解节点，但不能标记S0为可解节点，须继续扩展。当前的希望树仍然是左子树。S09A8D11BCEF3372322276GJHIKL002226扩展节点B后得到的与/或树4.3.2与/或树的启发式搜索过程2.例子(3/4)或结点或结点与结点与结点智能搜索技术全文共106页，当前为第62页。63

对节点C进行扩展，扩展两层后得到的与/或树如右图所示。由于节点N和P是可解节点，故调用可解标记过程，得节点M、C、A也为可解节点，进而可标记S0为可解节点，这就的到了代价最小的解树。按和代价法，该最优解的代价为9。S09A8D11BCEF3372322276GJHIKL002226扩展节点C后得到的与/或树4.3.2与/或树的启发式搜索过程2.例子(4/4)或结点或结点与结点与结点29MPN0052智能搜索技术全文共106页，当前为第63页。64第4章智能搜索技术4.1搜索概述4.2状态空间的启发式搜索4.3与/或树的启发式搜索4.4博弈树的启发式搜索4.4.1博弈