搜索问题_人工智能

1、1 3.1 3.1 状态空间搜索概述状态空间搜索概述 3.2 3.2 回溯策略回溯策略 3.3 3.3 图搜索策略图搜索策略 3.4 3.4 盲目的图搜索过程盲目的图搜索过程 3.5 3.5 启发式图搜索过程启发式图搜索过程 人类的实际搜索行为人类的实际搜索行为人工智能所要解决的问题大部分不具备明确的解题人工智能所要解决的问题大部分不具备明确的解题步骤，而只能是利用已有的知识一步一步地摸索前步骤，而只能是利用已有的知识一步一步地摸索前进。进。 根据问题的实际情况不断寻找可利用的知识，从而根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解构造一条代价较少的推

2、理路线，使问题得到圆满解决的过程称之为搜索决的过程称之为搜索 。搜索法的主要任务：确定以何种方式选择规则？搜索法的主要任务：确定以何种方式选择规则？求任一解路的搜索策略：求任一解路的搜索策略： backtrackingbacktracking、 Hill ClimbingHill Climbing、Breadth-firstBreadth-first、 Depth-firstDepth-first、Beam SearchBeam Search、 Best-first Best-first (A).(A).求最佳解路的搜索策略：求最佳解路的搜索策略：British MuseumBritish M

3、useum、Branch and Branch and BoundBound、 Dynamic ProgrammingDynamic Programming、Optimal search (AOptimal search (A* *). ). 求与或图解图的搜索策略：求与或图解图的搜索策略： AOAO* *、 MinimaxMinimax、Alpha-beta Alpha-beta PruningPruning、 Heuristic PruningHeuristic Pruning. .8 8数码问题数码问题传教士和野人问题传教士和野人问题旅行商问题旅行商问题4 4皇后问题皇后问题迷宫问题迷宫

4、问题博弈问题博弈问题搜索算法的输入是给定的问题，输出时表示为动作序列的方案。一旦有了方案，就可以执行该方案所给出的动作了。（执行阶段）求解问题包括：目标表示搜索执行 内容：状态空间的搜索问题。搜索方式：盲目搜索启发式搜索关键问题：如何利用知识，尽可能有效地找到问题的解（最佳解）。3.1.1 3.1.1 图的概念图的概念图是节点及连接节点的弧的集合。图是节点及连接节点的弧的集合。由方向性的弧连接的图是有向图。由方向性的弧连接的图是有向图。节点深度的表示：根节点深度为节点深度的表示：根节点深度为0 0，其他节点深度，其他节点深度d dn+1n+1=d=dn n+1+1。路径：路径：N N个有序节点

5、组成的序列中，若每对相邻节点都表示一条弧，则称该个有序节点组成的序列中，若每对相邻节点都表示一条弧，则称该序列为图中长度为序列为图中长度为N-1N-1的一条路径。的一条路径。 路径耗散值：令路径耗散值：令C C（n ni i，n nj j）为节点）为节点n ni i到节点到节点n nj j这段路径（或弧线）的耗散这段路径（或弧线）的耗散值，一条路径的耗散值等于这条路径上所有弧线耗散值的总和。路径耗散值，一条路径的耗散值等于这条路径上所有弧线耗散值的总和。路径耗散值可按如下递归公式计算：值可按如下递归公式计算：C C（n ni i，t t）=C=C（n ni i，n nj j）+C+C（n nj

6、 j，t t）节点的扩展：操作符（规则）作用到节点（对应于某一状态描述）上，生节点的扩展：操作符（规则）作用到节点（对应于某一状态描述）上，生成其所有后继节点（新状态），并给出弧线的耗散值（相当于使用规则的成其所有后继节点（新状态），并给出弧线的耗散值（相当于使用规则的代价），这个过程叫做扩展一个节点。代价），这个过程叫做扩展一个节点。 图是最直观的描述问题状态空间的工具，属于显图是最直观的描述问题状态空间的工具，属于显式描述。式描述。 图中的节点表示问题的状态，图中的弧表示状图中的节点表示问题的状态，图中的弧表示状态之间的关系。态之间的关系。 初始状态对应待求解问题的已知信息，是图的初始状态

7、对应待求解问题的已知信息，是图的根节点。根节点。状态空间法将一个待定问题的求解过程定义为若干状态空间法将一个待定问题的求解过程定义为若干算子与搜索的有机结合体。算子与搜索的有机结合体。算子定义了对状态的操作，求解的目的在于找出从初始算子定义了对状态的操作，求解的目的在于找出从初始状态转换为某个（或某些）目标状态的一个（或一组）状态转换为某个（或某些）目标状态的一个（或一组）操作算子序列。操作算子序列。以上问题等价于在图中寻找从根节点到某个（或某些）以上问题等价于在图中寻找从根节点到某个（或某些）目标节点的一条（或一组）路径。目标节点的一条（或一组）路径。为提供对问题的形式描述，需要：为提供对问

