搜索问题-人工智能

搜索问题1第三章 搜索问题

3.1状态空间搜索概述

3.2回溯策略

3.3图搜索策略

3.4盲目的图搜索过程

3.5启发式图搜索过程搜索与搜索问题

人类的实际搜索行为人工智能所要解决的问题大部分不具备明确的解题步骤，而只能是利用已有的知识一步一步地摸索前进。

根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过程称之为搜索。搜索法的主要任务：确定以何种方式选择规则？求任一解路的搜索策略：backtracking、HillClimbing、Breadth-first、Depth-first、BeamSearch、Best-first(A).求最佳解路的搜索策略：BritishMuseum、BranchandBound、DynamicProgramming、Optimalsearch(A*).求与或图解图的搜索策略：AO*、Minimax、Alpha-betaPruning、HeuristicPruning.搜索方法的经典应用8数码问题传教士和野人问题旅行商问题4皇后问题迷宫问题博弈问题…………搜索算法的输入是给定的问题，输出时表示为动作序列的方案。一旦有了方案，就可以执行该方案所给出的动作了。（执行阶段）求解问题包括：目标表示搜索执行

内容： 状态空间的搜索问题。搜索方式：盲目搜索启发式搜索关键问题： 如何利用知识，尽可能有效地找到问题的解（最佳解）。搜索问题3.1状态空间搜索概述

3.1.1图的概念图是节点及连接节点的弧的集合。由方向性的弧连接的图是有向图。节点深度的表示：根节点深度为0，其他节点深度dn+1=dn+1。路径：N个有序节点组成的序列中，若每对相邻节点都表示一条弧，则称该序列为图中长度为N-1的一条路径。路径耗散值：令C（ni，nj）为节点ni到节点nj这段路径（或弧线）的耗散值，一条路径的耗散值等于这条路径上所有弧线耗散值的总和。路径耗散值可按如下递归公式计算：C（ni，t）=C（ni，nj）+C（nj，t）节点的扩展：操作符（规则）作用到节点（对应于某一状态描述）上，生成其所有后继节点（新状态），并给出弧线的耗散值（相当于使用规则的代价），这个过程叫做扩展一个节点。3.1.2问题状态空间的图描述

图是最直观的描述问题状态空间的工具，属于显式描述。 图中的节点表示问题的状态，图中的弧表示状态之间的关系。 初始状态对应待求解问题的已知信息，是图的根节点。 3.1.3问题状态空间的搜索状态空间法将一个待定问题的求解过程定义为若干算子与搜索的有机结合体。算子定义了对状态的操作，求解的目的在于找出从初始状态转换为某个（或某些）目标状态的一个（或一组）操作算子序列。以上问题等价于在图中寻找从根节点到某个（或某些）目标节点的一条（或一组）路径。为提供对问题的形式描述，需要：定义状态空间，包含问题相关对象的各种可能排列。对空间的定义不必枚举所有状态。规定一个或多个属于该空间的初始状态。该状态用以描述问题求解过程开始时的状态。规定一个或多个属于该空间的目标状态。该状态用以判断是否得到了问题的解。规定一组规则。描述可使用的操作或算子。

将待求解问题转换成状态空间描述后，使用控制策略对规则进行选择性的应用，在问题状态空间内进行搜索，直到找出从初始状态到目标状态的一条（或一组）路径。3.1.4搜索的基本概念

状态空间图的搜索，是搜索满足条件的一个（或一组）操作算子序列的过程，这个过程也是将一个隐式图中包含目的节点的某个子图变为显式的过程。这种搜索过程是状态空间问题求解的主要基础。搜索过程的要点是：

从初始或目的状态出发，并将它作为当前状态。扫描操作算子集合，将适用于当前状态的一些操作算子作用在其上得到新的状态，并建立新状态与父母节点的连接指针。检查生成的新状态是否是结束状态，如果是，则沿着有关指针从结束状态反向到达开始状态，给出一个解；否则，将新状态作为当前状态，返回第2)步继续搜索。搜索问题S0Sg有哪些常用的搜索算法。问题有解时能否找到解。找到的解是最佳的吗？什么情况下可以找到最佳解？求解的效率如何。搜索需考虑的问题盲目搜索只是可以区分出哪个是目标状态。一般是按预定的搜索策略进行搜索。没有考虑到问题本身的特性，这种搜索具有很大的盲目性，效率不高，不便于复杂问题的求解。启发式搜索是在搜索过程中加入了与问题有关的启发式信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解并找到最优解。3.2回溯策略

