8 难问题的部分分类

8.1 包装问题

包装问题主要有独立集问题和集合包装问题。
(1)独立集问题:给定图G和数k,问G包含大小至少为k的独立集吗?
(2)集合包装问题:给定 n 个元素的集合 U , U 的子集 S_1,S_2,…,S_m 以及数 k , 问在这些子集中至少含有 k 个集合两两不相交?

8.2 覆盖问题

覆盖问题主要有顶点覆盖和集合覆盖问题。
(1)顶点覆盖:给定图G和数k,G是否包含大小为k的顶点覆盖?
(2)集合覆盖:给定 n 个元素的集合U,U 的子集S_1,…,S_m 以及数 k, 问在这些子集中有一组子集,它的并等于整个 U 且至多含有 k 个子集?

8.3 划分问题

划分问主要是三维匹配问题和图着色问题。
(1)三维匹配问题:给定三个不相交的集合X、Y、Z,三个集合的大小都为n。给定一个三元组集合,集合T的大小为m。问:T中是否存在一个大小为n的子集T’,这个子集恰好包含X,Y,Z每个元素一次。
(2)图着色问题:任意给图G和界限k,问G有k-着色吗?

8.4 排序问题

排序问题主要是巡回售货员问题、哈密顿圈、哈密顿路径问题。
(1)巡回售货员问题:给定n个城市之间的距离的集合以及界限D,问有长度不超过D的路线吗?
(2)哈密顿圈:给定有向图G,问G有哈密顿圈吗?
(3)哈密顿路径:给定有向图G,问G有哈密顿路径吗?

8.5 数值问题

数值问题主要是子集和问题。
(1)子集和:给定自然数w_1,w_2,…,w_n和目标值W,问{w_1,w_2,…,w_n}有一个子集加起来恰好等于W吗?

8.6 约束满足问题

约束满足问题主要是电路可满足性问题、SAT和3-SAT。
(1)电路可满足性:给定一个电路,需要确定是否存在对输入的赋值使得输出值为1。如果存在这样的赋值,则称这个电路是可满足的。这个赋值也被称为一个满足的赋值。
(2)SAT:给定变量集 X={{x_1,x_2,…,x_n}} 上的一组子句 C_1,C_2,…,C_n ,问存在满足的真值赋值吗?
(3)3-SAT:给定变量集 X={{x_1,x_2,…,x_n}} 上的一组子句 C_1,C_2,…,C_n ,每一个子句的长度为3,问存在满足的真值赋值吗?

0
Posted in 算法设计与分析

Leave a Comment:

电子邮件地址不会被公开。