Нестандартная задача для программистов

[Nataly-Mak]

Добрый день, уважаемые форумчане!

Думаю, среди вас есть много программистов.
Хочу предложить хорошую задачку.

Ну, чтобы не делать копипаст, даю ссылку, где задача подробно сформулирована:
http://e-science.ru/forum/index.php?showtopic=34163
(это очень близкий форум ПЕН).

Задачка относится к теме "Knight's tours" (см. тему там же, рядом с задачей). Я давно веду эту тему. Разработаны алгоритмы создания маршрутов. Коллега по задаче А. Чернов создал уникальную базу маршрутов, которая работает в режиме он-лайн:
http://ukt:alex-black.ru/
Сейчас в базе более 1000 маршрутов, но многие из них не максимальные и требуют улучшения.

Вот для работы с маршрутами и нужна модификация программы.
Программа уже существует, но она не делает всего того, что мне нужно.
Исходник программы выложен на форуме. Могу прислать и исполняемую программу, чтобы посмотреть работу программы.

Если задача кого-нибудь заинтересует, пишите. Можно здесь, можно на ПЕН, можно в личку.

На этом форуме тоже есть тема о данной задаче, но по сравнению с темой на ПЕН она, как комарик по сравнению с бегемотом

[Circiter]

Простите, если немного не в тему, но не известно ли вам, каков на данный момент прогресс в аналитическом подсчете количества (незамкнутых) маршрутов коня?

[Zealint]

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

ростите, если немного не в тему, но не известно ли вам, каков на данный момент прогресс в аналитическом подсчете количества (незамкнутых) маршрутов коня?

Если вы имеете в виду любые простые маршруты, а не те, что предлагает автор темы, то для произвольных размеров доски $m\times n$ ответ неизвестен и скорее всего он не представим в виде d-конечной функции (считайте, не может быть выписан аналитически вообще). Если зафиксировать параметр $m$, то легко можно получить последовательность решений для произвольного $n$, когда число $m$ не очень велико, так как очевидно, что решение выписывается в виде рекуррентного соотношения. Я не видел ответов по этой задаче, но про циклы шахматного коня ответ известен для $m\leq4$ (по-моему). Не буду сейчас искать ссылки, но вот гамильтоновы циклы для $m=3$ есть здесь A070030.

К сожалению, простой случай доски $8\times 8$ до сих пор не решён. Уже несколько лет жду, когда кто-нибудь это сделает; ещё год подожду и предоставляю свой ответ, а то надоело... Эта нелепая фраза из википедии:

Цитата:

В то же время задача подсчёта всех возможных незамкнутых маршрутов значительно сложнее и не решена до сих пор

слегка выводит из себя именно выражением "значительно сложнее". Я бы написал "немногим более сложна".

[Nataly-Mak]

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

Простите, если немного не в тему, но не известно ли вам, каков на данный момент прогресс в аналитическом подсчете количества (незамкнутых) маршрутов коня?

Какого количества? Досок разных размеров бесконечно много. Соответственно и маршрутов бесконечно много. Или вас интересует количество разных (максимальных) маршрутов на доске одного конкретного размера?

Я тут в предыдущем посте дала ссылку на базу маршрутов, к сожалению, с ошибкой, правильно так:
http://ukt.alex-black.ru/
Кроме того, в теме на ПЕН (ссылка дана в теме о маршрутах коня "Knight's tours") приведены полученные формулы для вычисления максимальной длины пути для некоторых размеров досок.

[Circiter]

Ух-ты, я даже и подумал, что доски рассматривают в том числе и нестандартные, я то про обычную шахматную говорил, $8\times 8$. :)

2Zealint

Цитата:

ещё год подожду и предоставляю свой

Ничего себе. Как же вы можете ждать? Я бы не усидел бы на месте. :) Ну а, скажем, хотя-бы само число незамкнутых маршрутов для стандартной доски вы тоже пока не собираетесь сообщать (пусть даже без доказательства)? Жаль... Ведь пока есть только грубая верхняя оценка и всё...

[Zealint]

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

Ничего себе. Как же вы можете ждать? Я бы не усидел бы на месте. :) Ну а, скажем, хотя-бы само число незамкнутых маршрутов для стандартной доски вы тоже пока не собираетесь сообщать (пусть даже без доказательства)? Жаль... Ведь пока есть только грубая верхняя оценка и всё...

