Wolfram 语言

最大切割问题

最大切割问题确定图的顶点 的一个子集 ,从 到其补集 的边的权重 的和被最大化。

这个例子演示了如何使用 SemidefiniteOptimization 来设置一个函数,能有效求解 NP 完备的最大切割问题的松弛问题。

假定 个顶点,可以用索引描述 描述。设 为一个向量,其分量为 ,只有当 非零 (=2)。因此可通过最大化 找到最大切割,其中 。可将目标函数改写为:

... 其中 是图的拉普拉斯矩阵, 是加权邻接矩阵。

对于简单的问题,可以精确求解最大割问题,但对于较大的图是不切实际的,因为通常问题具有 NP 完备复杂性。

该问题要最小化 ,其中 是对称 1 阶半制定矩阵,对于每个 ,等价于 ,其中 是第 个对角元素为 1、其他位置上的元素为 0 的矩阵。

为了得到实用解,求解 1 阶条件被排除掉的松弛问题,只要求

对偶形式的半定问题如下所示:

SemidefiniteOptimization[c, {a0, a1, , ak}, {"DualMaximizer" }] 求解。

对于松弛问题的解 ,通过随机舍入构建切割:分解 ,令 为具有单位范数的均匀分布的随机向量,令 。为了演示,我们定义了一个函数来显示松弛条件下的值、舍入值和图,用红色显示 中的顶点。

用以上所示步骤求近似切割,并与精确结果相比较。

求网格图的最大切割。

求随机图的最大切割。

比较 Peterson 图的松弛算法和精确算法的用时。

相关范例

de en es fr ja ko pt-br