案例-解决最大割问题

最大割问题 (Max-Cut)

最大割问题是图论中的经典优化问题，目标是将图中的节点分成两个集合，使得横跨两个集合的边数最多。

1. 问题描述

给定一个图

G = (V, E)

，我们需要将所有节点

V

分成两个互不相交的集合

S_{1}

和

S_{2}

。如果一条边的两个端点分别属于不同的集合，则称这条边被“割”开了。我们的目标是最大化被割开的边的总数。

2. 建模步骤

定义变量：为每个节点

i

分配一个自旋变量

σ_{i}

。

若节点属于

S_{1}

，则

σ_{i} = + 1

。

若节点属于

S_{2}

，则

σ_{i} = - 1

。

构建能量函数：

当边

(i, j)

的两个端点在不同集合时，

σ_{i} \cdot σ_{j} = - 1

（贡献割边）。

当两个端点在同一集合时，

σ_{i} \cdot σ_{j} = 1

。

目标是最小化

H = \sum_{(i, j) \in E} σ_{i} σ_{j}

。最小化这个能量函数等价于让尽可能多的项变为 -1，即最大化割边的数量。

提取系数：

如果节点

i

和

j

之间有边，则设置耦合系数

J_{ij} = 1

。

如果没有边，则

J_{ij} = 0

。

外部磁场系数

h_{i} = 0

。

3. 云平台输入

将上述

J_{ij}

组成的矩阵和全为 0 的

h_{i}

向量上传至伊辛云平台，选择 Spin 模型求解即可。

修改于 2025-12-22 06:40:29

SDK使用教程

案例-特征选择