algorithm - 探索图中的每个节点

Question

我得到一个有 N 个节点（从 1..N 开始编号）和 M 个由一对（A，B）组成的双向边的连通图。边缘未加权。

我有 K 个人从节点 1 开始，我想探索图中的每个节点。我需要一个单位的时间让一个人从一个节点移动到它的一个邻居节点。

探索每个节点需要多长时间？我正在寻找一种有效的算法来计算最小遍历时间，但恐怕这是一个 NP 完全问题。（虽然对边数和人数的限制很小）。

Answer 1

假设 K 为 1。那么最小化问题简化为找到至少接触每个节点一次的最小长度路径。

如果我们构造一个新的加权图 G' 具有相同的节点并且每两个节点之间都有边，其权重是原始图中这些节点之间的最小距离，那么通过 G 中所有节点的最小长度路径是最小长度哈密顿量通过 G' 的路径，旅行商问题，这是众所周知的 NP 完全问题。

因此，对于至少一个 K 值，问题是 NP 完全的。然而，对于较大的 K 值（例如，≥ N），我们可以在更短的时间内产生最小解，因为我们可以构造最小生成树并找到最远元素的距离。我怀疑对于小 K 值是否有任何这种简化的解决方案，但我肯定会使用 MST 作为寻找合理解决方案的启发式方法。

Answer 2

对我来说，这似乎是 BFS。

您可以像查看树一样查看图形，其中起始节点是根。从这个角度来看，如果叶子的数量 <= 人数，答案将是最深的叶子（离根最远），答案是该叶子的深度。这是正确的，因为如果每个人访问每个叶子，那么在这样做的过程中，所有节点都会被访问。

但是，如果在每个人访问叶子后仍有未访问的节点，那么您需要在答案中添加最近的人访问未访问节点所需的最大时间（或距离）。

然而，这不是完整的答案。比这更复杂。

如果您有以下图像：

你不会想盲目地bfs。您可能希望按照从最浅到最深的顺序访问节点，因为这样您就不必再往下走。例如，0 -> 1 -> 0 -> 2 -> 0 -> 3 -> 0 -> 4 比 0 -> 4 -> 0 -> 3 -> 0 -> 2 -> 0 -> 更有效1. 这是正确的原因是因为你只能节省最后一次遍历的时间，所以你想让那个时间最长。

此外，也许让来自不同分支的人访问未访问的节点可能更有效（以帮助来自当前分支的人），因此如果需要时间，您希望将未访问的节点分配给周围分支的人该人到达 0 的时间小于当前分支中的人员访问该分支中所有节点所需的时间。如果可以将一个分支中的一个人分配到多个其他分支，则您希望选择未访问节点数最多的分支。这个“帮助”人也是为什么您要按顺序从最浅到最深的节点访问节点，而不是最后访问最深的节点。

所有这些听起来可能令人困惑，但关键是 BFS。这就是你的问题的解决方案。它基本上是经过修改的 BFS。

至于实现，您可以使用递归（或堆栈），它们通常用于树遍历。请注意，对于未访问节点 > 人数的情况，您不必模拟到剩余未访问节点的行进。