算法设计与分析_08一些NP完全问题

非常经典的算法设计技术,例如递归与分治、动态规划、贪心、回溯、分支限界、图算法,也包括了一些高级的算法设计主题,例如网络流和匹配、启发式搜索、线性规划、数论以及计算几何。在算法分析方面,介绍了概率分析以及最新的分摊分析和实验分析方法。在算法的理论方面,介绍了问题的下界、算法的正确性证明以及NP完全理论等方面的内容。

算法设计与分析

——一些NP完全问题

2016/2/10

算法设计与分析演示稿 纪玉波制 作(C)

非常经典的算法设计技术,例如递归与分治、动态规划、贪心、回溯、分支限界、图算法,也包括了一些高级的算法设计主题,例如网络流和匹配、启发式搜索、线性规划、数论以及计算几何。在算法分析方面,介绍了概率分析以及最新的分摊分析和实验分析方法。在算法的理论方面,介绍了问题的下界、算法的正确性证明以及NP完全理论等方面的内容。

一些NP完全问题1.顶点覆盖: 图G=(V,E),正整数K≤|V|。

问：是否存在关于G的大小不超过K的顶点覆盖，即是否有 子集V’ V,使得|V’|≤K ,并且对于每一条边{u,v}∈E,

u和v中至少有一个属于V’?注释：问题的变形一一如果要求由V’所导出的子图是连通 的——甚至对于顶点度数不超过4的平面图，也是NP完全的。 相关的边覆盖问题一一即求最小的集使得所有v∈V’都至 少属于一个e∈E’——能通过图的匹配在多项式时间内得到 解决。2016/2/10 算法设计与分析演示稿 纪玉波制 作(C) 2

非常经典的算法设计技术,例如递归与分治、动态规划、贪心、回溯、分支限界、图算法,也包括了一些高级的算法设计主题,例如网络流和匹配、启发式搜索、线性规划、数论以及计算几何。在算法分析方面,介绍了概率分析以及最新的分摊分析和实验分析方法。在算法的理论方面,介绍了问题的下界、算法的正确性证明以及NP完全理论等方面的内容。

2.图的可着K色性:图G=(V,E),正整数 K≤|V|。 问：G是否可着K色，即是否存在函数 f:V→{1,2,…,K}, 使得只要{u,v}∈E,就有f(u)≠f(v)? 注释：对于K=2,是多项式时间内可解的，但 对于所有固定的K≥3,和对于K=3而且不含4度 以上顶点的平面图，仍是NP完全的。

2016/2/10

算法设计与分析演示稿 纪玉波制 作(C)

非常经典的算法设计技术,例如递归与分治、动态规划、贪心、回溯、分支限界、图算法,也包括了一些高级的算法设计主题,例如网络流和匹配、启发式搜索、线性规划、数论以及计算几何。在算法分析方面,介绍了概率分析以及最新的分摊分析和实验分析方法。在算法的理论方面,介绍了问题的下界、算法的正确性证明以及NP完全理论等方面的内容。

3.三角划分:图G=(V,E),且|V|=3q,q是某 个整数。 问：G的顶点是否能被划分成q个不相交的集合 V1,V2,…,Vq, 其中每个集合恰好包含有三个顶点，使得对于 每个Vi={ui,vi,wi},1≤i≤q,三条边{ui,vi,}, {ui,wi}{vi,wi},都属于E?

2016/2/10

算法设计与分析演示稿 纪玉波制 作(C)

非常经典的算法设计技术,例如递归与分治、动态规划、贪心、回溯、分支限界、图算法,也包括了一些高级的算法设计主题,例如网络流和匹配、启发式搜索、线性规划、数论以及计算几何。在算法分析方面,介绍了概率分析以及最新的分摊分析和实验分析方法。在算法的理论方面,介绍了问题的下界、算法的正确性证明以及NP完全理论等方面的内容。

4.划分成完美匹配:图G=(V,E),正整数K≤|V|。 问：G的顶点是否能划分成k≤K个不相交的集合 V1,V2,…,Vk, 使得对于1≤i≤k,由Vi诱导的子图是一个完美匹 配(全部由1度的顶点组成)? 注释：对于K=2,仍然是NP完全的。

2016/2/10

