算法第4次作业

1 判断正误

对下面的每个描述，请判断其是正确或错误，或无法判断正误。对于你判为错误的描述，请说明它为什么是错的。

如果一个问题是 NP-Hard 问题，那么它一定是 NP 问题。

P 问题 ∩ NPC 问题 = 。

若 TSP 问题无法在多项式时间内被解决，则 3-SAT 问题也无法在多项式时间内被解决。

对某问题 X NP 而言，若可以证明规约式 3-SAT X ，则 X NPC 。

分析：
1. 错误。所有的 NP 问题都能约化到 NP-Hard 问题，但是 NP-Hard 问题不一定是一个 NP 问题。 NP 问题可在多项式时间内验证其解正确性，而 NP-Hard 问题则不一定。
2. 无法确定。P 问题指可以在多项式时间内解决的问题，而 NP 完全问题指可以在多项式时间内转化的 NP 问题。目前无法证明 P 问题与 NP 问题之间的关系，若 P = NP 那么 P = NPC，P 问题 ∩ NPC 问题 = 。
3. 正确。TSP（旅行商问题）和 3-SAT（三可满足性问题）都属于 NP 完全问题，按照 NP 完全问题的性质，如果一种 NP 完全问题无法在多项式时间内被解决，那么其余所有 NP 完全问题都无法在多项式时间内被解决。
4. 正确。3-SAT 属于 NP 完全问题，规约式 3-SAT X 表示可以将 3-SAT 的求解时间通过某种多项式时间算法转化为 X 的求解时间，进一步表示 X 问题也可在多项式时间内验证求解，则 X 是 NP 完全问题，即 X NPC 。

2 最小点集问题

给定一个包含个点的连通有向图，节点编号为，请设计算法找出最小的点集，使得：对所有点，均存在某点，满足图中存在一条从到的路径。如果这样的点集有多个，求出任意一个即可。此外，请描述算法的核心思想，给出算法伪代码并分析其对应的时间复杂度。

例如，给定一个包含个点的图，边集。可以发现，在该图中从出发可到达，从出发可到达。因此，选择点集即可满足条件。

分析：寻找最小点集，实际上是寻找最少的节点，使得从这些点出发，可以到达整个图任意一点（可以使用深度优先遍历搜寻从该店出发可以到达的点）。对于连通有向图，我们认为任意两点、之间最多有两条有向边、。对于双向边的两个节点，因为其可以互相到达，选择任意一点即可，因此可以将双向边中任意一向去除，以便后期遍历。入度越小的点，越不容易被其他点到达，因此按照入度由小到大的顺序进行点的选择和遍历。以选择的点为起点遍历后，每一个到达的点都应该加入已到达点集中，后续不再选择该点作为起点。
复杂度：，其中代表点的数量，代表边的数量。
伪代码：

3 最小环问题

给定一个包含个点的无向图，保证无重边无自环。边权使用矩阵 () 表示。

请设计一个高效的算法，计算图中最小环（最少包含三个节点）的最小边权和，请描述算法的核心思想，给出该算法伪代码并分析时间复杂度。

如图所示，节点组成的环权重为，是该图中的最小环，节点组成的环权重为，不能被称为该图中的最小环，节点不满足最少包含三个节点的条件，不能被称为该图中的最小环。

分析：对于最小环问题，可以使用动态规划和深度优先遍历算法，寻找最小的环权重。当只有三个点且构成一个环时，该环即是最小环；如果不构成一个环，则最小环权重就是。当新加入一个点和其相应边时，以该点为起点，遍历图寻找包含该点的最小环权重，具体取值同上。如果该最小权重小于加入该点前的权重，则以新权重作为当前最小环权重；反之则以加入该点前的权重作为当前最小环权重。当一次遍历已找到一个环，则可以判定该环就是包含当前路径的环中权重最小的，不用继续向下遍历。
复杂度：，其中代表点的数量，代表边的数量。最差情况下（完全图）会达到。
伪代码：