回溯策略是一种尝试状态空间中各种不同路径的技术。带回溯策略的搜索从初始状态出发，不停地、试探地寻找路径直到找到目标节点或“不可解节点”—“死胡同”。找到目标节点，退出搜索，返回解路径。遇到不可解节点时，回溯到路径中最近的父节点上，查看该节点是否还有其他子节点未被扩展，如有则沿这些子节点继续搜索。可以看出，这种求解过程呈现出递归过程的性质。求解过程在每个节点上的检查遵循着递归方式。递归法是回溯策略的一种最直接的实现方法。

回溯搜索策略例：四皇后问题在４×４方格的棋盘内，放置四个皇后使任意两个皇后不在同一行、同一列、同一对角线（斜线）上要求：找出所有的摆法回溯搜索策略状态描述：单个皇后位置的描述：用(i,j)表示皇后在第i行j列系统状态的描述四个皇后((i1,j1),(i2,j2),(i3,j3),(i4,j4))()()Q((1,1))()QQ((1,1))((1,1)(2,3))()Q((1,1))((1,1)(2,3))()QQ((1,1))((1,1)(2,3))((1,1)(2,4))()QQ((1,1))((1,1)(2,3))((1,1)(2,4))Q((1,1)(2,4)(3.2))()QQ((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()Q((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))()((1,1))((1,1)(2,3))((1,1)(2,4))((1,1)(2,4)(3.2))Q((1,2))Q((1,2)(2,4))Q((1,2)(2,4)(3,1))Q((1,2)(2,4)(3,1)(4,3))递归的思想从前有座山……

从前有座山……

从前有座山……递归的思想（续）当前状态目标状态g递归过程伪码描述中用到的一些符号的含义：变量：DATA=当前状态；RULES=规则集合序列表；R=当前调用规则；RDATA=新生成的状态；PATH=当前解路径表。常量：NIL=空表；FAIL=回溯点标记；LOOP=循环标号。谓词：TERM(DATA)；(DATA满足结束条件)DEADEND(DATA)；(DATA是非法状态)NULL(RULES)。(规则集合序列表空)函数：RETURN返回自变量的值；APPRULES求可应用的规则表；FIRST从表中取表头的一个元素；TAIL除去表头的一个元素后得到新表；GEN

调用规则生成新状态；CONS在表头插入新元素，构造新表；BACKTRACK(RDATA)递归过程作用于新状态。 BACKTRACK（DATA）

DATA：当前状态。 返回值：从当前状态到目标状态的路径 （以规则表的形式表示） 或FAIL。回溯搜索算法递归过程BACKTRACK(DATA)1. ifTERM(DATA),returnNIL； //当DATA满足终止条件时，返回空表.ifDEADEND(DATA),renturnFAIL； //当DATA状态不合法时，必须回溯。3. RULES←APPRULES(DATA) //DATA状态的可用规则加入规则集合序列表。4. LOOP:ifNULL(RULES),returnFAIL； //如果规则集合序列表空，必须回溯。

5. R←FIRST(RULES)；

//读规则集合序列表的第一条规则到变量R。6. RULES←TAIL(RULES)；

//从规则集合序列表删除被选中的规则。7. RDATA←GEN（R，DATA）；

//被选中的规则作用于当前状态。8. PATH←BACKTRACK(RDATA)； //对新状态递归调用本过程9. ifPATH=FAIL,goLOOP；

//如果递归失败，则用另一条规则10. returnCONS(R,PATH)；

//否则把R加在解路径表中，向上传递成功的 规则表，过程返回解路径规则表（或局部解 路径子表）回溯搜索算法解决办法：对搜索深度加以限制记录从初始状态到当前状态的路径存在问题及解决办法当前状态问题：深度问题死循环问题

对于可能出现重复状态且搜索深度无限的问题，必须设置深度范围限制及防止出现重复状态引起死循环这两个回溯点。

改进的算法如下BACKTRACK1(DATALIST):[1]

DATAFIRST(DATALIST)[2]ifMEMBER(DATA,TAIL(DATALIST)),returnFAIL //有环路，回溯

[3]

ifTERM(DATA),returnNIL //到达目标，成功返回[4]

ifDEADEND(DATA),returnFAIL //到达不合理状态，回溯[5]

ifLENGTH(DATALIST)>BOUND,returnFAIL //已到深度限制，回溯[6]

RULESAPPRULES(DATA) //得出可应用的规则集[7]

LOOP:ifNULL(RULES),returnFAIL //进入死胡同，回溯[8]

RFIRST(RULES) //取出第一条可应用规则[9]

RULESTAIL(RULES)[10]RDATAGEN(R,DATA) //运用规则，生成新状态[11]RDATALISTCONS(RDATA,DATALIST)[12]PATHBACKTRACK1(RDATALIST) //递归[13]ifPATH=FAIL,goLOOP[14]returnCONS(R,PATH)问题的引出回溯搜索：只保留从初始状态到当前状态的一条路径。不能找出全部解

回溯搜索策略的问题问题的引出回溯搜索：只保留从初始状态到当前状态的一条路径。图搜索：保留所有已经搜索过的路径。

图搜索策略3.3图搜索策略

在产生式系统中，如果控制系统保留应用所有规则后生成并连接起来的状态记录图，则称控制系统使用了图搜索策略。其实质是，从一个隐含图中生成确实含有一个目标节点的显式表示子图的搜索过程。节点深度： 根节点深度=0

其它节点深度=父节点深度+1一些基本概念0123路径 设一节点序列为(n0,n1,…,nk)，对于i=1,…,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径。路径的耗散值 一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni,nj)表示从ni到nj的路径的耗散值。扩展一个节点 生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。一些基本概念（续1）搜索方法的一般步骤1、定义状态描述形式2、定义算符—是把问题从一种状态变换到另一种状态的方法代号，即状态演变规则3、确定初始状态（初始节点）和目标状态（目标节点）4、状态更新——根据算符更新当前状态5、目标测试——判断更新后的状态是否为目标状态，若不是则转到4，否则转到66、搜索成功,记录搜索路径用open表和closed表保存搜索经过的各个节点open表和closed表的一般结构开始把S放入OPEN表OPEN表为空表？把第一个节点(n)从OPEN表移至CLOSED表n为目标节点吗？把n的后继节点放入OPEN表的末端，提供返回节点n的指针修改指针方向重排OPEN表失败成功图搜索过程框图是是否否1.G:=G0(G0=s)，Open:=(s)；//G表示图，s为初始节点，设置Open表，最初只含初始节点，存储待扩展的节点。2.Closed:=()； //设置Closed表,起始设置为空表，存储已扩展完的节点。3.

LOOP:IFOpen=(),THENEXIT(FAIL);4.n:=FIRST(Open),REMOVE(n,Open),ADD(n,Closed); //称n为当前节点。5.

IFGOAL(n)，THENEXIT(SUCCESS)； //返回由n到s的路径上的指针，可给出解路径。6.

EXPAND(n)→(mi),G:=ADD(mi,G)；//子节点集{mi}中不能包含n的先辈节点，即不能有环路。7.

标记和修改指针//对出现多路径的情况，根据耗散值选择最好的解路，此时{mi}={mj}∪{mk}∪{ml}7-1)ADD(mj，Open),并标记mj连接到n的指针;

//mj表示Open和Closed中未出现过的子节点。7-2)计算是否要修改mk、ml到n的指针； //mk表示已出现在Open中的子节点，ml表示已出现在Closed中的子节点。7-3)计算是否要修改ml到其后继节点的指针；8．对Open中的节点按某种原则重新排序； 9．GOLOOP(察看Open表)；一般的图搜索算法{mi}节点类型说明mjmkml12345已扩展过的节点

(Closed)待扩展的节点

(Open)s图3-7(a)扩展节点6得到的搜索图实心圆点在Closed中（已扩展节点），空心圆点在Open中（待扩展点）

。设下一步要扩展节点6，并设生成两个子节点:其中子节点4已在Open中(mk)，路径（s→3→2→4）耗散值为5（设每段为单位耗散），新路径（s→6→4）耗散值为4，则节点4的解路径指针应修正：（4→2）改为（4→6），如图3-7(a)。

假设:下一循环扩展节点1，若节点1只生成一个子节点2(Closed中已有，ml)。比较耗散值，显然要修改节点2的指针（3→1），由此又会引起节点4指针的修改（６→２），如图3-7(b)。图3-7(b)扩展节点1得到的搜索图无信息搜索又称盲目搜索/穷举式搜索，只能按照预先规定的搜索控制策略进行搜索，没有任何中间信息来改变这些控制策略。具有盲目性，效率不高，不便于复杂问题的求解。常用方法有广度优先搜索和深度优先搜索以及这两种搜索方法的改良方法。深度优先搜索宽度优先搜索无信息图搜索过程宽度优先搜索最简便的图的搜索算法之一，属于一种盲目搜寻法。目的是系统地展开并检查图中的所有节点，以找寻结果。基本思想是首先搜索和初始节点距离为1的所有顶点，然后再去搜索和出始节点距离为2的其他顶点，依次类推它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

宽度优先搜索宽度优先搜索算法：步1把初始节点S0放入OPEN表中。步2若OPEN表为空,则搜索失败,退出。步3取OPEN表中前面第一个节点N放在CLOSED表中,并冠以顺序编号n。步4若目标节点Sg=N,则搜索成功,结束。步5若N不可扩展,则转步2。步6扩展N,将其所有子节点配上指向N的指针依次放入OPEN表尾部,转步2。宽度优先搜索例：8数码问题九宫格中有8个数码，其中只有一个空格规则是一次只能把一个数码移动到空的格子中要求从一个初始状态移动到一个目标状态宽度优先搜索根据CLOSED表确定解树宽度优先搜索优点完备性：如果问题有解，广度优先搜索总能够在有限步内找到目标节点最优性：在不考虑路径耗散的前提下，广度优先搜索总能够找到最浅的目标节点缺点：遍历各个节点，搜索效率差，消耗大量内存和时间宽度优先搜索的拓展

—代价树宽度搜索代价树宽度搜索（代价一致搜索）对于任意单步路径耗散都是最优的搜索策略其基本思想是优先扩展路径耗散最小的节点对于任意节点n，用f(n)来表示n到初始节点的路径耗散，即代价代价树宽度搜索例：旅行商问题设A、B、C、D、E五个城市，旅行者从A出发，到达城市E，旅行费用如图所示，走怎样的路线费用最小？要求画出代价树、OPEN表和CLOSED表由CLOSED表倒推：E1—C1—A，因此最优旅行路径为：A—C—E，代价为3深度优先搜索深度优先搜索总是先扩展搜索树的当前边缘中最深的节点一种最原始的仿生学算法，来源于爬虫在树枝的搜索过程深度优先搜索深度优先搜索算法：步1把初始节点S0放入OPEN表中。步2若OPEN表为空,则搜索失败,退出。步3取OPEN表中前面第一个节点N放入CLOSED表中,并冠以顺序编号n。步4若目标节点Sg=N,则搜索成功,结束。步5若N不可扩展,则转步2。步6扩展N,将其所有子节点配上指向N的返回指针依次放入OPEN表的首部,转步2。深度优先搜索例：传教士和野人问题有3个传教士和3个野人过河只有一条能装下两个人的船在河的任何一方或者船上，如果野人的人数大于传教士的人数，那么传教士就会有危险.要求安全渡河深度优先搜索分析：由于传教士与野人的总数目是一常数,所以只要表示出河的某一岸上的情况就可以了另外还需要表示出船的位置因此用一个三元组(M,C,B),来表示系统状态M表示河左岸传教士的人数C表示河左岸野人的人数B表示船的位置，1表示船在左岸，0表示船在右岸于是，初始状态为目标状态为深度优先搜索深度优先搜索沿着树的宽度遍历树的节点，它从深度为0的层开始，直到最深的层次。它可以很容易地用队列实现。一般不能保证找到最优解当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制最坏情况时，搜索空间等同于穷举与回溯法的差别：图搜索是一个通用的与问题无关的方法搜索最优策略的比较宽度优先搜索是一种盲目搜索，时间和空间复杂度都比较高，当目标节点距离初始节点较远时会产生许多无用的节点，搜索效率低。宽度优先搜索中，时间需求是一个很大的问题，特别是当搜索的深度比较大时，尤为严重，但是空间需求是比执行时间更严重的问题。

宽度优先搜索优点：目标节点如果存在，用宽度优先搜索算法总可以找到该目标节点，而且是最小（即最短路径）的节点。深度优先搜索的优点是比宽度优先搜索算法需要较少的空间，该算法只需要保存搜索树的一部分，它由当前正在搜索的路径和该路径上还没有完全展开的节点标志所组成。深度优先搜索的存储器要求是深度约束的线性函数。目的解决宽度优先方法的空间问题和回溯方法不能找到最优解的问题。思想 首先给回溯法一个比较小的深度限制，然后逐渐增加深度限制，直到找到解或找遍所以分支为止。渐进式深度优先搜索方法有界深度优先搜索过程总体上按深度优先算法方法进行，但对搜索深度需要给出一个深度限制dm，当深度达到了dm的时候，如果还没有找到解答，就停止对该分支的搜索，换到另外一个分支进行搜索。3.2.3迭代加深搜索（1）深度限制dm很重要。当问题有解，且解的路径长度小于或等于dm时，则搜索过程一定能够找到解，但是和深度优先搜索一样这并不能保证最先找到的是最优解。但是当dm取得太小，解的路径长度大于dm时，则搜索过程中就找不到解，即这时搜索过程甚至是不完备的。（2）深度限制dm不能太大。当dm太大时，搜索过程会产生过多的无用节点，既浪费了计算机资源，又降低了搜索效率。（3）有界深度搜索的主要问题是深度限制值dm的选取。策略说明:

改进方法：（迭代加深搜索）先任意给定一个较小的数作为dm，然后按有界深度算法搜索，若在此深度限制内找到了解，则算法结束；如在此限制内没有找到问题的解，则增大深度限制dm，继续搜索。迭代加深搜索，试图尝试所有可能的深度限制：首先深度为0，然后深度为1，然后为2，等等。如果初始深度为0，则该算法只生成根节点，并检测它。如果根节点不是目标，则深度加1，通过典型的深度优先算法，生成深度为1的树。当深度限制为m时，树的深度为m。迭代加深搜索看起来会很浪费，因为很多节点都可能扩展多次。然而对于很多问题，这种多次的扩展负担实际上很小，直觉上可以想象，如果一棵树的分支系数很大，几乎所有的节点都在最底层上，则对于上面各层节点扩展多次对整个系统来说影响不是很大。表注：b是分支系数，d是解答的深度，m是搜索树的最大深度，l是深度限制。搜索最优策略的比较启发式搜索启发式搜索，也称为有信息搜索，借助问题的特定知识来帮助选择搜索方向在搜索过程中对待扩展的每一个节点进行评估，得到最好的位置，再从这个位置进行搜索直到目标。启发式搜索的目的是省略大量无谓的搜索路径，提到效率。在启发式搜索中，对节点的评价是十分重要的，评价函数是搜索成败的关键。启发式搜索评价函数，也称为启发函数提供问题的启发性信息，按其用途划分，可分为以下三类：用于扩展节点的选择，即用于决定应先扩展哪一个节点，以免盲目扩展用于生成节点的选择，即用于决定应生成哪些后续节点，以免盲目地生成过多无用节点用于删除节点的选择，即用于决定应删除哪些无用节点，以免造成进一步的时空浪费启发式搜索一个节点n的评价函数的构造通常由两部分构成从初始节点到当前节点n的路径耗散从当前节点n到目标节点的期望耗散即：评价函数可表示为：这两部分里，通常是比较明确的，容易得到而难以构造，也没有固定的模式，需要根据具体问题分析利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。启发信息的强度强：降低搜索工作量，但可能导致找不到最优解弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解启发式图搜索引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。希望：定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。基本思想评价函数的格式：

f(n)=g(n)+h(n) f(n)：评价函数

h(n)：启发函数g(x)——从初始节点S0到节点x的实际代价；h(x)——从x到目标节点Sg的最优路径的评估代价，它体现了问题的启发式信息，其形式要根据问题的特性确定，h(x)称为启发式函数。90/641，启发式搜索算法A（A算法）g*(n)：从s到n的最短路径的耗散值h*(n)：从n到g的最短路径的耗散值f*(n)=g*(n)+h*(n)：从s经过n到g的最短路径的耗散值g(n)、h(n)、f(n)分别是g*(n)、h*(n)、f*(n)的估计值91/64符号的意义92/64开始把S放入OPEN表，计算估价函数f(s)OPEN表为空表？选取OPEN表中f值最小的节点i放入CLOSED表i为目标节点吗？扩展i，得后继节点j，计算f(j)，提供返回节点i的指针，利用f(j)对OPEN表重新排序，调整亲子关系及指针失败成功图3.9有序搜索算法框图是否是否算法93/64A算法1.Open:=(s)，f(s):=g(s)+h(s);2.LOOP:IFOpen=()THENEXIT(FAIL);3.n:=FIRST(OPEN);4.IFGOAL(n)THENEXIT(SUCCESS);5.

REMOVE(n,Open),ADD(n,Closed);

6.EXPAND(n)→(mi)，把mi作为n的后继节点添入G，计算

f(n→mi)=g(n→mi)+h(mi)；6-1)ADD(mj,Open);6-2)IFf(n→mk)<f(mk)THENf(mk):=f(n→mk);6-3)IFf(n→ml)<f(ml)THENf(ml):=f(n→ml);ADD(ml,Open);7.Open中的节点按f

