探索图中的每个节点

Question

我有一个具有N个节点（从1到N编号）和M个双向边（由(A,B)组成）的连接图。边没有权重。

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

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

- user1637030

Answer 1

假设 K 等于 1。那么最小化问题就变成了找到一条至少经过每个节点一次的最短路径。

如果我们构建一个新的加权图 G'，其节点与原始图相同，并在原始图中两个节点之间的边上添加权重，该权重为这些节点之间的最小距离，则通过 G 中所有节点的最小长度路径是 G' 中的最小长度哈密顿路径，即旅行商问题，这是众所周知的 NP 完全问题。

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

- rici

Answer 2

对我来说，这似乎是BFS。

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

但是，如果每个人访问叶子节点后仍有未访问的节点，则必须将最接近未访问节点的人访问该节点所需的最长时间（或距离）添加到答案中。

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

如果您有以下图像：

你不想盲目地进行广度优先搜索。你应该按照从最浅到最深的顺序访问节点，这样你就不必再次下降和上升路径。例如，0 -> 1 -> 0 -> 2 -> 0 -> 3 -> 0 -> 4比0 -> 4 -> 0 -> 3 -> 0 -> 2 -> 0 -> 1更有效率。之所以正确是因为你只能在最后一次遍历中节省时间，所以你希望使它成为最长的。

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

所有这些可能听起来很混乱，但关键在于BFS。这是你问题的解决方案。它基本上是修改后的BFS。

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

- timg