Максимизировать карточку

Question

Доска простая 31 на 31 шахматной сетке.

• до одной части могут быть размещены на каждой площади (так технически до 961 штук)
• Кусочки грант [16 - taxicab_distance_from_middle_square] оценка (не может опускаться ниже 0 баллов)
• Но каждый часть теряет 1/24 своего время бигованного любой другой кусок, который находится внутри 5 по 5 квадрату центрированного вокруг куска
  • Так полностью окружали штучных гранты точно нет точек
  • и кусок окружен 12 других грантами шт exactl у половины его партитура
• Цель состоит в том, конечно, чтобы найти расположение деталей, что дает самый высокий счет

Я попытался запустить программу, которая помещает один кусок в то время, в любом место, которое дало бы наивысший балл, но поскольку каждое место размещения влияет на оценку других предметов, результат, очевидно, даже не близок к оптимальному.

Что было бы лучшим способом найти (или хотя бы приблизиться к) состояние платы с наивысшей оценкой?

Answer 1

Кажется, что хорошие решения имеют интересную структуру. Вот решение со значением 879.25:

0000000000000001000000000000000 
0000000000000011100000000000000 
0000000000000001000000000000000 
0000000000001001001000000000000 
0000000000011111111100000000000 
0000000000001001001000000000000 
0000000000000000000000000000000 
0000000011111111111111100000000 
0000000111111111111111110000000 
0000000000000000000000000000000 
0000000000000000000000000000000 
0000111111111111111111111110000 
0001111111111111111111111111000 
0000000000000000000000000000000 
0000000000000000000000000000000 
1111111111111111111111111111111 
0111111111111111111111111111110 
0000000000000000000000000000000 
0000000000000000000000000000000 
0000111111111111111111111110000 
0000011111111111111111111100000 
0000000000000000000000000000000 
0000000000000000000000000000000 
0000000011111111111111100000000 
0000000001111111111111000000000 
0000000000000000000000000000000 
0000000000001001001000000000000 
0000000000001111111000000000000 
0000000000000011000000000000000 
0000000000000001000000000000000 
0000000000000001000000000000000 

Я нашел это решение, и 7 вращения и отражения его, путем имитации отжига.

Если вы «угадаете», что средний ряд строк такой же, как указано выше, вы получаете управляемые малые подзадачи выше и ниже указанной группы строк. Например, вы можете найти оптимальные решения для этих подзадач путем динамического программирования.