8、题的形式描述，需要：定义状态空间，包含问题相关对象的各种可能排列。对空间的定义状态空间，包含问题相关对象的各种可能排列。对空间的定义不必枚举所有状态。定义不必枚举所有状态。 规定一个或多个属于该空间的初始状态。该状态用以描述问题规定一个或多个属于该空间的初始状态。该状态用以描述问题求解过程开始时的状态。求解过程开始时的状态。 规定一个或多个属于该空间的目标状态。该状态用以判断是否规定一个或多个属于该空间的目标状态。该状态用以判断是否得到了问题的解。得到了问题的解。 规定一组规则。描述可使用的操作或算子。规定一组规则。描述可使用的操作或算子。 将待求解问题转换成状态空间描述后，使用控制策略对规将

9、待求解问题转换成状态空间描述后，使用控制策略对规则进行选择性的应用，在问题状态空间内进行搜索，直到找出则进行选择性的应用，在问题状态空间内进行搜索，直到找出从初始状态到目标状态的一条（或一组）路径。从初始状态到目标状态的一条（或一组）路径。 状态空间图的搜索，是搜索满足条件的一个（或一组）操作状态空间图的搜索，是搜索满足条件的一个（或一组）操作算子序列的过程，这个过程也是将一个隐式图中包含目的节点的算子序列的过程，这个过程也是将一个隐式图中包含目的节点的某个子图变为显式的过程。这种搜索过程是状态空间问题求解的某个子图变为显式的过程。这种搜索过程是状态空间问题求解的主要基础。主要基础。 搜索过程

10、的要点是：搜索过程的要点是： 从初始或目的状态出发，并将它作为当前状态。从初始或目的状态出发，并将它作为当前状态。扫描操作算子集合，将适用于当前状态的一些操作算子作用扫描操作算子集合，将适用于当前状态的一些操作算子作用在其上得到新的状态，并建立新状态与父母节点的连接指针。在其上得到新的状态，并建立新状态与父母节点的连接指针。1)1)检查生成的新状态是否是结束状态，如果是，则沿着有关指检查生成的新状态是否是结束状态，如果是，则沿着有关指针从结束状态反向到达开始状态，给出一个解；否则，将新针从结束状态反向到达开始状态，给出一个解；否则，将新状态作为当前状态，返回第状态作为当前状态，返回第2)2)步

11、继续搜索。步继续搜索。S0Sg有哪些常用的搜索算法。问题有解时能否找到解。找到的解是最佳的吗？什么情况下可以找到最佳解？求解的效率如何。盲目搜索只是可以区分出哪个是目标状态。一般是按预定的搜索策略进行搜索。没有考虑到问题本身的特性，这种搜索具有很大的盲目性，效率不高，不便于复杂问题的求解。 n启发式搜索n是在搜索过程中加入了与问题有关的启发式信息，用于指导搜索朝着最有希望的方向前进，加速问题的求解并找到最优解。 回溯策略是一种尝试状态空间中各种不同路径的技术。回溯策略是一种尝试状态空间中各种不同路径的技术。带回溯策略的搜索从初始状态出发，不停地、试探地寻找路径直带回溯策略的搜索从初始状态出发，

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

13、方法。递归法是回溯策略的一种最直接的实现方法。 例：四皇后问题例：四皇后问题在在方格的棋盘内，方格的棋盘内，放置四个皇后放置四个皇后使任意两个皇后不在同一使任意两个皇后不在同一行、同一列、同一对角线行、同一列、同一对角线（斜线）上（斜线）上要求：找出要求：找出所有所有的摆法的摆法状态描述：状态描述：单个皇后位置的描述：单个皇后位置的描述： 用用(i,j)(i,j)表示皇后在第表示皇后在第i i行行j j列列系统状态的描述系统状态的描述 四个皇后四个皇后( (i1,j1), (i2,j2), (i3,j3), (i1,j1), (i2,j2), (i3,j3), (i4,j4)(i4,j4) )

14、( )( )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

15、,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)从前有座山 从前有座山 从

16、前有座山当前状态目标状态g变量：变量：DATADATA= =当前状态；当前状态；RULESRULES= =规则集合序列表；规则集合序列表；R R= =当前调用规则；当前调用规则； RDATARDATA= =新生成的状态；新生成的状态；PATHPATH= =当前解路径表。当前解路径表。常量：常量： NILNIL= =空表；空表；FAILFAIL= =回溯点标记；回溯点标记； LOOPLOOP= =循环标号。循环标号。谓词： TERM(DATA)；(DATA满足结束条件) DEADEND(DATA)；(DATA是非法状态) NULL(RULES)。(规则集合序列表空)函数： RETURN 返回自变

17、量的值； APPRULES 求可应用的规则表； FIRST 从表中取表头的一个元素； TAIL 除去表头的一个元素后得到新表； GEN 调用规则生成新状态； CONS 在表头插入新元素，构造新表； BACKTRACK(RDATA) 递归过程作用于新状态。BACKTRACK（DATA）DATA：当前状态。返回值：从当前状态到目标状态的路径（以规则表的形式表示）或FAIL。1.1.if TERM (DATA), return NILif TERM (DATA), return NIL； / / 当当DATADATA满足终止条件时，返回空表满足终止条件时，返回空表. .if DEADEND (DAT

18、A), renturn FAILif DEADEND (DATA), renturn FAIL； /当当DATADATA状态不合法时，必须回溯。状态不合法时，必须回溯。3.3.RULES APPRULES(DATA) RULES APPRULES(DATA) /DATA/DATA状态的可用规则加入规则集合序列状态的可用规则加入规则集合序列表。表。4.4.LOOP: if NULL(RULES), return FAILLOOP: if NULL(RULES), return FAIL；/如果规则集合序列表空，必须回溯。如果规则集合序列表空，必须回溯。5.5.R FIRST(RULES)R FI

