查找所需的最小数量 'central points'
Finding minimum number of required 'central points'
我有一组 'n' 个节点。函数 returns 一种两个节点之间的距离，使得 dist(a,c) 可能不是 dist(a,b)+dist(b,c)。基于阈值，我通过边连接某些节点。我希望 select 节点的最小数量，使得这些节点的集合及其直接边缘连接的邻居组成整个 n 节点集合。是否可能有最佳解决方案？在纸上涂鸦让我觉得中心性可以提供帮助（程度，亲密度？）。我想到了聚类，但此图中的节点没有属性。我如何 select 最小节点数？提前致谢
I wish to select the minimum number of nodes such that the set of
these nodes and their immediate edge connected neighbours comprise the
whole set of n nodes
由于我们可以轻松地为所有以 (u,v) 为边的节点定义 d(u,v) = 1，因此我们可以轻松地减少顶点覆盖到您的问题。
由于 Dominating-Set 是 NP-Complete，并且上面是多项式约简，所以是你的问题。
tl;dr: 你的问题是 NP-Complete 并且没有已知的有效解决方案来最优地解决它。
我有一组 'n' 个节点。函数 returns 一种两个节点之间的距离，使得 dist(a,c) 可能不是 dist(a,b)+dist(b,c)。基于阈值，我通过边连接某些节点。我希望 select 节点的最小数量，使得这些节点的集合及其直接边缘连接的邻居组成整个 n 节点集合。是否可能有最佳解决方案？在纸上涂鸦让我觉得中心性可以提供帮助（程度，亲密度？）。我想到了聚类，但此图中的节点没有属性。我如何 select 最小节点数？提前致谢
I wish to select the minimum number of nodes such that the set of these nodes and their immediate edge connected neighbours comprise the whole set of n nodes
由于我们可以轻松地为所有以 (u,v) 为边的节点定义 d(u,v) = 1，因此我们可以轻松地减少顶点覆盖到您的问题。
由于 Dominating-Set 是 NP-Complete，并且上面是多项式约简，所以是你的问题。
tl;dr: 你的问题是 NP-Complete 并且没有已知的有效解决方案来最优地解决它。