动态规划解决带相邻约束的花园种植成本优化问题

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

动态规划解决带相邻约束的花园种植成本优化问题

2025-11-30

浏览次数：次

返回列表

动态规划解决带相邻约束的花园种植成本优化问题

本文详细介绍如何使用动态规划解决一个经典的优化问题：在一条街上为N栋房屋种植鲜花，每栋房屋有3种花色可选，且相邻房屋不能种植同色鲜花。文章首先阐述了问题的背景及暴力解法的局限性，随后深入讲解了动态规划的核心思想，并通过Python示例代码展示了如何高效计算最低总成本，以及如何回溯并获取具体的种植方案，显著提升了大规模问题的求解效率。

问题描述

假设一条街上有N栋房屋，每栋房屋的花园可以种植三种不同颜色的鲜花（例如，白色、黄色、红色）。对于每栋房屋，每种颜色的鲜花都有其对应的种植成本。这些成本通常以矩阵形式给出，其中每一行代表一栋房屋，每一列代表一种花色。

核心约束条件： 如果一栋房屋种植了某种颜色的鲜花，那么其相邻的房屋不能种植相同颜色的鲜花。

我们的目标是找到一种种植方案，使得所有房屋的鲜花种植总成本最低，同时满足上述相邻约束。

示例： 考虑4栋房屋的成本矩阵：

房屋/花色	白色	黄色	红色
H1	5	6	7
H2	3	7	9
H3	6	7	3
H4	1	8	4

根据规则，最便宜的方案可能是：H1-黄色(6), H2-白色(3), H3-红色(3), H4-白色(1)，总成本为 6 + 3 + 3 + 1 = 13。

暴力解法的局限性

一个直观但效率低下的方法是枚举所有可能的种植组合。对于N栋房屋和3种花色，总共有 $3^N$ 种组合。然后，对每种组合进行检查，排除不符合相邻约束的组合，并计算其余组合的总成本，最终找出最低成本。

例如，可以使用 itertools.product([1, 2, 3], repeat=n) 生成所有长度为N的颜色序列（1、2、3分别代表三种颜色）。之后，遍历这些序列，去除相邻元素相同的序列，再计算剩余序列的成本。

然而，当N值较大时（例如N > 20），$3^N$ 会迅速增长，导致：

内存错误： 生成所有组合可能耗尽系统内存。
时间复杂度过高： 遍历并检查大量组合会非常耗时，导致程序运行缓慢甚至崩溃。

因此，我们需要一种更高效的算法来解决这个问题。

GoEnhance

全能AI视频制作平台：通过GoEnhance AI让视频创作变得比以往任何时候都更简单。

347 查看详情 GoEnhance

动态规划解决方案

动态规划是解决这类优化问题的有效方法，它通过将大问题分解为相互重叠的子问题来避免重复计算。

核心思想

我们可以定义一个状态 dp[i][color] 表示在处理到第 i 栋房屋时，第 i 栋房屋种植 color 颜色鲜花所能达到的最低总成本。

由于第 i 栋房屋的颜色不能与其前一栋房屋（第 i-1 栋）的颜色相同，所以 dp[i][color] 的值将取决于 dp[i-1][other_color1] 和 dp[i-1][other_color2] 的最小值，再加上第 i 栋房屋种植 color 的成本。

状态定义与转移方程

设 costs[i][j] 为第 i 栋房屋种植第 j 种颜色的成本（j 可以是 0, 1, 2）。我们维护三个变量 a, b, c，分别代表当前房屋种植第一、第二、第三种颜色鲜花时，到目前为止的最低总成本。

对于第 i 栋房屋：

如果第 i 栋房屋种植第一种颜色 (color_0)：其前一栋房屋（第 i-1 栋）必须种植第二种颜色 (color_1) 或第三种颜色 (color_2)。因此，dp[i][color_0] = min(dp[i-1][color_1], dp[i-1][color_2]) + costs[i][0]
如果第 i 栋房屋种植第二种颜色 (color_1)：其前一栋房屋（第 i-1 栋）必须种植第一种颜色 (color_0) 或第三种颜色 (color_2)。因此，dp[i][color_1] = min(dp[i-1][color_0], dp[i-1][color_2]) + costs[i][1]
如果第 i 栋房屋种植第三种颜色 (color_2)：其前一栋房屋（第 i-1 栋）必须种植第一种颜色 (color_0) 或第二种颜色 (color_1)。因此，dp[i][color_2] = min(dp[i-1][color_0], dp[i-1][color_1]) + costs[i][2]

