数据结构课件-第16章.pptx

数据结构计算机领域本科教育教学改革试点工作计划（“101计划”）研究成果俞勇、张铭、陈越、韩文弢上海交通大学、北京大学、浙江大学、清华大学101

高级算法设计第16章朱允刚吉林大学

16.1近似算法16.2启发式有哪些信誉好的足球投注网站算法16.3随机算法

动机16.1近似算法针对难以在多项式时间内精确求得最优解的问题，一种可行的替代方案是：不追求最优解，而是退而求其次，找到一种方法能够在多项式时间内求得近似最优解。在实际应用中，近似最优解往往能满足实际需要。求得近似最优解的算法就称为近似算法。

近似算法的性能比16.1近似算法?

例：顶点覆盖问题16.1近似算法无向图的顶点覆盖是图中一些顶点的集合，使得图中的每条边都至少以该集合中的一个顶点为端点。形式化地，无向图G=（V，E）的一个顶点覆盖是一个顶点子集V?V，若(u,v)是G的一条边，则必有u?V或v?V，即G中每条边都至少有一个端点在V’中。顶点覆盖问题是指在给定的无向图中，找出一个包含顶点数最少的顶点覆盖，称这样的顶点覆盖为最优顶点覆盖。目前尚无精确求解该问题的多项式时间算法。

例：顶点覆盖问题16.1近似算法算法16.1顶点覆盖问题的近似算法VertexCoverApproximation(E)输入：图的边集合E输出：近似最优顶点覆盖集合CInitSet(C) //将顶点覆盖集合初始化为空whileIsEmpty(E)≠truedo |从E中任意选取一条边(u,v)|Insert(C,u,v)//将顶点u和v插入顶点覆盖集合|Delete(E,u,v)//从E中删除以顶点u或顶点v为端点的所有边endreturnC

例：顶点覆盖问题16.1近似算法

例：顶点覆盖问题16.1近似算法定理16-1算法VertexCoverApproximation的近似比为2。证明：设A为算法每次迭代过程中选出的边（u，v）的集合，C*为最优顶点覆盖。在算法迭代过程中，若一条边被选中，与该边有共同端点的边随后都将被删去，故A中的边没有共同的端点。这意味着C*中的一个顶点最多只能覆盖A中的一条边，故C*中的顶点个数大于等于A中的边数，即：|C*|?|A|又由于A中每次被选出的1条边的2个端点均被放入集合C中，故C中顶点个数等于A中边数的2倍，即：|C|=2|A|综上，有：|C|=2|A|?2|C*|

例：离散背包问题16.1近似算法约定：假定一共有n个物品，编号为1至n。第i个物品的重量记为wi，第i个物品的价值记为vi。算法：通过每次选取剩余物品中“价值最大”的物品获得一个贪心解S1，通过每次选取剩余物品中“单位重量下价值最大”的物品获得一个贪心解S2，然后从这两个解中选取总价值最大的解作为最终解。性能：上述算法的近似比为2。

A算法与A*算法16.2启发式有哪些信誉好的足球投注网站算法A算法和A*算法是经典的启发式有哪些信誉好的足球投注网站算法，首先介绍A算法。在A算法中，定义如下评价函数对某一状态X进行评估f(X)=g(X)+h(X)其中，X表示当前状态，g(X)表示从初始状态到达当前状态X已经花费的代价，例如在图有哪些信誉好的足球投注网站中，可以是起点到当前点的路径长度；h(X)称为启发函数，表示从当前状态X到目标状态所需最小代价的估计值，例如在图有哪些信誉好的足球投注网站中，可表示当前点到目标点的最短路径长度的估计值。f(X)反映了从初始状态经过X到达目标状态的路径的最小代价估计值，f(X)越小意味着X越有可能在解路径上。在有哪些信誉好的足球投注网站过程中，A算法每次选择f(X)值最小的状态进行下一步有哪些信誉好的足球投注网站。

八数码问题16.2启发式有哪些信誉好的足球投注网站算法有一个3?3的九宫格棋盘，棋盘中放置8个棋子，每个棋子标有1-8的某个数字，不同棋子上标的数字各不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要解决的问题是：给定一个初始状态和一个目标状态，找出一种从初始状态变换为目标状态的最优方案，该方案使棋子的移动步数最少。

八数码问题16.2启发式有哪些信誉好的足球投注网站算法h(X)=状态X对应的棋盘中不在目标位置的棋子个数有哪些信誉好的足球投注网站过程中，每次从OPEN表中选择评价函数值最小的结点X进行扩展。如果X是目标结点，则找到一个解，算法终止；若X不是目标结点，则扩展X。对于由X扩展出的结点Y：若Y既不在OPEN表中，也不在CLOSED表中，说明Y之前没有被扩展过，将Y加入OPEN表中；若Y已经在OPEN表中，意味着找到了从初始结点到Y的两条路径，保留其中代价小的路径；若Y已经在CLOSED表中，也意味着找到了从初始结点到Y的两条路径，如果新路径的代价低，则将Y从CLOSED表中取出，重新放入OPEN表中，以备后续重新扩展。重复以上过程，直至找到解或OPEN表为空。若算法以O