Конкурс для программистов - предгамильтоновы циклы

[Zealint]

Модераторам: Чтобы было честно, форум dxdy указан на странице конкурса в качестве информационного спонсора.

Делаю третий конкурс. Призовой фонд 3000 р. Задача, как и всегда, имеет простую формулировку, но довольна сложна для решения. Задан граф в виде квадратной решётки размером $(2n+1)\times (2n+1)$ (такой граф принято обозначать $P_{2n+1}\times P_{2n+1}$). Сколько в нём простых циклов с максимальной длиной? Поясню. Дело в том, что интерес представляют гамильтоновы циклы, но их на квадратной решётке нечётного размера быть не может, поэтому будем считать "предгамильтоновы" циклы - длина которых на единицу меньше числа вершин (про такие структуры ещё говорят, что они "с одним дефектом"). Например, на рисунке ниже представлен один из предгамильтоновых циклов на решётке $P_{7}\times P_{7}$. Дефект отмечен синим цветом.



Подробные правила конкурса - на моем сайте. Там же поясняется, зачем и кому нужна такая задача. Задача для чётных решёток (и гамильтоновых циклов в ней) уже была решена для $P_{22}\times P_{22}$. В общих чертах, цикл моделирует полимерную молекулу, количество различных конформаций полимера (точнее, логарифм этого количества) даёт энтропию системы. Известно, что циклы можно считать и приближённо, но для вывода приближённой формулы необходимо сначала насчитать как можно больше точных значений, чтобы как можно точнее провести экстраполяцию результатов на бесконечные решётки.

PS. Само слово "предгамильтонов" не является традиционным в науке, то есть это неформальное название. Считайте его однозначно определённым в рамках конкурса, но не дальше.

[maxal]

Zealint в сообщении #357945 писал(а):

Задача для чётных решёток (и гамильтоновых циклов в ней) уже была решена для $P_{22}\times P_{22}$.

А где решение для $P_{22}\times P_{22}$? В A003763 приведены значения только до $P_{20}\times P_{20}$.

[Zealint]

maxal в сообщении #358011 писал(а):

А где решение для $P_{22}\times P_{22}$? В A003763 приведены значения только до $P_{20}\times P_{20}$.

Оно ещё не появилось, появится со дня на день, так как было добавлено в базу вчера.
Можете посмотреть здесь, если угодно.

[Zealint]

Я опубликовал на Хабре свой подход к решению поставленной задачи.

[Zealint]

Конкурс завершён. Удалось получить ответ для решётки размером $21\times21$. С результатами можно ознакомиться здесь.

[maxal]

Zealint
Не забудьте послать результаты в OEIS.

-- Sun Oct 31, 2010 10:13:53 --

Кстати, я хотя в конкурсе и не участвовал, выкроил немного времени на поиграться с задачей.
Задача оказалась не совсем подходящей для конкурса, так как существенно лучшее решение, чем приведенно вами на хабре, придумать очень тяжело (тем более в условиях конкурса). Поэтому конкурс получился по сути на оптимизацию участниками одного и того же алгоритма (по крайней мере теми, кто хотел вычислить для $n>10$).

Тем не менее, у меня возникло несколько идей, одну из которых я даже успел проверить на практике:

1) использовать диагональные разрезы по вершинам. К сожалению, количество таких допустимых разрезов растёт пропорционально $4^n$.

2) построить автомат с магазинной памятью, который бы "строил" разрезы пошагово (змейкой - первый разрез справо-налево, затем слева-направо и т.д.) Точнее говоря, этот автомат распознавал бы образуют ли данные последовательные разрезы (пред)гамильтонов цикл или нет. В чистом виде количество состояний у такого автомата невелико (на вскидку десяток-два), хотя для нахождения количества его успешных вычислений (соответствующие различным гамильтоновым циклам), пришлось бы также включать в описание состояния содержимое стека. Не знаю, может ли этот подход дать лучший алгоритм.

3) использование meet-in-the-middle. По сути любой из описанных алгоритмов (включая ваш) для решения этой задачи может быть ускорен с помощью meet-in-the-middle. Нужно всего лишь вычислить количество половинок (пред)гамильтоновых циклов, а затем замкнуть все подходящие пары половинок.

[Zealint]

Цитата:

Не забудьте послать результаты в OEIS.

Уже послал. Общался с одним физиком из франции, он год назад собирался что-то такое считать, но, видимо, не успел.

Цитата:

Задача оказалась не совсем подходящей для конкурса, так как существенно лучшее решение, чем приведенно вами на хабре, придумать очень тяжело (тем более в условиях конкурса).