值从小到大排序;

8.

GOLOOP;算法的说明：A算法由一般的图搜索算法改变而成。算法第7步每次按照f(n)值的大小对Open表中的元素进行排序，f(n)值小的节点排在前面，而f(n)值大的节点则放在Open表的后面，这样每次扩展节点时，都选择当前f(n)值最小的节点来优先扩展。A算法是按f(n)递增的顺序来排列Open表中节点的，因而优先扩展f(n)值小的节点，体现了好的优先搜索的思想，所以算法A是一个好的优先搜索策略。扩展n后新生成的子节点m1({mj})、m2({mk})、m3({ml})分别计算评价函数值：f(m1)=g(m1)+h(m1)f(n,m2)=g(n,m2)+h(m2)f(n,m3)=g(n,m3)+h(m3)按第6步比较不同路径的耗散值并进行相应的指针修正.snf(n)m2m1m3m31m32f(m3)f(m1)f(m2)f(m31)f(m32)图3-12搜索示意图定义评价函数：

f(x)=d(x)+w(x)

d(x)表示节点在x搜索树中的深度，w(x)表示节点x中不在目标状态中相应位置的数码个数，w(x)就包含了问题的启发式信息。一般来说某节点的w(x)越大，即“不在目标位”的数码个数越多，说明它离目标节点越远。

