第二章总结PPT课件

1、深入解读深入解读搜索进阶章节概要章节概要010203目录Contents第1页/共44页深入解读深入解读搜索进阶0203目录Contents章节概要章节概要01第2页/共44页搜索进阶章节概要0103目录Contents深入解读深入解读02第3页/共44页深入解读深入解读章节概要0102目录Contents03搜索进阶第4页/共44页章节概要搜索 概述博弈搜索问题表示图的搜索Search and Problem Solving（效果与效率矛盾）1状态空间（五要素）与或图（规约，回溯）2博弈树（与或树）极大极小搜索（掌握）-剪枝（掌握）4章节概要Bread PPT图搜索一般的数据结构（Open表

2、，Close表）盲目图搜索（了解）启发式图搜索（重点）3第5页/共44页How to get there第6页/共44页状态空间S：状态的集合C：状态转换代价的集合I：初始状态的集合G：目标状态的集合状态空间五元组G GI I, ,C C, ,F F, ,S S, ,F：状态转换操作符的集合第7页/共44页基于状态空间表示的问题求解Step1 问题表示: Step1-1. 表示出所有可能的状态，并确定起始和终止状态 Step1-2 表示出所有的转移关系 Step1-3 把状态作为点，转移关系作为边构图.Step2 用图搜索的方法求解基于状态空间表示的问题求解第8页/共44页基于状态空间表示的问

3、题求解例基于状态空间表示的问题求解 states? locations of tiles actions? move blank left, right, up, down Initial and goal states? given action costs? 1 per move第9页/共44页与或图1.简化问题：规约。2. 规约：分解（与） 变换（或）3. 几个概念：初始顶点，端顶点，终止顶点，可解顶点（三个条件），不可解顶点。与或图P1P2P3PP1P2P3P第10页/共44页基于与或图表示的问题求解 Step1. 问题表示问题表示 Step1-1. 确定单个问题的表示 Step1-2

4、. 进行分解和变换，并转化成与或图。 Step2. 搜索解搜索解 Step2-1. 从端顶点开始，逐级回溯，标注顶点是否可解，直到原始顶点。 Step2-2. 如可解，输出相应解基于与或图表示的问题求解第11页/共44页基于与或图表示的问题求解例 汉诺塔问题基于与或图表示的问题求解第12页/共44页状态空间和与或图与状态空间表不同，与或图是基于规约的方法，在求解过程中需要不断的回溯判断。两种方法的图一般都不是直接生成的，而是慢慢展开的。状态空间和与或图比较及注意点第13页/共44页图搜索基本数据结构：Open 表，Close 表图搜索第14页/共44页图搜索基本算法流程：Step1. 将起始节

5、点放入Open表*Step2. 从Open表中选出一个节点放入Close表Step3. 扩展选中的节点:(蓝色: 针对与或图) 如果节点可以被扩展: 把扩展到的结点放入Open表 如果是终止顶点，标注可解，并逐步回溯，确定祖先节点是否可解。 否则: 标注不可解，并逐步回溯，确定祖先节点是否不可解。Step4. 重复 Step2-3 直到: 目标节点在Step2被选中弹出， 或者Open表为空(针对状态空间) 起始节点被标识为可解或不可解,或者Open表为空 (针对与或图)第15页/共44页图搜索赶个时髦第16页/共44页盲目图搜索 广度优先搜索(BFS) 深度优先搜索(DFS) 有界深度优先搜

6、索 (DLS) 迭代加深深度优先搜索 (IDS) 盲目图搜索第17页/共44页启发式搜索启发式搜索 搜索时通过估价函数来拓展结点，使搜索朝着最可能的方向进行。 启发式搜索举例：A*算法。 估值函数 f(n) = g(n) + h(n)g(n) = 从开始到的实际花费 h(n) = 从到的估计花费第18页/共44页启发式搜索*算法 估值函数 f(n) = g(n) + h(n)g(n) = 从开始到的实际花费 h(n) = 从到的估计花费 要点1：h(n)h*(n) (h*(n)为从n到goal的实际花费) 要点2：当目标状态从Open弹出放入Close表才可以结束搜索 思考：Open表的存放用

7、什么数据结构比较好？队列？堆！目标状态，并弹出第19页/共44页A*搜索过程A*搜索过程Step1. 将起始节点加入Open表*Step2. 根据h函数，从Open表中选择一个节点放入Close表。Step3. 扩展选中的节点（如果可以扩展，就将扩展得到的节点加入Open表）Step4. 重复 Step2-3 直到目标节点在Step2被选中弹出， 或者Open表为空。第20页/共44页21AI:Search and Problem Solving212 8 31 47 6 5h=4, f=4S0h=5, f=6h=5, f=6h=3, f=4h=4, f=52 31 8 47 6 52 8 3

8、1 6 47 52 8 3 1 47 6 52 8 31 47 6 5g=1S1S2S3S4h=2, f=4h=4, f=6 2 31 8 47 6 52 31 8 47 6 5g=2S5S61 2 3 8 47 6 5g=3h=1, f=4S7h=0, f=4h=2, f=61 2 38 47 6 51 2 37 8 4 6 5Sgg=4S8Open表：S0Open表S1，S2，S3，S4Open表S1,S2,S4,S5,S6Open表S1,S2,S4,S6,S7Open表S1,S2,S4,S6,S8,Sg第21页/共44页基于与或图表示的问题求解6891171031542121413第22