4 最短路经过次数问题

给定一张由个点组成的无向带权图，其所有边权都是正数，现指定一个起点和一个终点。对于图中的每一个节点，请求出从到的所有最短路径中，一共有几条最短路径经过了节点。请你设计一个高效算法求解本问题，描述算法的核心思想，并给出算法伪代码和对应的时间复杂度分析。

例如，在图中，包含个结点和条无向带权边，分别是：和之间的无向边，边权为；和之间的无向边，边权为；和之间的无向边，边权为；和之间的无向边，边权为；和之间的无向边，边权为。指定为结点，为结点，那么到之间的最短路有两条，分别为和，则结点被经过次，结点被经过次，对应问题的输出为。

分析：本题实际上是一个最短路径问题，考虑使用迪杰斯特拉算法。设置数组，代表从起点出发到达每个点最短路径的前驱节点（可能有多个，故使用二维数组）。设置数组，代表从起点出发到达每个点路径的最小权重。使用迪杰斯特拉算法，遍历整张图，标记从起点出发到达每个节点的路径最小值和前驱节点。设置代表从到的所有最短路径中，经过每个节点的次数。在使用迪杰斯特拉算法获得数组和数组后，从终点出发，填充数组，即是所求答案。
复杂度：，其中代表点的数量，代表边的数量。
伪代码：

5 扩张树问题

给定一个包含个点的带权无向树，保证边权均为整数，要求你在的基础上添加条带权无向边（完全图的边数为，树的边数为，故添加的边数为两者之差），得到图，并且满足：

是一张完全图。

是的唯一最小生成树。

的边权均为整数。

求添加的条无向边的边权之和的最小值。请你设计一个高效算法求解本问题，描述算法的核心思想，并给出算法伪代码及对应的时间复杂度分析。

例如，如图所示：有一棵如图所示的无向树，节点个数为。有条树边，分别是：和之间的无向边，边权为；和之间的无向边，边权为；和之间的无向边，边权为。

将作为本问题的输入，则对应的输出为，一种最优的方案如图所示，添加的条边为：和之间的无向边，边权为；和之间的无向边，边权为；和之间的无向边，边权为。所添加边的边权和为，可以证明，的唯一最小生成树是，且不存在一种另外的方案，使得边权和小于。

分析：对于该扩张树问题，可以使用动态规划的方法。首先对图进行解析，设置代表最小生成树中两节点之间的边权重；设置代表待添加的两节点边权重（两个权重矩阵是互补的，即中值不为的位置在中一定为，反之亦然）；设置代表各节点在最小生成树中的父节点（按照编号顺序，父节点编号一定小于子节点编号，使用 DFS 预存储该数组）数组设置代表存在个节点时新增的最小边权和。按照原编号顺序，每次新加入的节点一定与加入之前的树节点有一条边相连。初始只有两个点一条边，即。后续加入新节点，假设其与节点连接（实际上就是的父节点），则遍历剩余节点进行边的添加。以 , , 作为三个顶点构造三角形，如果之间存在一条最小生成树边，则应有；如果之间不存在一条最小生成树边，则应有。获得全部要添加的边后，即可得到转移方程。
时间复杂度：。
伪代码：

改进

分析：对于原算法，我们注意到添加的部分边可能数值相同，因此可以寻求一定的规律减少时间复杂度。对于一个四点构成的树，如果边的权重最大，则要保证题目要求（新添加边不能出现在最小生成树中），新添加的边的权重应该等于的权重加一。进一步可以推广为两个完全图相连接，这两个完全图中的点在生成树中有一条连接边，权重为，则新添加边的权重和为。因此对原生成树边按权重从小到大排序，逐个选取边并为边左右两侧的完全图（单点作为完全图）进行全连接。同时，为了高效的获得边左右两侧的完全图点数量，可以使用并查集存储完全图的点集。
时间复杂度：，时间开销主要在边的排序。
伪代码：