IS＆QUOT;有三种颜色和QUOT房子着色; NP？

本文介绍了IS＆QUOT;有三种颜色和QUOT房子着色; NP？的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

考虑描述这里（转载如下）。可一些较著名NP-问题完整的问题减少到了吗？

Consider the problem described here (reproduced below.) Can some better known NP-complete problem be reduced to it?

问题：

有一排房子。每个房子可以涂上三种颜色：红色，蓝色和绿色。画每间房子带有一定颜色的成本是不同的。你要画所有这类的房子，没有两个相邻的房子具有相同的颜色。你画的房子以最小的成本。你会怎么做呢？

There are a row of houses. Each house can be painted with three colors: red, blue and green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color. You have to paint the houses with minimum cost. How would you do it?

请注意：画房子1红的代价是从绘画家2红的不同。房子和颜色的每个组合都有自己的成本。

Note: The cost of painting house 1 red is different from that of painting house 2 red. Each combination of house and color has its own cost.

推荐答案

没有，它不是 NP -hard （从技术上讲， NP完全是错误的术语这一点，因为这不是一个决策问题）。

No, it is not NP-hard (technically, "NP-complete" is the wrong term for this, as this is not a decision problem).

动态规划的工作，并为您提供一个O（ N 的）时间的算法。 （ N 的是房子的数量）。

Dynamic programming works, and gives you an O(n) time algorithm. (n is the number of houses).

您保持三个阵列 - [R [1 .. N 的]，B [1 .. N 的]，G [1 .. N 的]。

You maintain three arrays R[1..n], B[1..n], G[1..n].

在R [我的]是画栋的最低成本1,2,3 ...，的我的那个的我这样的是红色。

Where R[i] is the minimum cost of painting houses 1,2,3...,i such that i is colored Red.

类似地B〔的我的]是绘画1,2分钟的成本，...，的我的用的我的被颜色为蓝色，和政[我的]是的我的被颜色为绿色。

Similary B[i] is min cost of painting 1,2,...,i with i being colored Blue, and G[i] is with i being colored Green.

您可以计算 - [R [我的+1] =（房屋粉刷费用的我的+1红）+最小值{绿[我的]，B [我的]}。

You can compute R[i+1] = (Cost of painting house i+1 Red) + minimum {G[i], B[i]}.

同样B〔的我的+1]和G [我的+1]可以被计算出来。

Similarly B[i+1] and G[i+1] can be computed.

最后你把最小的 - [R [ N 的]，B [ N 的]和G [ N 的。

Ultimately you take the minimum of R[n], B[n] and G[n].

这是O（ N 的）时间和O（ N 的）空间。

This is O(n) time and O(n) space.

快速的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 r,b,g def main(): print min_paint([1,4,6],[2,100,2],[3,100,4]) if __name__ == "__main__": main()