9、页/共44页博弈搜索 博弈树： 博弈树就是一颗与或树，满足如下特点： 1.初始状态是初始顶点。 2.“或”顶点与“与”顶点交替出现。 3.整个博弈站在一方立场，能使自己获胜的是本原问题。博弈搜索第23页/共44页(7, MIN)(6,1, MAX)(5,2, MAX)(4,3, MAX)(5,1,1, MIN)(4,2,1, MIN) (3,2,2, MIN)(3,3,1, MIN)(4,1,1,1, MAX)(3,2,1,1, MAX)(2,2,2,1, MAX)(3,1,1,1,1, MIN) (2,2,1,1,1, MIN)(2,1,1,1,1,1, MAX)第24页/共44页博弈搜索

10、极大极小搜索： 1.设定评估函数，对每一个叶顶点打分。 2.从叶顶点向上倒退，该MAX走的为MAX顶点，该MIN走的为MIN顶点，MAX估值时选取最大值，MIN估值是选取最小值。（想想对方至少和自己一样强） 3.得到结果。 博弈搜索第25页/共44页博弈搜索 极大极小搜索第26页/共44页博弈搜索 - 剪枝： 1.深度优先，一边生成，一边剪枝。 2. : MAX顶点倒推值的最小边界。 3. : MIN顶点倒推值的最大边界。 4. 剪枝: 任何MIN顶点Sn的值小于或等于它的某一祖先MAX顶点的值，则Sn以下的分枝可以停止搜索，并令顶点Sn的倒推值为。 5. 剪枝：任何MAX顶点Sn的值大于或等

11、于它的某一祖先MAX顶点的值，则Sn以下的分枝可以停止搜索，并令顶点Sn的倒推值为。博弈搜索第27页/共44页博弈搜索博弈搜索P1QP3P5475(P)=5, (Q) =4MAXQ1PQ3Q4574Q1Q2Q345745(Q) =4, (P)=5MINP1QP3第28页/共44页S0ABCDFGHEIJKLMNPQRS4861580-6441445544000-6004- 剪枝举例博弈搜索第29页/共44页搜索进阶搜索进阶 1. IDA*简介 2.解数独，dancing links在搜索中的应用简介 3. 博弈中搜索的优化第30页/共44页搜索进阶搜索进阶第31页/共44页搜索进阶搜索进阶ID

12、A*连续循环并不是对应搜索深度的增加, 而是对应路径费用的不断增加,。对于A* 算法, 该路径费用f 为从初始节点到搜索达到节点的费用g 加上从所达到节点到目标节点的估计费用h,而 IDA* 算法是如下执行的: 每次循环都进行深度优先搜索, 当f 超过一给定的阈值( th reshold) 时, 去掉相应的分支并进行回溯, 该阈值的初始值为对初始节点路径费用的估计f s, 且该阈值随着算法的每一次循环而不断增加. 在每一次循环中计算用于下一次循环的阈值, 其计算方法为取本次循环中路径费用超过当前阈值的那些费用中的最小值作为下一次循环的阈值.第32页/共44页搜索进阶搜索进阶第33页/共44页搜

13、索进阶搜索进阶第34页/共44页搜索进阶搜索进阶双向链表的删除双向链表的恢复！（居然可以恢复！？）第35页/共44页搜索进阶第36页/共44页搜索进阶慢在哪？ 矩阵中虽然标记被删除，可是寻址时还是会访问。第37页/共44页搜索进阶对于一个9 * 9的数独，建立如下的矩阵。: （黑板上画图）行： 一共9 * 9 * 9 = 729行。一共9 * 9小格，每一格有9种可能性(1 - 9)，每一种可能都对应着一行。 列： 一共(9 + 9 + 9) * 9 + 81 = 324 种前面三个9分别代表着9行9列和9小块。乘以9的意思是9种可能，因为每种可能只可以选择一个。81代表着81个小格，限制着每

14、一个小格只可以放一个地方。 这样我们把矩阵建立起来，把行和列对应起来之后，行i可以放在列j上就把Aij设为1否则设为0。然后套用Exact Cover Problem的定义：选择一些行，使得每一列有且仅有一个1。哈哈，是不是对应着sudoku的一个解？ 前面我已经说过Sudoku的搜索模型，现在再结合转化后的模型，你会不会觉得本质上是一样的呢？其实是一样的。 请注意每一列只能有一个1，而且必需有一个1。 我们把列分成两类的话，一类是代表着每一个小格的可能性，另一类是代表着每个区域的某个数的可能性。第一类是式子中的81，第二类是(9 + 9 + 9) * 9这一部分。 这样我们所选择的行就对应着答案，而且因为列的限制，这个答案也是符合Sudoku的要求的。 那你也有可能会说，Dancing Links的优化体现在哪里呢？试想，这个矩阵是非常大的(324 * 729)，如果不用Dancing Links来解，可能出解吗？ 第38页/共44页搜索进阶2种操作：删除恢复效率飞跃！第39页/共44页