一.NP完全性理论
(1)在图灵机计算模型中,移动函数δ是单值的,即对于Q´Tk中的每一个值,当它属于δ的定义域时Q´(T´{L,R,S})k
中只有唯一的值与之对应,称这种图灵机为确定性图灵机,简记为DTM(Deterministic Turing Machine)。
(2)非确定性图灵机(NDTM ):一个k带的非确定性图灵机M是一个7元组:(Q,T,I,δ,b,q0,qf)。与确定性图灵机不同的是非确定性图灵机允许移动函数δ具有不确定性,即对于Q´Tk中的每一个值(q;x1,x2,…,xk),当它属于δ的定义域时,Q´(T´{L,R,S})k中有唯一的一个子集δ(q;x1,x2,…,xk)与之对应。可以在δ(q;x1,x2,…,xk)中随意选定一个值作为它的函数值。
P类和NP类语言的定义:
P={L|L是一个能在多项式时间内被一台DTM所接受的语言}
NP={L|L是一个能在多项式时间内被一台NDTM所接受的语言}
(3)三类问题:P类、NP类、NPC类问题
P类问题:在多项式时间内可以解决的问题
NP类问题:能被一个多项式时间算法验证的问题
NPC类问题:
它的状态是未知的,既没有人找出求解NPC问题的多项式时间算法,也没有人能够证明对这类问题不存在多项式时间算法。
(4)三者关系
(5)NP理论应用
1. 3-CNF可满足性
2. 团问题
3. 顶点覆盖问题
4. 哈密顿回路问题
5. 旅行商问题
6. 子集和问题
二.近似算法
迄今为止,所有的NP完全问题都还没有多项式时间算法。对于这类问题,通常可采取以下几种解题策略。
(1)只对问题的特殊实例求解
(2)用动态规划法或分支限界法求解
(3)用概率算法求解
(4)只求近似解
(5)用启发式方法求解