一个A算法的例子2831647512384765对初始节点S0，由于d(S0)=0，w(S0)=5，因此f(S0)=5。在搜索过程中除了需要计算初始节点的评估函数外，更多的是需要计算新生节点的评估函数。

w(n)=4h计算举例2

831

64751234576

8由CLOSED表可知，解路径为S0-S2-S5-S9-S11-S122831647528314765283164752831647523184765283147652831476528371465832147652318476523184765123847651238476512378465s(4)A(6)B(4)C(6)D(5)E(5)F(6)G(6)H(7)I(5)J(7)K(5)L(5)M(7)目标123456OPEN和CLOSED表的元素排列如下：

OPEN表：1）初始化（s（4））2）第一循环结束（B（4）A（6）C（6））3)第二循环结束（D（5）E（5）A（6）C（6）F（6））4)第三循环结束（E（5）A（6）C（6）F（6）G（6）H（7））5)第四循环结束（I（5）A（6）C（6）F（6）G（6）H（7）J（7））6)第五循环结束（K（5）A（6）C（6）F（6）G（6）H（7）J（7））7)第六循环结束（L（5）A（6）C（6）F（6）G（6）H（7）J（7）M（7））第七循环结束在算法第4步成功退出CLOSED表：1)（）2)（s（4））3)（s（4）B（4））4)（s（4）B（4）D（5））5)（s（4）B（4）D（5）E（5））6)（s（4）B（4）D（5）E（5）I（5））7)（s（4）B（4）D（5）E（5）I（5）K（5））启发式搜索A算法的表现极大地依赖于评价函数，特别是h(n),即：从节点n到目标节点最佳路径的估计耗散假定h*(n)表示节点n到目标节点最佳路径的实际耗散如果h(n)>

