本文主要是介绍《算法概论》课后习题8.22——NP-完全问题,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!
8.22 在任务调度中,常常会用到图。其中节点对应于任务,任务i到j的有向边表示i到j的先期条件。这样的图描述了调度问题中的任务先后关系(约束)。显然,一个调度是可行的当且仅当该图无环;如果调度不可行,我们需要求使其无环所需的最小约束数量。
给定有向图G=(V, E),子集E’⊆E称为一个反馈弧集合是指:将其移除后将使得G无环。
反馈弧集合(FEEDBACK ARC SET,简称FAS)问题:给定有向图G=(V, E)和预算b,求包含不超过b条边的反馈弧集合——如果这样的集合存在。
(a)证明FAS属于NP。
通过将顶点覆盖问题归约为FAS,可以证明FAS是NP-完全的。给定一个顶点覆盖实例(G, b),我们如下构造一个FAS实例(G’, b): 如果G=(V, E)包含n个顶点v1, …, vn,则生成一个包含2n个顶点w1, w1’, …, wn, wn’和n+2|E|条边的有向图G’=(V’, E’),其中的边为:
- 对所有i=1, 2, …, n, 有(wi, wi’).
- 对每个(vi, vj)∈E,有(wi’, wj)和(wj’, wi).
(b)证明如果G包含规模为b的顶点覆盖,则G’有规模为b的反馈弧集合。
(c)证明如果G’包含规模为b的反馈弧集合,则G有规模不超过b的顶点覆盖。
(提示:给定G’的规模为b的反馈弧集合,首先需要对其进行一点修改,得到一个形式更简洁但规模不超过原反馈弧集合的集合。然后说明G必然包含一个与修改后的反馈弧集合规模相同的顶点覆盖即可。)
答:
这篇关于《算法概论》课后习题8.22——NP-完全问题的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!