第二章人工智能搜索问题

人工智能第二章搜索问题本章的内容与目标搜索与搜索问题搜索问题的求解步骤无信息（盲目）搜索有信息（启发式）搜索搜索与搜索问题

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

根据问题的实际情况不断寻找可利用的知识，从而构造一条代价较少的推理路线，使问题得到圆满解决的过程称之为搜索。搜索方法的经典应用8数码问题传教士和野人问题旅行商问题4皇后问题迷宫问题博弈问题…………搜索方法的一般步骤1、定义状态描述形式2、定义算符—是把问题从一种状态变换到另一种状态的方法代号，即状态演变规则3、确定初始状态（初始节点）和目标状态（目标节点）4、状态更新——根据算符更新当前状态5、目标测试——判断更新后的状态是否为目标状态，若不是则转到4，否则转到66、搜索成功,记录搜索路径用open表和closed表保存搜索经过的各个节点open表和closed表的一般结构无信息搜索又称盲目搜索/穷举式搜索，只能按照预先规定的搜索控制策略进行搜索，没有任何中间信息来改变这些控制策略。具有盲目性，效率不高，不便于复杂问题的求解。常用方法有广度优先搜索和深度优先搜索以及这两种搜索方法的改良方法。宽度优先搜索最简便的图的搜索算法之一，属于一种盲目搜寻法。目的是系统地展开并检查图中的所有节点，以找寻结果。基本思想是首先搜索和初始节点距离为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表示船在右岸于是，初始状态为目标状态为深度优先搜索深度优先搜索优点：对内存需求比较少，如果一个节点的全部后代都被完全探索过，那么这个节点和它的全部后继都可以从内存(open表和closed表)中删掉了缺点：不完备，也不最优回溯搜索策略回溯策略属于深度优先搜索的一种变形与深度优先搜索的区别：扩展一个节点时，每次只产生一个后继节点，而不是全部后继回溯策略只保存单一的解路径，占用内存空间很少，只需要一张表即可完成搜索回溯搜索策略例：四皇后问题在４×４方格的棋盘内，放置四个皇后使任意两个皇后不在同一行、同一列、同一对角线（斜线）上要求：找出所有的摆法回溯搜索策略状态描述：单个皇后位置的描述：用(i,j)表示皇后在第i行j列系统状态的描述四个皇后((i1,j1),(i2,j2),(i3,j3),(i4,j4))深度优先搜索的拓展