h*(n),搜索的节点数少，搜索范围小，效率高，但不能保证得到最优解。如果h(n)<=h*(n)

，这种情况下，搜索的节点数多，搜索范围大，效率低，但能得到最优解启发式搜索满足h(n)<=h*(n)

条件的A搜索，称为A*(A-star)搜索A*搜索中，h(n)越接近h*(n)

，搜索效率越高宽度优先算法可以看作A*算法的特例，即：g(n)是节点所在的层数，h(n)=0

代价树宽度搜索也可以看作A*算法的特例，即：g(n)是节点n的实际路径耗散，h(n)=0跟前两个算法一样，A*算法也具有完备性和最优性启发式搜索例：八数码问题启发函数1：h1(n)=不在位的数码的总数问题1：图中S0状态h(S0)是什么，h*(S0)

又是什么问题2：这个启发函数是否一定满足h(n)<=h*(n)

问题3：对于八数码问题，还能提出其他的启发函数吗？h(S0)=4h*(S0)=5启发式搜索例：八数码问题启发函数2：h2(n)=所有数码到目标位置的距离和（曼哈顿距离）问题1：图中S0状态h(S0)是什么，h*(S0)

又是什么问题2：这个启发函数是否一定满足h(n)<=h*(n)

数码1：1数码2：1数码3：0数码4：0数码5：0数码6：1数码7：0数码8：2h2(S0)=5启发式搜索A*算法当h(n)<=h*(n)