19、RST(RULES)； /读规则集合序列表的第一条规则到变量读规则集合序列表的第一条规则到变量R R。6.6.RULES TAIL(RULES)RULES TAIL(RULES)； /从规则集合序列表删除被选中的规则。从规则集合序列表删除被选中的规则。7.7.RDATA GENRDATA GEN（R R，DATADATA）；）； /被选中的规则作用于当前状态。被选中的规则作用于当前状态。8.8.PATHBACKTRACK(RDATA)PATHBACKTRACK(RDATA)； /对新状态递归调用本过程对新状态递归调用本过程9.9.if PATH =FAIL, go LOOPif PATH =F

20、AIL, go LOOP； /如果递归失败，则用另一条规则如果递归失败，则用另一条规则10.10.return CONS(R,PATH)return CONS(R,PATH)； /否则把否则把R R加在解路径表中，向上传递成功的加在解路径表中，向上传递成功的 规则表，过程返回解路径规则表（或局部解规则表，过程返回解路径规则表（或局部解 路径子表）路径子表）解决办法：对搜索深度加以限制记录从初始状态到当前状态的路径当前状态l问题：深度问题死循环问题11 DATA FIRST(DATALIST)DATA FIRST(DATALIST)2 if MEMBER(DATA,TAIL(DATALIST),

21、 return FAIL2 if MEMBER(DATA,TAIL(DATALIST), return FAIL / / / / 有环路，回溯有环路，回溯 33 if TERM(DATA), return NIL if TERM(DATA), return NIL / / / / 到达目标，成功返回到达目标，成功返回4 if DEADEND(DATA), return FAIL 4 if DEADEND(DATA), return FAIL / / / / 到达不合理状态，回溯到达不合理状态，回溯5 if LENGTH(DATALIST) BOUND, return FAIL5 if LENG

22、TH(DATALIST) BOUND, return FAIL / / / / 已到深度限制，回溯已到深度限制，回溯6 RULES APPRULES(DATA) 6 RULES APPRULES(DATA) / / / / 得出可应用的规则集得出可应用的规则集7 LOOP: if NULL(RULES), return FAIL 7 LOOP: if NULL(RULES), return FAIL / / / / 进入死胡同，回溯进入死胡同，回溯8 R FIRST(RULES) 8 R FIRST(RULES) / / / / 取出第一条可应用规则取出第一条可应用规则9 RULES TAIL

23、(RULES)9 RULES TAIL(RULES)10 RDATA 10 RDATA GEN(R, GEN(R, DATA) DATA) / / / / 运用规则，生成新状态运用规则，生成新状态11 RDATALIST CONS(RDATA, DATALIST)11 RDATALIST CONS(RDATA, DATALIST)12 PATH BACKTRACK1(RDATALIST) 12 PATH BACKTRACK1(RDATALIST) / / / / 递归递归13 if PATH=FAIL, go LOOP13 if PATH=FAIL, go LOOP14 return CONS

24、(R, PATH) 14 return CONS(R, PATH) 问题的引出回溯搜索：只保留从初始状态到当前状态的一条路径。不能找出全部解问题的引出回溯搜索：只保留从初始状态到当前状态的一条路径。图搜索：保留所有已经搜索过的路径。 在产生式系统中，如果控制系统保留应用所有规则后生成并连接起来的状态记录图，则称控制系统使用了图搜索策略。 其实质是，从一个隐含图中生成确实含有一个目标节点的显式表示子图的搜索过程。 节点深度：根节点深度=0其它节点深度=父节点深度+10123路径设一节点序列为(n0, n1,nk)，对于i=1,k，若节点ni-1具有一个后继节点ni，则该序列称为从n0到nk的路径

25、。路径的耗散值一条路径的耗散值等于连接这条路径各节点间所有耗散值的总和。用C(ni, nj)表示从ni到nj的路径的耗散值。扩展一个节点生成出该节点的所有后继节点，并给出它们之间的耗散值。这一过程称为“扩展一个节点”。1 1、定义状态描述形式、定义状态描述形式2 2、定义算符、定义算符是把问题从一种状态变换到另一种是把问题从一种状态变换到另一种状态的方法代号，即状态演变规则状态的方法代号，即状态演变规则3 3、确定初始状态（初始节点）和目标状态（目标、确定初始状态（初始节点）和目标状态（目标节点）节点）4 4、状态更新、状态更新根据算符更新当前状态根据算符更新当前状态5 5、目标测试、目标测试

26、判断更新后的状态是否为目标状判断更新后的状态是否为目标状态，若不是则转到态，若不是则转到4 4，否则转到，否则转到6 66 6、搜索成功、搜索成功, ,记录搜索路径记录搜索路径 用用openopen表和表和closedclosed表保存搜索经过的各个节表保存搜索经过的各个节点点开始开始把把S放入放入OPEN表表OPEN表为空表？表为空表？把第一个节点把第一个节点(n)从从OPEN表移至表移至CLOSED表表n为目标节点吗？为目标节点吗？把把n的后继节点放入的后继节点放入OPEN表的表的末端，提供返回节点末端，提供返回节点n的指针的指针修改指针方向修改指针方向重排重排OPEN表表失败失败成功成功

27、图搜索过程框图图搜索过程框图是是是是否否否否1. G:=G0 (G0=s)，Open:=(s)；/G表示图表示图，s为初始节点，设置为初始节点，设置Open表，最初只含初始节点，存储待表，最初只含初始节点，存储待扩展的节点。扩展的节点。2. Closed:=( )；/设置设置Closed表表,起始设置为空表，存储已扩展完的节点。起始设置为空表，存储已扩展完的节点。3. LOOP: IF Open=( ), THEN EXIT(FAIL);4. n:=FIRST(Open), REMOVE(n, Open), ADD(n, Closed); /称称n为当前节点。为当前节点。5. IF GOAL(

28、n)，THEN EXIT(SUCCESS)；/返回由返回由n到到s的路径上的指针，可给出解路径的路径上的指针，可给出解路径。6. EXPAND(n) (mi), G:=ADD(mi, G)；/子节点集子节点集mi中不能包含中不能包含n的先辈节点，即不能有环路。的先辈节点，即不能有环路。7 . 标 记 和 修 改 指 针标 记 和 修 改 指 针 / / 对 出 现 多 路 径 的 情 况 ， 根 据 耗 散 值 选 择 最 好 的 解 路 ， 此 时对 出 现 多 路 径 的 情 况 ， 根 据 耗 散 值 选 择 最 好 的 解 路 ， 此 时mi=mjmkml 7-1) ADD(mj，Op

29、en), 并标记并标记mj连接到连接到n的指针的指针;/mj表示表示Open和和Closed中未出现过的子节点。中未出现过的子节点。7-2)计算是否要修改计算是否要修改mk、ml到到n的指针；的指针； /mk表示已出现在表示已出现在 Open中的子节点，中的子节点，ml表示已出表示已出现在现在Closed中的子节点。中的子节点。7-3)计算是否要修改计算是否要修改ml到其后继节点的指针；到其后继节点的指针；8对对Open中的节点按某种原则重新排序；中的节点按某种原则重新排序；9GO LOOP(察看察看Open表表)；mjmkml12345已扩展过的节点 ( Closed )待扩展的节点 ( O

30、pen )s图3-7(a)扩展节点6得到的搜索图 实心圆点在Closed中（已扩展节点），空心圆点在Open中（待扩展点） 。设下一步要扩展节点6，并设生成两个子节点:其中子节点4已在Open中(mk)，路径（s324）耗散值为5（设每段为单位耗散），新路径（s64）耗散值为4，则节点4的解路径指针应修正：（42）改为（46），如图3-7(a)。 假设假设: :下一循环扩展节点下一循环扩展节点1 1，若节点若节点1 1只生成一个子节点只生成一个子节点2 (Closed2 (Closed中中已有已有，mml l) ) 。比较耗散值，显比较耗散值，显然 要 修 改 节 点然 要 修 改 节 点 2

