如何找到将某些顶点相互连接的最小顶点

Question

我想找到将某些顶点相互连接的最小顶点。例如，假设边列表为

connections = [(2,0),(0,5),(2,3),(3,4),(0,4),(4,1),(5,1)]

，图形如下所示：

然后我想知道如何将顶点

2, 4, 5

与最少数量的顶点连接在一起。在本例中是顶点

0

。

因此输出应该是

[0,2,4,5]

，这意味着需要4个顶点。我尝试用蛮力实现该算法，因为会有更复杂的情况，但我不确定如何从所有可能的组合中找到最佳答案。

from itertools import combinations

verticis = [0,1,2,3,4,5]
connections = [(2,0),(0,5),(2,3),(3,4),(0,4),(4,1),(5,1)]
key = [2,4,5]

i, j = 2, len(verticis)
res1 = [com for sub in range(j) for com in combinations(verticis, sub + 1)] 
res2 = [com for sub in range(i - 1) for com in combinations(verticis, sub + 1)] 
res = list(set(res1) - set(res2)) 

Answer 1

这个问题实际上是一个著名的 NP 难组合优化问题：Steiner 树问题。

给定一个具有非负边权重和顶点子集（通常称为终端）的无向图，图中的斯坦纳树问题需要一棵包含所有终端（但可能包括附加顶点）并最小化的最小权重树其边缘的总重量。

换句话说：

S 的最小 Steiner 生成树（或简称 Steiner 树）是总长度最小的树，其节点是给定集合 S 的超集。那些不是 S 的点的节点通常称为 Steiner 点（源）。

由于问题的内在难度，获得最小斯坦纳树的精确方法都是指数最坏情况时间复杂度（除非 P=NP）。您可以在文献中找到该问题的各种精确解决方法。然而，一种简单而精确的方法是将现有的问题实例建模为约束优化问题 (COP)，并使用 COP 求解工具（例如 MiniZinc：

）来解决它

include "steiner.mzn";
var int : weight;
array[1..6] of var bool: vertex;
array[1..7] of var bool: edge;

constraint vertex[3] = true;        % v2 is a terminal
constraint vertex[5] = true;        % v4 is a terminal
constraint vertex[6] = true;        % v5 is a terminal
constraint steiner(6,7,[1,1,1,2,2,4,4],[3,5,6,5,6,3,5],[1,1,1,1,1,1,1],vertex,edge,weight);

solve minimize weight;

在此代码中，布尔决策变量

vertex[i]

表示斯坦纳树是否包含第（i-1）个顶点。在您描述的实例中，我们有三个终端。因此，我们需要将对应的决策变量设置为

true

。使用最少数量的顶点连接这三个节点的目标相当于找到最小斯坦纳树，前提是边权重均为 1。因此，在全局约束

steiner

中，我们将所有边权重设置为 1。给定实例的最佳解决方案如下：

----------
weight = 3;
vertex = array1d(1..6, [true, false, true, false, true, true]);
edge = array1d(1..7, [true, true, true, false, false, false, false]);
----------

可以看出，只需将顶点0作为斯坦纳点（返回解中

vertex[1]

为

true

），对应的斯坦纳树有3条边（即{0,2}，{ 0,4} 和 {0,5}）。有关全局约束

steiner

的更多信息，请参阅 此链接。