Задачка

[spamsink]

Найти матрицу 5х5, с максимальной суммой элементов - целых в диапазоне от 1 до 4 включительно, такую, что с каждым элементом, равным 2, соседствует по вертикали или горизонтали элемент, равный 1; с каждым элементом, равным 3, соседствует 2 и 1, и с каждым элементом, равным 4, соседствует 1, 2 и 3.

Comments

[stumari.livejournal.com]

у меня получилось 58 (никоим образом не уверен, что самое большое, просто я лучше ничего не вижу):
1 4 2 4 1
2 3 1 3 2
1 4 2 4 1
2 3 1 3 2
1 4 2 4 1

[spamsink]

Красиво, у меня вручную больше 55 не получалось. Но можно лучше. Программа у меня неким улучшенным случайным поиском очень быстро добирается до лучшего результата, причем похоже, что всё время находятся повороты и отражения малого числа конфигураций. Но я все равно не уверен, что мой результат оптимален.

[stumari.livejournal.com]

о, наконец-то у меня что-то из ваших задачек получилось, хотя бы на "неплохо" :)
я делал только вручную, причем сразу получилось 57 (может случайно), потом все больше 55-56, но все казалось, что хорошее решение должно быть симметричным, и наконец получилось это.
А сколько у программы самое большое, и сколько там 4-к?

[stumari.livejournal.com]

поменяв местами 1-ы и 2-и получается 59 :)
2 4 1 4 2
1 3 2 3 1
2 4 1 4 2
1 3 2 3 1
2 4 1 4 2

[raindog-2.livejournal.com]

61:

14212
23414
31423
42331
13142

[spamsink]

У меня столько же, но по-другому. Мутаций и hill climbing хватило, спаривание не потребовалось.

Но как доказать, что это максимум?

[raindog-2.livejournal.com]

А я человек простой и решал в лоб, полным перебором, с учетом constraints. Интуиция подсказывала, что легальных вариантов не так много, и пересчет должен занять меньше дня. Так и получилось - полный перебор всех вариантов занял 2 часа 15 минут, и то я потом понял, что можно бы еще оптимизировать.

Так что - доказательство грубой силой :)

[spamsink]

Надо же! Я сначала сделал просто мутации (если конфигурация была хорошая, ячейка меняется с вероятностью 1/8, если плохая - 1/2), и оно в большинстве случаев за пару минут долезало до 57-59, а минут за 5 - до 60. Пока думал, как их скрещивать, и вообще, правильно ли это делать в данном случае, приписал для хороших конфигураций карабканье (а чё, хороший перевод для hill climbing) на единицу по первой из ячеек, для которой это возможно, и стал стабильно получать максимум в первую же секунду, причем, что смешно, один из вариантов почему-то чаще, чем повороты и отражения этого варианта.

[raindog-2.livejournal.com]

Перебором тоже достаточно быстро доходит до 61 - примерно секунды за 3, хотя это зависит от порядка, в котором перебирать. Пробовал другой порядок - секунд за 5. Наверное, 61-решений - много.

Добавил в программу счетчик вариантов и гистограмму по суммам. Запускаю. Результат выложу через пару часов.

[raindog-2.livejournal.com]

...готово. Всего есть 12 768 889 837 легальных вариантов расстановки, и они распределны по суммам следующим образом:


25: 1
26: 25
27: 300
28: 2376
29: 14284
30: 69939
31: 289274
32: 1034066
33: 3247543
34: 9063472
35: 22671006
36: 51187336
37: 104926799
38: 196220849
39: 336166382
40: 529297110
41: 767532445
42: 1026215385
43: 1265148198
44: 1437089988
45: 1502225820
46: 1442146912
47: 1268094018
48: 1017907016
49: 742422773
50: 489532640
51: 289873498
52: 152717528
53: 71041606
54: 28804482
55: 10024674
56: 2987842
57: 745570
58: 157350
59: 27438
60: 3572
61: 320

[spamsink]

Круто, спасибо! Интересно, есть ли среди максимальных вариантов симметричные.

[raindog-2.livejournal.com]

Поменял программу, рассматривать только вертикально симметричные позиции. В этом случае считает очень быстро, есть всего 622585 вертикально симметричных позиции.

Лучшая сумма в вертикально симметричных вариантах - 60. Таких вариантов 6, вот 3 (остальные 3 получаются переворачиванием):

24142
13231
24142
43134
12321

24142
13231
24142
34143
12321

23132
14241
24142
43134
12321

[raindog-2.livejournal.com]

...а для вертикально и горизонтально симметричных лучший ответ - 59, есть два варианта решения:

24142
13231
24142
13231
24142

21212
43434
12121
43434
21212

[spamsink]

Оказывается, это лучшее, чего можно добиться, рассматривая симметричные позиции:

http://spamsink.livejournal.com/332836.html?thread=3253028#t3253028

[spamsink]

Это одно и то же, если учитывать повороты, но не будем придираться. :)

[stumari.livejournal.com]

ага, интерeсно

[http://users.livejournal.com/_navi_/]

Тьфу, вы тут переборами решаете, а я честно пытался какие-то свойства вывести и понять, как доказывать максимальность.

[spamsink]

Не тьфу, а методами, адекватными задаче. :)

[http://users.livejournal.com/_navi_/]

я думал, что это задача на-подумать, а тут соревнавание на полный перебор ради доказания максимальности :-)

[morontt.livejournal.com]

Круто, жалко, что пропустил.