31、 2 的 指 针的 指 针（3131），），由此又会引起节点由此又会引起节点4 4指针的修改指针的修改（） ，如如图图3-7(b)3-7(b)。图3-7(b)扩展节点1得到的搜索图 又称盲目搜索又称盲目搜索/ /穷举式搜索，只能按照预先规定穷举式搜索，只能按照预先规定的搜索控制策略进行搜索，没有任何中间信息来的搜索控制策略进行搜索，没有任何中间信息来改变这些控制策略。改变这些控制策略。具有盲目性，效率不高，不便于复杂问题的求解。具有盲目性，效率不高，不便于复杂问题的求解。常用方法有广度优先搜索和深度优先搜索以及这常用方法有广度优先搜索和深度优先搜索以及这两种搜索方法的改良方法。两种搜索方法的改

32、良方法。深度优先搜索宽度优先搜索最简便的图的搜索算法之一，属于一种盲目搜寻法。最简便的图的搜索算法之一，属于一种盲目搜寻法。目的是系统地展开并检查图中的所有节点，以找寻目的是系统地展开并检查图中的所有节点，以找寻结果。结果。基本思想是首先搜索和初始节点距离为基本思想是首先搜索和初始节点距离为1 1的所有顶的所有顶点，然后再去搜索和出始节点距离为点，然后再去搜索和出始节点距离为2 2的其他顶点，的其他顶点，依次类推依次类推它并不考虑结果的可能位置，彻底地搜索整张图，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。直到找到结果为止。 宽度优先搜索算法：宽度优先搜索算法：步步1 1 把

33、初始节点把初始节点S S0 0放入放入OPENOPEN表中。表中。步步2 2 若若OPENOPEN表为空表为空, , 则搜索失败则搜索失败, ,退出。退出。步步3 3 取取OPENOPEN表中前面第一个节点表中前面第一个节点N N放在放在CLOSEDCLOSED表中表中, , 并冠以并冠以顺序编号顺序编号n n。步步4 4 若目标节点若目标节点Sg= Sg= N N, ,则搜索成功则搜索成功, , 结束。结束。步步5 5 若若N N不可扩展不可扩展, , 则转步则转步2 2。步步6 6 扩展扩展N N, , 将其所有子节点配上指向将其所有子节点配上指向N N的指针依次放入的指针依次放入OPEN

