跳转到内容
本文内容

最大割问题 ​

最大割问题是NP完备问题。给定一张图,求一种分割方法将所有顶点分割成两部分,同时使得被切断的边的数量最大或边的总权重最大。

以无向无权图为例,在图G(V,E)中,V为图的顶点集合,E为图的边集,w为图的邻接矩阵。对于i,j∈V,wij表示顶点i到顶点j是否有边,有连边关系则取1,无连边关系则取0。以决策变量si表示顶点i的分类,其可能的取值为{1,−1},分别表示将顶点i分为A类或B类。

则在给定的无向图中,将所有顶点分割成两群的分割方法所对应割的边的个数为Z,模型表示为:

maxZ=12(∑i<ji∈V∑j∈Vwij−∑i<ji∈V∑j∈Vwijsisj)

以一个四顶点实例说明,如下图所示,通过观察可以发现将1、2分为A类,3、4分为B类的“割”法将得到问题的最优解Z=4。

描述

通过连边关系可知,邻接矩阵为:

描述

∑i<j,i∈V∑j∈Vwij=w12+w13+w14+w23+w24+w34∑i<j,i∈V∑j∈Vwijsisj=w12s1s2+w13s1s3+w14s1s4+w23s2s3+w24s2s4+w34s3s4

当顶点1、2为一组,顶点3、4为另一组时,s1=s2=1,s3=s4=−1.则上式变为:

∑i<j,i∈V∑j∈Vwijsisj=w12−w13−w14−w23−w24+w34

此时目标函数为:

maxZ=∑i<j,i∈V∑j∈Vwij−∑i<j,i∈V∑j∈Vwijsisj2=w13+w14+w23+w24=4

最大割数量为4,符合前文通过观察得到的答案。

注意到,wij为输入的常量,并不影响模型的计算,所以上式可以简化为:

minH=∑i<j,i∈V∑j∈Vwijsisj

其中, H表示哈密尔顿量,w为输入的邻接矩阵,决策变量si表示顶点i的分类,上述式子就是一个最大割问题的Ising模型。

建模代码 ​

输入矩阵 ​

矩阵表示N个节点的连接关系,如果两个点之间有边,就用1表示,没有边,就用0表示。

python
import numpy as np
import kaiwu as kw

# Import the plotting library
import matplotlib.pyplot as plt

# invert input graph matrix
matrix = -np.array([
                [0, 1, 0, 1, 1, 0, 0, 1, 1, 0],
                [1, 0, 1, 0, 0, 1, 1, 1, 0, 0],
                [0, 1, 0, 1, 1, 0, 0, 0, 1, 0],
                [1, 0, 1, 0, 0, 1, 1, 0 ,1, 0],
                [1, 0, 1, 0, 0, 1, 0, 1, 0, 1],
                [0, 1, 0, 1, 1, 0, 0, 0, 1, 1],
                [0, 1, 0, 1, 0, 0, 0, 0, 0, 1],
                [1, 1, 0, 0, 1, 0, 0, 0, 1, 0],
                [1, 0, 1, 1, 0, 1, 0, 1, 0, 1],
                [0, 0, 0, 0, 1, 1, 1, 0, 1, 0]])

使用经典求解器进行计算 ​

由于Maxcut问题矩阵就是一个Ising矩阵,所以可以调用SDK提供Optimizer直接求解,本例中使用SimulatedAnnealingOptimizer。

python
np.random.seed(0)
worker = kw.classical.SimulatedAnnealingOptimizer(initial_temperature=100,
                                                  alpha=0.99,
                                                  cutoff_temperature=0.001,
                                                  iterations_per_t=10,
                                                  size_limit=100)
output = worker.solve(matrix)

输出结果 ​

从输出的多个解中取最好的解,通过最好解和原来的矩阵算出最大割的值并输出。

python
best = output[0]
max_cut = (np.sum(-matrix)-np.dot(-matrix,best).dot(best))/4
print("The obtained max cut is " + str(max_cut) + ".")