如何解决CSP问题中出现错误解及每次运行结果不同的问题？

问题背景 #

给定测试用例，代码生成的解不在提供的解集中，且每次运行结果不同。约束条件如下：

• Red：无约束
• Yellow：等于所有邻居值乘积的最右位
• Green：等于所有邻居值之和的最右位
• Blue：等于所有邻居值之和的最左位
• Violet：等于所有邻居值乘积的最左位

每个节点取值范围为{1,2,...,9}

用户代码 #

import random

def get_neighbors(node, arcs):
    # Returns the neighbors of the given node
    neighbors = []
    for arc in arcs:
        if arc[0] == node:
            neighbors.append(arc[1])
        elif arc[1] == node:
            neighbors.append(arc[0])
    return neighbors

def is_valid_coloring(node, value, node_values, arcs):
    # Checks if the current node coloring satisfies the constraints
    neighbors = get_neighbors(node, arcs)
    color = node_values[node]
    
    if color == 'Y':
        product = 1
        for neighbor in neighbors:
            product *= node_values[neighbor]
        return value == product % 10
        
    elif color == 'G':
        s = sum(node_values[neighbor] for neighbor in neighbors)
        return value == s % 10

    elif color == 'B':
        sum = 0
        for neighbor in neighbors:
            sum += node_values[neighbor]
        return value == sum % 10
        
    elif color == 'V':
        product = 1
        for neighbor in neighbors:
            product *= node_values[neighbor]
        return value == product % 10
    else:
        return True

def select_unassigned_variable(node_values, nodes, arcs):
    """
    Returns an unassigned node that has the most conflicts with its neighbors.
    """
    unassigned_nodes = [i for i, val in enumerate(node_values) if val == 0]
    max_conflicts = -1
    max_conflict_nodes = []
    for node in unassigned_nodes:
        neighbors = get_neighbors(node, arcs)
        node_conflicts = 0
        for neighbor in neighbors:
            if node_values[neighbor] != 0 and not is_valid_coloring(neighbor, node_values[neighbor], node_values, arcs):
                node_conflicts += 1
        if node_conflicts > max_conflicts:
            max_conflicts = node_conflicts
            max_conflict_nodes = [node]
        elif node_conflicts == max_conflicts:
            max_conflict_nodes.append(node)
    if len(max_conflict_nodes) == 0:
        return None
    return random.choice(max_conflict_nodes)


def get_conflicts(node_values, node, arcs, nodes):
    conflicts = 0
    node_idx = node
    for arc in arcs:
        if node_idx == arc[1]:
            if node_values[node_idx] == node_values[arc[0]]:
                conflicts += 1
        if node_idx == arc[0]:
            if node_values[node_idx] == node_values[arc[1]]:
                conflicts += 1
    return conflicts

def min_conflicts(node_values, nodes, arcs, max_steps):
    # Solves the csp using the mini conflicts algorithm
    for step in range(max_steps):
        unassigned_node = select_unassigned_variable(node_values, nodes, arcs)
        if unassigned_node is None:
            return node_values
        domain = [i for i in range(1, 10)]
        conflicts = [get_conflicts(node_values, unassigned_node, arcs, nodes)]
        min_conflicts = float('inf')
        min_conflict_values = []
        for value in domain:
            new_node_values = node_values.copy()
            new_node_values[unassigned_node] = value
            if is_valid_coloring(unassigned_node, value, new_node_values, arcs):
                num_conflicts = get_conflicts(new_node_values, unassigned_node, arcs, nodes)
                if num_conflicts < min_conflicts:
                    min_conflicts = num_conflicts
                    min_conflict_values = [value]
                elif num_conflicts == min_conflicts:
                    min_conflict_values.append(value)
        if min_conflict_values:
            new_value = random.choice(min_conflict_values)
            node_values[unassigned_node] = new_value
        else:
            # If there are no values that result in a minimum number of conflicts,
            # choose a random value from the domain
            new_value = random.choice(domain)
            node_values[unassigned_node] = new_value
        # If the new node values lead to an invalid coloring, try again with a different value
        if not is_valid_coloring(unassigned_node, new_value, node_values, arcs):
            node_values[unassigned_node] = random.choice([x for x in domain if x != new_value])
    return None