时，同时满足完备性和最优性要求h(n)越接近于真实耗散h*(n)，算法的搜索效率越高，对内存和时间的需求越小如果满足h(n)=h*(n)，是最完美的A*算法h(n)的设计是A*算法的核心，也是最困难的地方完备的最优的效率最优的但，在搜索空间中处于目标等值线内的节点数仍然是解长度的指数级，并且，它在内存空间中保存了所有的节点。108/69A*算法分析爬山法搜索模拟退火搜索局部剪枝搜索遗传算法109/69局部搜索算法启发式搜索-爬山法爬山法模拟人们出游爬山的决策过程以目标值增加的方向为搜索方向如果有多个增加的方向，选使目标值增加速度最快的方向爬山法会在某个峰顶终止，其相邻状态中没有更高的目标值了，称为局部极大值启发式搜索-爬山法爬山法的基本步骤1、初始化，确定初始节点等参数2、检查当前节点是否满足目标条件，如果满足，则搜索成功，结束3、取邻域中每一个相邻节点，计算其目标函数的改进值4、取改进值最大的相邻节点作为搜索目标，替换当前节点5、检查是否满足循环终止条件。如果满足，则中止循环，否则转步2启发式搜索-爬山法爬山法的缺陷难以处理山肩的情况贪婪搜索方向不一定是正确的搜索方向启发式搜索-爬山法爬山法的改进随机爬山法：在上山移动中随机的选择下一步可回溯爬山法：给定启发式的回溯策略，允许回头搜索其他节点洪水爬山法：不断寻找改进方向允许水平移动可回溯启发式搜索-模拟退火算法模拟退火算法（simulatedannealing）爬山法是不完备的，有可能停留在局部最优解上随机行走（遍历）是完备的，但是搜索效率很差模拟退火算法将爬山法与随机行走结合起来，希望同时得到效率和完备性模拟退火搜索：结合爬山法和随机行走比喻：在冶金中退火是为了增强金属和玻璃的韧性和硬度而先把它们加热到高温然后逐渐冷却的过程115/69启发式搜索-模拟退火算法模拟退火过程思想来源于固体退火原理，属于热力学范畴将固体加温至充分高，再让其缓慢冷却加温时，固体内部的粒子随温升脱离原先的平衡态，变为无序状缓慢冷却时，粒子活性逐渐下降，逐渐停留在不同状态，重新形成粒子的排列结构如果降温过程足够缓慢，粒子的排列就会达到一种平衡态，使系统能量最小启发式搜索-模拟退火算法初始状态加温冷却启发式搜索-模拟退火算法模拟退火的基本步骤:

