NP-Complete涵义-天津大学计算机学院.ppt

* * * * A quantum computer is any device for computation that makes direct use of distinctively quantum mechanical phenomena, such as superposition and entanglement, to perform operations on data. In a classical (or conventional) computer, the amount of data is measured by bits; in a quantum computer, the data is measured by qubits. The basic principle of quantum computation is that the quantum properties of particles can be used to represent and structure data, and that quantum mechanisms can be devised and built to perform operations with these data.[1] Though quantum computing is still in its infancy, experiments have been carried out in which quantum computational operations were executed on a very small number of qubits. Research in both theoretical and practical areas continues at a frantic pace, and many national government and military funding agencies support quantum computing research to develop quantum computers for both civilian and national security purposes, such as cryptanalysis.[2] (See Timeline of quantum computing for details on current and past progress.) * * * * * * * L, the class of problems decidable in a logarithmic amount of memory space AL： the set of problems solvable in logarithmic memory by alternating Turing machines PSPACE, the class of problems decidable in polynomial space EXPTIME is the class of problems solvable in exponential time * * * * * * * * * * * * * * * * * * * * * * * * * 近似算法（2） 设A为一近似算法,令A(I)为输入I时该算法输出的可行解 极小化和极大化问题度量近似性能的指标rA(I) 续 式(13.5)定义的RA(m)为最坏情形rA(I)的值,是与输入I无关的指标: 在固定优化值m下求最坏情形的比值 式(13.6)定义的SA(n)也是一与输入独立的指标 Bin-Packing的近似算法 怎么装不同大小、不同形状的货物才能使占用的箱子数最少。该问题形式化如下： 装箱问题 设S = (s1, …, sn) 0 si = 1 ， 1 = i = n 将 s1, …, sn 装入尽可能少的箱子里。假定每个箱子都有容量1。 装箱问题是NP-难度问题 搜索算法有指数的复杂度：须试所有可能的S的分划。 装箱问题：FFD算法（贪心法） 将物品按尺寸递减排序，箱子从左到右排列并尽可能放在前面的箱子里。 算法的时间复杂度t(n)=?(n2) 算法：装箱问题 输入: S=(s1,….,sn) ，0si≤1 ，1≤i≤n. S 代表货物1,...,n 的尺寸，每个箱子的容量都是1.0。 输出: bin[i]是放物品i的箱子号,1≤i≤n. 为了使算法简单，在装箱前，货物已经按尺寸从大到小排序。 装箱问题的程序 binpackFFd(S,n,bin) {