文档介绍：NP-完全问题(plete Problem) Thinking about Algorithms Abstractly
宫秀军
天津大学计算机科学与技术学院
******@tju.
主要内容
NP-完全问题:一些典型的例子
NP-完全问题:相关定义
近似算法
两种新的计算模型
plete: 涵义
N-Nondeterministic
Deterministic algorithm: Given a particular input, it will always produce the same correct output
Non-deterministic algorithm: with one or more choice points where multiple different continuations are possible, without any specification of which one will be taken
P-Polynomial (time)
Computable
Polynomial time is assumed the plexity
Complete
Reducible
输入/输出
算法复杂性
变换/封闭性
NP-C:典型的问题(1)
问题1 图着色问题
判定问题:是否存在不超过k种颜色的着色方案?
优化问题:求图的最小着色数和着色方案
问题2 作业调度问题
判定问题:是否存在罚款额不超过k的作业调度?
优化问题:求最小罚款额调度
NP-C:典型的问题(2)
问题3 Bin packing问题:假设有n种物品,它们的尺寸分别为s1,…,sn,0<si≤1另有任意多个箱子(Bins),箱子的容量为1,
判定问题:任意给定k,是否存在一种装箱方法使用的箱子数≤k?
优化问题:求使用最小箱数的装箱方法
NP-C:典型的问题(3)
问题4 背包问题
判定问题:是否存在效益值至少为k的可行子集?
优化问题
问题5 子集和数问题s1,s2,┅,sn,C
判定问题:是否存在和数等于C的子集?
优化问题:求≤C的最大子集和数.
可归约为背包问题: pi=wi.
NP-C:典型的问题(3)
F(合取范式)-可满足问题(SAT)
判定问题::
问题7 Hamiltonian 回路
判定问题
问题8 TSP(旅行商)问题
判定问题:任意给定一整数k,是否存在一长度不超过k的Hamiltonian回路?
优化问题
NP-C:典型的问题(4)
问题9:节点覆盖:无向图中的每一条边都被某些节点关联
判定问题:给定无向图G和正整数k,是否存在一k节点覆盖.
优化问题:最小节点覆盖
问题10: 给定一无向图G, k-独立集;最大独立集.
问题11: 给定一无向图G , k-集团;最大集团.
问题10和11可互相转化: 边互补图
目标函数取整数值时,优化值问题和判定问题等价我们可用二分查找从判定问题解得到优化值的问题的解
类P与类NP
(Class P & Class NP)
类P(1)
算法输入为问题实例的二进制编码. 定义该0/1字符串的长度为输入长度. 例如n个节点和m条边的图的长度为Θ(mlogn)().
多项式界:如一算法的最坏情形时间复杂度T(n)=O(p(n)),其中p(n)为输入长度n 的多项式, 则称该算法有多项式界.
如一个问题有多项式界的算法,则称该问题有多项式界.