资源描述
算法设计与分析算法设计与分析复习重点复习重点内容分治法大数相乘，归并排序图的分解Explore算法，深度优先搜索图中的路径Dijkstra算法、Bellman-Ford算法贪心算法最小生成树，Kruskal算法、Prim算法动态规划Dag最短路径、最长递增子序列线性规划巧克力工厂n-bit大数相乘算法4归并排序给定一个数列，将其排序排序问题的分治法求解将待排序数列一分为二，每个子数列分别排序将完成排序的两个子数列合并5考虑合并两个排序的数组 和 ，结果存入 中6“o”表示元素与数列连接一个mergesort算法执行实例7习题使用分治大数相乘算法，计算两个二进制整数10011011和10111010的乘积。要求画出算法执行的问题分解树。8Explore算法Explore算法算法执行情况一个节点上多条边存在时按字母顺序访问下一节点。这个树被称为深度优先搜索树（DFS树）实线表示图上实际被访问的边，每条实线边代表一个explore调用。实线边被称为树边。虚线边表示图上没有被访问的边，因为访问这些边不会发现新的节点。虚线边被称为回边。10深度优先搜索explore(u)可以访问所有从u出发可达的节点对于没有访问过的节点v，调用explore(v)访问从v出发能够到达的所有节点，直到图G上的所有节点都被访问过11在以上算法中，每个节点有两个关键事件：算法首次访问到该节点；算法完成从该节点出发的所有探索，离开该节点定义数组pre和post分别记录节点的这两个时间通过在previsit和postvisit，和一个初始化为1的计数变量clock来实现12算法执行实例算法先后调用explore(A)，explore(C)和explore(F)。算法产生三棵DFS搜索树，称为一个DFS森林节点上数值分别为该节点pre和post的值13有向图上深度优先搜索-边的类型将DFS算法应用到有向图上，注意在explore中严格按照边的方向访问节点。DFS在有向图中执行示例14对于有向图DFS产生的搜索树（森林），一些定义：A是树的根节点，是所有节点的祖先所有节点是A的后裔F、G和H是E的后裔，E是F、G和H的祖先A是C和B的父节点、C和B是A的子节点15将有向图G上边集E中的边对应到DFS森林中，有一些定义：DFS森林中的实线被称为树边，在这条边上调用explore一条从节点到其非子节点的后裔的边被称为前向边一条从节点到其祖先的边被称为回边两个非祖先-后裔关系的节点之间的边被称为横跨边16习题在下图中执行深度优先搜索，如果遇到多个节点可供选择的情况，按照节点字母顺序搜索。画出DFS树，给出图上每条边是树边、前向边、回边还是横跨边，并标出每个节点的pre和post值。17Dijkstra算法考虑边有长度的图，其中每条边的长度是正数，我们希望计算图中节点之间的距离。优先队列支持以下操作：insert：队列中加入一个新元素decreasekey：将队列中某个元素的键值减少deletemin：返回队列中具有最小键值的元素，并且将该元素从队列中移除makequeue：给定一组元素和键值，构造一个优先队列Dijkstra算法19算法执行实例：从A出发，右边列出所有节点当前的dist值2021A到各节点的最短路径树Bellman-Ford算法一个运行实例在每一轮，可以按照边长从小到大调用update，边调用update的顺序不唯一23习题在下图中从节点S出发执行Bellman-Ford算法(a)使用表格描述算法执行过程中从S到各节点的当前最短距离(b)画出最短路径树24最小生成树Kruskal的算法：将图G中所有的边按照权重从小到大排序；树T初始化为空，依次挑选不在T中权重最小的，且在T上不产生环的边加入T算法执行实例加入B-C和C-D，但是B-D产生环，略过，Kruskal算法的实现使用分离集描述算法的状态。每个分离集包含当前获得连通部件的节点。如上例中A,B,C和D,E分离集上实现以下操作makeset(x)：构造一个仅包含x的单集find(x)：返回当前x所在的集合union(x,y)：合并包含x和y的集合为一个集合26完整的Kruskal算法描述27分离集数据结构使用树结构表示一个集合。树可以任意构造。树上每个节点代表一个集合元素，每个节点有一个指针，指向其父节点。根节点的指针指向自己。用根节点代表相应的集合。树上每个节点保存一个数值rank，表示悬挂于该节点下的子树的高度。28B,EH,C,D,F,G,A实现makeset和findmakeset耗时为O(1)，而find耗时正比于树的高度合并两个集合：将较矮的树的根节点直接连到较高的树的根节点上29function find(x)while x(x):x=(x)return x操作示例，上标代表节点的rank首先执行makeset构造单集执行union(A,D)，union(B,E)，union(C,F)执行union(C,G)，union(E,A)30Prim算法使用优先队列，类似Dijkstra算法执行实例32习题考虑下图(a)它的最小生成树权重（树上边权重的总和）是多少?画出最小生成树。(b)在其上运行Kruskal算法，边加入MST的顺序是怎样的？33有向无环图dag上最短路径问题dag中所有节点可以线性排列，这一性质启发我们考虑一种新的算法计算dag中两点间最短路径例如：考虑下图中从S到D的最短路径 34从S到D必须经过B或者C，因此对dag中所有节点，都存在类似的问题分解关系，如果我们按照下图dag节点线性化的顺序计算节点的dist，则在计算每个节点时，所需要的其它节点的距离信息已经是已知的了算法如下35最长递增子序列给定一个序列的数定义原序列的子序列为原序列元素的一个子集，且子序列各元素的相对顺序不变 。找出给定序列的最长递增子序列 例如，序列5,2,8,6,3,6,9,7 的最长递增子序列是2,3,6,936上图的有向边表示元素间的增长关系。如果考虑所有可能添加的有向边，我们得到下图这是一个dag，其中对任意有向边(i,j)，ij。令L(j)是终止于元素j的最长递增子序列的长度，则这个子序列必然包含某条指向j的有向边(i,j)，使得L(j)=L(i)+1。得到算法如下37最大利润问题某巧克力工厂生产两种巧克力，普通巧克力和高级巧克力。工厂每生产一盒普通巧克力，利润为￥1，每生产一盒高级巧克力，利润为￥6。每天最多有200盒普通巧克力和300盒高级巧克力的订单，并且工厂每天生产最多400盒巧克力。工厂希望最大化利润，应该怎样安排生产？假设工厂每天生产x1盒普通巧克力，x2盒高级巧克力。如何确定它们的取值？38使用线性规划描述问题如下目标函数：max x1+6x2限制条件：x1200 x2300 x1+x2400 x1,x2039假设巧克力工厂开发了一种更高档的巧克力产品，称为礼盒巧克力。每生产一盒礼盒巧克力，实现利润￥13。与上例相同，工厂每天最多生产400盒巧克力，同时，高级巧克力和礼盒巧克力都采用相同的包装材料，不同的是礼盒巧克力消耗3倍于高级巧克力的包装材料。工厂每天有600单位的包装材料。用x3表示每天生产的礼盒巧克力数量，线性规划问题如下maxx1+6x2+13x3x1200,x2300,x1+x2+x3400 x2+3x3600,x1,x2,x3040习题7.2 某种农产品产于A和B两地，其中A地产量15，B地产量为8。这种产品只在C和D两个城市销售，其中C城需求量为8而D城需求量为13。将每单位产品从A地运往C城需要￥2，运往D城需要￥3；将每单位产品从B地运往C城需要￥4，运往D城需要￥1。问如何运输使得运输代价最小，写出线性规划表达式。41
展开阅读全文