——深度有限搜索深度有限搜索预先设定一个搜索深度l，用以解决搜索树无边界的问题搜索过程中认为深度为l的节点没有后继节点，必须回溯缺点：增加了算法的不完备性双向搜索双向搜索同时进行两个搜索，可以采用任意搜索方法一个从初始状态向前搜索另一个从目标状态向后搜索当两个搜索在某个节点相遇时，搜索成功无信息搜索的讨论算法评判完备性——是否一定能找到目标节点最优性——搜索得到的解是否最优解时间复杂度——算法的时间需求空间复杂度——算法对计算机内存的需求无信息搜索的讨论重复状态扩展一个节点时，新生成的节点已经在open表或者closed表中存在了，这种情况称为重复状态有些情况下，重复状态会导致搜索失败；有些情况下，重复状态可以保留，但是会带来额外的计算资源的消耗因此，一般期望尽可能避免重复状态这时，有可能出现节点指针重新定向的情况无信息搜索的讨论问题的形式化描述状态描述——用数学方法定义系统状态初始状态、目标状态行动规则——产生后继节点目标测试——判断当前节点是否就是目标节点路径耗散——为每一条搜索路径定义数值化的消耗值无信息搜索的讨论状态描述八数码问题3X3的二维数组行动规则假设r[i][j]=0,则它跟相邻元素可以互换无信息搜索的讨论状态描述4皇后问题状态：在棋盘上任意放置1-4个皇后，每一种放置都是一个状态状态描述：逐一给出各个皇后的放置位置行动规则：增加一个皇后到棋盘上的任何空格无信息搜索的讨论状态描述四色问题，又称四色猜想，世界近代三大数学难题之一要求：只用四种颜色对平面地图染色，要求每两个相同区域不能染成相同颜色1976年美国数学家阿佩尔（K.Appel）与哈肯（W.Haken）宣告借助电子计算机获得了四色定理的证明，又为用计算机证明数学定理开拓了前景无信息搜索的讨论四色问题的状态描述若干地区，四种颜色状态：对任意地区的进行染色，任意染色结果都是一种状态状态描述：用s[k]表示第k个地区的染色，逐一列出所有地区的染色就是系统的状态描述行动规则：给一个没有染色的地区染色无信息搜索的讨论吸尘器的世界只有两个房间A和B每个房间有可能有灰尘也可能没有吸尘器可以在两个房间里移动如果有灰尘，则吸取；否则移动到另一个房间状态：吸尘器位置，房间A、B有没有灰尘状态描述：三元组（A,B,C）行动规则：三个（ToA,ToB,suck）无信息搜索的讨论课堂练习自动抓药系统三个勺子，容量分别为8克、5克和2克可以从药箱把勺子装满或倒空，也可以从一个勺子倒进另一个勺子目标是从药箱抓1克药给出状态描述、初始状态、目标状态以及行动规则状态：三个勺子中药物的数量状态描述：（m1，m2，m3）初始状态：（0，0，0）目标状态:(1,x,x)或(x,1,x)或(x,x,1)行动规则：抓满、倒空或者倒进另一个勺子启发式搜索启发式搜索，也称为有信息搜索，借助问题的特定知识来帮助选择搜索方向在搜索过程中对待扩展的每一个节点进行评估，得到最好的位置，再从这个位置进行搜索直到目标。启发式搜索的目的是省略大量无谓的搜索路径，提到效率。在启发式搜索中，对节点的评价是十分重要的，评价函数是搜索成败的关键。启发式搜索评价函数，也称为启发函数提供问题的启发性信息，按其用途划分，可分为以下三类：用于扩展节点的选择，即用于决定应先扩展哪一个节点，以免盲目扩展用于生成节点的选择，即用于决定应生成哪些后续节点，以免盲目地生成过多无用节点用于删除节点的选择，即用于决定应删除哪些无用节点，以免造成进一步的时空浪费启发式搜索一个节点n的评价函数的构造通常由两部分构成从初始节点到当前节点n的路径耗散从当前节点n到目标节点的期望耗散即：评价函数可表示为：这两部分里，通常是比较明确的，容易得到而难以构造，也没有固定的模式，需要根据具体问题分析启发式搜索贪婪搜索优先扩展距离目标最近的节点例：西安到上海的贪婪搜索启发式搜索贪婪搜索的启发函数只考虑待扩展节点到目标节点的期望耗散，而不考虑初始节点到待扩展节点的实际耗散贪婪搜索类似于深度优先搜索，总是先沿着一条枝搜索下去贪婪搜索既不是完备的，也不是最优的启发式搜索A算法代价树宽度搜索只考虑初始节点到待扩展节点的路径耗散贪婪搜索只考虑待扩展节点到目标节点的期望耗散A算法既考虑待扩展节点到目标节点的期望耗散，又考虑初始节点到待扩展节点的路径耗散启发式搜索A搜索算法的步骤步1把初始节点So放入OPEN表。步2若OPEN表为空,则搜索失败,退出。步3移出OPEN表中第一个节点N放入CLOSED表中,并冠以顺序编号n。步4若目标节点Sg=N,则搜索成功,结束。步5若N不可扩展,则转步2。步6扩展N,生成一组子节点,并利用评价函数为子节点估值，对这组子节点做如下处理：(1)处理重复状态(2)对其余子节点配上指向N的返回指针后放入OPEN表中,并对OPEN表按f(n)值以升序排序,转步2。取open表中f(n)最小的节点，放入closed表启发式搜索A算法举例八数码问题确定用节点深度，也就是初始节点到待扩展节点移动的数码的步数确定

不在位数码的总数初始状态：不在位的数码为1，2，6，8；共四个数码不在位由CLOSED表可知，解路径为S0-S2-S5-S9-S11-S12启发式搜索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*算法的核心，也是最困难的地方启发式搜索启发式函数的构造思想之一松弛法放松行动规则约束的思想方法八数码问题：行动规则：如果以下条件成立，则一个数码可以从A方格移动到B方格

1、B为空

2、A与B相邻放松约束1：A可以移动到B

放松约束2：如果A与B相邻，则A可以移动到B