Может вы меня неправильно поняли... у меня нет строгих аналитических доказательств, какие приняты в математике. У меня нет даже числа, но я знаю, как его легко посчитать на компьютере (я решил множество подобных задач и для более большой доски, не решённых ранее). Просто пока не располагаю временем на решение упражнений для студентов 2-3 курса, занимающихся программированием. Чуть меньше чем через год такое время может появиться, тогда почти сразу за этим появится и число. Из списка нерешённых задач такого типа, эта является наиболее простой, поэтому я как раз жду, что именно её решат в первую очередь, сам сейчас занимаюсь более сложными.

А чисто с философской точки зрения, само по себе число ради числа мало интересно. Интересны методы вычислений, либо интерпретация полученных данных в контексте уже имеющегося знания. Поскольку метод получения числа незамкнутых маршрутов мне кажется чуть ли не тривиальным, а как интерпретировать это число (какие новые знания оно даёт), мне пока непонятно, постольку считаю задачу неинтересной с данных позиций.

[Circiter]

2Zealint
Надо ли полагать, что, учитывая акцент на почти тривиальности подсчета (и даже его доступности студентам-программистам), ваш подход основан на сведении задачи подсчета незамкнутых маршрутов к уже решенной задаче о количестве гамильтоновых циклов на графе коня над стандартной доской? Например, известна идея, заключающаяся в добавлении к графу коня ещё одной вершины, соединенной со всеми остальными 64-мя вершинами, с последующим счетом гамильтоновых циклов уже в полученном графе... Или же намеки на ваше видение возможного решения следует искать в ваших недавних отжигах по физике полимеров?

Кстати, спасибо за ваши ответы в этой теме. Мне вот одно время эта задача была очень-очень интересна (самостоятельно продвинуться, конечно, нисколечки не удалось), но последнее время я уже не слежу за её прогрессом; думал, что, возможно, дело сдвинулось с места...

[Zealint]

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

2Zealint
Надо ли полагать, что, учитывая акцент на почти тривиальности подсчета (и даже его доступности студентам-программистам), ваш подход основан на сведении задачи подсчета незамкнутых маршрутов к уже решенной задаче о количестве гамильтоновых циклов на графе коня над стандартной доской? Например, известна идея, заключающаяся в добавлении к графу коня ещё одной вершины, соединенной со всеми остальными 64-мя вершинами, с последующим счетом гамильтоновых циклов уже в полученном графе... Или же намеки на ваше видение возможного решения следует искать в ваших недавних отжигах по физике полимеров?

Нет, интерпретировать мои слова нужно не более чем как амбиции, а искать причину этих амбиций не следует ни в физике полимеров, ни в добавлении вершины к графу шахматного коня [ ну зачем же так граф портить? : ) ]. Возможно, я ошибаюсь, и задачу недаром никто поднять не смог... (было бы наивно полагать, что все такие глупые вокруг)

Хотя такого раньше не было - я всегда заранее знал, решу задачу или нет и никогда не ошибался. Если я вижу, что задача неподъёмная, то это как-то сразу понятно. Несколько раз я ошибался, называя простую задачу неподъемной. А вот когда мне кажется, что задача решается просто, то значит так оно и есть. Когда сяду за её решение, сообщу сюда в первую очередь, или признаюсь, что был по отношению к ней неправ, но получение новых результатов (пусть не для $8\times8$, а например для $6 \times n\,\forall n$ могу гарантировать, если никто раньше их не получит, что было бы неплохо).

(отжиг)

Не совсем понятно слово "отжиг" - то ли намёк на то, что я занимаюсь ерундой, то ли ещё на что-то. Мы ведь в разных школах учились, и одинаковые бытовые выражения применяли в разных ситуациях... И что именно я отжёг по физике полимеров, тоже непонятно. Там есть 5-6 любопытных результатов, но отжигом их называть я бы не стал

Цитата:

Кстати, спасибо за ваши ответы в этой теме. Мне вот одно время эта задача была очень-очень интересна (самостоятельно продвинуться, конечно, нисколечки не удалось), но последнее время я уже не слежу за её прогрессом; думал, что, возможно, дело сдвинулось с места...

Не за что. Меня удивило только то, что вы про шахматные доски отличного от стандарта размера ничего не думали.

