给定n个电阻与目标阻值，如何找到最优串并联组合的实现方案

问题核心原因 #

原有算法是按排列顺序逐个把电阻和当前总等效电阻串/并联，本质是只允许「线性增量」的组合方式，无法覆盖多个子电路分别组合后再拼接的场景，属于逻辑框架缺陷，而非遍历不充分导致的问题。

优化思路：分治+子集枚举 #

正确的思路是对任意电阻集合，拆分出所有非空真子集，分别计算子集所有可能的等效电阻值，再把两个子集的等效电阻两两做串/并联，即可覆盖所有子电路组合的场景：

• 边界条件：如果集合只有1个电阻，等效电阻只有它本身，组合描述就是电阻值本身
• 对任意大小≥2的集合，枚举所有可能的二分拆分方式（规定子集包含第一个元素可减少重复计算）
• 每个拆分的左右子集递归得到所有可能的（等效阻值、组合描述、使用电阻数）三元组
• 左右子集的三元组两两组合，计算串联、并联后的结果，加入当前集合的结果列表
• 最后对所有可能的结果（支持选任意数量电阻），按和目标阻值的误差从小到大、相同误差下使用电阻数从小到大排序，取最优解

优化后代码实现 #

import itertools
from collections import defaultdict

# 缓存已经计算过的电阻组合的所有可能结果，避免重复计算
calc_cache = {}

def get_all_equivalent(resistor_tuple):
    # 用排序后的tuple做key，相同电阻不管顺序都复用缓存
    sorted_key = tuple(sorted(resistor_tuple))
    if sorted_key in calc_cache:
        return calc_cache[sorted_key]
    n = len(sorted_key)
    # 边界情况：只有一个电阻
    if n == 1:
        res = [(sorted_key[0], f"{sorted_key[0]}Ω", 1)]
        calc_cache[sorted_key] = res
        return res
    # 所有可能的结果存储，用set去重
    all_res = set()
    # 枚举所有非空真子集，为了避免重复，规定子集必须包含第一个元素
    for mask in range(1, (1 << n) - 1):
        if not (mask & 1):
            continue
        # 拆分出左右两个子集
        left_resistors = tuple(sorted_key[i] for i in range(n) if mask & (1 << i))
        right_resistors = tuple(sorted_key[i] for i in range(n) if not (mask & (1 << i)))
        # 递归获取两个子集的所有等效结果
        left_options = get_all_equivalent(left_resistors)
        right_options = get_all_equivalent(right_resistors)
        # 两两组合计算串并联
        for (r_left, desc_left, cnt_left) in left_options:
            for (r_right, desc_right, cnt_right) in right_options:
                # 串联
                r_series = r_left + r_right
                desc_series = f"({desc_left} 串联 {desc_right})"
                cnt_series = cnt_left + cnt_right
                all_res.add((round(r_series, 8), desc_series, cnt_series))
                # 并联
                if r_left != 0 and r_right != 0:
                    r_parallel = 1 / (1/r_left + 1/r_right)
                    desc_parallel = f"({desc_left} 并联 {desc_right})"
                    cnt_parallel = cnt_left + cnt_right
                    all_res.add((round(r_parallel, 8), desc_parallel, cnt_parallel))
    # 转成列表存缓存
    res_list = list(all_res)
    calc_cache[sorted_key] = res_list
    return res_list

def optimalResistance(resistor_list, target_R):
    # 清空缓存
    calc_cache.clear()
    all_possible = []
    n = len(resistor_list)
    # 枚举所有非空电阻子集，支持选任意数量电阻
    for k in range(1, n+1):
        for subset in itertools.combinations(resistor_list, k):
            all_possible.extend(get_all_equivalent(subset))
    # 排序：先按误差从小到大，再按使用电阻数从小到大
    all_possible.sort(key=lambda x: (abs(x[0] - target_R), x[2]))
    best_r, best_desc, best_cnt = all_possible[0]
    return f"最接近的等效电阻是: {best_r}Ω，使用{best_cnt}个电阻，连接方式为：{best_desc}"

# 测试案例1：原代码的失败案例
R1 = 4
R2 = 4
R3 = 9
R4 = 1
target = 1/(1/(R1+R2) + 1/(R3+R4))
print("目标阻值：", target)
print(optimalResistance([R1,R2,R3,R4], target))

# 测试案例2：8.24Ω目标案例
print("\n第二个测试案例：")
R1=4;R2=12;R3=10;R4=7
target=8.24
print("目标阻值：", target)
print(optimalResistance([R1,R2,R3,R4], target))

运行效果 #

第二个测试案例会正确输出等效阻值8.24242424Ω的最优解，连接方式为((4Ω 串联 12Ω) 并联 (7Ω 串联 10Ω))，完全符合预期的最优结果。

效率说明 #

• 增加缓存后相同电阻组合不会重复计算，比原全排列方案效率高很多，6个以内电阻可秒出结果
• 如果电阻数量更多，可针对相同阻值的电阻做进一步去重，降低计算量

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