algorithm - 探索图中的每个节点

标签 algorithm graph

我有一个连通图,它有 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/

相关文章:

java - 对具有负整数的数字字符串进行排序

c - long int 数组导致错误 : subscripted value is neither array nor pointer nor vector

javascript - C3.js x 轴显示所有其他类别

C++ Intel TBB和Microsoft PPL,如何在并行循环中使用next_permutation?

c - 找到不同数字组合的数量,使其总和等于总和

python - 如何在 SPOJ 问题硬币中使用 Python 输入?

matlab - 如何绘制矩阵中非零元素的坐标?

python - 从庞大的邻接列表中提取边缘列表的最有效方法是什么?

python - Networkx 图形绘制节点权重

algorithm - 解决日志空间中无向图中的循环?