我有一个连通图,它有 N 个节点(从 1..N 开始编号)和 M 个双向边,由一对 (A,B) 组成。边缘未加权。
我有 K 个人从节点 1 开始,我想探索图中的每个节点。我需要一个单位的时间让一个人从一个节点旅行到它的邻居之一。
探索每个节点需要多长时间?我正在寻找一种有效的算法来计算最小遍历时间,但恐怕这是一个 NP 完全问题。 (虽然对边数和人数的限制很小)。
最佳答案
假设 K 为 1。那么最小化问题就简化为找到一条至少与每个节点接触一次的最小长度路径。
如果我们构造一个新的带权图G',它具有相同的节点,并且每两个节点之间有边,其权重是原始图中这些节点之间的最小距离,那么通过G中所有节点的最小长度路径是通过 G' 的最小长度哈密顿路径,旅行商问题,这是众所周知的 NP 完全问题。
所以对于至少一个 K 值,问题是 NP 完全问题。然而,对于较大的 K 值(例如,≥ N),我们可以在更短的时间内生成最小解,因为我们可以构造最小生成树并找到最远元素的距离。我怀疑对于较小的 K 值是否存在任何此类简化的解决方案,但我肯定会使用 MST 作为寻找合理解决方案的启发式方法。
关于algorithm - 探索图中的每个节点,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/13809107/