是"用三种颜色的房子着色"NP吗？

Question

考虑一下这里描述的问题(在下面重现.)可以将一些更好的已知NP完全问题减少到它吗？

问题:

有一排房子.每个房子都可以涂上三种颜色:红色,蓝色和绿色.用一定颜色绘制每个房子的成本是不同的.你必须为所有的房屋涂漆,使两个相邻的房屋没有相同的颜色.你必须以最低的成本为房屋涂漆.你会怎么做？

注意:绘画房屋1红色的成本与绘画房屋2红色的成本不同.房屋和颜色的每种组合都有自己的成本.

Answer 1

不,它不是NP难的(从技术上讲," NP-complete "是错误的术语,因为这不是决策问题).

动态编程可以工作,并为您提供O(n)时间算法.(n是房屋数量).

您维护三个数组R [1 .. n ],B [1 .. n ],G [1 .. n ].其中R [ i ]是绘画房屋的最低费用1,2,3 ...,我这样我就是红色.与之相似B [ 我 ]是画1,2,...,的最小代价我与我被着色蓝,和G [ 我 ]是与我被着色绿色.

你可以计算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)空间.

例如,考虑房屋的以下成本矩阵:

House #: 1   2   3
R      : 1   4   6
G      : 2  100  2
B      : 3  100  4

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

Houses : 0  1   2    3
R      : 0  1   6   107
G      : 0  2  101   8
B      : 0  3  101  10

从最后一列,所有3个房屋都被绘制,我们可以找到最低成本,等于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]),这是导致解决方案的成本矩阵.