算法分析与设计第十章优秀PPT.ppt
算法分析与设计 Analysis and Design of Computer Algorithms算法实力的极限 Limitations of Algorithm Power杨春明 School of Computer Science and Technology,SWUST计算模型n算法是理论计算机的灵魂。在理论计算算法是理论计算机的灵魂。在理论计算机中，算法已不限于只是定义中的计算机中，算法已不限于只是定义中的计算机程序。机程序。n确定型图灵机模型。确定型图灵机模型。n给出固定的程序，模型依据程序和输入给出固定的程序，模型依据程序和输入完全确定性地运行。完全确定性地运行。n非确定型图灵机。非确定型图灵机。n它在进行计算的时候，会自动选择最优它在进行计算的时候，会自动选择最优路径进行计算。通俗地说，它有预料实路径进行计算。通俗地说，它有预料实力。力。P和NP问题n理论计算机科学的核心问题n它是Clay探讨所的七个百万美元大奖问题之一n在2006国际数学家大会上，它是某个1小时讲座的主题。PNP？注：这里面的两个P都是指Polynomial(多项式)P类n假如一个算法，它能在以输入规模为参变量的某个多项式的时间内给出答案，则称它为多项式时间算法。nP类问题是一类用(确定性)算法在多项式的时间内求解的判定问题。nP类问题指在确定型图灵机上的具有多项式算法的问题集合。NP类n不确定算法是一个两个阶段的过程，它把一个判定问题的实例l作为它的输入，并做以下操作：n非确定性(揣测)阶段：生成随意一个S。n确定(验证)阶段：验证S是否是l的一个解。n假如一个不确定算法在验证阶段的时间效率是多项式级的，这个算法就是不确定多项式类型的。NP类nNP类问题是一类可以用不确定多项式算类问题是一类可以用不确定多项式算法求解的判定问题。法求解的判定问题。nNP类问题指非确定型图灵机上具有多项类问题指非确定型图灵机上具有多项式算法的问题集合，这里式算法的问题集合，这里N是是Non-Deterministic的意思。的意思。n在一般看来，在一般看来，P问题是指能够在多项式时问题是指能够在多项式时间求解的判定问题，而间求解的判定问题，而NP问题则是指那问题则是指那些确定解能够在给定正确信息下在多项些确定解能够在给定正确信息下在多项式时间内验证的判定问题。式时间内验证的判定问题。NP问题nP vs NP问题指P是否完全等于NP，即确定型图灵机和非确定图灵机的性能是否一样。n人们为何要提出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完全。正因为如此，多数理论计算机学家都揣测PNP。n假如NPP，那么NP-P中存在非NP完全问题。n当然，这种问题具体是什么样子，是无法用直观的语言表示出来，它纯粹是一个数学上的构造性证明。相关资源nNP完全问题的不完全列表n :/nada.kth.se/viggo/problemlist/compendium.htmlnClay Mathematics Instituten :/claymath.org/millennium/P_vs_NP/n图灵机-Wikipedia n :/zh.wikipedia.org/wiki/图灵机数值算法的挑战Challenges of Numerical Algorithmsn数值分析是指关切那些求解数学问题的算数值分析是指关切那些求解数学问题的算法。这里指的问题是法。这里指的问题是“连续连续”的数学问题。的数学问题。数值算法的挑战Challenges of Numerical Algorithmsn数值算法的挑战来自于：n在求解问题时不能得到精确的解。n这种不精确解的误差有两种：n截断误差：用有限来靠近无穷所造成的。n舍入误差：由于计算机在表示数字时的不精确性造成的。超越算法实力的极限Coping with the Limitations of Algorithm Powern教学内容n回溯（Backtracking）nn皇后（n-Queens Problem）n哈密顿回路（Hamiltonian Circuit Problem）n子集和数问题（Subset-Sum Problem）n分支限界（Branch-and-Bound）n安排问题 School of Computer Science and Technology,SWUST13 :/mryang.org/例：迷宫游戏回溯法与分支限界法n回溯与分支限界是对穷举法的改进。n它们每次只构造候选解的一个重量，然后评估这个部分解：n假如加上剩下的重量也不行能求得一个解，就不在生成剩下的重量。n回溯法和分支限界都是以构造一棵状态空间树为基础，树的节点反映了对 一个部分解所做的特定的选择。回溯法 Backtrackingn问题的解可以用一个n元组(x1,xn)来表示，其中的xi取自于某个有穷集Si，并且这些解必需使得某一规范函数P(x1,xn)取极值。n不断地用修改过规范函数Pi(x1,xn)去测试正在构造的n元组的部分向量，看是否可能导致最优解，假如不能，那么就将可能要测试的mi+1,mn个向量略去。n皇后问题 n-Queens Problemn把n个皇后放到一个n*n的棋盘上，使得任何两个皇后都不能相互攻击，即它们不能同行，不能同列，也不能在同一跳对角线上。4皇后问题的状态空间树解向量：(x1,x2,xn)，显约束：xi=1,2,n隐隐束：1)不同列：xixj 2)不处于同一正、反对角线：|i-j|xi-xj|School of Computer Science and Technology,SWUST19 :/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子集和数问题Subset-Sum Problem假定有n个不同的正数，要求找出这些数中全部使得某和数M的组合0-1背包问题 School of Computer Science and Technology,SWUST22 :/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+;/装满背包 if(i=n)bound+=pi/wi*cleft;return bound;分支限界（Branch-and-Bound）n与回溯法相比，分支限界须要两个额外条件：n对于一棵状态空间树的每一个节点所代表的部分解，须要供应一种方法，计算出通过这个部分解繁衍出的任何解在任何解在目标函数上的最佳值边界。n目前求得的最佳解的值。分支限界（Branch-and-Bound）n路径查找终止条件该节点的边界值不能超越目前最佳解的值。该节点无法代表任何可行解，因为它已违反了问题的约束。该节点代表的可行解的子集只包含一个单独的点（没有更多的选择）。School of Computer Science and Technology,SWUST24 :/mryang.org/安排问题nN个任务安排给n个人，任务j安排给人i的成本是CI,j School of Computer Science and Technology,SWUST25 :/mryang.org/任务任务1任务任务2任务任务3任务任务4人员19278人员26437人员35818人员47694边界（下界）的选择：边界（下界）的选择：包括最优解在内，任何解的成本都不会小于矩阵每行中最小元素的和。安排问题 School of Computer Science and Technology,SWUST26 :/mryang.org/安排问题 School of Computer Science and Technology,SWUST27 :/mryang.org/安排问题 School of Computer Science and Technology,SWUST28 :/mryang.org/背包问题边界（上界）的选择：边界（上界）的选择：已经选择物品的总价值v+背包的剩余承重W-w与剩下物品的最佳单位回报vi+1/wi+1的乘积。Ub=v+(W-w)(vi+1/wi+1)TSP边界（下界）的选择：边界（下界）的选择：对于每一个城市，求对于每一个城市，求出该城市到最近另个城出该城市到最近另个城市的距离和，并把全部市的距离和，并把全部城市的该距离和除以城市的该距离和除以2取整。取整。