34、OPEN表表尾部尾部, , 转步转步2 2。例：例： 8 8数码问题数码问题九宫格中有九宫格中有8 8个数码，其中只有一个空格个数码，其中只有一个空格规则是一次只能把一个数码移动到空的格子中规则是一次只能把一个数码移动到空的格子中要求从一个初始状态移动到一个目标状态要求从一个初始状态移动到一个目标状态 根据CLOSED表确定解树S13S22S5S1S0S0S1S5S13S22优点优点完备性：如果问题有解，完备性：如果问题有解，广度优先搜索总能够在有广度优先搜索总能够在有限步内找到目标节点限步内找到目标节点最优性：在不考虑路径耗最优性：在不考虑路径耗散的前提下，广度优先搜散的前提下，广度优先搜索

35、总能够找到最浅的目标索总能够找到最浅的目标节点节点缺点：缺点：遍历各个节点，搜索效率遍历各个节点，搜索效率差，消耗大量内存和时间差，消耗大量内存和时间代价树宽度搜索（代价一致代价树宽度搜索（代价一致搜索）对于任意单步路径耗搜索）对于任意单步路径耗散都是最优的搜索策略散都是最优的搜索策略其基本思想是优先扩展路径其基本思想是优先扩展路径耗散最小的节点耗散最小的节点对于任意节点对于任意节点n n，用，用f(n)f(n)来来表示表示n n到初始节点的路径耗到初始节点的路径耗散，即代价散，即代价f(B)=1f(C)=2f(D)=3f(E)=2f(F)=5f(G)=4例：例： 旅行商问题旅行商问题设设A

36、A、B B、C C、D D、E E五个五个城市，旅行者从城市，旅行者从A A出发，出发，到达城市到达城市E E，旅行费用如，旅行费用如图所示，走怎样的路线图所示，走怎样的路线费用最小？费用最小？要求画出代价树、要求画出代价树、OPENOPEN表和表和CLOSEDCLOSED表表由CLOSED表倒推：E1C1A，因此最优旅行路径为：ACE，代价为3深度优先搜索总是先扩深度优先搜索总是先扩展搜索树的当前边缘中展搜索树的当前边缘中最深的节点最深的节点一种最原始的仿生学算一种最原始的仿生学算法，来源于爬虫在树枝法，来源于爬虫在树枝的搜索过程的搜索过程深度优先搜索算法：深度优先搜索算法：步步1 1 把初

37、始节点把初始节点S S0 0放入放入OPENOPEN表中。表中。步步2 2 若若OPENOPEN表为空表为空, , 则搜索失败则搜索失败, , 退出。退出。 步步3 3 取取OPENOPEN表中前面第一个节点表中前面第一个节点N N 放入放入CLOSEDCLOSED表中表中, ,并冠以并冠以顺序编号顺序编号n n。步步4 4 若目标节点若目标节点S Sg=g=N N, , 则搜索成功则搜索成功, ,结束。结束。 步步5 5 若若N N 不可扩展不可扩展, , 则转步则转步2 2。步步6 6 扩展扩展N, N, 将其所有子节点配上指向将其所有子节点配上指向N N 的返回指针依次放入的返回指针依次

38、放入OPENOPEN表的表的首部首部, , 转步转步2 2。例：传教士和野人问题例：传教士和野人问题有有3 3个传教士和个传教士和3 3个野人个野人过河过河只有一条能装下两个人的只有一条能装下两个人的船船在河的任何一方或者船上，在河的任何一方或者船上，如果野人的人数大于传教如果野人的人数大于传教士的人数，那么传教士就士的人数，那么传教士就会有危险会有危险. . 要求安全渡河要求安全渡河分析：分析：由于传教士与野人的总数目是一常数由于传教士与野人的总数目是一常数, , 所以只要表示出河所以只要表示出河的某一岸上的情况就可以了的某一岸上的情况就可以了另外还需要表示出船的位置另外还需要表示出船的位置

39、因此用一个三元组因此用一个三元组(M, C, B), (M, C, B), 来表示系统状态来表示系统状态 MM表示河左岸传教士的人数表示河左岸传教士的人数 C C表示河左岸野人的人数表示河左岸野人的人数 B B表示船的位置，表示船的位置，1 1表示船在左岸，表示船在左岸，0 0表示船在右岸表示船在右岸于是，初始状态为于是，初始状态为 目标状态为目标状态为(3,3,1)(0,0,0)沿着树的宽度遍历树的节点，它从深度为0的层开始，直到最深的层次。它可以很容易地用队列实现。一般不能保证找到最优解当深度限制不合理时，可能找不到解，可以将算法改为可变深度限制最坏情况时，搜索空间等同于穷举与回溯法的差别

