Is NP Three Color Home Coloring?

Question

Consider the described problem here (reproduced below). Could any more well-known NP-complete problem be reduced to it?

Problem:

There are a number of houses. Each house can be painted in three colors: red, blue and green. The cost of painting each house with a specific color is different. You must draw all the houses so that not one neighboring house has the same color. You must paint the house at the lowest cost. How do you do this?

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

Answer 1

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

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

You support three arrays R [1..n], B [1..n], G [1..n]. Where R [i] is the minimum cost of painting houses 1,2,3 ..., i, so I am painted in red. Similary B [i] - the minimum cost of the figure is 1,2, ..., i, and I am colored in blue, and G [i] - with the fact that I am painted in green.

You can calculate R [i + 1] = (Cost of painting the house i + 1 Red) + minimum {G [i], B [i]}. Similarly, B [i + 1] and G [i + 1] can be calculated.

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

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

For example, consider the following cost matrix for homes:

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

The algorithm builds the following matrix to get the answer:

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

In the last column, where all 3 houses are painted, we can find the minimum cost equal to 8, and corresponds to the combination [Green (2), Red (4), Green (2)].

Fast 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() 

The output will be ([1, 6, 107], [2, 101, 8], [3, 101, 10]), which is the cost matrix leading to the solution.

Answer 2

The explanation from @Knoothe comes from, but I believe that the implementation can be improved - it uses O(n) extra space to store the previous values, but we can do this in O(1) space, noting that we only need the previous value for each color, not the entire array of values. Here's how:

 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) 

For instance:

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