?

Log in

No account? Create an account

Задачка - Общество дровосеков Бердичева по изучению Мишны

Jul. 7th, 2010

01:01 am - Задачка

Previous Entry Share Next Entry

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

Comments:

[User Picture]
From:stumari
Date:July 7th, 2010 07:06 pm (UTC)
(Link)
у меня получилось 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
(Reply) (Thread)
[User Picture]
From:spamsink
Date:July 7th, 2010 07:28 pm (UTC)
(Link)
Красиво, у меня вручную больше 55 не получалось. Но можно лучше. Программа у меня неким улучшенным случайным поиском очень быстро добирается до лучшего результата, причем похоже, что всё время находятся повороты и отражения малого числа конфигураций. Но я все равно не уверен, что мой результат оптимален.
(Reply) (Parent) (Thread)
[User Picture]
From:stumari
Date:July 7th, 2010 07:32 pm (UTC)
(Link)
о, наконец-то у меня что-то из ваших задачек получилось, хотя бы на "неплохо" :)
я делал только вручную, причем сразу получилось 57 (может случайно), потом все больше 55-56, но все казалось, что хорошее решение должно быть симметричным, и наконец получилось это.
А сколько у программы самое большое, и сколько там 4-к?
(Reply) (Parent) (Thread)
[User Picture]
From:stumari
Date:July 7th, 2010 08:59 pm (UTC)
(Link)
поменяв местами 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
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:July 9th, 2010 01:41 am (UTC)
(Link)
Оказывается, это лучшее, чего можно добиться, рассматривая симметричные позиции:

http://spamsink.livejournal.com/332836.html?thread=3253028#t3253028
(Reply) (Parent) (Thread)
[User Picture]
From:stumari
Date:July 9th, 2010 08:17 pm (UTC)
(Link)
ага, интерeсно
(Reply) (Parent) (Thread)
[User Picture]
From:raindog_2
Date:July 8th, 2010 12:39 am (UTC)
(Link)
61:

14212
23414
31423
42331
13142
(Reply) (Thread)
[User Picture]
From:spamsink
Date:July 8th, 2010 12:46 am (UTC)
(Link)
У меня столько же, но по-другому. Мутаций и hill climbing хватило, спаривание не потребовалось.

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

Edited at 2010-07-08 12:46 am (UTC)
(Reply) (Parent) (Thread)
[User Picture]
From:raindog_2
Date:July 8th, 2010 09:27 pm (UTC)
(Link)
А я человек простой и решал в лоб, полным перебором, с учетом constraints. Интуиция подсказывала, что легальных вариантов не так много, и пересчет должен занять меньше дня. Так и получилось - полный перебор всех вариантов занял 2 часа 15 минут, и то я потом понял, что можно бы еще оптимизировать.

Так что - доказательство грубой силой :)
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:July 8th, 2010 09:49 pm (UTC)
(Link)
Надо же! Я сначала сделал просто мутации (если конфигурация была хорошая, ячейка меняется с вероятностью 1/8, если плохая - 1/2), и оно в большинстве случаев за пару минут долезало до 57-59, а минут за 5 - до 60. Пока думал, как их скрещивать, и вообще, правильно ли это делать в данном случае, приписал для хороших конфигураций карабканье (а чё, хороший перевод для hill climbing) на единицу по первой из ячеек, для которой это возможно, и стал стабильно получать максимум в первую же секунду, причем, что смешно, один из вариантов почему-то чаще, чем повороты и отражения этого варианта.

Edited at 2010-07-08 10:07 pm (UTC)
(Reply) (Parent) (Thread)
[User Picture]
From:raindog_2
Date:July 8th, 2010 10:23 pm (UTC)
(Link)
Перебором тоже достаточно быстро доходит до 61 - примерно секунды за 3, хотя это зависит от порядка, в котором перебирать. Пробовал другой порядок - секунд за 5. Наверное, 61-решений - много.

Добавил в программу счетчик вариантов и гистограмму по суммам. Запускаю. Результат выложу через пару часов.
(Reply) (Parent) (Thread)
[User Picture]
From:raindog_2
Date:July 9th, 2010 12:18 am (UTC)
(Link)
...готово. Всего есть 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
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:July 9th, 2010 12:24 am (UTC)
(Link)
Круто, спасибо! Интересно, есть ли среди максимальных вариантов симметричные.
(Reply) (Parent) (Thread)
[User Picture]
From:raindog_2
Date:July 9th, 2010 12:52 am (UTC)
(Link)
Поменял программу, рассматривать только вертикально симметричные позиции. В этом случае считает очень быстро, есть всего 622585 вертикально симметричных позиции.

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

24142
13231
24142
43134
12321

24142
13231
24142
34143
12321

23132
14241
24142
43134
12321
(Reply) (Parent) (Thread)
[User Picture]
From:raindog_2
Date:July 9th, 2010 12:59 am (UTC)
(Link)
...а для вертикально и горизонтально симметричных лучший ответ - 59, есть два варианта решения:

24142
13231
24142
13231
24142

21212
43434
12121
43434
21212
(Reply) (Parent) (Thread)
[User Picture]
From:spamsink
Date:July 9th, 2010 01:43 am (UTC)
(Link)
Это одно и то же, если учитывать повороты, но не будем придираться. :)
(Reply) (Parent) (Thread)
[User Picture]
From:_navi_
Date:July 9th, 2010 11:33 pm (UTC)
(Link)
Тьфу, вы тут переборами решаете, а я честно пытался какие-то свойства вывести и понять, как доказывать максимальность.
(Reply) (Thread)
[User Picture]
From:spamsink
Date:July 9th, 2010 11:53 pm (UTC)
(Link)
Не тьфу, а методами, адекватными задаче. :)
(Reply) (Parent) (Thread)
[User Picture]
From:_navi_
Date:July 10th, 2010 01:47 am (UTC)
(Link)
я думал, что это задача на-подумать, а тут соревнавание на полный перебор ради доказания максимальности :-)
(Reply) (Parent) (Thread)
[User Picture]
From:morontt
Date:August 29th, 2010 12:36 am (UTC)
(Link)
Круто, жалко, что пропустил.
(Reply) (Thread)