算法导论实战（六）（算法导论习题三十四、三十五章）

🌈 个人主页：十二月的猫-CSDN博客
🔥 系列专栏： 🏀算法启示录

💪🏻 十二月的寒冬阻挡不了春天的脚步，十二点的黑夜遮蔽不住黎明的曙光

前言

算法导论的知识点学习将持续性更新在算法启示录_十二月的猫的博客-CSDN博客，欢迎大家订阅呀（反正是免费的哦~~）

实战篇也将在专栏上持续更新，主要目的是强化对理论的学习（题目来源：山东大学孔凡玉老师推荐）

前言

第三十四章

34.1-4

34.5-1

34.5-5

第三十五章

35.1-4

35.2-3

总结

第三十四章

34.1-4

问题描述：

练习 16. 2-2 中曾要求读者给出的 0-1 背包问题的“动态规划算法“，它是一个多项式时间的算法吗？解释你的答案。

问题分析：

首先回忆：0-1背包问题的动态规划算法是什么？

0-1背包动态规划算法：

0-1bag(w,v,n,m) //n表示物品数量，m表示背包最大重量
    let d(i,j) be a Two-dimensional arrays
    for i=0 to n
        d(i,0)=0
    for j=1 to m
        d(0,j)=0
    for i =1 to n
        for j=1 to m
            if(j>w(i))
                d(i,j)=max(d(i-1,j),d(i-1,j-w(i))+v(i))
            else
                d(i,j)=d(i-1,j)

分析算法我们不难知道算法的时间复杂度为O(nm)，其中n为物品最大数量，m为背包重量上限

问题本质就是让我们思考O(nm)这个时间复杂度是不是多项式时间的

时间复杂度分为：编码时间复杂度、非编码时间复杂度

很多算法在非编码情况下时间复杂度为多项式时间的，但是在编码下就是非多项式时间

编码时间复杂度更贴和计算机实际运行的情况

问题求解：

这不是一个多项式时间的算法。考虑问题的编码。通过给出每个物品的索引、价值和重量的二进制表示，可以进行多项式编码，这些被表示为长度为a = Ω(n)的二进制字符串（每个物品独立需要一串编码，不能用两个位表示四个物品）。我们在多项式时间内对W进行编码，这将有长度为Θ(log W) 的编码（能用两位表示四个重量）。这个长度为a + b的问题的解的时间为Θ(nW) = Θ(a · 2^b)。因此，该算法实际上是指数级的。

注：本题实际上是问算法实际运行的时间复杂度

34.5-1

问题描述：

子图同构问题取两个无向图 G1、G2, 要回答 G1 是否与 G2 的一个子图同构这一问题。证明：子图同构问题是 NP 完全的。（本题就是证明子图同构问题是NP完全问题）

问题分析：

证明L问题是NP完全问题的步骤：

证明L∈NP
选取一个已知的NP完全问题L’
描述一个归约函数f（x）能够把L‘归约到L
证明归约函数f的归约是多项式时间的
当且仅当L‘有解时L有解

总的思路：假设L’有解将每个实例归约成L，此时L也有解；但是L‘是NPC问题，所以L也是NPC问题无解

问题求解：

1、假如我们得到了G1、G2以及其对应的解——G2的子图G2‘与G1同构。此时我们只需要遍历G2’中的点和每一个与点相连的边，同时检查G1中是够有对应的点即可验证。这个验证的时间复杂度是O(EV)（其中E为G2‘的边集，V为G1的点集），所以是多项式时间。但是假如不知道G2哪个子图与G1同构，要去寻找的话，由于G2的子图有2^n个，所以寻找的时间显然不是多项式时间

2、选择团问题作为已知的NPC问题，接下去思考如何把团问题归约到子图同构问题上

3、假如现在我们有一个有解团问题<G,k>，即G中存在一个k规模的团（即有k个点的完全子图），记这个完全子图为Gk。此时我们构造一个G2，令G2是和Gk一样规模的完全子图。那么我们将G和G2放到子图同构中不难证明，G一定有子图Gk与G2同构