40、：图搜索是一个通用的与问题无关的方法宽度优先搜索是一种盲目搜索，时间和空间复杂度都比较高，当目标节点距离初始节点较远时会产生许多无用的节点，搜索效率低。宽度优先搜索中，时间需求是一个很大的问题，特别是当搜索的深度比较大时，尤为严重，但是空间需求是比执行时间更严重的问题。 宽度优先搜索优宽度优先搜索优点：点：目标节点如果存在，用宽度优先搜索算法总可以找到该目标节点，而且是最小（即最短路径）的节点。深度优先搜索的优点是比宽度优先搜索算法需要较少的空间，该算法只需要保存搜索树的一部分，它由当前正在搜索的路径和该路径上还没有完全展开的节点标志所组成。深度优先搜索的存储器要求是深度约束的线性函数。 目的

41、解决宽度优先方法的空间问题和回溯方法不能找到最优解的问题。思想首先给回溯法一个比较小的深度限制，然后逐渐增加深度限制，直到找到解或找遍所以分支为止。有界深度优先搜索有界深度优先搜索过程总体上按深度优先算法方法进行，但对搜索深度需要给出一个深度限制dm，当深度达到了dm的时候，如果还没有找到解答，就停止对该分支的搜索，换到另外一个分支进行搜索。（1）深度限制深度限制dmdm很重要很重要。当问题有解，且解的路径长度小于或等于dm时，则搜索过程一定能够找到解，但是和深度优先搜索一样这并不能保证最先找到的是最优解。但是当dm取得太小，解的路径长度大于dm时，则搜索过程中就找不到解，即这时搜索过程甚至是

42、不完备的。（2）深度限制深度限制dmdm不能太大不能太大。当dm太大时，搜索过程会产生过多的无用节点，既浪费了计算机资源，又降低了搜索效率。（3）有界深度搜索的主要问题是深度限制值深度限制值dmdm的的选取选取。改进方法： （迭代加深搜索） 先任意给定一个较小的数作为dm，然后按有界深度算法搜索，若在此深度限制内找到了解，则算法结束；如在此限制内没有找到问题的解，则增大深度限制dm，继续搜索。迭代加深搜索，试图尝试所有可能的深度限制：首先深度为0，然后深度为1，然后为2，等等。如果初始深度为0，则该算法只生成根节点，并检测它。如果根节点不是目标，则深度加1，通过典型的深度优先算法，生成深度为1

43、的树。当深度限制为m时，树的深度为m。 迭代加深搜索看起来会很浪费，因为很多节点都可能扩展多次。然而对于很多问题，这种多次的扩展负担实际上很小，直觉上可以想象，如果一棵树的分支系数很大，几乎所有的节点都在最底层上，则对于上面各层节点扩展多次对整个系统来说影响不是很大。 表注：b是分支系数，d是解答的深度，m是搜索树的最大深度，l是深度限制。启发式搜索，也称为有信息搜索，借助问题的特定启发式搜索，也称为有信息搜索，借助问题的特定知识来帮助选择搜索方向知识来帮助选择搜索方向在搜索过程中对待扩展的每一个节点进行评估，得在搜索过程中对待扩展的每一个节点进行评估，得到最好的位置，再从这个位置进行搜索直到

44、目标。到最好的位置，再从这个位置进行搜索直到目标。启发式搜索的目的是省略大量无谓的搜索路径，提启发式搜索的目的是省略大量无谓的搜索路径，提到效率。到效率。在启发式搜索中，对节点的评价是十分重要的，评在启发式搜索中，对节点的评价是十分重要的，评价函数是搜索成败的关键。价函数是搜索成败的关键。 评价函数，也称为启发函数提供问题的启发性信息，评价函数，也称为启发函数提供问题的启发性信息，按其用途划分，可分为以下三类：按其用途划分，可分为以下三类：用于扩展节点的选择，即用于决定应先扩展哪一个节点，用于扩展节点的选择，即用于决定应先扩展哪一个节点，以免盲目扩展以免盲目扩展用于生成节点的选择，即用于决定应

45、生成哪些后续节点，用于生成节点的选择，即用于决定应生成哪些后续节点，以免盲目地生成过多无用节点以免盲目地生成过多无用节点用于删除节点的选择，即用于决定应删除哪些无用节点，用于删除节点的选择，即用于决定应删除哪些无用节点，以免造成进一步的时空浪费以免造成进一步的时空浪费一个节点一个节点n n的评价函数的构造通常由两部分构成的评价函数的构造通常由两部分构成从初始节点到当前节点从初始节点到当前节点n n的路径耗散的路径耗散从当前节点从当前节点n n到目标节点的期望耗散到目标节点的期望耗散即：评价函数可表示为：即：评价函数可表示为：这两部分里，这两部分里， 通常是比较明确的，容易得到通常是比较明确的，

46、容易得到而而 难以构造，也没有固定的模式，需要根难以构造，也没有固定的模式，需要根据具体问题分析据具体问题分析( )( )( )f ng nh n( )g n( )h n( )g n( )h n利用知识来引导搜索，达到减少搜索范围，降低问题复杂度的目的。启发信息的强度强：降低搜索工作量，但可能导致找不到最优解弱：一般导致工作量加大，极限情况下变为盲目搜索，但可能可以找到最优解引入启发知识，在保证找到最佳解的情况下，尽可能减少搜索范围，提高搜索效率。定义一个评价函数f，对当前的搜索状态进行评估，找出一个最有希望的节点来扩展。评价函数的格式：f(n) = g(n) + h(n)f(n)：评价函数h

