1、AI:问题求解基本理论与方法内容提要搜索的定义具体问题的形式化盲信息搜索有信息搜索/启发式搜索优化问题的搜索算法联机/在线搜索搜索的定义三国华容道找出：一个移动序列，放出曹操Introduced in 1878 by Sam Loyd,who dubbed himself“Americas greatest puzzle-expert”类似游戏：数码（8，15，,n2-1,)12345678121511141013956784321.12141115101395 6 7 8432112151114101395 6 7 84321?=$1000三国华容道不同的初始布局编程求解三国华容道状态：每个
2、“局面”行动：可行的“移动”实现问题：如何在计算机内表示“状态”和“行动”定义一个“搜索”问题 State space S Successor function:x S SUCCESSORS(x)2S Initial state s0 Goal test:xS GOAL?(x)=T or F Arc cost，路径耗散S132State space S =State graph每个节点表示一个状态弧及其两个端点表示后继函数可能包括多个不连通的分量搜索问题的“解”IG解：从初始节点“I”到任何目标节点“G”的一条路径（沿箭头方向）解是路径，可能存在多条从I到G的路径，最优解就是路径耗散(路径上c
3、ost之和）最小的路径最短路径问题？搜索问题的“解”无解解就是连通源点和目标点的路径IG构建好的状态空间问题问题状态定义状态定义状态数目状态数目8-数码每个格子放置一个数9！=362,88015-数码每个格子放置一个数16!2.09 x 1013 24-数码每个格子放置一个数25!1025八皇后问题每行放一个皇后88N皇后问题每行放一个皇后NNN皇后问题任何一个位置都可以放一个皇后(N2)!/(N2-N+1)!存在大量“不可达/违背约束”的状态！n2-1 数码问题的状态空间逆序值（每个数被逆序的次数之和）的奇偶性，将整个状态图分为两个不联通的分量所以Sam Loyd不用担心他的钱被领走！121
4、41115101395 6 7 8432112151114101395 6 7 84321?121511146139510784321n2=0 n3=0 n4=0n5=0 n6=0 n7=1n8=1 n9=1 n10=4n11=0n12=0n13=0n14=0n15=0 逆序值=7如何证明?什么是“好的”状态空间所有状态？所有“可达的”状态？“不可达”状态的判断，在无解时非常重要！状态数目：少，越少越好？最少？状态数目一般情形下，太多！（无法全部在计算机内表示出来，或者遍历一次）状态空间/状态图的设计和后继函数密切相关！数码问题的搜索时间 8-puzzle 362,880 states 15-
5、puzzle 2.09 x 1013 states24-puzzle 1025 states100 millions states/sec0.036 sec 55 hours 109 years我们的搜索问题是寻找一个“状态”迁移的序列，为什么搜索状态空间大小个状态就一定可以完成搜索任务？基准算法：搜索整个状态图图的宽度优先搜索算法生成树Search tree我们关心的搜索算法仅仅搜索整个状态空间的一小部分相同点：(与基准算法比）算法大框架所有的解（可行+不可行）构成的集合不同点：从状态图中选择的子集S不一样S构成的状态图（弧）不一样，后继函数空间大小/解的数量为N，则搜索过的部分是log(N
6、)的多项式函数获得状态空间/状态图后，执行“搜索”8皇后问题和n2-1数码问题的求解方法的异同！8皇后问题，简单的解法就是在空棋盘上不停添加皇后，其解是“构造”出来，构造出一个状态，然后对状态进行目标测试，不同状态之间不迁移，相邻两次目标测试之间的“动作序列”是“后继函数”！(深度优先？）n2-1数码问题，求解过程是从初态出发，不停地在不同状态之间迁移，直到到达目标状态状态的解释事物可能的抽象表示，关键属性上相同，不重要细节的影响可以忽略不计比如棋盘的布局，棋子偏移1毫米，对布局/状态没有影响状态空间是离散的，有限或者无限后继函数的解释数独求解器的例子。每个状态可行的所有“行动”的集合函数的返
7、回值，行动的结果（后继状态）和行动的代价（cost）后继函数是算法设计的“关键”！最复杂的部分路径耗散/代价路径耗散/代价是沿着某条边/弧，转移到下一个状态，执行动作的代价（后继函数执行的代价），一般总是正数；数码问题，每移动一次，代价为1N皇后问题，每放置/撤回一个皇后，代价为1，从一个状态转移到下一个状态，花费的代价=0Why？目标状态可以是一个被精确定义的状态可以是满足某些条件的状态可以是满足某些条件的状态集合搜索问题状态/状态空间/状态图后继函数/状态转移目标状态初始状态路径耗散/代价解形式化搜索问题，设计算法求解具体问题的形式化例子：8皇后问题皇后问题国际象棋棋盘上放置8个皇后，彼此
8、间不能吃掉对方正确的解错误的解形式化8皇后问题：方法一状态，任何0，1，2，,8个皇后在棋盘上时的布局代表一个状态初始状态：0个皇后在棋盘上目标测试/目标状态：8个皇后在棋盘上，彼此间不互吃路径耗散：放置一个皇后，代价为1后继函数：在一个空的格子上放置一个皇后，得到一个新状态高度为9的64-叉树 64x63x.x57 3x1014 states形式化8皇后问题：方法二状态，任何0，1，2，,8个皇后在棋盘左侧，且互不攻击时代表一个状态；所谓棋盘左侧互不攻击，就是前k列每列一个皇后，互不攻击；初始状态：0个皇后在棋盘上目标测试/目标状态：8个皇后在棋盘上路径耗散：放置一个皇后，代价为1后继函数：
9、在k+1列放置第k+1个皇后到一个不受攻击的位置状态数目急剧减少！2,057 statesN皇后问题“解”是一个状态，而非从初始态到目标状态的序列；这类搜索问题，一般称为“设计问题”上述形式化方法二是否能“简单”求解N皇后问题？8皇后 2057个状态100皇后 1052个状态能否有算法能快速求解N皇后问题？问题特点：很多个解，解的分布较好（较均匀）路径规划问题状态空间是什么？如何形式化？禁止触碰障碍物路径规划问题的形式化：方法一路径规划问题的形式化：方法一网格化地图令小网格边长为1，则对角线距离为2路径规划问题的形式化：方法一路径规划问题的形式化：方法一最优解，仅仅是网格化的离散空间中的最优解
10、解释一个序列路径规划问题的形式化：路径规划问题的形式化：方法二方法二假设垂直扫描线从左到右进行扫描；遇到障碍物的顶点（不妨设障碍物为多边形）则暂停，标记标记方法：对两次暂停之间的被扫描区域染上不同的颜色被障碍物割裂的扫描线获得不同颜色的区域扫描线路径规划问题的形式化：方法二路径规划问题的形式化：方法二路径规划问题的形式化：方法二路径规划问题的形式化：方法二每个染色区域用其重心点表示每个重心点代表一个状态，获得状态空间路径规划问题的形式化：方法二路径规划问题的形式化：方法二后继函数：具有相邻边界线的色块之间互为后继获得状态图边/弧的路径耗散/代价为状态点之间的距离路径规划问题的形式化：方法二路径
11、规划问题的形式化：方法二解为一条路径路径需要通过特定的边界点最优路径需要进一步优化和平滑路径规划问题的形式化：路径规划问题的形式化：方法三方法三取障碍物（不妨设为多边形）的顶点以及初始地点和目标地点构成图的顶点；对任何顶点，连接其可视顶点（没有被障碍物阻挡），获得后继函数路径耗散/代价：边/弧的长度，顶点间的距离路径规划问题的形式化：方法三路径规划问题的形式化：方法三最优解是连续的搜索与AIAI系统中搜索无处不在路径搜索与导航打包/邮件分发超大规模集成电路布局设计蛋白质比对和折叠制药电脑游戏无信息搜索/盲搜索（Un-informed Search)状态图和搜索树某些节点可能会被重复访问！Sea
12、rch treeState graph搜索节点和状态123456781234567812345678135681345678247212345678如果状态允许被重复访问，则即使状态有限，搜索树也可能是无限的同样的状态，在树中可同样的状态，在树中可能有多个节点表示，我能有多个节点表示，我们先暂时认为们先暂时认为“不同的不同的节点代表不同的状态节点代表不同的状态”，也就是说也就是说“节点节点”和和“状态状态”暂时是同义词暂时是同义词搜索算法设计细节：节点数据结构父节点12345678状态节点N的Depth =从根到N的路径长度(根的深度为0)存储信息3Path-Cost3DepthExpande
13、dyes.子节点搜索算法设计细节：节点扩展节点N的扩展，包括的处理：1.评估状态/节点N的后继函数2.对后继函数返回的所有状态，在搜索树上产生一个子节点12345678N135681345678247212345678节点产生 节点扩展搜索算法设计细节：搜索树的边界搜索树的边界：未被扩展的节点集合，可能在排队等待扩展！123 45678123 45678123 4567813568134567824 72123 45678注意与叶节点进行区别！搜索算法设计细节：搜索策略搜索树的边界实际就是等待扩展的节点集合！等待扩展的节点用“优先队列”FRINGE来实现INSERT(node,FRINGE)R
14、EMOVE(FRINGE)等待扩展节点的优先次序我们称之为“搜索策略”搜索算法设计细节：算法框架（基准算法）1.if (GOAL?(S0)=T)then return S02.INSERT(S0,FRINGE)3.Repeat:a)if(empty(FRINGE)=T)then return failurea.s REMOVE(FRINGE)b.For every state s in SUCCESSORS(s)i.If(GOAL?(s)=T)then return path or goal stateii.INSERT(s,FRINGE)节点节点/状态扩展状态扩展度量算法求解问题的性能完备性
15、：完备性：问题有解时，算法能否保证返回一个解？问题无解时，算法能否保证返回failure？最优性：最优性：能否找到最优解？返回代价/路径耗散最小的路径？复杂性：复杂性：算法需求的时间和内存1.状态图的大小：初态和后继函数决定，影响因素：分支因子（后继的最大个数），最前目标状态的深度，路径的最大长度2.时间复杂度：访问过的节点数目3.空间复杂度：同时保存在内存中节点数目的最大值我们研究搜索算法的目标很多搜索问题是NP-hard，比如TSP，数码问题因此，别期望能在多项式时间内（时间复杂度是问题规模的多项式函数）求解出问题的所有实例（instances），没有通用算法！没有免费的午餐算法设计的意义
16、：对每个instance/每类instances找到其最有效（尽可能高效）的求解算法无信息搜索和有信息搜索的差异未扩展节点集合FRINGE是“无序”将更有希望的节点放在未扩展节点集合FRINGE的前面，优先扩展Uninformed/BlindInformed/HeuristicQ:如何排序或者判断优先扩展节点？例子：盲搜索和启发式搜索盲搜索：s1和s2的次序是“随机的”，树的结构确定的，在算法实现时预先“确定”下来的启发式搜索：状态s2更接近目标状态（错误位置更少），因此可以优先扩展状态s2Goal states1s2STATESTATE123456781234567812345678新节点/
17、状态插入到未扩展节点队列FRINGE的队尾FRINGE=(3,4,5)2345167FRINGE=(4,5,6,7)基准算法（宽度优先搜索算法）的进一步解释算法的重要参数1.分支因子b，后继函数返回的最大状态数目2.从初态到目标状态的最小深度d，或者说是宽度优先生成树上“埋藏最浅”的目标节点的深度基准算法（宽度优先搜索算法）的进一步解释评价基准算法p完备性？p最优性？p复杂性？完备的完备的 如果边的权值都为如果边的权值都为1访问节点数：访问节点数：1+b+b2+bd =(bd+1-1)/(b-1)=O(bd)基准算法（宽度优先搜索算法）的进一步解释时间和内存需求的直观认知d#NodesTime
18、Memory2111.01 msec11 Kbytes411,1111 msec1 Mbyte61061 sec100 Mb8108100 sec10 Gbytes1010102.8 hours1 Tbyte12101211.6 days100 Tbytes1410143.2 years10,000 Tbytes假设:b=10;1,000,000 nodes/sec;100bytes/node基准算法（宽度优先搜索算法）的进一步解释关于无解的讨论问题无解时，若状态空间无限大或者任意状态可被任意次重复访问，则宽度优先搜索算法不会停止12141115101395678432112151114101
19、3956784321?基准算法的改进策略:双向搜索2个未扩展节点集合:FRINGE1 和 FRINGE2s时间和空间复杂度是 O(bd/2)O(bd)（假设两个方向的分支因子都是b）问题:两个方向的分支因子不一样会怎样?双向搜索的进一步解释时间复杂度：获得极大的优化O(bd/2)O(bd)，但是“问题本质”（指数时间复杂度）没有变化。这已经是双向搜索带来的明显进步；空间复杂度：O(bd/2)O(b)，极大地“恶化”了完备性：完备的 最优性：边的代价都为1时，能保证最优性双向搜索，是策略/算法框架，而非“原子的”的搜索算法，双向搜索的两个方向（前向/反向）搜索算法，可以一样，也可以不一样问题：总
20、是能找到“好”的反向搜索算法吗？目标状态是单个精确描述的状态？满足某个条件的状态集合？后继函数的逆函数“前驱函数”能方便地描述或表达吗？（比如象棋的目标状态：获胜的布局，个数？如何描述，等等）无信息搜索算法：深度优先搜索新状态/节点总是插入到队列的“队头”（栈）12345FRINGE=(4,5,3)深度优先搜索算法的评价p完备性？p最优性？p复杂性？若搜索树有限，则是完备的若搜索树有限，则是完备的 不一定是最优的不一定是最优的访问节点数访问节点数(最坏情形最坏情形)：1+b+b2+bm =O(bm)空间复杂度空间复杂度O(bm)注：注：m是叶子节点的最大深度是叶子节点的最大深度深度优先搜索变型
21、I:回溯搜索每次扩展节点的时候，只扩展一个节点，节省内存，最多同时保存O(m)个节点若深度优先搜索树是无限的，则搜索可能是不完备的，也可能无法得到最优解深度优先搜索变型II:深度受限搜索设置扩展节点的深度阈值k，当节点深度大于k时，节点不再扩展算法返回结果：解无解failure深度阈值k内无解Q:k比d(最浅目标状态的深度)大或小时，会怎样？如何容易得到k，算法性能将会得到提升深度优先搜索变型III:迭代深入搜索思想：使用不同的受限深度参数k=0,1,2,.不断重复执行“深度受限搜索”目的：寻找合适的深度受限深度参数k值带来的好处：结合了宽度优先和深度优先二者的长处（时空复杂度，完备性和最优性
22、）付出的代价？迭代深入搜索的评价p完备性？p最优性？p复杂性？完备的完备的，当，当k=d时时最优的，当边权值都是最优的，当边权值都是1时时访问节点数访问节点数(最坏情形最坏情形)：(d+1)(1)+db+(d-1)b2+(1)bd=O(bd)空间复杂度空间复杂度O(bd)迭代深入搜索付出的额外代价宽度优先迭代深入11 x 6=622 x 5=1044 x 4=1688 x 3=241616 x 2=323232 x 1=3263120宽度优先迭代深入1610501004001,0003,00010,00020,000100,000100,000111,111123,456d=5 and b=1
23、0d=5 and b=2对未知问题，解对未知问题，解的深度未知，付的深度未知，付出较小的代价，出较小的代价，迭代深入搜索是迭代深入搜索是首选的盲搜索算首选的盲搜索算法法盲搜索的比较避免状态重复访问行动可逆，则有可能会出现重复状态，如“三国华容道”；搜索树是无限的行动不可逆，不会出现重复状态，如“8皇后问题”的形式化方法二；搜索树有限如何避免？（宽度优先搜索）条件1：对扩展出来的状态进行标记和存储标记到visited中（用hash table实现）条件2：进行比较，若新扩展出来的状态在visited中，则放弃该状态问题：空间需求是多少？深度优先搜索？深度优先搜索？深度优先搜索标记存储深度优先搜索
24、标记存储需要的内存空间同宽度需要的内存空间同宽度优先搜索！优先搜索！避免状态重复访问：记住所有访问过的状态增加CLOSED表，存储所有访问过（扩展过）的节点/状态未扩展的节点/状态用OPEN表来标识若当前待扩展的节点/状态已经在CLOSED表中，则丢弃该状态/节点；否则扩展当前节点/状态上述算法框架称为“图搜索”，直接探索“状态图”空间（内存需求巨大！）最优性如何保证？宽度优先搜索的实现方式可以保证！区分“树搜索”和“图搜索”树搜索中，不同的节点N1,N2可能表示的是相同的状态s，分别表示从初态出发，到达状态s的两条不同路径（可能具有不同的路径耗散）图搜索中，相同的状态只有一个节点来表示；不同
25、的节点代表不同的状态；可以想象成把“树搜索”中具有相同状态的节点合并为一个节点，得到了“图”树的“层次遍历”算法和图的“宽度优先搜索”遍历算法基本认知若状态空间是无限的，一般来说，搜索是不完备的若状态空间有限，但允许状态被任意次重复访问，搜索一般是不完备的若状态空间有限，访问时重复访问的节点被丢弃，则搜索是完备的，但是一般不是最优的代价一致的搜索宽度优先搜索，未扩展节点集合是“随机”次序，具有隐含的约束：单步路径耗散都是1优先扩展“扩展深度最小”的节点若单步耗散因边不同而不同，会怎样？所谓代价一致搜索：扩展的节点是使得路径消耗最低的节点。确保代价c=0，（为0则会陷入无穷循环）未扩展节点进行了
26、排序性能分析变得复杂，因问题而异。代价一致的搜索：避免状态重复访问采用图搜索来实现CLOSED表中保存每个状态的最优路径耗散（从初态出发）若s在CLOSED表中，则检查s的代价（从初始状态到s的路径耗散），并和当前路径+s的总路径耗散进行比较，取较小的路径耗散，更新状态s的路径耗散；若s不在CLOSED表中，则放入CLOSED中，并开始扩展；将s的所有不在CLOSED表中的后继状态放入OPEN表中重复上两步启发式搜索/有信息的搜索(Informed Search)未扩展节点集合的次序，表示了搜索的“策略”1.if (GOAL?(S0)=T)then return S02.INSERT(S0,F
27、RINGE)3.Repeat:a)if(empty(FRINGE)=T)then return failurea.s REMOVE(FRINGE)b.For every state s in SUCCESSORS(s)i.If(GOAL?(s)=T)then return path or goal stateii.INSERT(s,FRINGE)节点节点/状态扩展状态扩展策略：最佳优先搜索从FRINGE中选择最佳节点进行扩展。何为“最佳”节点？如何求得“最佳”节点？利用状态信息/状态描述来估计节点的“好/坏”设计评估函数f，将搜索树的节点N映射为一个非负实数f(N)，表示从初始状态到达某个节点
28、的路径耗散（越小越好！）将整个未扩展节点集合FRINGE按增序排列，排在最前面的称为“最佳”（best），优先进行扩展（first），Best-first search若两个节点f值相等，则可任意指定其次序，或者添加其他的信息进行进一步排序注意“最佳”的概念，并非指最后获得的解是最佳的；（局部贪婪）什么时候能获得最优解？如何设计评估函数f搜索问题求解 算法框架 搜索策略 评估函数f的设计常用两种方法来估计f值f(N)=g(N)+h(N)，完整解的路径耗散（A*算法）f(N)=h(N)，从当前节点到目标节点的路径耗散（贪婪算法）符号解释：N：当前待判决/估计/评价的节点g(N)：从初始节点到N的
29、路径耗散h(N)：从N到目标节点的路径耗散函数f的具体形式，因问题而异！启发式函数，估计值搜索问题求解 算法框架 搜索策略 评估函数f的设计 启发式函数一般情形下，启发式函数值由当前节点和目标节点二者所确定例如：14752638N64715283Goalh1(N)=错误放置的格子数=6h(N)应该保证的性质：h(N)=0，h(Goal)=0，h(N)越小，离目标越近数码问题的不同启发式函数h1(N)=错误放置的格子数=6h2(N)=所有数字到其正确位置的Manhattan距离之和 =2+3+0+1+3+0+3+1=13h3(N)=逆序数之和 =n5+n8+n4+n2+n1+n7+n3+n6 =
30、4 +6 +3 +1 +0 +2 +0 +0 =1614752638N64715283Goal8数码问题的搜索过程：f(N)=h(N)=错误放置的格子数45533434421203438数码问题的搜索过程：f(N)=g(N)+h(N)h(N)=错误放置的格子数0+41+51+51+33+33+43+43+24+15+25+02+32+42+38数码问题的搜索过程：f(N)=h(N)=所有数字到其正确位置的Manhattan距离之和566442120553路径规划问题82xNyNNxgyg22gg1NNh(N)=(x-x)+(y-y)(Euclidean distance)h2(N)=|xN-x
31、g|+|yN-yg|(Manhattan distance)最佳优先搜索存在的局部最小问题：引导搜索进入错误的方向f(N)=h(N)=到目标的直线距离局部最小问题降低了搜索效率降低了搜索效率“可采纳的”(admissiable)启发式函数假设h*(N)是节点N到目标节点的实际最优路径耗散启发式函数h(N)是“可采纳的”，当且仅当 0 h(N)h*(N)总是“乐观地”估计路径耗散！Why?松弛问题：放宽问题的限制（约束），减少行动限制，获得更好的解。用松弛问题来构造启发式函数是最常用的技术8数码问题的启发式函数h1(N)=错误放置的格子数=6 可采纳的h2(N)=所有数字到其正确位置的Manha
32、ttan距离之和 =2+3+0+1+3+0+3+1=13 可采纳的h3(N)=逆序数之和 =n5+n8+n4+n2+n1+n7+n3+n6 =4 +6 +3 +1 +0 +2 +0 +0 =16 不可采纳的14752638N64715283Goal node反证法：找一个违背可采纳定义的状态反证法：找一个违背可采纳定义的状态路径规划问题水平/垂直移动一格，路径耗散为1对角线移动一格，路径耗散为 222gg1NNh(N)=(x-x)+(y-y)可采纳的h2(N)=|xN-xg|+|yN-yg|h*(I)=42h2(I)=8允许沿对角线移动，允许沿对角线移动，则是不可采纳的则是不可采纳的不允许沿对
33、角线移动，是可采纳的不允许沿对角线移动，是可采纳的A*算法f(N)=g(N)+h(N),where:g(N)=从初始节点到N的路径耗散h(N)：从N到目标节点的路径耗散，可采纳的启发式函数uAI中最著名的搜索算法A*算法结论一：是完备的和最优的（树搜索）（重复访问状态时，不丢弃新节点）（重复访问状态时，不丢弃新节点）完备性证明：1.未扩展节点集合FRINGE中每个节点满足f(N)=g(N)+h(N)g(N)d(N)e,其中d(N)是节点 N 的深度2.只要A*算法没结束，在FRINGE中至少有一个节点k属于解代表的路径3.节点扩展会使得路径变长，k将最终被扩展，除非在这之前找到一个到达目标节点
34、的其他路径。简单理解：算法搜索到树的一定深度就会结束，若深度无穷大，则d(N)e会无穷大！KA*算法结论一：是完备的和最优的（树搜索）（重复访问状态时，不丢弃新节点）（重复访问状态时，不丢弃新节点）最优性证明C*=最优解的路径耗散G:未扩展节点集合中“非最佳”目标节点（为什么只要考虑目标节点？）f(G)=g(G)+h(G)=g(G)C*未扩展节点集合中的节点k位于最优解的路径上:f(K)=g(K)+h(K)C*所以,G 不会被选择扩展一旦某个目标节点被选择扩展，则一定是最优的！KGA*算法：树搜索实现的问题无解时，算法可能永远运行下去（状态允许重复访问）对于未知问题，不知道有解还是无解，怎么办
35、？解决办法：增加时间约束，超过给定时间就结束搜索；此时无解，也不能判定问题是无解，还是搜索时间太少因此，产生了新问题：如何设置时间约束？（没办法！）A*算法：图搜索的实现c=1100212h=1000901明显地，启发式函数是可采纳的！1044+90f=1+1002+1?这时候两个候选扩展节点的f值为104和101，选择101进行扩展，扩展的新节已经被访问过如果丢掉，那么接下来就直接扩展104，得到非最优解A*算法：图搜索的实现c=1100212h=10009011044+901+1002+12+90102如果不丢弃重复访问状态的节点，那么我们可以得到最优解！这时候实际上就是“树搜索”，且允许
36、状态用不同的节点表示，允许重复访问状态！获得最优解的代价是访问了更多的节点！不丢弃且允许访问表示同一状态的重复节点，会造成搜索树节点指数增加！121112112n+1 states1+11+12+12+12+12+144444444O(2n)nodes二难的抉择丢弃同一已访问状态的新产生节点不丢弃同一已访问状态的新产生节点丢弃已访问状态的新节点并不总是有害的当表示某个已访问状态的新节点产生了，同时其路径耗散估计值f大于已有路径，则可以丢弃该新节点！此时A*算法仍然是最优的，但是搜索树可能节点变少了（也可能仍是指数个节点）同一状态仍然可能会被多次访问/扩展有没有好的可采纳的启发式函数能更有效地处
37、理状态的重复访问问题？一致的/单调的启发式函数保证第一次到达某个状态时，路径是最优的，以后达到该状态，路径耗散总是更大一致的/单调的启发式函数一致的启发式函数h：1.可采纳的h2.满足三角不等式任何节点N和它的后继节点N，满足h(N)c(N,N)+h(N)(三角不等式)NNh(N)h(N)c(N,N)h(N)C*(N)c(N,N)+h*(N)h(N)-c(N,N)h*(N)h(N)-c(N,N)h(N)h*(N)理解：随着搜索的深度越来越深，估计的启发式函数值越来越准确！可采纳的一致的违背一致性的启发式函数不满足三角不等式NNh(N)=100h(N)=10c(N,N)=10三角不等式8数码问题
38、的启发式函数h1(N)=错误放置的格子数=6 可采纳的，一致的h2(N)=所有数字到其正确位置的Manhattan距离之和 =2+3+0+1+3+0+3+1=13 可采纳的，一致的14752638N64715283Goal nodeNNh(N)h(N)c(N,N)h(N)c(N,N)+h(N)证明？路径规划问题水平/垂直移动一格，路径耗散为1对角线移动一格，路径耗散为 222gg1NNh(N)=(x-x)+(y-y)可采纳的,一致的h2(N)=|xN-xg|+|yN-yg|h*(I)=42h2(I)=8允许沿对角线移动，则是允许沿对角线移动，则是不可采纳的，不一致的不可采纳的，不一致的不允许沿
39、对角线移动，是可采纳的，一致的不允许沿对角线移动，是可采纳的，一致的NNh(N)h(N)c(N,N)h(N)c(N,N)+h(N)A*算法结论二：若h是一致的，那么得到当前节点的路径都是此时最优的证明一致性意味着单调性：（考虑N 及其后继 N）f(N)=g(N)+h(N)g(N)+c(N,N)+h(N)=f(N)如右图，K被选择进行扩展，我们要证明此时路径到K是最优的，即g(K)最小。考虑在未扩展节点集合中存在一个其他节点N，经N到K，K此时用节点N表示，存在一条路径，那么有：（N和K是同一个状态不同的节点表示）f(N)f(N)f(K)以及 h(N)=h(K)所以，g(N)g(K)KNNG该结
40、论及其证明隐含：从第二次开始重复扩展的状态总是不如第一次扩展一致的启发式函数：作用于状态的重复访问节点被扩展，则状态进入CLOSED表当一个新节点N产生了若N表示的状态在CLOSED表中，则丢弃节点N若N表示的状态不在CLOSED 表中，但是在未扩展节点集合FRINGE中（不妨设为N），则去掉f(N),f(N)中较大的节点，等价于去掉g(N)和g(N)中较大的节点特殊的一致的启发式函数：h0一致的，当然也是可采纳的等价于单步路径耗散相同A*退化为宽度优先搜索，代价一致搜索评价/比较不同的启发式函数若对任何节点N，都有h1(N)h2(N)，则称h2比h1更精确 h1(N)=错误放置的格子数目 h
41、2(N)=每个数字到对应目标位置的Manhattan距离 h2 is more accurate than h114752638STATE(N)64715283Goal stateA*算法结论三：当解存在时，较精确启发式函数导致的被扩展节点集合包括在“不精确”启发式函数导致的被扩展节点集合中，除了f值相同且等于最优解的路径耗散的那些节点。证明任何f(N)C*的节点都将会被扩展（在获得最优解之前）。可用绘制等g(N)值线的方式来逐步扩展初始状态为核心的等值线系统，在最优解路径耗散C*围成的等值线包括了所有f(N)C*的节点。（完备性容易由此被证明）所以由h1(N)h2(N)可知，在找到最优解之前
42、，h2扩展的节点，h1都会进行扩展除了最后达到最优解时，可能获得的是不同的最优目标节点！不精确的启发式函数会访问更多的节点！有效分支因子b*b*可以度量启发式函数的有效性通过隐函数来定义：n=b*+(b*)2+.+(b*)d 其中n是被扩展的节点数目，d是解的深度有效分支因子和搜索效率实验结果8数码问题，考虑无信息的迭代深入搜索、h1和h2，随机产生1200个instancesn=b*+(b*)2+.+(b*)d被扩展节点数目nd=12,h1227,h273d=24,h139135,h21641设计好的启发式函数基本思路：求解原问题的松弛问题，获得灵感例如8数码问题h1的设计：假设错了数字，可
43、以一次就放到正确位置，忽略其它所有因素h2的设计：假设数字可以水平和垂直任意移动，忽略移动目标位置是否被占据更复杂有效的启发式函数设计：假设数字可以水平和垂直移动，使得1，2，3，4移动到目标位置，忽略5，6，7，8的阻挡，计算移动次数d1；使得5，6，7，8移动到目标位置，忽略1，2，3，4的阻挡，计算移动次数d2；d1+d2就是h。（产生大约3024个状态节点）其他方法：从经验中学习，归纳学习，不同启发式函数的集成等A*算法的目标：精确的、一致的启发式函数保证了完备性、最优性，不需要重复访问同一个状态实际上，问题并没有解决。问题规模大时，因为时空要求都是解长度的指数函数算法时间限制及其设置
44、其它实用的，不可采纳的启发式函数，不能保证最优性和完备性，但是能快速获得最优解或近似最优解迭代深入A*算法：IDA*思想：设置f的阈值，超过f的阈值，节点不再扩展；迭代执行A*，降低A*算法对内存的需求要求：一致的启发式函数算法描述：1.初始化f的阈值t为f(N0)2.重复执行I.执行深度优先搜索，扩展f(N)=h(current)then current neighbor 3.return currentl上述2.1中所采用的策略称为：“best-found”，还有”first-found”策略，也就是将current的所有邻居随机排列，然后一个一个neighbor判断其和current的h
45、值大小，若碰到了较大的h值，就令用neighbor替换currentl另一种策略就是“随机”选择一个邻居移动，称为Random walk算法，也许不能称为算法。就是在地图（landscape）上漫步，有点象随机采样，用来分析landscape特征注意条件判断中的等号！会出现问题吗？梯度信息？爬山法评估优点：简单、快速！内存要求低；不足：严重依赖初值，容易陷入局部最优，不完备简单而高效的改进：用不同的随机初始值重启算法，对于300万个皇后问题，不到一分钟，随机初值重启的爬山法能求解出局部最优的存在是和邻域结构的定义相关，故就有“变”邻域结构结构的局部搜索算法。比如迭代爬山法，到达局部最优解后，调
46、整邻居算子，实现“扰动”，然后再回到局部搜索。模拟退火(=爬山法+随机行走）模拟退火(最小化问题）爬山法：容易陷入局部最优模拟退火思想：小概率允许“坏”的移动，而不是像爬山法一样，每次都选最好的移动，算法框架：1.随机生成初始解current2.Repeat:2.1)找到current的一个后继neighbor，2.2)if h(neighbor)=h(current)then current neighbor 2.3）else 以概率p：current neighbor 3.return current温度T的下降过程，称为schedule,可以证明，T下降得足够慢，算法找到最优解的概率逼近
47、1禁忌搜索：Tabu搜索简单、带记忆的局部搜索算法不能算法算法，是一种策略，可以添加到各种局部搜素算法中算法思想：一个长度有限的（不妨设为k）最近历史解列表Tabu-list（用队列实现）在搜索过程中，发现的新解如果出现在Tabu-list，直接放弃Tabu-list能一定程度上防止在局部最优动不了Tabu-list的长度k多少最好？从爬山法到：1+1-EA(最小化问题）Function 1+1-Evolutionary-algorithm(problem)1.随机生成初始解current2.Repeat:2.1)随机产生一个current的一个后继neighbor2.2)if h(neigh
48、bor)=h(current)then current neighbor 3.return currentl其中2.1）中的邻居算子能够有概率一步访问到其它任何一个解，这是一个特殊的邻居算子（全局算子），可能不同解之间的跳转概率不一样，一般1+1-EA会“系统地”设置这样一个概率分布局部剪枝搜索 Local Beam Search初始时刻，开始k个随机种子，准备执行爬山法接下来的步骤，是循环迭代过程，可以有不同的策略：策略一：假设每个解有N个后继，每一步会在所有Nk个后继中选择最优的k作为当前的k个解策略二：所有Nk个后继对应一个被选择的概率分布（比如：来自自然选择，根据适应性来选择），选择k
49、个出来代价？一种演化算法！局部剪枝搜索典型的演化算法采用策略二的局部剪枝搜索，在迭代循环过程中添加一个步骤：在当前k个解中，随机选择2个，执行“交叉”算子，产生“后继/孩子”，生物学上称为“有性繁殖”演化算法对有性繁殖的“后继/孩子”的Nk个后继（变异算子），再执行按一定概率分布选择（选择算子）下一代“解”集合演化算法对于“交叉”算子，“变异”算子，“选择”算子可以用各种不同的方法来定义，产生各种演化算法的各种“变型”。遗传算法：演化算法的典型代表解的表示：二进制串表示一个解，遗传算法一般包括一个解集合交叉算子：两个二进制串的混杂/分解变异算子：二进制串的某些位置的概率“翻转”（01,10）选
50、择算子：在“后继”或者“后继+当前解集”中用某种方式选择出“新的”当前解集。树型编码？EP演化计算的发展算子（后继函数）的变化1：单性繁殖两性繁殖4个体杂交？差分演化：x和其它三个不同a,b,c个体产生的中间个体y=a+F(b-c)进行传统的“交叉”，产生后继z算子（后继函数）的变化2：单性繁殖两性繁殖多个个体杂交？EDA：估计群体的分布，依据估计得到的分布进行采样算子（后继函数）的变化3：存在“Queen”的某些昆虫社会系统粒子群算法：个体和Queen交配，产生后代。模拟鸟类飞行的“从众”现象。假设群体中最佳解是“queen”，所谓“交配”，定义为非最佳个体“面向”群体的“queen”方向，