算法设计与分析演示稿 纪玉波制 作(C)

非常经典的算法设计技术,例如递归与分治、动态规划、贪心、回溯、分支限界、图算法,也包括了一些高级的算法设计主题,例如网络流和匹配、启发式搜索、线性规划、数论以及计算几何。在算法分析方面,介绍了概率分析以及最新的分摊分析和实验分析方法。在算法的理论方面,介绍了问题的下界、算法的正确性证明以及NP完全理论等方面的内容。

5.独立集:图G=(V,E),正整数K≤|V|。 问：G是否会有大于等于K的独立集，即是否有 子集 V’ V 使得|V’|≥K并且V’中的任意两个顶点都不被E 中的边所连接？

2016/2/10

算法设计与分析演示稿 纪玉波制 作(C)

非常经典的算法设计技术,例如递归与分治、动态规划、贪心、回溯、分支限界、图算法,也包括了一些高级的算法设计主题,例如网络流和匹配、启发式搜索、线性规划、数论以及计算几何。在算法分析方面,介绍了概率分析以及最新的分摊分析和实验分析方法。在算法的理论方面,介绍了问题的下界、算法的正确性证明以及NP完全理论等方面的内容。

6.单连通子图:有向图G=(V,A),正整数 K≤|A|。 问：是否有子集A’ A,|A’|≥K,使得 G’=(V,A’)在任意一对顶点之间至多只有一条有 向通路？注释：对于无圈有向图仍然是NP完全的。

2016/2/10

算法设计与分析演示稿 纪玉波制 作(C)

非常经典的算法设计技术,例如递归与分治、动态规划、贪心、回溯、分支限界、图算法,也包括了一些高级的算法设计主题,例如网络流和匹配、启发式搜索、线性规划、数论以及计算几何。在算法分析方面,介绍了概率分析以及最新的分摊分析和实验分析方法。在算法的理论方面,介绍了问题的下界、算法的正确性证明以及NP完全理论等方面的内容。

7.最小的K连通子图:图G=(V,E),正整数 K≤|V|, B≤|E|。 问：是否有子集E’ E,|E’|≥B使得G’=(V, E’)是K连通的，即去掉少于K个顶点不能使它 成为不连通的？ 注释：对于任一固定的K≥2,这个问题仍是NP 完全的，而对于K=1,则在多项式时间内可解。

2016/2/10

算法设计与分析演示稿 纪玉波制 作(C)

非常经典的算法设计技术,例如递归与分治、动态规划、贪心、回溯、分支限界、图算法,也包括了一些高级的算法设计主题,例如网络流和匹配、启发式搜索、线性规划、数论以及计算几何。在算法分析方面,介绍了概率分析以及最新的分摊分析和实验分析方法。在算法的理论方面,介绍了问题的下界、算法的正确性证明以及NP完全理论等方面的内容。

8.哈密顿回路:图G=(V,E)。 问：G中是否包含有哈密顿回路？ (包含G的每个顶点的路称为G的Hamilton路)

2016/2/10

算法设计与分析演示稿 纪玉波制 作(C)

非常经典的算法设计技术,例如递归与分治、动态规划、贪心、回溯、分支限界、图算法,也包括了一些高级的算法设计主题,例如网络流和匹配、启发式搜索、线性规划、数论以及计算几何。在算法分析方面,介绍了概率分析以及最新的分摊分析和实验分析方法。在算法的理论方面,介绍了问题的下界、算法的正确性证明以及NP完全理论等方面的内容。

9.有向的哈密顿回路:有向图G=(V,A)。 问：G中是否含有有向的哈密顿回路？ 注释：即使G是平面图，并且没有顶点包含在3条 以上的弧中，仍是NP完全的。

2016/2/10

算法设计与分析演示稿 纪玉波制 作(C)

非常经典的算法设计技术,例如递归与分治、动态规划、贪心、回溯、分支限界、图算法,也包括了一些高级的算法设计主题,例如网络流和匹配、启发式搜索、线性规划、数论以及计算几何。在算法分析方面,介绍了概率分析以及最新的分摊分析和实验分析方法。在算法的理论方面,介绍了问题的下界、算法的正确性证 …… 此处隐藏：3699字，全部文档内容请下载后查看。喜欢就下载吧 ……