47、(n)：启发函数g(x)从初始节点S0到节点x的实际代价；h(x)从x到目标节点Sg的最优路径的评估代价，它体现了问题的启发式信息，其形式要根据问题的特性确定，h(x)称为启发式函数。90/64g*(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/6492/64开始开始把把S放入放入OPEN表，表，计算估价函数计算估价函数 f (s)OPEN表为空表？表为空表？选取选取OPEN表中表中f值最小的节点值最小的节点i放入放入CL

48、OSED表表i为目标节点吗？为目标节点吗？扩展扩展i，得后继节点，得后继节点j，计算，计算f(j)，提供返回，提供返回节点节点i的指针，利用的指针，利用f(j)对对OPEN表重新排表重新排序，调整亲子关系及指针序，调整亲子关系及指针失败失败成功成功图图3.9 有序搜索算法框图有序搜索算法框图是是否否是是否否v算法93/641. Open:=(s)1. Open:=(s)，f(s):=g(s)+h(s); f(s):=g(s)+h(s); 2. LOOP: IF Open=( ) THEN EXIT(FAIL); 2. LOOP: IF Open=( ) THEN EXIT(FAIL); 3.

49、n:=FIRST(OPEN); 3. n:=FIRST(OPEN); 4. IF GOAL (n) THEN EXIT(SUCCESS); 4. IF GOAL (n) THEN EXIT(SUCCESS); 5.REMOVE (n, Open), ADD(n, Closed); 5.REMOVE (n, Open), ADD(n, Closed); 6. EXPAND(n) (m6. EXPAND(n) (mi i) )，把把mmi i作为作为n n的后继节点添入的后继节点添入G G，计算计算f(nmf(nmi i)=g(nm)=g(nmi i)+h(m)+h(mi i) )； 6-1) A

50、DD(m6-1) ADD(mj j, Open); , Open); 6-2) IF f(nm6-2) IF f(nmk k) f(m) f(mk k) THEN f(m) THEN f(mk k):=f(nm):=f(nmk k); ); 6-3) IF f(nm6-3) IF f(nml l) ) h*(n) , , 搜索的节点数少，搜索范围小，搜索的节点数少，搜索范围小，效率高，但不能保证得到最优解。效率高，但不能保证得到最优解。如果如果h(n)= = h*(n) ，这种情况下，搜索的节点数多，这种情况下，搜索的节点数多，搜索范围大，效率低，但能得到最优解搜索范围大，效率低，但能得到最优

51、解满足满足h(n)= = h*(n) 条件的条件的A A搜索，称为搜索，称为A A* * (A- (A-star)star)搜索搜索A A* * 搜索中，搜索中，h(n)越接近越接近h*(n) ，搜索效率越高，搜索效率越高宽度优先算法可以看作宽度优先算法可以看作A A* *算法的特例，即：算法的特例，即：g(n)是节点所在的层数，是节点所在的层数，h(n)=0 0 代价树宽度搜索也可以看作代价树宽度搜索也可以看作A A* *算法的特例，即：算法的特例，即：g(n)是节点是节点n的实际路径耗散，的实际路径耗散，h(n)=0 0跟前两个算法一样，跟前两个算法一样，A A* *算法也具有完备性和最优

52、算法也具有完备性和最优性性例：八数码问题例：八数码问题启发函数启发函数1 1：h1(n)=不在位的不在位的数码的总数数码的总数 问题问题1 1：图中：图中S0S0状态状态h(S0)是什么，是什么， h*(S0) 又是什么又是什么 问题问题2 2：这个启发函数是否一定：这个启发函数是否一定满足满足h(n)= = h*(n) 问题问题3 3：对于八数码问题，还能：对于八数码问题，还能提出其他的启发函数吗？提出其他的启发函数吗？h(S0)=4h*(S0)=5例：八数码问题例：八数码问题启发函数启发函数2 2： h2(n)=所所有数码到目标位置的距有数码到目标位置的距离和（曼哈顿距离）离和（曼哈顿距离

53、） 问题问题1 1：图中：图中S0S0状态状态h(S0)是什么，是什么， h*(S0) 又是什又是什么么 问题问题2 2：这个启发函数是：这个启发函数是否一定满足否一定满足h(n)= = h*(n) 数码1：1 数码2：1数码3：0 数码4：0数码5：0 数码6：1数码7：0 数码8：2h2(S0)=5A A* *算法算法当当h(n)= = h*(n) 时，同时满足完备性和最优时，同时满足完备性和最优性要求性要求h(n)越接近于真实耗散越接近于真实耗散h*(n)，算法的搜索效算法的搜索效率越高，对内存和时间的需求越小率越高，对内存和时间的需求越小如果满足如果满足h(n)= = h*(n)，是最