Ну так я и говорю, "кто первым встал, того и тапки" : ). Конкурс научный, поэтому сюда подходит любая нерешённая до этого задача. Остальные "задачи" я называю словом "упражнения". Немного пафосно, но что поделать, если другие задачи уже кто-то решил... Когда-нибудь, когда будет много денег, я буду устраивать научные конкурсы на год и больше. Задач немерено, денег - только то, что удалось сэкономить с бомжовой зарплаты преподавателя. Сейчас школьники больше на карманные расходы получают : )

Цитата:

1) использовать диагональные разрезы по вершинам. К сожалению, количество таких допустимых разрезов растёт пропорционально $4^n$.

Это я делал, не удалось довести идею до такого состояния, чтобы хоть немного работало. Действительно, слишком быстро растет число состояний.

Цитата:

2) построить автомат с магазинной памятью, который бы "строил" разрезы пошагово (змейкой - первый разрез справо-налево, затем слева-направо и т.д.) Точнее говоря, этот автомат распознавал бы образуют ли данные последовательные разрезы (пред)гамильтонов цикл или нет. В чистом виде количество состояний у такого автомата невелико (на вскидку десяток-два), хотя для нахождения количества его успешных вычислений (соответствующие различным гамильтоновым циклам), пришлось бы также включать в описание состояния содержимое стека. Не знаю, может ли этот подход дать лучший алгоритм.

Не понял идею, но я верю только тому, что может дать конкретную цифру. Вот есть ответ для n=10, если кто-то претендует на хороший алгоритм, он должен сказать, что может данную цифру повторить. Может это и лучше, но надо, чтобы кто-то написал и проверил. Я этой задачей в ближайший год больше заниматься не буду. У меня на очереди еще полдюжины таких.

Цитата:

использование meet-in-the-middle. По сути любой из описанных алгоритмов (включая ваш) для решения этой задачи может быть ускорен с помощью meet-in-the-middle. Нужно всего лишь вычислить количество половинок (пред)гамильтоновых циклов, а затем замкнуть все подходящие пары половинок.

Этим методом пользовался участник alexBlack. Я его тоже хотел применить, но вовремя одумался. Оптимизация по скорости всего в два раза, не заслуживает того, чтобы её применять, так как перехода от n=10 к n=11 она не даст. Надо применять только такие оптимизации, которые экономят либо память, либо память и время одновременно. Например, учет того, что симметричные разрезы можно хранить как один. То есть, (())() и ()(()) - это одно и тоже. Уже почти вдвое по памяти и по времени. В труднорешаемых задачах все, что не даёт разумного по времени перехода от n к n+1 за оптимизацию не считается. Если ускорять, то надо раз в 20.

[maxal]

Кстати, та же OEIS - прекрасный источник задач для подобных конкурсов:
http://oeis.org/search?q=keyword%3Ahard+keyword%3Amore

[Zealint]

Не совсем. Надо, чтобы задачу вообще никто не решал. Чтобы участники начинали с нуля. Если последовательность кто-то уже начал, то шансов получить следующее число уж очень мало (за редким исключением).

[Circiter]

Можно идиотский вопрос для самопроверки? Что будет ответом для решетки $3\times 3$? :)

[EtCetera]

Circiter в сообщении #368837 писал(а):

Что будет ответом для решетки $3\times 3$?

5:
1 цикл приходится на выколотую центральную вершину;
4 $\text{---}$ на дефекты в углах.

[maxal]

Zealint в сообщении #368674 писал(а):

Если последовательность кто-то уже начал, то шансов получить следующее число уж очень мало (за редким исключением).

Неправда ваша. Я лично вычислил новые члены порядка сотни hard последовательностей в OEIS. И это не предел.

[Zealint]

maxal в сообщении #368872 писал(а):

Неправда ваша. Я лично вычислил новые члены порядка сотни hard последовательностей в OEIS. И это не предел.

Это я понимаю. Я не о том. Маловероятно, что это сможет сделать ЛЮБОЙ участник конкурса. Надо делать так, чтобы начинать пришлось с нуля, чтобы каждый школьник мог начать. А если сразу что-то сложное дать, то многие отвалятся, не начав. Это все-таки массовый конкурс.

[maxal]

Zealint в сообщении #368937 писал(а):

Маловероятно, что это сможет сделать ЛЮБОЙ участник конкурса.

То же самое можно сказать о задаче с вашего последнего конкурса.

И вообще, например, в процессе конкурса вы указывали найденные на данный момент количества циклов, и чтобы победить, нужно было вычислить их же для больших $n$. Чем эта ситуация отличается от подобной, где количества циклов были бы изначально указаны виде последовательности в OEIS? Я не вижу отличий.

Так что, либо массовость, либо сложные задачи, интересные только "продвинутым" участникам.

[Zealint]

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

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