この問題に取り組むための新しい方法として、シミュレーテッド アニーリングを学ぶことにしました。基本的に、各行と列の合計が一意になるように、グリッドを -1、0、または 1 で埋める方法を尋ねます。テスト ケースとして、6x6 グリッドを使用しました。これには、Neil によって与えられた最適なソリューションが確実に存在します。
1 1 1 1 1 1 6
1 1 1 1 1 -1 4
1 1 1 1 -1 -1 2
1 1 0 -1 -1 -1 -1
1 0 -1 -1 -1 -1 -3
0 -1 -1 -1 -1 -1 -5
5 3 1 0 -2 -4
私のコードは通常、実行の大部分で最適なケースに到達せず、間違ったグリッド コストを返します (old_cost一致する必要がありますcount_conflict(grid))。パラメーターが正しく設定されていないか、実装が間違っているか、またはシミュレートされたアニーリングが実行可能な方法ではない可能性がありますか?
import random
from math import exp
G_SIZE = 6
grid = [[1]*G_SIZE for i in range(G_SIZE)]
def count_conflict(grid):
cnt = [0]*(2*G_SIZE+1)
conflicts = 0
for row in grid:
cnt[sum(row)] += 1
for col in zip(*grid):
cnt[sum(col)] += 1
#print(cnt)
for c in cnt:
if c == 0: conflicts += 1
if c > 1: conflicts += c-1
return conflicts
def neighbor(grid):
new_grid = grid[:]
i = random.choice(range(G_SIZE))
j = random.choice(range(G_SIZE))
new_cells = [-1, 0, 1]
new_cells.remove(new_grid[i][j])
new_grid[i][j] = random.choice(new_cells)
return new_grid
def acceptance_probability(old_cost, new_cost, T):
if new_cost < old_cost: return 1.0
return exp(-(new_cost - old_cost) / T)
# Initial guess
for i in range(1, G_SIZE):
for j in range(0, i):
grid[i][j] = -1
#print(grid)
old_cost = count_conflict(grid)
T = 10.0
T_min = 0.1
alpha = 0.99
while T > T_min:
for i in range(1000):
new_sol = neighbor(grid)
new_cost = count_conflict(new_sol)
ap = acceptance_probability(old_cost, new_cost, T)
print(old_cost, new_cost, ap, T)
if ap > random.random():
grid = new_sol
old_cost = new_cost
T *= alpha
for row in grid:
print(row)
print(count_conflict(grid))