《算法分析与设计第十章》由会员分享，可在线阅读，更多相关《算法分析与设计第十章（30页珍藏版）》请在金锄头文库上搜索。
1、算法分析与设计 Analysis and Design of Computer Algorithms算法能力的极限 Limitations of Algorithm Power杨春明 School of Computer Science and Technology, SWUST计算模型n算法算法是理论计算机理论计算机的灵魂。在理论计算机中，算法已不限于只是定义中的计算机程序。n确定型图灵机确定型图灵机模型。给出固定的程序，模型按照程序和输入完全完全确定性确定性地运行。n非确定型图灵机非确定型图灵机。它在进行计算的时候，会自动选择最优路径进行计算。通俗地说，它有预测能力预测能力。P和NP问题n
2、理论计算机科学的核心问题n它是Clay研究所的七个百万美元大奖问题之一n在2006国际数学家大会上，它是某个1小时讲座的主题。 PNP？注：这里面的两个P都是指Polynomial(多项式)P类n如果一个算法，它能在以输入规模为参变量的某个多项式的时间内给出答案，则称它为多多项式时间算法项式时间算法。nP类问题是一类用(确定性确定性) 算法在多项式的时间内求解的判定问题判定问题。nP类问题指在确定型图灵机确定型图灵机上的具有多项式算法的问题集合。NP类n不确定算法是一个两个阶段的过程，它把一个判定问题的实例l作为它的输入，并做以下操作：非确定性(猜测)阶段：生成任意一个S。确定(验证)阶段：验
3、证S是否是l的一个解。n如果一个不确定算法在验证阶段的时间效率是多项式级的，这个算法就是不确定多项式类不确定多项式类型型的。NP类nNP类问题类问题是一类可以用不确定多项式不确定多项式算法求解的判定问题。nNP类问题类问题指非确定型图灵机上具有多项式算法的问题集合，这里N是Non-Deterministic的意思。n在一般看来，P问题是指能够在多项式时多项式时间间求解的判定问题判定问题，而NP问题则是指那些肯定解肯定解能够在给定正确信息下在多项多项式时间式时间内验证验证的判定问题。 NP问题nP vs NP问题指P是否完全等于NP，即确定型图灵机和非确定图灵机的性能是否一样。 n人们为何要提出
4、NP问题？因为，大多数遇到的自然界的难解问题，最后都发现它们是NP问题。如果我们能证明NP跟P的关系，则解决了无数问题的算法复杂度问题。 P NPPNP？NP完全问题nNP里面有无数个不同的问题，我们是否要一个一个地判定它们是否属于P呢？nNP完全完全(NP Complete，简记为NPC)问题，指的是那些NP中最难的那些问题：所有其它的NP问题都可以归约到这些NP完全问题。也就是说，只要这些NP完全问题的某一个到解决，无论是证明其存在多项式算法，还是不存在，都意味着P vs NP问题的解决。NP完全问题n几乎所有NP里面无法确定是否属于P的问题最后都被证明为NP完全。正因为如此，多数理论计算
5、机学家都猜测PNP。n如果NPP，那么NP-P中存在非NP完全问题。n当然，这种问题具体是什么样子，是无法用直观的语言表示出来，它纯粹是一个数学上的构造性证明。相关资源nNP完全问题的不完全列表http:/www.nada.kth.se/viggo/problemlist/compendium.htmlnClay Mathematics Institutehttp:/www.claymath.org/millennium/P_vs_NP/n图灵机- Wikipedia http:/zh.wikipedia.org/wiki/图灵机数值算法的挑战Challenges of Numerical A
6、lgorithmsn数值分析数值分析是指关心那些求解数学问题的算法。这里指的问题是“连续连续”的数学问题。数值算法的挑战Challenges of Numerical Algorithmsn数值算法的挑战来自于：在求解问题时不能得到精确的解。这种不精确解的误差有两种：截断误差：用有限来逼近无穷所造成的。舍入误差：由于计算机在表示数字时的不精确性造成的。超越算法能力的极限Coping with the Limitations of Algorithm Powern教学内容回溯（Backtracking）nn皇后（n-Queens Problem）n哈密顿回路（Hamiltonian Circui
7、t Problem）n子集和数问题（Subset-Sum Problem）分支限界（Branch-and-Bound）n分配问题 School of Computer Science and Technology, SWUST13http:/www.mryang.org/例：迷宫游戏回溯法与分支限界法n回溯与分支限界是对穷举法的改进。n它们每次只构造候选解的一个分量，然后评估这个部分解：如果加上剩下的分量也不可能求得一个解，就不在生成剩下的分量。n回溯法和分支限界都是以构造一棵状态空间树为基础，树的节点反映了对 一个部分解所做的特定的选择。回溯法 Backtrackingn问题的解可以用一个n
8、元组(x1,xn)来表示，其中的xi取自于某个有穷集Si，并且这些解必须使得某一规范函数P(x1,xn)取极值。n不断地用修改过规范函数Pi(x1,xn)去测试正在构造的n元组的部分向量，看是否可能导致最优解，如果不能，那么就将可能要测试的mi+1,mn个向量略去。n皇后问题 n-Queens Problemn把n个皇后放到一个n*n的棋盘上，使得任何两个皇后都不能互相攻击，即它们不能同行，不能同列，也不能在同一跳对角线上。http:/en.wikipedia.org/wiki/N-queens_problem4皇后问题的状态空间树解向量：(x1, x2, , xn) ，显约束：xi=1,2,
9、 ,n隐约束： 1)不同列：不同列：xi xj 2)不处于同一正、反对角线：不处于同一正、反对角线：|i-j| |xi-xj| School of Computer Science and Technology, SWUST19http:/www.mryang.org/ private static boolean place (int k) for (int j=1;jn) sum+; else for (int i=1;i=n;i+) xt=i; if (place(t) backtrack(t+1); 哈密顿回路Hamiltonian Circuit Problem子集和数问题Subse
10、t-Sum Problem假定有n个不同的正数，要求找出这些数中所有使得某和数M的组合0-1背包问题 School of Computer Science and Technology, SWUST22http:/www.mryang.org/可行性约束函数：上界函数：private static double bound(int i) / 计算上界 double cleft = c - cw; / 剩余容量 double bound = cp; / 以物品单位重量价值递减序装入物品 while (i = n & wi = cleft) cleft -= wi; bound += pi; i+
11、; / 装满背包 if (i = n) bound += pi / wi * cleft; return bound; 分支限界（Branch-and-Bound）n与回溯法相比，分支限界需要两个额外条件：对于一棵状态空间树的每一个节点所代表的部分解，需要提供一种方法，计算出通过这个部分解繁衍出的任何解在任何解在目标函数上的最佳值边界边界。目前求得的最佳解的值。分支限界（Branch-and-Bound）n路径查找终止条件该节点的边界值不能超越目前最佳解的值。该节点无法代表任何可行解，因为它已违反了问题的约束。该节点代表的可行解的子集只包含一个单独的点（没有更多的选择）。 School of
12、Computer Science and Technology, SWUST24http:/www.mryang.org/分配问题nN个任务分配给n个人，任务j分配给人i的成本是CI,j School of Computer Science and Technology, SWUST25http:/www.mryang.org/任务任务1任务任务2任务任务3任务任务4人员19278人员26437人员35818人员47694边界（下界）的选择：边界（下界）的选择：包括最优解在内，任何解的成本都不会小于矩阵每行中最小元素的和。分配问题 School of Computer Science and
13、Technology, SWUST26http:/www.mryang.org/分配问题 School of Computer Science and Technology, SWUST27http:/www.mryang.org/分配问题 School of Computer Science and Technology, SWUST28http:/www.mryang.org/背包问题边界（上界）的选择：边界（上界）的选择：已经选择物品的总价值v+背包的剩余承重W-w与剩下物品的最佳单位回报vi+1/wi+1的乘积。Ub=v+(W-w)(vi+1/wi+1)TSP边界（下界）的选择：边界（下界）的选择：对于每一个城市，求出该城市到最近另个城市的距离和，并把所有城市的该距离和除以2取整。