[Circiter]

2Zealint

Цитата:

Когда сяду за её решение, сообщу сюда в первую очередь

Было бы замечательно. Не то что бы задача неподъемная, но, очевидно, какие-то грабли там есть...

Цитата:

А чисто с философской точки зрения, само по себе число ради числа мало интересно

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

А может число маршрутов коня специалисты ещё не подсчитали исключительно из-за лени или нежелания тратить время на результат, который и так вот-вот кто-нибудь получит? Не понятно... Циклы подсчитали, а незамкнутые пути нет. Странно (наверное, сама эта гамильтоновость сильно мешает, это же не просто матрицу в степень возвести как при поиске циклов, тут и мозгом повредиться можно).

Цитата:

ни в добавлении вершины к графу шахматного коня [ ну зачем же так граф портить? : ) ]

Ну в нем и так есть некрасивости, нерегулярности из-за края доски... Делов-то, ещё одну клетку к доске пририсовать. :) Впрочем, я не знаю, стоит ли этот подход внимания. Я попробовал покопать в эту сторону, но ничего не получилось. Вообще, это же вроде стандартный прием поиска путей в графе имея только алгоритм поиска циклов.

(Оффтоп)

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

[Zealint]

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

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

Ну так а что делать, если, например, формула состоит из 30 миллионов символов? Кто её будет доказывать с карандашом в руке? А у меня одна такая формула есть и есть еще несколько чуть поменьше. В перечислительной комбинаторике почти всё, что можно было легко решить на бумаге, уже решили, теперь в ход идут чисто вычислительные доказательства. Причём доказать строго, что программа на тысячу строк работает правильно, насколько мне известно, невозможно. Мне кажется, это чисто философская проблема - нужно переосмыслить наши представления о том, что такое доказательство и в каких случаях считать что-то правильным. Например, задача про n ферзей A000170 для n=26 была решена, но считать ответ правильным начали после того, как кто-то другой получил такое же число. А кто докажет?

Цитата:

А может число маршрутов коня специалисты ещё не подсчитали исключительно из-за лени или нежелания тратить время на результат, который и так вот-вот кто-нибудь получит? Не понятно... Циклы подсчитали, а незамкнутые пути нет.

Может быть. Только вот я не специалист, поэтому жду, когда именно специалисты назовут ответ, чтобы у них хлеб не отбирать : ) . Я просто любитель, решаю только то, что хочу и когда хочу. Вроде моего друга из Чехии, который всякие шахматные задачи решает в своё удовольствие. Вот тут есть его книга (слева кнопка "Problems", потом справа книга "Non-attacking chess pieces"), где собраны результаты. В следующем издании там появятся ещё некоторые мои формулы и даже данные, полученные участниками моих конкурсов по программированию.

Цитата:

Вообще, это же вроде стандартный прием поиска путей в графе имея только алгоритм поиска циклов.

Так-то оно так, но поиск циклов и подсчёт циклов - совершенно разные задачи. А ещё все зависит от подхода. Может быть добавление вершины чем-то поможет, но мне оно пока мешает. Представьте, было 64 клетки (красиво), а стало 65 (ужасно). Один лишний бит всю картину портит. Вместо 64 битового числа в некоторых алгоритмах нужно заводить 65 битовое - это же ужас! А с точки зрения других - это нарушает красивую симметричную структуру графа.

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

[alexBlack]

Извините, что поднимаю старую тему, но есть некоторые результаты по этой проблеме (речь идет об A165134), а поскольку здесь уже было обсуждение этого вопроса, нет смысла создавать новую.

Мне удалось посчитать количество незамкнутых маршрутов для доски 8x8, но есть некоторые сомнения в результате. А именно: на страничке Guenter Stertenbrink приведены данные по количеству маршрутов для доски 8x8 (в том числе) с фиксированными окончаниями. Во-первых, часть данных для доски 8x8 там отсутствует и хотелось бы независимого подтверждения, а, во-вторых, одно значение не совпадает с тем, которое получено мной. Пересчитать это значение другим методом я пока не могу.

Алгоритм, который был применен, и результаты приведены здесь.

Если есть способ посчитать маршруты проще, хотелось бы о нем услышать.

[cepesh]

Тема перемещена из форума «Программирование» в форум «Олимпиадные задачи (CS)»
Причина переноса: не указана.