Leetcode 256: Paint House
I am trying to solve the this problem with the Simulated Annealing algorithm. But the result is far away from the correct answer, which is calculated with the DP method.
e.g., I made a 10x3 costs matrix as following, the correct minimum cost is 50, but the result of Simulated Annealing is 70~90 in most cases.
Briefly speaking, I constructed an initial status(a combination of houses' colors), the color of the 1st house was Red, and Blue for the 2nd one, Green for the 3rd one, Red for the 4th one, and so on. And let's assume the cost of the this combination of colors is the minimum cost.
Under the process of annealing, I choose a house randomly firstly, changed its color, and adjusted the colors of two neighbors of this house to meet the precondition of "no two adjacent houses have the same color." Then I recalculated the cost of the new combination of colors. If the new cost is less than the minimum one, the new cost will become the minimum. Otherwise, I accepted the more expensive combination if and only if rand() <= acceptanceProbability. And I repeated these steps again and again until the temperature T is near 0.
Is the SA algorithm suitable for this problem? And if the answer is YES and there are no bugs in my code, what should I tunning, the initial combination of colors, the speed of cool down, or anything else, to make the cost calculating with SA to approach the correct one.
package main
import (
"fmt"
"math"
"math/rand"
"time"
)
const (
RED = iota // 0
BLUE // 1
GREEN // 2
)
var randSrc = rand.NewSource(time.Now().UnixNano())
var randGen = rand.New(randSrc)
func main() {
var costs [][]int
costs = append(costs, []int{10, 4, 11})
costs = append(costs, []int{14, 4, 6})
costs = append(costs, []int{ 2, 6, 2})
costs = append(costs, []int{10, 5, 2})
costs = append(costs, []int{16, 11, 2})
costs = append(costs, []int{ 6, 16, 6})
costs = append(costs, []int{ 6, 7, 2})
costs = append(costs, []int{ 8, 15, 9})
costs = append(costs, []int{ 9, 12, 11})
costs = append(costs, []int{13, 15, 3})
fmt.Println(minCost(costs))
}
func minCost(costs [][]int) int {
// STEP1. init start status(a list of colors)
rows := len(costs)
colors := make([]int, rows, rows)
for r := 0; r < rows; r++ {
// suppose 1st house is RED, 2nd is BLUE, 3rd is GREEN, 4th is RED, ...
colors[r] = (RED + r) % 3
}
// calculate initial cost
cost := calcCosts(costs, colors)
// STEP2. simulated annealing
minCost := cost
bestColors := colors
for T := 5000000.0; T > 0.001; T = T * 0.99 {
nextColors := next(bestColors)
nextCost := calcCosts(costs, nextColors)
if nextCost < minCost {
minCost = nextCost
bestColors = nextColors
} else if randGen.Float64() <= acceptanceProbability(cost, nextCost, T) {
minCost = nextCost
bestColors = nextColors
}
}
return minCost
}
// generates next candidate, another combination of colors
func next(colors []int) []int {
rows := len(colors)
nextColors := make([]int, rows, rows)
copy(nextColors, colors)
// chose 1 row randomly, change this row's color
rr := randGen.Intn(rows) // rr in [0, rows)
oc := nextColors[rr] // old color of this row
nc := randGen.Intn(3) // random new color for this row
for oc == nc {
nc = randGen.Intn(3)
}
nextColors[rr] = nc
// Adjust up-next and down-next's colors
if rr-1 >= 0 {
// up-next exists
neighbourColor := nextColors[rr-1]
for neighbourColor == nc {
neighbourColor = randGen.Intn(3) // [0,n)
}
nextColors[rr-1] = neighbourColor
}
if rr+1 <= rows-1 {
// down-next exists
neighbourColor := nextColors[rr+1]
for neighbourColor == nc {
neighbourColor = randGen.Intn(3) // [0,n)
}
nextColors[rr+1] = neighbourColor
}
return nextColors
}
func calcCosts(costs [][]int, colors []int) int {
cost := 0
for r, row := range costs {
cost += row[colors[r]]
}
return cost
}
func acceptanceProbability(cost int, nextCost int, T float64) float64 {
if cost > nextCost {
return 1.0
}
p := math.Exp(float64(cost-nextCost) / T) // cost - next <= 0
return p
}
Yes, this can be done with Simulated Annealing,
I will give you a straigh forward python example, few things to notice:
Python code:
import frigidum
houses = [{ 'cost' : (10, 4,11) },
{ 'cost' : (14, 4, 6) },
{ 'cost' : ( 2, 6, 2) },
{ 'cost' : (10, 5, 2) },
{ 'cost' : (16, 11, 2) },
{ 'cost' : ( 6, 16, 6) },
{ 'cost' : ( 6, 7, 2) },
{ 'cost' : ( 8, 15, 9) },
{ 'cost' : ( 9, 12,11) },
{ 'cost' : (13, 15, 3) },]
def valid_new_colors_for_house( n, color_pallet ):
if n == 0:
return list( set([0,1,2]) - set( [color_pallet[1], color_pallet[n]] ) )
if n == len(color_pallet) - 1:
return list( set([0,1,2]) - set( [color_pallet[n], color_pallet[n-1]] ) )
valid_colors = list( set([0,1,2]) - set( [color_pallet[n-1],color_pallet[n],color_pallet[n+1]] ) )
return valid_colors
import random
def start_state():
return [0,1,0,1,0,1,0,1,0,1]
def swap_random_color( color_pallet ):
random_house = random.randint(0,len(color_pallet)-1)
valid_colors = valid_new_colors_for_house(random_house, color_pallet)
while len(valid_colors) < 1 :
random_house = random.randint(0,len(color_pallet)-1)
valid_colors = valid_new_colors_for_house(random_house, color_pallet)
new_color = random.choice(valid_colors)
color_pallet[ random_house ] = new_color
return color_pallet
def color_cost(color_pallet):
global houses
return sum([ h['cost'][p] for h,p in zip(houses,color_pallet) ])
And run the Annealing Scheme with
import frigidum
import random
import frigidum
import random
local_opt = frigidum.sa(random_start=start_state,
neighbours=[swap_random_color],
objective_function=color_cost,
T_start=10**4,
T_stop=0.01,
repeats=10**2,
alpha=.9,
copy_state=frigidum.annealing.copy)
It will find a minimum cost of 50.
I hope this will help you. Check that if the proposal is not accepted, the current state is not changed.