西安邮电大学算法资料.doc

选择：1.算法的性质包括输入、输出、（ A ）、有限性。A. 确定性 B. 随机性 C. 复杂性 D. 渐近复杂性2.备忘录法是那种算法的变形（ B ）。A、 分治算法 B、动态规划算法 C、贪心算法 D、回溯法3.具有最优子结构的算法有（ D ）。A概率算法 B回溯法 C分支限界法 D动态规划法4.回溯法解旅行商问题时的解空间树是（ B ）。A、子集树 B、排列树 C、深度优先生成树 D、广度优先生成树5.下面哪种函数是回溯法中避免无效搜索采取的策略（ C ）。A、递归函数 B、随机函数 C、剪枝函数 D、搜索函数简答：（1） 算法的概念：算法是指解决问题的一种方法或一个过程。（2） 算法的性质：算法是若干指令的有穷序列，满足性质：（1）输入：有外部提供的量作为算法的输入。（2）输出：算法产生至少一个量作为输出。（3）确定性：组成算法的每条指令是清晰，无歧义的。（4）有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。（5）可行性：算法的每一条指令必须足够基本，它们可以通过已经实现的基本运算执行有限次来实现。（3） 程序的概念：程序是算法用某种程序设计语言的具体实现（4） 算法与程序的不同：（1）算法是给人来读的，直接将算法输入计算机是不能运行的（2）程序可以不满足算法的“有限性”。（5） 算法复杂性：算法所需要的计算机资源，所需资源多，算法的复杂性高；反之则复杂性低。【时间复杂性（指令数）、空间复杂性（存储器大小）、渐近复杂性】（6） 计算复杂性：是用计算机求解问题的难易程度。其度量标准：一是计算所需的步数或指令条数（时间复杂度），二是计算所需的存储单元数量（空间复杂度）。（7） 渐近复杂性的基本分析方法（8） 可操作性最好且最有实际价值的是最坏情况下的时间复杂性。（9） 算法渐近复杂性分析中常用函数：单调函数；取整函数；多项式函数；指数函数；对数函数；阶乘函数；第 2 章 递归与分治策略（1）分治法的基本思想：将一个问题不断分割成若干个小问题，然后通过对小问题的求解再生成大问题的解。（2）分治法所能解决问题具有的特征：将要求解的较大规模的问题分割为 k 个较小规模的子问题。对这 k 个子问题分别求解。如果子问题的规模仍然不够小，则再划分为 k 个子问题，如此递归的进行下去，直到问题规模足够小，很容易求出其解为止。（3）分治法与动态规划算法的相同点和不同点是什么：分治法与动态规划的相同点：分治法与动态规划，二者要求原问题具有最有子结构，都是将问题分而治之分解成若干个规模较小的子问题；不同点：动态规划是将原问题分解为多个子问题，通过计算出子问题的结果构造一个最优解。动态规划通过迭代法自底向上求解，动态规划将分解后的子问题理解为相互间有联系，有重叠的部分；算法的应用：装配线，矩阵乘法，最长公共子序列，构造最优的二叉树分治法是将原问题分解为多个子问题，利用递归对各个子问题独立求解，最后利用各子问题的解进行合并形成原问题的解。分治法将分解后的子问题看成是相互独立的。（4）二分搜索方法的基本思想：将 n 个元素分成个数大致相同的两半，取 a n / 2 与欲查找的 x 作比较，如果 x = a n / 2 则找到 x，算法终止；如果 x a n / 2 ，则只要在数组 a 的右半部继续搜索 x。！（5）二分搜索方法的程序设计：充分利用了元素间的次序关系，采用分治策略（6）棋盘覆盖问题的基本思想：棋盘覆盖问题初看起来很难下手解决，但仔细思考后可以采用分治策略设计针对该问题的一个巧妙解法：如下图所示，当 k 0 时，将 2k 2k 棋盘分割为 4 个 2k-1 2k-1 子棋盘，如图 (a) 所示。显然特殊方格必位于图 (a) 中 4 个较小子棋盘之一中，其余 3 个子棋盘中则无特殊方格。为了将这 3 个无特殊方格的子棋盘转化为特殊棋盘，可以用一个 L 型骨牌覆盖这 3 个较小棋盘的会合处，如图 (b) 和 (c) 所示。从而将原问题转化为 4 个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘 11（易于求解）。（7）合并排序基本思想是：（1）将待排序元素分成大小大致相同的两个子集合，（2）分别对两个子集合进行排序，（3）最终将排好序的子集合合并成为所要求的排好序的集合。（8）快速排序基本思想：排序子数组 a p : r ，步骤如下：（1）分解：以 a p 为基准元素将 a p : r 分成 3 段： a p : q - 1 、 a q 、 a q + 1 : r 。满足条件： a p : q - 1 中任何一个元素 = a q 。下标 q 在划分过程中确定。（2）递归求解：通过递归调用快速排序算法分别对 a p : q - 1 和 a q + 1 : r 进行排序。（3）合并：对 a p : q - 1 和 a q + 1 : r 的排序在各自的范围内进行，因此排好序后不需任何运算整个数组 a p : r 即完成排序。第 3 章 动态规划（1）动态规划的基本思想及其要素：基本思想：将待求解问题分解成若干个子问题。要素：最优子结构性质和重叠问题性质。（2）矩阵连乘问题！（3）备忘录方法的概念：备忘录方法是动态规划方法的变形。与动态规划算法不同的是，备忘录方法的递归方式是自顶向下的，而动态规划算法则是自底向上的。备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。（4）最长公共子序列：一个数列 ，如果分别是两个或多个已知数列的子序列，且是所有符合此条件序列中最长的，则 称为已知序列的最长公共子序列。（5）最大子段和的基本概念：（6） 0-1背包问题的基本思想第 4 章 贪心算法（1）贪心法的思想：当一个问题具有最优子结构性质时，可用动态规划法求解。但有时会有更简单有效的算法。（2）活动安排问题：活动安排问题就是要在所给的活动集合中选出最大的相容活动子集合，该问题要求高效地安排一系列争用某一公共资源的活动。（3）贪心算法的基本要素：贪心选择性质和最优子结构性质。与动态规划算法的差异：（1）贪心选择性质是指所求问题的整体最优解可以通过一系列局部最优的选择，即贪心选择来达到。这是贪心算法可行的第一个基本要素，也是贪心算法与动态规划算法的主要区别。（2）动态规划算法通常以自底向上的方式解各子问题，而贪心算法则通常以自顶向下的方式进行，以迭代的方式作出相继的贪心选择，每作一次贪心选择就将所求问题简化为规模更小的子问题。（3）对于一个具体问题，要确定它是否具有贪心选择性质，必须证明每一步所作的贪心选择最终导致问题的整体最优解。回溯法的基本思想：从一条路往前走，能进则进，不能进则退回来，换一条路再试。 基本概念：是一种系统地搜索解空间树而求得问题解的搜索算法。计算：1.2.3.使用分治算法找一组数的最大最小数。采用如下设计思想：将数据集 S 均分为 S1 和 S2；求解 S1 和 S2 中的最大和最小值；最终的最大和最小值可以计算得到：min( S1, S2 ), max( S1, S2 )；采用同样的处理方法递归处理 S1 和 S2。可以得到该算法复杂性的递推公式如下：根据递推公式推导出该复杂性表达式。4.下面给出了非递归形式的二分搜索方法代码，请补充下划线处的代码。5.利用动态规划法设计如下的矩阵连乘最小次数问题，写出动态规划法求解过程。A1：4025 A2：2525 A3：2515解：m00=m11 =m22 =m33=0 r=2 i=1 j=2 m12=40*25*10=10000 i=2 j=3 m23= 25*10*15=3750 r=3 i=1 j=3 m13= m11+ m23+ 40*25*15=18750 k=2 t= m12+ m33+ 40*10*15=16000 m13=t=160006.上机实验：用分治法找最大最小数7.上机实验：编辑距离8.上机实验：数字三角形证明：1.2.证明上述问题具有“贪心选择性质”和“最优子结构性质”。算法：1.有一个箱子容量为 V（正整数），同时有 n 个物品，每个物品有一个体积（正整数）。要求 n 个物品中，任取若干个装入箱内，使箱子的剩余空间为最小。编写程序实现，自定义输入和输出。【提示】使用二维数组 f i j , 表示前 i 个物品装入容量为 j 的箱子能获得的最大体积，则状态转移方程：f i j = max( f i - 1 j , f i -1 j - a i + a i );2.用回溯法搜索排列树的算法是什么？void Backtrack ( int t ) if ( t n ) output( x ); else for ( int i = t; i = n; i+ ) swap( x t , x i ); if ( Constraint( t ) & Bound( t ) ) Backtrack( t + 1 ); swap( x t , x i ); 3.对批处理作业调度问题：作业需要机器处理时间的表如下，如果调度方案为：1，2，3，计算完成时