如何用Python迭代法求解可变规模的整数解线性方程组

需求说明 #

• 处理字符串格式的线性方程组，求解所有Xi/Yj类型变量的整数解（正负均可）
• 变量和方程数量不固定，程序需自适应适配
• 强制要求：等号右侧为0的方程，必须分解为绝对值相等、符号相反的两个变量值
• 必须使用迭代法实现求解

示例方程组与初始代码 #

给定的方程组及变量提取基础代码如下：

from sympy import symbols, Eq, solve
import re

system_equations = [
'5 = X0 + Y0', 
'6 = X0 + Y1', 
'5 = X0 + Y3', 
'5 = X0 + Y4', 
'3 = X1 + Y2', 
'0 = X2 + Y2', 
'1 = X2 + Y4'
]

# 提取所有变量名
variable_names = list(set(re.findall(r'[XY]\d+', ' '.join(system_equations))))

# 创建符号变量
variables = symbols(' '.join(variable_names))

注：示例包含8个未知量与7个线性方程

示例可行解 #

一组满足所有要求的整数解示例：

# 可行解示例
values_of_int_decomposition_variables = [['X0', 2], ['X1', 1], ['X2', -2], ['Y0', 3], ['Y1', 4], ['Y2', 2], ['Y3', 3], ['Y4', 3]]

解的有效性验证 #

代入方程组验证所有约束：

ij_number_to_decompose = Xi + Yj

5 = 2 + 3
6 = 2 + 4
5 = 2 + 3
5 = 2 + 3
3 = 1 + 2
0 = (-2) + 2  # 满足0方程的符号相反、绝对值相等要求
1 = -2 + 3

迭代法实现方案 #

核心思路 #

1. 解析所有方程，区分普通约束与0值特殊约束
2. 对0值方程直接绑定变量的相反数关系
3. 选择一个自由变量（因方程数少于变量数，存在自由度），在整数范围内迭代取值
4. 代入约束推导所有变量值，验证是否满足所有方程，找到第一个有效解

代码实现 #

import re

def solve_system_iteratively(equations):
    # 解析方程，提取约束和0值变量对
    constraints = []
    zero_pairs = {}  # 存储0方程的变量映射：{变量: 相反数变量}
    all_vars = set()

    for eq in equations:
        left_str, right_expr = eq.strip().split('=')
        target_val = int(left_str.strip())
        var1, var2 = [v.strip() for v in right_expr.split('+')]
        all_vars.update({var1, var2})

        if target_val == 0:
            zero_pairs[var1] = var2
            zero_pairs[var2] = var1
        else:
            constraints.append((target_val, var1, var2))

    # 确定自由变量（优先选未被0约束的变量）
    free_var = None
    for var in all_vars:
        if var not in zero_pairs:
            free_var = var
            break
    if not free_var:
        free_var = next(iter(all_vars))

    # 迭代尝试整数取值（范围可按需调整）
    for val in range(-100, 101):
        var_values = {free_var: val}
        # 填充0约束的变量值
        for var in zero_pairs:
            if zero_pairs[var] in var_values and var not in var_values:
                var_values[var] = -var_values[zero_pairs[var]]
        
        # 根据普通约束推导其他变量
        valid = True
        for target, a, b in constraints:
            if a in var_values and b in var_values:
                if var_values[a] + var_values[b] != target:
                    valid = False
                    break
            elif a in var_values:
                var_values[b] = target - var_values[a]
            elif b in var_values:
                var_values[a] = target - var_values[b]
        
        # 验证所有变量已赋值且满足所有方程
        if len(var_values) != len(all_vars):
            continue
        # 二次验证所有方程
        for eq in equations:
            left_str, right_expr = eq.strip().split('=')
            target = int(left_str.strip())
            v1, v2 = [v.strip() for v in right_expr.split('+')]
            if var_values[v1] + var_values[v2] != target:
                valid = False
                break
        if valid:
            # 转换为要求的输出格式，按变量名排序
            return sorted([[var, var_values[var]] for var in var_values], key=lambda x: x[0])
    
    return None

# 测试示例方程组
system_equations = [
'5 = X0 + Y0', 
'6 = X0 + Y1', 
'5 = X0 + Y3', 
'5 = X0 + Y4', 
'3 = X1 + Y2', 
'0 = X2 + Y2', 
'1 = X2 + Y4'
]

solution = solve_system_iteratively(system_equations)
if solution:
    print("找到的整数解：")
    print(solution)
else:
    print("在设定的迭代范围内未找到有效解")

代码说明 #

• 解析阶段自动识别0值方程，直接建立变量间的相反数约束
• 自由变量选择逻辑优先避开0约束变量，减少迭代冲突
• 迭代范围默认设为-100到100，可根据实际需求扩大或缩小
• 双重验证机制确保解的正确性：先推导再全局验证所有方程
• 输出结果按变量名排序，与示例格式一致

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