0

我正在学习算法：设计与分析 II课程，其中一个问题是：

假设 P ≠ NP。考虑具有非负边长的无向图。以下哪个问题可以在多项式时间内解决？

提示：哈密顿路径问题是：给定一个具有 n 个顶点的无向图，判断是否存在一条（无环）路径具有 n-1 条边，并且恰好访问每个顶点一次。您可以使用哈密顿路径问题是 NP 完全的事实。从哈密顿路径问题到以下 4 个问题中的 3 个问题相对简单。

  • 对于给定的源 s 和目标 t，计算恰好具有 n - 1 条边的最短 st 路径的长度（或 +∞，如果不存在这样的路径）。路径允许包含循环。
  • 在图的所有生成树中，计算具有最小可能叶数的一棵。
  • 在图的所有生成树中，计算具有最小可能最大程度的一棵。（回想一下顶点的度数是入射边的数量。）
  • 对于给定的源 s 和目标 t，计算恰好具有 n - 1 条边的最短 st 路径的长度（或 +∞，如果不存在这样的路径）。路径不允许包含循环。

请注意，哈密顿路径是图的生成树，并且只有两个叶节点，并且恰好具有两个叶节点的图的任何生成树都必须是哈密顿路径。这意味着确定图中是否存在哈密顿路径的 NP 完全问题可以通过找到图的最小叶生成树来解决：当且仅当最小叶生成树正好有两个叶时，路径才存在. 因此，问题 2 是 NP 完全的。

问题 3 是 NP-Hard；这是证明这一点的论文。

这意味着，在 1 和 4 之间，一个是 NP-Complete，另一个是 P。似乎问题 4 可以简单地简化为哈密顿路径问题，但我无法理解循环如何使其可解决？还是相反？

4

1 回答 1

0

对于第一个，您可以使用 Dijkstra 获得最短的偶数和奇数距离。为此，对于每个顶点，您需要存储的不是一个最小数量，而是其中两个。一个是奇数路径的最小权重，另一个是偶数路径的最小权重。有了这两个长度后，如果允许循环，您可以轻松地将路径长度增加偶数个边。因此，第一个问题来自 P。逐步算法将是：

  1. 找到最短的偶数和奇数路径。
  2. 通过添加长度为 2 的循环所需的次数来增加n-1具有相同奇偶校验的这些路径之一的长度。n-1
于 2019-01-08T08:38:09.513 回答