空间优化

注意到计算 dp[i] 时只依赖于 dp[i-1] 的值，我们可以将空间复杂度从 O(N) 优化到 O(1)，只存储前一个房屋的三种颜色最低成本。

初始化：对于第一栋房屋（索引 0），a = costs[0][0], b = costs[0][1], c = costs[0][2]。实际上，为了简化代码，我们可以将 a, b, c 初始化为0，然后从第一个房屋的成本开始迭代，效果相同。

1. 只计算最低总成本

以下Python代码实现了只计算最低总成本的动态规划：

def solve_min_cost(rows):
    """
    计算满足相邻约束的最低花卉种植总成本。
    :param rows: 列表的列表，每行代表一栋房屋，包含三种花色的成本。
                 例如: [[5, 6, 7], [3, 7, 9], ...]
    :return: 最低的种植总成本。
    """
    # a, b, c 分别代表当前房屋种植第一、第二、第三种颜色时，到目前为止的最低总成本
    # 初始化为0，迭代从第一个房屋开始。
    a = b = c = 0 

    for x, y, z in rows: # x, y, z 分别是当前房屋三种花色的成本
        # 计算当前房屋种植第一种颜色 (x) 的最低成本
        # 它必须从前一个房屋种植第二种 (b) 或第三种 (c) 颜色中选择成本最低的
        new_a = min(b, c) + x

        # 计算当前房屋种植第二种颜色 (y) 的最低成本
        # 它必须从前一个房屋种植第一种 (a) 或第三种 (c) 颜色中选择成本最低的
        new_b = min(a, c) + y

        # 计算当前房屋种植第三种颜色 (z) 的最低成本
        # 它必须从前一个房屋种植第一种 (a) 或第二种 (b) 颜色中选择成本最低的
        new_c = min(a, b) + z

        # 更新 a, b, c 为当前房屋的最低成本
        a, b, c = new_a, new_b, new_c

    # 遍历完所有房屋后，a, b, c 分别是最后一栋房屋种植三种颜色时的最低总成本
    # 取三者中的最小值即为全局最低总成本
    return min(a, b, c)

# 示例数据
rows_data = [
    [5, 6, 7],
    [3, 7, 9],
    [6, 7, 3],
    [1, 8, 4]
]

print(f"最低总成本: {solve_min_cost(rows_data)}") # 输出: 13

2. 同时获取最低总成本和具体种植方案

为了获取具体的种植方案，我们需要在动态规划过程中不仅存储最低成本，还要存储导致该成本的路径信息。这可以通过存储 (成本, 路径) 对来实现。路径可以是一个元组或列表，记录了从第一栋房屋到当前房屋的颜色选择。