4、假如G有子图Gk与G2同构，那么至少G中会存在规模为k的团，即L语言在NPC问题L’中一定有对应的解。同时团问题有解时由3可知子图同构问题也一定有解。所以当且仅当关系证明完毕！

5、由于归约算法中，我们仅仅构造一个规模为k的完全图G2，所以这个归约算法是多项式时间内可以完成的

34.5-5

问题描述：

给定一个整数集合S，求集合S的一个划分S1和S2（即：S=S1∪S2且S1∩S2=Φ），使得S1中的元素之和等于S2中的元素之和（本题就是证明集合划分问题是NPC问题）

问题分析：

证明L问题是NP完全问题的步骤：

证明L∈NP
选取一个已知的NP完全问题L’
描述一个归约函数f（x）能够把L‘归约到L
证明归约函数f的归约是多项式时间的
当且仅当L‘有解时L有解

总的思路：假设L’有解将每个实例归约成L，此时L也有解；但是L‘是NPC问题，所以L也是NPC问题无解

问题求解：

1、假如给定一个集合S的划分S1和S2，那么分别对S1和S2的元素求和并比较，因此可以在多项式时间验证这个集合划分的正确性。同时如果并没有给这个S的划分，那么S1和S2的划分个数都有2^n个，所以寻找S1、S2算法的时间复杂度肯定不是多项式时间的

2、选择子集和求和问题作为已知NPC问题

3、假如存在一个集合U，已知其中的元素xi、xj,....,等之和为t，t为提前已经设定好的量。那么我们取这个集合U，令U’=U 并 {U-2t}，此时U‘中就存在几个可拆分的集合对象。这时，可以确定新集合U‘中的集合元素可以拆分为两个U-t。因为只要将集合{U-2t}中的t挪动到U中即可。而t已知为xi、xj,....,等元素的和，所以是可以挪动的。证毕！

4、归约算法仅仅涉及有限集合的并以及拆操作，所以整体的归约时间必然是多项式的

5、当新集合U'中元素可以拆分为两个相等的元素时，我们可以令这两个相等元素为U-t。那么重新拆分组合这两个元素，可以得到集合U，并且其中有元素求和为t。也就是说此时集合U的子集和问题必然存在解。

第三十五章

35.1-4

问题描述：

给出一个有效的贪心算法，使其能够在线性时间内找出一棵树的最优顶点覆盖。

问题分析：

已知顶点覆盖算法是NPC难度的，题目要我们找可行的线性时间算法，本质就是让我们去使用近似算法找最优顶点覆盖

所谓贪心算法实现就是算法导论中的方法

问题求解：

APPROX-VERTEX-COVER(G)
    C=Ø
    E'=G.E
    while(E'!=Ø)
        let (u,v) be a arbitrary edge of E'
        C=C ∪ (u,v)
        remove from E' every edge incident on either u or v
    return C

该算法是一个多项式时间的2近似算法

问题深究：

下面给出证明，说明为什么这个算法是多项式时间的2近似算法：

证：

定义C：为算法实际找出的顶点覆盖；C*：为图G最优顶点覆盖；A为算法找出的边的集合

由于每找到一个边（u，v）则把与u或v连接的边删除，所以A集合中没有两个边存在共同的顶点，即所有边都是不相连的。因此，想要覆盖这些边至少需要边个数的顶点，即有：

$\left | C^* \right |>=\left | A \right |$

由由于A的边并不相交，所以并不存在一个点连接两个边的情况，每个边的两个端点都是不相同的。因此有：

$\left | C \right |=2\left | A \right |$

结合上面两个式子，我们可以得到：

即该算法是多项式时间上的2近似算法

35.2-3

问题描述：

考虑下述用于构造近似旅行商旅行路线（代价函数满足三角不等式）的最近点启发式：从只包含任意选择的某一顶点的平凡回路开始，在每一步中，找出一个顶点 u, 它不在回路中，但到回路上任何顶点之间的距离最短。假设回路上距离u最近的顶点为 v, 则将u插入到v之后，从而对回路加以扩展。重复这一过程，直到所有顶点都在回路上为止。证明：这一启发式方法返回的旅行路线总代价不超过最优旅行路线代价的2倍。

问题分析：