def solve_csp(nodes, arcs, max_steps):
    # Convert nodes to strings
    nodes = [str(node) for node in nodes]
    node_values = [0] * len(nodes)
    return min_conflicts(node_values, nodes, arcs, max_steps)



def main():
    # test Case 1

    nodes = 'YGVRB'
    arcs = [(0,1), (0,2), (1,2), (1,3), (1,4), (2,3), (2,4)]
    max_steps = 1000

    for _ in range(max_steps):
        sol = solve_csp(nodes, arcs, max_steps)
        if sol != []:
            break
            
    all_solutions = [[1, 1, 1, 7, 2],[2, 1, 2, 4, 3],[2, 6, 7, 6, 1],[2, 8, 9, 6, 1],
                    [3, 3, 1, 5, 4],[6, 2, 8, 7, 1],[6, 7, 8, 2, 1],[6, 9, 4, 8, 1]]

    if sol == []:
        print('No solution')
    else:
        if sol in all_solutions:
            print('Solution found:', sol)
        else:
            print('ERROR: False solution found:', sol)


if __name__ == '__main__':
    main()

运行输出 #

ERROR: False solution found: [7, 4, 2, 1, 8]

核心错误分析 #

1. 约束条件完全实现错误 #

is_valid_coloring函数中，Blue和Violet的约束逻辑完全写错：

• Blue要求是邻居值之和的最左位，但代码写成了和Green一样的sum % 10（取最右位）
• Violet要求是邻居值乘积的最左位，代码写成了和Yellow一样的product % 10（取最右位）
  这直接导致约束校验完全不符合题目要求，生成大量错误解。

2. 节点颜色获取逻辑错误 #

is_valid_coloring中color = node_values[node]是错误的：node_values存储的是节点的数值（1-9），而节点的颜色应该从输入的nodes参数中获取，正确写法是color = nodes[node]。当前逻辑把数值当成颜色判断，完全混乱了约束的判断依据。

3. 冲突计算逻辑错误 #

get_conflicts函数的逻辑是判断节点值和邻居值是否相等，这和题目中的约束冲突完全无关。正确的冲突数应该是统计当前节点赋值后，自身或邻居违反约束的次数。

4. 无效的重试逻辑 #

min_conflicts函数末尾的if not is_valid_coloring...逻辑会覆盖之前选择的最小冲突值，随机赋值，加剧结果的不确定性，且完全没必要。

修复后的关键代码片段 #

修正约束校验函数 #

def is_valid_coloring(node, value, node_values, nodes, arcs):
    neighbors = get_neighbors(node, arcs)
    color = nodes[node]  # 从nodes参数获取节点颜色
    
    if color == 'Y':
        product = 1
        for neighbor in neighbors:
            product *= node_values[neighbor]
        return value == product % 10
        
    elif color == 'G':
        s = sum(node_values[neighbor] for neighbor in neighbors)
        return value == s % 10

    elif color == 'B':
        sum_val = sum(node_values[neighbor] for neighbor in neighbors)
        # 取和的最左位
        sum_str = str(sum_val)
        leftmost = int(sum_str[0])
        return value == leftmost
        
    elif color == 'V':
        product = 1
        for neighbor in neighbors:
            product *= node_values[neighbor]
        # 取乘积的最左位
        product_str = str(product)
        leftmost = int(product_str[0])
        return value == leftmost
    else:  # Red
        return True

修正冲突计算函数 #

def get_conflicts(node_values, node, nodes, arcs):
    conflicts = 0
    # 检查当前节点自身是否违反约束
    if not is_valid_coloring(node, node_values[node], node_values, nodes, arcs):
        conflicts += 1
    # 检查邻居是否因当前节点赋值违反约束
    neighbors = get_neighbors(node, arcs)
    for neighbor in neighbors:
        if node_values[neighbor] != 0:
            if not is_valid_coloring(neighbor, node_values[neighbor], node_values, nodes, arcs):
                conflicts += 1
    return conflicts

其他修复点 #

• solve_csp函数中，nodes = [str(node) for node in nodes]改为nodes = list(nodes)，避免对输入字符串的无效转换
• 调用is_valid_coloring时需要传入nodes参数，比如在min_conflicts函数中：

  if is_valid_coloring(unassigned_node, value, new_node_values, nodes, arcs):
  

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