def solve_with_path(rows):
    """
    计算满足相邻约束的最低花卉种植总成本，并返回具体的种植方案。
    :param rows: 列表的列表，每行代表一栋房屋，包含三种花色的成本。
    :return: 一个元组 (最低总成本, 种植方案列表)。
             种植方案列表中的元素为1, 2, 3，分别代表三种花色。
    """
    # a, b, c 分别存储 (成本, 路径) 对
    # 路径用 (当前房屋颜色索引, 前一个房屋的路径) 的元组表示，方便回溯
    # 初始化时，成本为0，路径为None
    a = b = c = (0, None)

    def extend(prev_a, prev_b, current_cost, current_color_index):
        """
        辅助函数：根据前一房屋两种不同颜色状态的最小值，计算当前房屋的 (成本, 路径) 对。
        :param prev_a: 前一房屋状态A的 (成本, 路径) 对
        :param prev_b: 前一房屋状态B的 (成本, 路径) 对
        :param current_cost: 当前房屋种植指定颜色的成本
        :param current_color_index: 当前房屋种植的颜色索引 (1, 2, 或 3)
        :return: 当前房屋的 (成本, 路径) 对
        """
        # 比较前一房屋两种不同颜色状态的成本，选择较小的那个
        sum_val, path = min(prev_a, prev_b)
        # 返回新的 (总成本, 新路径)
        # 新路径是 (当前颜色索引, 前一个房屋的路径)
        return sum_val + current_cost, (current_color_index, path)

    for x, y, z in rows: # x, y, z 是当前房屋三种花色的成本
        # 计算当前房屋种植第一种颜色 (x) 的 (成本, 路径)
        new_a = extend(b, c, x, 1) # 1 代表第一种颜色

        # 计算当前房屋种植第二种颜色 (y) 的 (成本, 路径)
        new_b = extend(a, c, y, 2) # 2 代表第二种颜色

        # 计算当前房屋种植第三种颜色 (z) 的 (成本, 路径)
        new_c = extend(a, b, z, 3) # 3 代表第三种颜色

        # 更新 a, b, c
        a, b, c = new_a, new_b, new_c

    # 遍历完所有房屋后，a, b, c 包含了所有以不同颜色结束的最低总成本及路径
    # 找到三者中总成本最低的那个
    total_sum, path_tuple = min(a, b, c)

    # 从路径元组中回溯并展平路径
    flat_path = []
    while path_tuple:
        color_index, path_tuple = path_tuple
        flat_path.append(color_index)

    # 路径是从后往前构建的，需要反转以得到正确的顺序
    return total_sum, flat_path[::-1]

# 示例数据
rows_data = [
    [5, 6, 7],
    [3, 7, 9],
    [6, 7, 3],
    [1, 8, 4]
]

min_cost, path = solve_with_path(rows_data)
print(f"最低总成本: {min_cost}") # 输出: 13
print(f"种植方案: {path}") # 输出: [2, 1, 3, 1] (代表黄, 白, 红, 白)

复杂度分析

时间复杂度： 算法对每栋房屋进行一次迭代，每次迭代内部的操作（比较、加法）都是常数时间。因此，对于N栋房屋，时间复杂度为 O(N)。这比暴力解法的 $O(3^N)$ 有了巨大的提升。
空间复杂度：
- 如果只计算最低总成本，我们只需要存储三个变量 (a, b, c)，空间复杂度为 O(1)。
- 如果需要存储并回溯路径，每个 (成本, 路径) 对的路径部分会随着房屋数量的增加而变长。最坏情况下，路径的长度为N。因此，存储路径需要 O(N) 的空间。

总结与注意事项

动态规划的优势： 对于这类具有重叠子问题和最优子结构的问题，动态规划能够将指数级的时间复杂度降低到线性级别，从而高效解决大规模问题。
问题变体： 这个动态规划模式非常灵活。如果花色数量改变，只需要调整 a, b, c 变量的数量和 extend 函数的逻辑。如果相邻约束条件改变（例如，不能和前两栋房屋颜色相同），状态定义和转移方程也需要相应调整。
数据读取： 教程中示例直接使用了Python列表，实际应用中，你需要从文件（如 domy.txt）读取数据并将其转换为 rows 列表的格式。确保正确解析文件中的字符串为整数。

通过采用动态规划，我们能够高效地解决带有相邻约束的花园种植成本优化问题，无论房屋数量N有多大，都能在可接受的时间内找到最优解。

以上就是动态规划解决带相邻约束的花园种植成本优化问题的详细内容，更多请关注其它相关文章！

# 两种 # 适合做优化的网站 # 沈阳seo教程系统 # seo和推广的区别 # 正规的电商网站推广技术 # 仙桃房产网站推广 # 口口福的网站推广目标 # 温州seo维护 # 视频营销推广论文 # 营销推广公司咨询b火15星服务 # 好的网络推广营销方式 # 表一 # python # 第一个 # 迭代 # 转换为 # 我们可以 # 遍历 # 三种 # 总成本 # 种颜色 # cos # app