(1)初始化：初始温度T(充分大)，初始状态S，迭代次数L

(2)对k=1，……，L重复第(3)至第6步：

(3)产生新解S’

(4)计算增量Δt’=C(S’)-C(S)，其中C(S)为评价函数

(5)若Δt’<0则接受S’作为新的当前解，否则以概率exp(-Δt’/T)接受S’作为新的当前解

(6)如果满足终止条件则输出当前解作为最优解，结束程序。终止条件通常取为连续若干个新解都没有被接受时终止算法。

(7)T逐渐减少，且T>0，然后转第2步。启发式搜索-模拟退火算法冷却进度表：是指调整模拟退火法的一系列重要参数，它控制温度参数T的初值及其衰减函数。冷却进度表的内容：控制参数T的初值;控制参数T的衰减函数；每一个温度下的迭代次数L，即每一次随机游走过程，要迭代多少次，才能趋于一个准平衡分布结束条件启发式搜索-模拟退火算法Metropolis准则:假设在状态xold时，系统受到某种扰动而使其状态变为xnew。与此相对应，系统的能量也从E(xold)变成E(xnew)系统由状态xold变为状态xnew的接受概率p为：若Δt’<0则接受S’作为新的当前解S，否则以概率exp(-Δt’/T)接受S’作为新的当前解S

启发式搜索-模拟退火算法模拟退火算法的关键点初始温度必须足够高在每一个温度下，状态的转换必须足够充分温度T的下降必须足够缓慢启发式搜索-模拟退火算法模拟退火算法的优缺点

优点：计算过程简单，通用，鲁棒性强适用于并行处理，可用于求解复杂的非线性优化问题缺点：如果降温过程足够缓慢，多得到的解的性能会比较好，但与此相对的是收敛速度太慢;如果降温过程过快，很可能得不到全局最优解随机搜索算法动态规划算法 如果对于任何n，当h(n)=0时，A*算法就成为了动态规划算法。其他的搜索算法（续1）启发式搜索-遗传算法遗传算法(geneticalgorithm,GA)