54、完美的是最完美的A*算法算法h(n)的设计是的设计是A*算法的核心，也是最困难的算法的核心，也是最困难的地方地方完备的最优的效率最优的但，在搜索空间中处于目标等值线内的节点数仍然是解长度的指数级，并且，它在内存空间中保存了所有的节点。108/69爬山法搜索模拟退火搜索局部剪枝搜索遗传算法109/69爬山法爬山法模拟人们出游爬山的决策过模拟人们出游爬山的决策过程程以目标值增加的方向为搜索以目标值增加的方向为搜索方向方向如果有多个增加的方向，选如果有多个增加的方向，选使目标值增加速度最快的方使目标值增加速度最快的方向向爬山法会在某个峰顶终止，爬山法会在某个峰顶终止，其相邻状态中没有更高的目其相邻状

55、态中没有更高的目标值了，称为局部极大值标值了，称为局部极大值爬山法的基本步骤爬山法的基本步骤1 1、初始化，确定初始节点等参数、初始化，确定初始节点等参数2 2、检查当前节点是否满足目标条件，如果满足，则搜索成、检查当前节点是否满足目标条件，如果满足，则搜索成功，结束功，结束3 3、取邻域中每一个相邻节点，计算其目标函数的改进值、取邻域中每一个相邻节点，计算其目标函数的改进值4 4、取改进值最大的相邻节点作为搜索目标，替换当前节点、取改进值最大的相邻节点作为搜索目标，替换当前节点5 5、检查是否满足循环终止条件。如果满足，则中止循环，、检查是否满足循环终止条件。如果满足，则中止循环，否则转步否

56、则转步2 2爬山法的缺陷爬山法的缺陷难以处理山肩的情况难以处理山肩的情况贪婪搜索方向不一定是正确的搜索方向贪婪搜索方向不一定是正确的搜索方向爬山法的改进爬山法的改进随机爬山法：在上山移动中随机的选择下一步随机爬山法：在上山移动中随机的选择下一步可回溯爬山法：给定启发式的回溯策略，允许回头搜索其他可回溯爬山法：给定启发式的回溯策略，允许回头搜索其他节点节点洪水爬山法：洪水爬山法： 不断寻找改进方向不断寻找改进方向 允许水平移动允许水平移动 可回溯可回溯模拟退火算法（模拟退火算法（simulated annealingsimulated annealing）爬山法是不完备的，有可能停留在局部最优解

57、上爬山法是不完备的，有可能停留在局部最优解上随机行走（遍历）是完备的，但是搜索效率很差随机行走（遍历）是完备的，但是搜索效率很差模拟退火算法将爬山法与随机行走结合起来，希望同时得模拟退火算法将爬山法与随机行走结合起来，希望同时得到效率和完备性到效率和完备性比喻：在冶金中退火是为了增强金属和玻璃的韧性和硬度而先把它们加热到高温然后逐渐冷却的过程115/69模拟退火过程模拟退火过程思想来源于固体退火原理，属于热力学范畴思想来源于固体退火原理，属于热力学范畴将固体加温至充分高，再让其缓慢冷却将固体加温至充分高，再让其缓慢冷却加温时，固体内部的粒子随温升脱离原先的平衡态，变为加温时，固体内部的粒子随温

58、升脱离原先的平衡态，变为无序状无序状缓慢冷却时，粒子活性逐渐下降，逐渐停留在不同状态，缓慢冷却时，粒子活性逐渐下降，逐渐停留在不同状态，重新形成粒子的排列结构重新形成粒子的排列结构如果降温过程足够缓慢，粒子的排列就会达到一种平衡态，如果降温过程足够缓慢，粒子的排列就会达到一种平衡态，使系统能量最小使系统能量最小 初始状态加温冷却模拟退火的基本步骤模拟退火的基本步骤: : (1) 初始化：初始温度初始化：初始温度T(充分大充分大)，初始状态，初始状态S， 迭代迭代次数次数L (2) 对对k=1，L重复第重复第(3)至第至第6步：步： (3) 产生新解产生新解S (4) 计算增量计算增量t=C(S

59、)-C(S)，其中，其中C(S)为评价函数为评价函数 (5) 若若t0，然后转第，然后转第2步。步。 冷却进度表：冷却进度表：是指调整模拟退火法的一系列重要参数，它控制温度参数是指调整模拟退火法的一系列重要参数，它控制温度参数T T的初值及其衰减函数。的初值及其衰减函数。冷却进度表的内容：冷却进度表的内容： 控制参数控制参数T T的初值的初值; ; 控制参数控制参数T T的衰减函数；的衰减函数； 每一个温度下的迭代次数每一个温度下的迭代次数L L，即每一次随机游走过程，要迭代，即每一次随机游走过程，要迭代多少次，才能趋于一个准平衡分布多少次，才能趋于一个准平衡分布 结束条件结束条件Metrop

60、olis准则准则: 假设在状态假设在状态xold时，系统受到某种扰动而使其状态变为时，系统受到某种扰动而使其状态变为xnew。与此相对应，系统的能量也从与此相对应，系统的能量也从E(xold)变成变成E(xnew)系统由状态系统由状态xold变为状态变为状态xnew的接受概率的接受概率p为：为： 若若t0则接受则接受S作为新的当前解作为新的当前解S， 否则以概率否则以概率exp(-t/T)接受接受S作为新的当前解作为新的当前解S 模拟退火算法的关键点模拟退火算法的关键点初始温度必须足够高初始温度必须足够高在每一个温度下，状态的转换必须足够充分在每一个温度下，状态的转换必须足够充分温度温度T T