algorithm - “房子用三色着色”是NP吗？

Question

考虑这里描述的问题（转载如下。）可以将一些更知名的 NP 完全问题简化为它吗？

问题：

有一排房子。每个房子都可以涂上三种颜色：红色、蓝色和绿色。用某种颜色粉刷每个房子的成本是不同的。你必须给所有的房子涂漆，这样相邻的两个房子就没有相同的颜色。你必须以最低的成本粉刷房屋。你会怎么做？

注：将房屋 1 涂成红色的成本与将房屋 2 涂成红色的成本不同。房屋和颜色的每种组合都有其自身的成本。

Answer 1

不，它不是NP 难的（从技术上讲，“ NP 完全”是错误的术语，因为这不是决策问题）。

动态编程有效，并为您提供 O( n ) 时间算法。（n是房屋数量）。

您维护三个数组R[1..n], B[1..n], G[1..n]，其中R[i]是绘制房屋 1、2、3 ... 的最低成本，i例如i红色。同样B[i]，涂漆 1、2 ... 的最低成本是i蓝色i的，并且G[i]是i绿色的。

您可以计算R[i+1]: R[i+1]= (Cost of painting house i+1 Red) + minimum {G[i], B[i]}。

类似B[i+1]和G[i+1]可以计算。

最终你会取最少的R[n], B[n] and G[n].

这是 O( n ) 时间和 O( n ) 空间。

例如，考虑以下房屋的成本矩阵：

房屋编号：1 2 3
右：1 4 6
克：2 100 2
乙：3 100 4

该算法正在构建以下矩阵以获得答案：

房屋：0 1 2 3
R：0 1 6 107
克：0 2 101 8
乙：0 3 101 10

从最后一列中，所有 3 栋房屋都已涂漆，我们可以找到最小成本，等于 8，对应于组合 [Green (2), Red (4), Green (2)]。

快速Python：

# rc = costs of painting red, bc of blue and gc of green.
def min_paint(rc, bc, gc):
    n, i = len(rc), 1
    r, b, g = [0]*n, [0]*n, [0]*n
    r[0], b[0], g[0] = rc[0], bc[0], gc[0]
    while i < n:
        r[i] = rc[i] + min(b[i-1], g[i-1])
        b[i] = bc[i] + min(r[i-1], g[i-1])
        g[i] = gc[i] + min(b[i-1], r[i-1])
        i += 1

    return min(r, b, g)

def main():
    print min_paint([1, 4, 6], [2, 100, 2], [3, 100, 4])

if __name__ == "__main__":
    main()

输出将是 ([1, 6, 107], [2, 101, 8], [3, 101, 10])，这是一个导致解决方案的成本矩阵。

Answer 2

@Knoothe 的解释很到位，但我相信可以改进实现 - 它使用O(n)额外的空间来存储以前的值，但我们可以O(1)通过注意到我们只需要每种颜色的以前的值，而不是整个值数组。就是这样：

def min_paint(rc, bc, gc):
    # `r` is the min cost of painting the current house
    # using color red; similarly for `b` and `g`
    r, b, g = 0, 0, 0
    for cr, cb, cg in zip(rc, bc, gc):
        # new value for `r` is current cost for `r` plus the
        # minimum cost for painting the previous house in one
        # of the other two colors; similarly for `b` and `g`
        r, b, g = cr + min(b, g), cb + min(r, g), cg + min(r, b)
    # answer is the min cost for painting the last house
    return min(r, b, g)

例如：

min_paint([1, 4, 6], [2, 100, 2], [3, 100, 4])
=> 8