如何 select 包含任意 k 个节点的图的最小子图

Question

我正在尝试解决以下问题。它就像 k-minimum-spanning-tree 和 steiner tree 问题，但它是有图的。

• 我们有一个非负无向加权图G = (V, E)。
• 对于每对顶点v1和v2，都存在一条边e12。换句话说，每个顶点都连接到每个其他顶点。
• 我们将创建包含 k 个顶点的顶点 U 的子集。
• 我们的目标是 select U 中的 n 个顶点，使得 U 中每个顶点到其他所有顶点的边之和最小。换句话说，我们想要 select U 中的顶点，以便从 U 中的节点向外的所有边的总和最小化。
• 1 < n < 顶点数

我是否正确认为 k-MST 或 Steiner 树近似解都不起作用？如果是这样，这个问题叫什么？解决方案是什么？我可以使用启发式或近似法来解决这个问题，不需要正式证明。

Answer 1

我不知道是否有更快的算法，但简单的算法（如果我的解释正确的话）是：

• 构建一个 array/map，其中保存从 vi 到任何其他顶点的每条边的权重总和。如果您考虑图形的矩阵表示，其中每个 row/column 是一个顶点，每个单元格是边上的权重。该数组将是每一行的总和。
• 生成所有k大小的顶点子集，保留和最小的那个。

如果有 n 个顶点，这是探索 n!/(k! (n-k)!) 这样的组合。

Answer 2

K-MST 或 Steiner 树不起作用的说法是正确的 - 它们仅生成树，而您需要具有特殊属性的图形，例如如果我理解你的问题，U 内顶点之间的成本为 0，所有其他边的成本最低。

虽然 answer looks correct, I think that using something like metaheuristic, e.g. simulated annealing, or constraint satisfaction 方法会更好。

对于元启发式：

1. 计算每个顶点的边成本
2. 贪婪地选择 k 个顶点 - 它形成了你的 初始解决方案
3. 如果是SA，开始修改初始解including/excluding个新的顶点（也许有更好的方法，你自己研究一下）
4. 给定足够的时间，它应该收敛到足够好的解决方案

对于约束满足：

1. Objective：给定图中的 select k 个顶点。对于每个顶点介绍 一个布尔变量，如果它是 1 - 顶点是 U 的一部分，否则它是 0。那么你的 objective 是：

sum (vertices==1) = k

2. 服从：k-顶点和其他顶点之间的边权重的最小总和。如果我是正确的，U 中边的成本是 0。我不知道如何正确地制定这样的约束，但它们应该相当简单。
3. 运行 有超时的求解器，比方说几个小时。

对于最后一种方法，约束满足，内存可能是个问题 - 您需要大量内存来表示完全连接的图和所有约束。不过，请检查 Minizinc, lpsolve and coin-or 个项目。