放松约束3：如果B为空，则A可以移动到B启发式搜索启发式搜索与最优化问题求解现实问题时往往不能明确的知道解的形式，而是只有一堆约束条件，满足约束条件的状态就是一个合法的解满足约束条件的解可能有很多个，人们希望找出使某个目标最满意的解，称为最优解这样的问题称为最优化问题目标条件就是搜索中的评价函数启发式搜索最优化问题目标条件（评价函数）约束条件表示在所有满足约束条件的解中取目标条件最小的为最优解启发式搜索-爬山法爬山法模拟人们出游爬山的决策过程以目标值增加的方向为搜索方向如果有多个增加的方向，选使目标值增加速度最快的方向爬山法会在某个峰顶终止，其相邻状态中没有更高的目标值了，称为局部极大值启发式搜索-爬山法爬山法的基本步骤1、初始化，确定初始节点等参数2、检查当前节点是否满足目标条件，如果满足，则搜索成功，结束3、取邻域中每一个相邻节点，计算其目标函数的改进值4、取改进值最大的相邻节点作为搜索目标，替换当前节点5、检查是否满足循环终止条件。如果满足，则中止循环，否则转步2启发式搜索-爬山法爬山法的缺陷难以处理山肩的情况贪婪搜索方向不一定是正确的搜索方向启发式搜索-爬山法爬山法的改进随机爬山法：在上山移动中随机的选择下一步可回溯爬山法：给定启发式的回溯策略，允许回头搜索其他节点洪水爬山法：不断寻找改进方向允许水平移动可回溯启发式搜索-模拟退火算法模拟退火算法（simulatedannealing）爬山法是不完备的，有可能停留在局部最优解上随机行走（遍历）是完备的，但是搜索效率很差模拟退火算法将爬山法与随机行走结合起来，希望同时得到效率和完备性启发式搜索-模拟退火算法模拟退火过程思想来源于固体退火原理，属于热力学范畴将固体加温至充分高，再让其缓慢冷却加温时，固体内部的粒子随温升脱离原先的平衡态，变为无序状缓慢冷却时，粒子活性逐渐下降，逐渐停留在不同状态，重新形成粒子的排列结构如果降温过程足够缓慢，粒子的排列就会达到一种平衡态，使系统能量最小启发式搜索-模拟退火算法初始状态加温冷却启发式搜索-模拟退火算法模拟退火的基本步骤:

(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的下降必须足够缓慢启发式搜索-模拟退火算法模拟退火算法的优缺点

优点：计算过程简单，通用，鲁棒性强适用于并行处理，可用于求解复杂的非线性优化问题缺点：如果降温过程足够缓慢，多得到的解的性能会比较好，但与此相对的是收敛速度太慢;如果降温过程过快，很可能得不到全局最优解启发式搜索-遗传算法遗传算法(geneticalgorithm,GA)

模拟达尔文生物进化论的自然选择和遗传学机理的生物进化过程的计算模型是一种通过模拟自然进化过程的随机优化搜索方法美国Michigan大学J.Holland教授于1975年首先提出来的启发式搜索-遗传算法自然选择过程遗传算法启发式搜索-遗传算法遗传算法的基本思想遗传算法模拟自然选择和自然遗传过程中发生的繁殖、交叉和基因突变现象在每次迭代中，根据适应度评估群体中的所有成员，然后选取适应度最高的个体产生新一代群体在被选中的个体中，一部分保持原样地进入下一代群体；另一部分利用遗传算子(选择、交叉和变异)对这些个体进行组合，产生新一代的候选解群重复此过程，直到满足某种收敛指标为止。启发式搜索-遗传算法编码编码就是模拟染色体的结构，染色体是由基因排成的串通过某种编码机制把对象抽象为由特定符号按一定顺序排成的串，常用由0，1组成的字串常用随机方法生成若干个个体的集合，该集合称为初始种群。初始种群中个体的数量称为种群规模。启发式搜索-遗传算法例：将[0，1]之间的数编码，精确到小数点以后两位，即0.01，0.02，0.03…0.991、确定编码长度：根据取值空间，可知有99种编码结果，而，因此01编码的长度为7位2、编码：乘以100，然后转化为7位二进制0.01→00000010.02→00000100.03→00000110.99→11000113、解码启发式搜索-遗传算法启发式搜索-遗传算法适应度函数即评价函数，用来描述一个个体的好坏遗传算法中，适应度函数值越大，解的质量越好适应度函数是遗传算法进化过程的驱动力，也是进行自然选择的