基于python-constraint API的最大团问题约束设置求助

你的建模逻辑存在根本性错误，导致约束冲突，所以返回空解。

原建模的问题 #

你设定的约束逻辑完全不符合最大团的定义：

• 邻居节点取值和为2 → 强制两个节点必须都取1（即都在团中）
• 非邻居节点取值和为-2 → 强制两个节点必须都取-1（即都不在团中）

但在你的图里，节点1和2是邻居（强制都为1），节点2和3是邻居（强制都为1），可节点1和3不是邻居（强制都为-1）——这直接产生矛盾：节点1既要为1又要为-1，节点3同理，自然没有可行解。

这种建模错误地要求所有邻居必须全部塞进团里，同时所有非邻居必须全部排除在团外，这只有在团是完全子图且和其他所有节点都没边时才成立，完全偏离了最大团的核心要求。

正确的CSP建模方式 #

最大团的核心是：选一个节点子集，子集里任意两个节点都互为邻居（也就是子集是完全子图）。正确的建模应该是：

• 变量：每个节点对应一个变量，取值为1（在团中）或0（不在团中）
• 约束：对每一对非邻居节点，添加约束——它们不能同时取1（不能同时在团里）

所有满足约束的解都是合法团，之后只要在所有解里挑出节点数最多的，就是最大团。

修改后的代码 #

from constraint import * 
import networkx as nx

graph_2 = nx.Graph()
graph_2.add_edges_from([('1','2'), ('2','3'), ('2','4'), ('3', '4')])
nodes = list(graph_2.nodes)

problem = Problem()
# 变量定义：1=在团中，0=不在团中
problem.addVariables(nodes, [0, 1])

# 添加约束：非邻居节点不能同时在团中
# 遍历所有无序节点对，避免重复处理
all_node_pairs = [(u, v) for u in nodes for v in nodes if u < v]
for u, v in all_node_pairs:
    if not graph_2.has_edge(u, v):
        # 非邻居，不能同时为1
        problem.addConstraint(lambda a, b: a + b <= 1, (u, v))

# 获取所有合法团的解
all_solutions = problem.getSolutions()

# 筛选出最大团的解
max_clique_size = -1
max_clique_list = []
for sol in all_solutions:
    current_size = sum(sol.values())
    if current_size > max_clique_size:
        max_clique_size = current_size
        max_clique_list = [sol]
    elif current_size == max_clique_size:
        max_clique_list.append(sol)

# 输出结果
print(f"最大团大小：{max_clique_size}")
print("所有最大团：")
for clique in max_clique_list:
    # 提取团内的节点
    nodes_in_clique = [node for node, val in clique.items() if val == 1]
    print(nodes_in_clique)

代码说明 #

1. 变量取值：用0/1替代-1/1，更直观表示节点是否在团中
2. 约束逻辑：只对非邻居节点加约束，禁止它们同时出现在团里——这样团内的节点必然两两相邻（要是两个节点在团里却不是邻居，会直接违反约束）
3. 筛选最大团：python-constraint会返回所有合法解，我们统计每个解里1的数量，找出数量最多的就是最大团

可选：用1/-1变量的修正建模 #

要是你坚持要用1/-1表示（1=在团中，-1=不在），约束改成lambda a,b: not (a == 1 and b == 1)就行，核心逻辑不变，只是变量取值换一下。

内容的提问来源于stack exchange，提问作者C96