寻求房屋花卉着色最小成本问题的高效Python解决方案

问题描述 #

• 街道上有N栋房屋，每栋房屋的花园只能种植3种颜色（白色、黄色、红色）的花卉之一。
• 价格列表存储在文件中，每行对应一栋房屋，每列对应一种颜色，格式示例：

  9 2 7
  5 8 3
  4 7 8
  ...
  3 5 2
  

• 核心规则：相邻房屋不能种植相同颜色的花卉，目标是找到总成本最低的种植方案。
• 示例场景（4栋房屋）：

  houses\colors	w	y	r
  H1	5	6	7
  H2	3	7	9
  H3	6	7	3
  H4	1	8	4

  符合规则的最低成本方案为：6+3+3+1=13，对应颜色顺序为黄色、白色、红色、白色。

现有方案的缺陷 #

当前使用itertools.product生成所有可能的颜色组合，排除相邻同色的组合后计算总成本找最小值。但当N>20时，组合数呈指数级增长（3^20≈35亿），直接导致程序运行极慢甚至内存溢出，必须使用更高效的解法。

现有实现代码 #

import itertools
file = open('domy.txt')
ceny = file.readlines()

for x in range(len(ceny)):
    ceny[x] = ceny[x][0:-1]

n = len(ceny)
domy = [[0]*3]*n

for x in range(n):
    test = ceny[x].split(' ')

test = list(itertools.product([1, 2, 3], repeat=n))

i = 0
while i < len(test):
    t = 0
    while t < len(test[t])-1:
        if test[i][t] == test[i][t+1]:
            test.pop(i)
            i -= 1
            break
        t += 1
    i += 1

index = 0
i = 0
minimum = 0
while i < len(test):
    suma = 0
    if i == 0:
        j = 0
        for x in test[i]:
            if x == 1:
                suma += int(ceny[j][0])
            elif x == 2:
                suma += int(ceny[j][2])
            elif x == 3:
                suma += int(ceny[j][4])
            j += 1
        index = i
        minimum = suma
    else:
        j = 0
        for x in test[i]:
            if x == 1:
                suma += int(ceny[j][0])
            elif x == 2:
                suma += int(ceny[j][2])
            elif x == 3:
                suma += int(ceny[j][4])
            j += 1
        if suma < minimum:
            minimum = suma
            index = i
    i += 1

print(minimum)
print(test[index])

优化解决方案：动态规划 #

这个问题是典型的动态规划适用场景，时间复杂度为O(N)，空间复杂度可优化至O(1)，完全能处理N很大的情况。

核心思路 #

定义dp[i][c]表示第i栋房屋种植颜色c（c=0,1,2分别对应白、黄、红）时的累计最低成本：

• 初始状态：第一栋房屋的dp[0][c]直接等于对应颜色的价格。
• 状态转移：对于第i栋房屋的颜色c，累计成本等于当前颜色价格加上第i-1栋房屋非c颜色的最低成本，即：

  dp[i][c] = price[i][c] + min(dp[i-1][other_c] for other_c in 0,1,2 if other_c != c)
  

• 最终结果：取最后一栋房屋三个颜色对应的dp值中的最小值，即为总成本最低的方案。若需要追踪具体颜色选择，可额外记录每一步的最优前驱颜色。

优化后代码 #

def min_cost_houses(file_path):
    # 读取并解析价格数据，跳过空行
    with open(file_path, 'r') as f:
        prices = []
        for line in f:
            stripped_line = line.strip()
            if not stripped_line:
                continue
            cost = list(map(int, stripped_line.split()))
            prices.append(cost)
    
    n = len(prices)
    if n == 0:
        return 0, []
    
    # 初始化动态规划数组与前驱颜色记录数组
    dp = [[0]*3 for _ in range(n)]
    prev_color = [[-1]*3 for _ in range(n)]
    
    # 第一栋房屋的初始成本
    for c in range(3):
        dp[0][c] = prices[0][c]
    
    # 从第二栋房屋开始递推计算
    for i in range(1, n):
        for c in range(3):
            min_prev_cost = float('inf')
            min_prev_c = -1
            # 找到前一栋非当前颜色的最小成本及对应颜色
            for prev_c in range(3):
                if prev_c != c and dp[i-1][prev_c] < min_prev_cost:
                    min_prev_cost = dp[i-1][prev_c]
                    min_prev_c = prev_c
            dp[i][c] = prices[i][c] + min_prev_cost
            prev_color[i][c] = min_prev_c
    
    # 找到最后一栋房屋的最小成本对应的颜色
    final_min = min(dp[-1])
    final_c = dp[-1].index(final_min)
    
    # 回溯得到完整颜色方案（转换为题目要求的1,2,3标识）
    color_plan = []
    current_c = final_c
    for i in range(n-1, -1, -1):
        color_plan.append(current_c + 1)
        current_c = prev_color[i][current_c]
    color_plan = color_plan[::-1]
    
    return final_min, color_plan

# 调用示例
min_total, plan = min_cost_houses('domy.txt')
print(f"最低总成本: {min_total}")
print(f"颜色方案: {plan}")

效率说明 #

• 时间效率：仅需遍历N栋房屋，每栋房屋遍历3种颜色，每种颜色遍历另外2种颜色取最小值，总时间复杂度为O(N)，远优于暴力枚举的O(3^N)。
• 空间优化：若不需要追踪颜色方案，可只用两个长度为3的数组（存储前一栋和当前栋的成本），将空间复杂度从O(N)降至O(1)。

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