模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型是一种通过模拟自然进化过程的随机优化搜索方法美国Michigan大学J.Holland教授于1975年首先提出来的启发式搜索-遗传算法遗传算法的基本思想遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象在每次迭代中，根据适应度评估群体中的所有成员，然后选取适应度最高的个体产生新一代群体在被选中的个体中，一部分保持原样地进入下一代群体；另一部分利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群重复此过程，直到满足某种收敛指标为止。遗传算法通过把两个父状态结合来生成后继8皇后的例子，其中每个状态用一个长度为8的字符串来表示，适应度函数取作不相互攻击的皇后对数目。128/69前一页图中（c）1和2生成（d）1启发式搜索-遗传算法遗传算法的特点遗传算法是一种成功的自适应方法，具有很好的健壮性，易于并处理遗传算法长于全局搜索,它不受搜索空间的限制性假设的约束,能以很大的概率从离散的、多极值的、含有噪声的复杂问题中找到全局最优解。遗传欺骗：在遗传算法进化过程中，有时会产生一些超常的个体，因竞争力太突出而控制了选择运算过程，从而影响算法的全局优化性能，导致算法获得某个局部最优解遗传算法最主要的优点（如果有的话）来自于杂交的操作但，数学上可以证明，如果基因编码的位置在初始时候就随机地转换的话，杂交就没有优势了。用模式的思想解释遗传算法模式是其中某些位置未确定的子串，例如246*****。但，目前还不清楚在什么情况下使用遗传算法能够达到好的效果。JamesBaldwin：在生物体存活的时间内学习到的行为能够加快进化速度已被计算机仿真确认130/69讨论3.5.3 分支限界法

分支限界法是优先扩展当前具有最小耗散值分支路径的叶节点n，其评价函数为f(n)=g(n)。其思想是：建立一个局部路径（或分支）的队列表，每次都选耗散值最小的那个分支上的叶节点来扩展，直到生成含有目标节点的路径为止。132/69分支界限法(最小代价优先法)

●基本思想是：每次从OPEN表中选出g(x)值最小的节点进行考察,而不管这个节点在搜索树的什么位置上。

●算法与前面的“全局择优法”

仅有引导搜索的函数不同，前者为启发函数h(x)，后者为代价g(x)。

●但注意：代价值g(x)是从初始节点So方向计算而来的,而启发函数值h(x)则是朝目标节点方向计算的。

分支限界法

过程Branch-Bound1）QUEUE：=（s-s），g（s）=0；2）LOOP：IFQUEUE=（）THENEXIT（FAIL）；3）PATH：=FIRST（QUEUE），n：=LAST（PATH）；4）IFGOAL（n）THENEXIT（SUCCESS）；5）EXPAND（n）→{mi}，计算g（mi）=g（n，mi），REMOVE（s-n，QUEUE），ADD（s-n-mi，QUEUE）；6）QUEUE中局部路径g值最小者排在前面；7）GOLOOP；例：八城市地图网问题应用分支限界法求解图3-14的最短路径问题，其搜索图如图3-15所示。

图3-14 八城市地图网示意图SDBDCEDFEBFABEBFACtg=01g=3A2g=4g=7g=83g=9g=64g=11g=105g=11g=126g=107g=139g=15g=148g=1310g=15g=151112g=14g=1613图3-15 分支限界搜索图求解过程中QUEUE的结果：

初始（s（0））1）（A（3）D（4））2）（D（4）B（7）D（8））3）（E（6）B（7）D（8）A（9））4）（B（7）D（8）A（9）F（10）B（11））5）（D（8）A（9）F（10）B（11）C（11）E（12））6）（A（9）F（10）E（10）B（11）C（11）E（12））7）（F（10）E（10）B（11）C（11）E（12）B（13））8）（E（10）B（11）C（11）E（12）t（13)B（13）)9）（B（11）C（11）E（12）t（13）B（13）F（14）B（15））10）（C（11）E（12）t（13）B（13）F（14）B（15）A（15)C（15））11）（E（12）t（13）B（13）F（14）B（15）A（15）C（15））12）（t（13）B（13）F（14）D（14）B（15）A（15）C（15）F（16））13）结束。3.5.4 动态规划法

动态规划法实际上是对分支限界法的改进。动态规划原理指出，求s→t的最佳路径时，对某个中间节点I，只考虑s到I中具有最小耗散值这一条局部路径就可以，其余s到I的路径是多余的。具有动态规划原理的分支限界算法过程Dynamic-Programming1）QUEUE：=（s-s），g（s）=0；2）LOOP：IFQUEUE：=（）THENEXIT（FAIL）；3）PATH：=FIRST（QUEUE），n：=LAST（PATH）；4）IFGOAL（n）THENEXIT（SUCCESS）；5）EXPAND（n）→{mi}，计算g（mi）=g（n，mi），REMOVE