代码生成 python实现最大割算法的随机版和去随机版

最割问题是一种经典的组合优化问题，其目标是将无向图的顶点划分成两个集合，使得两个集合中的顶点之间的边数最小。

以下是Python实现最大割算法的随机版和去随机版的代码：

随机版：

import random

def max_cut_random(graph):
    n = len(graph)
    x = [random.choice([0, 1]) for i in range(n)]
    while True:
        y = [1 - i for i in x]
        cut = 0
        for i in range(n):
            for j in range(i+1, n):
                if graph[i][j] == 1 and x[i] != x[j]:
                    cut += 1
        for i in range(n):
            diff = cut
            for j in range(n):
                if graph[i][j] == 1:
                    if x[i] != x[j]:
                        diff -= 1
                    else:
                        diff += 1
            if diff > 0:
                x[i] = 1 - x[i]
        if x == y:
            break
    return cut

# 示例代码
graph = [[0, 1, 1, 0], [1, 0, 1, 1], [1, 1, 0, 1], [0, 1, 1, 0]]
cut = max_cut_random(graph)
print("最大割值为：", cut)

去随机版：

def max_cut(graph):
    n = len(graph)
    x = [0 for i in range(n)]
    for i in range(n):
        if sum(graph[i]) >= n / 2:
            x[i] = 1
    while True:
        cut = 0
        for i in range(n):
            for j in range(i+1, n):
                if graph[i][j] == 1 and x[i] != x[j]:
                    cut += 1
        for i in range(n):
            diff = cut
            for j in range(n):
                if graph[i][j] == 1:
                    if x[i] != x[j]:
                        diff -= 1
                    else:
                        diff += 1
            if diff > 0:
                x[i] = 1 - x[i]
        if diff == 0:
            break
    return cut

# 示例代码
graph = [[0, 1, 1, 0], [1, 0, 1, 1], [1, 1, 0, 1], [0, 1, 1, 0]]
cut = max_cut(graph)
print("最大割值为：", cut)

其中，`graph`是输入的无向图的邻接矩阵，返回值为最大割值。