“房屋用三种颜色着色”是NP问题吗？

Question

考虑以下问题（此处复制）（下面重现）。 是否有更为知名的NP完全问题可以将其归约到它？

问题：

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

注：粉刷房子1红色的成本与粉刷房子2红色的成本不同。每个房子和颜色的组合都有自己的成本。

- user977476

---

@Sudhanshu：在我的回答中 :-) - Knoothe

你可以将其重新表述为最短路径问题的一个实例。每个房子/颜色组合是图中的一个顶点。表示相邻房屋的顶点相连，除非它们是相同颜色的。还有单独的起点和终点顶点。现在你可以为每条边分配成本，并找到从起点到终点顶点的最短路径。 - n. m.

@n.m. - 请您能否提供一些伪代码，以便解决带权图的最短路径问题！ - KGhatak

Answer 1

不，它不是NP-hard问题（从技术上讲，“NP-complete”这个术语对于这个问题是错误的，因为这不是一个决策问题）。 动态规划可行，并且给出O(n)时间复杂度的算法。（n是房屋数量）

您需要维护三个数组R[1..n]，B[1..n]，G[1..n]，其中R[i]是将房屋1、2、3...i涂成红色的最小成本。同样，B[i]是将房屋1、2...i涂成蓝色的最小成本，而G[i]是将房屋1、2...i涂成绿色的最小成本。

您可以计算R[i+1]: R[i+1]=（涂第i+1座房子为红色的成本）+最小值{G[i]，B[i]}。

同样地，B[i+1]和G[i+1]也可以计算出来。

最终，取R[n]，B[n]和G[n]的最小值。

这是O（n）时间和O（n）空间的算法。

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

房屋编号：1  2   3
R      : 1  4   6
G      : 2  100 2
B      : 3  100 4

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

房屋：0  1  2    3
R      : 0  1  6   107
G      : 0  2  101 8
B      : 0  3  101 10

从最后一列，即所有三个房子都被涂色的那一列，我们可以找到最小成本，它等于8并对应组合[绿色（2），红色（4），绿色（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])，这是一个导致解决方案的成本矩阵。

- Knoothe

---

它打印出([1, 6, 107], [2, 101, 8], [3, 101, 10])。这表示什么？ - user1247412

当然，更普遍的情况下，这个解决方案不是O(n)，而是O(n*c)。但是只有3种颜色被指定，那么就是O(n)。无论如何，这不是一个NP难问题。 - RichardPlunkett

@user1247412 这是结果矩阵，就像上面Python代码中描述的那样。 - shlatchz

@RichardPlunkett 这不是O(n*c^2)吗？因为对于每种颜色，您还必须计算其他颜色的最小值，这是一个双重 for 循环 - 因此是 c^2。 - shlatchz

解决方案在空间上不需要是 O(n)——分析颜色分配的整个历史记录并不是必要的，我们只需要保留最后一列即可。当然，这会增加将“当前”列复制到“上一个”列的开销，但这仍然是 O(n) 的时间复杂度，而内存使用量降至 O(1)。 - CiaPan

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

- Óscar López

---

如果只需要最小成本值，那么这样做是可以的，但如果问题要求每个房子的实际颜色值，就不能丢弃先前计算的 DP 值。 - Abhijit Sarkar