计算机算法复习重点.ppt

算法执行实例 * 习题 考虑下图 (a) 它的最小生成树权重（树上边权重的总和）是多少?画出最小生成树。 (b) 在其上运行Kruskal算法，边加入MST的顺序是怎样的？ * 有向无环图dag上最短路径问题 dag中所有节点可以线性排列，这一性质启发我们考虑一种新的算法计算dag中两点间最短路径 例如：考虑下图中从S到D的最短路径 * 从S到D必须经过B或者C，因此 对dag中所有节点，都存在类似的问题分解关系，如果我们按照下图dag节点线性化的顺序计算节点的dist，则在计算每个节点时，所需要的其它节点的距离信息已经是已知的了 算法如下 * 最长递增子序列 给定一个序列的数 定义原序列的子序列为原序列元素的一个子集，且子序列各元素的相对顺序不变 。找出给定序列的最长递增子序列 例如，序列5, 2, 8, 6, 3, 6, 9, 7 的最长递增子序列是2, 3, 6, 9 * 上图的有向边表示元素间的增长关系。如果考虑所有可能添加的有向边，我们得到下图 这是一个dag，其中对任意有向边(i,j)，ij。 令L(j)是终止于元素j的最长递增子序列的长度，则这个子序列必然包含某条指向j的有向边(i,j)，使得L(j)=L(i)+1。得到算法如下 * 最大利润问题 某巧克力工厂生产两种巧克力，普通巧克力和高级巧克力。工厂每生产一盒普通巧克力，利润为￥1，每生产一盒高级巧克力，利润为￥6。每天最多有200盒普通巧克力和300盒高级巧克力的订单，并且工厂每天生产最多400盒巧克力。工厂希望最大化利润，应该怎样安排生产？ 假设工厂每天生产x1盒普通巧克力，x2盒高级巧克力。如何确定它们的取值？ * 使用线性规划描述问题如下 目标函数： max x1+6x2 限制条件： x1≤200 x2≤300 x1+x2≤400 x1, x2≥0 * 假设巧克力工厂开发了一种更高档的巧克力产品，称为礼盒巧克力。每生产一盒礼盒巧克力，实现利润￥13。与上例相同，工厂每天最多生产400盒巧克力，同时，高级巧克力和礼盒巧克力都采用相同的包装材料，不同的是礼盒巧克力消耗3倍于高级巧克力的包装材料。工厂每天有600单位的包装材料。 用x3表示每天生产的礼盒巧克力数量，线性规划问题如下 max x1+6x2+13x3 x1≤200, x2≤300, x1+x2+x3≤400 x2+3x3≤600, x1,x2,x3≥0 * 习题 7.2 某种农产品产于A和B两地，其中A地产量15，B地产量为8。这种产品只在C和D两个城市销售，其中C城需求量为8而D城需求量为13。将每单位产品从A地运往C城需要￥2，运往D城需要￥3；将每单位产品从B地运往C城需要￥4，运往D城需要￥1。问如何运输使得运输代价最小，写出线性规划表达式。 * 算法设计与分析复习重点 内容 分治法 大数相乘，归并排序 图的分解 Explore算法，深度优先有哪些信誉好的足球投注网站 图中的路径 Dijkstra算法、Bellman-Ford算法 贪心算法 最小生成树，Kruskal算法、Prim算法 动态规划 Dag最短路径、最长递增子序列 线性规划 巧克力工厂 n-bit大数相乘算法 * 归并排序 给定一个数列，将其排序 排序问题的分治法求解 将待排序数列一分为二，每个子数列分别排序 将完成排序的两个子数列合并 * 考虑合并两个排序的数组 和 ，结果存入 中 * “o”表示元素与数列连接 一个mergesort算法执行实例 * 习题 使用分治大数相乘算法，计算两个二进制整10111010的乘积。要求画出算法执行的问题分解树。 * Explore算法 Explore算法 算法执行情况 一个节点上多条边存在时按字母顺序访问下一节点。这个树被称为深度优先有哪些信誉好的足球投注网站树（DFS树） 实线表示图上实际被访问的边，每条实线边代表一个explore调用。实线边被称为树边。 虚线边表示图上没有被访问的边，因为访问这些边不会发现新的节点。虚线边被称为回边。 * 深度优先有哪些信誉好的足球投注网站 explore(u)可以访问所有从u出发可达的节点 对于没有访问过的节点v，调用explore(v)访问从v出发能够到达的所有节点，直到图G上的所有节点都被访问过 * 在以上算法中，每个节点有两个关键事件： 算法首次访问到该节点； 算法完成从该节点出发的所有探索，离开该节点 定义数组pre和post分别记录