2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу 1, 2  След.
 
 Knights Tours
Сообщение04.08.2011, 20:37 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Интереснейшая древняя задача!

Непересекающиеся (замкнутые и назамкнутые) маршруты шахматного коня на досках размера mxn. Задачей занимаются, кажется, с 1930 г. Не густо с результатами за 80 лет :-)

Для ознакомления:
http://euler.free.fr/knight/

На форуме Портала ЕН веду тему по этой задаче:
http://e-science.ru/forum/index.php?sho ... 32643&st=0

В основном активны трое (считая ведущую). Однако сделано немало. Составлена уникальная база данных (около 1000 маршрутов). БД создана и пополняется по программе. Доступна всем!

Продолжаются поиски новых результатов. Анализируются максимальные результаты, ищутся закономерности.

Не нашла в Интернете незамкнутых маршрутов (замкнутые пока особо не искала) на полях 17х17, 20х20, 21х21, 22х22, 25х25. Мной получены симметричные маршруты на полях 17х17, 19х19, 21х21 и 25х25. Но, конечно, вопрос максимальности открыт.

Интересно подумать над общей формулой для $C(n,m)$ - максимальное количество ходов на поле nxm.

Я получила (эмпирическим путём) несколько частных формул, например:

$C(3,m)=m+1$ (m>6)
$C(4,m)=2m-3$ (m>3)
$C(6,m)=4m-9$ (m>10)
$C(7,m)=5m-11$ (m>9)

Однако формулы не доказаны. Думаю, что и для следующих n есть подобные формулы.

Предлагаю форумчанам подключиться к решению задачи.

В OEIS есть две последовательности: замкнутые и незамкнутые маршруты - A003192, A157416.

Один из моих последних результатов - симметричный незамкнутый маршрут на поле 18х19, 249 ходов (результат получен с ипользованием результата svb на поле 11х12):

Изображение

P.S. Почему тема в "Свободном полёте"? По аналогии :D Тема несерьёзная и в серьёзных тематических разделах ей, пожалуй, не место. На форуме Портала ЕН тема тоже во Флейме. Так-то оно лучше!

 Профиль  
                  
 
 Re: Knights Tours
Сообщение05.08.2011, 08:52 


24/05/09

2054
Вы вручную это рисуете, или компьютерная программа вычисляет?

 Профиль  
                  
 
 Re: Knights Tours
Сообщение05.08.2011, 09:02 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Я сама программу не писала. Сначала (на маленьких досках) рисовала вручную, очень нравится это занятие :-)

Потом коллеги svb и alexBlack сделали программы. Они получают маршруты по программе.
Интересно, что многие симметричные (незамкнутые) маршруты могут переноситься на бОльшие доски по аналогии, что я и делаю сейчас.
Например, размножается симметричный маршрут с поля 11х12, полученный svb по программе (87 ходов). При размножении таких маршрутов появилась задача доработки углового фрагмента. Сначала я решала эту задачу вручную. Потом alexBlack сделал программу для решения этой задачи, теперь пользуюсь программой.

Точно так же размножила симметричный маршрут с поля 15х15, найденный в Интернете. Этот маршрут размножается на поля с шагом 2, то есть на поля: 17х17, 19х19, ..., 25х25 и т. д.

 Профиль  
                  
 
 Re: Knights Tours
Сообщение06.08.2011, 14:39 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
На форуме Портала ЕН один товарищ высказал следующее:

Цитата:
Для не пересекающихся ходов. Прямоугольник 3х2 представить исходным паркетом.
Далее вырезать и склеивать до тех пор пока он не будет похож на сложный многоугольник приближающийся до диагональной линии. Это будет конечный продукт. Далее эти готовые паркетины последовательно складывать друг другом . Тогда задача будет решаться быстро и в уме для любой доски.

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

Кто-нибудь знает "теорию паркетов" настолько, чтобы показать её применение к данной задаче.
Ну, например, сделать маршрут на поле 17х17 или на поле 20х20, да не просто маршрут, а близкий к максимальному.

 Профиль  
                  
 
 Re: Knights Tours
Сообщение11.08.2011, 22:19 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
alexBlack создал уникальную базу маршрутов (замкнутых и незамкнутых) он-лайн.

Цитата:
Работает он-лайн версия базы маршрутов.
http://alexblack.wallst.ru/UncrossedKni ... /index.php

В конце страницы можно скачать и офф-лайн копию.

Приносите в БД свои результаты, у кого они есть :wink:

 Профиль  
                  
 
 Re: Knights Tours
Сообщение12.09.2011, 15:14 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Ах, как много маршрутов сделали форумчане :-)
Не получается? Не интересно?
Ну что за напасть: что ни тема у меня, то все ходят мимо :-(

Пришла сообщить, что у базы маршрутов изменился адрес:
http://ukt.alex-black.ru/

Ну и задачку одну напишу. Я что-то застряла на этом маршруте.
Известно, что многие маршруты (но вот все ли?) элементарно переносятся с поля на поле с шагом 8, например, с поля 20х24 на поле 12х16:

Изображение

Изображение

А теперь требуется перенести маршрут с поля 12х16 на поле 20х24.
Исходный маршрут на поле 12х16 такой:

Изображение

Может быть, кто-нибудь нарисует подобный маршрут на поле 20х24 :-)

Подробнее см. в теме на Портале ЕН (ссылка выше).

 Профиль  
                  
 
 Posted automatically
Сообщение04.11.2013, 01:47 
Основатель
Аватара пользователя


11/05/05
4312
 i  Тема перемещена из форума «Свободный полёт» в форум «Олимпиадные задачи (CS)»
Причина переноса: не указана.

 Профиль  
                  
 
 Re: Knights Tours
Сообщение24.03.2015, 11:27 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Новость отличная!
В БД alexBlack поступили новые решения.

Пришли они из Франции от Bernard Lemaire. Он пишет, что все свои маршруты построил вручную ещё до 1990 г. Здорово! Почти все его решения лучше тех, что уже имеются в БД для данных размеров досок.

С декабря 2011 г. в БД было затишье, никто не вводил новых результатов.

Эх, интереснейшая задача и решать там ещё очень много надо. К сожалению, мне надо заниматься квадратами и кубами, не могу уделить время турам коня :-(
Предлагаю задачу всем, кто ищет интересные задачи.
Задача хороша тем, что её можно решать на листе бумаги без всяких программ, как это делал Bernard.
А можно и с помощью программы. Одно другому не мешает. Я, например, использовала программу на завершение маршрута, а начинала его вручную по аналогии с каким-нибудь известным решением. С одного угла начинаем, а в противоположном углу уже по программе ищем хорошее окончание маршрута.

На форуме ПЕН есть большущая тема, где автор проекта alexBlack разрабатывал теорию, а мы с svb ему помогали в практической реализации. БД была создана приличная, но по замкнутым маршрутам решений очень мало.

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

 Профиль  
                  
 
 Re: Knights Tours
Сообщение30.03.2015, 10:32 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Восторг! Шедевр!

Цитата:
28×28, closed with 90° rotational symmetry, 580 moves, by George Jelliss (21 March 2015).

Смотрите здесь.

Мне сообщил об этом решении Bernard Lemaire.

 Профиль  
                  
 
 Re: Knights Tours
Сообщение31.03.2015, 07:26 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Шедевр George Jelliss уже внесён в БД alexBlack

тут

 Профиль  
                  
 
 Re: Knights Tours
Сообщение01.04.2015, 09:58 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Это так красиво!
Не могу удержаться, покажу ещё два новых маршрута George Jelliss.
Это замкнутые маршруты на доске 16х16; они проигрывают маршруту R. Merson (1991 год) по количеству ходов (164 против 172), но зато как красиво! Симметрия!
Мне всегда очень нравились именно симметричные маршруты, я построила немало таких незамкнутых маршрутов, все они есть в БД. Смотрите!

Изображение

Пользоваться БД очень просто. Кликаете в таблице на нужную доску мышкой и маршрут открывается со всеми характеристиками.

Я от души поздравляю alexBlack! Созданная им БД стала поистине международной.

 Профиль  
                  
 
 Re: Knights Tours
Сообщение01.04.2015, 16:06 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
Правда очень красивые решения и интересная задача. Задача напоминает соревнование Al Zimmerman - Snakes on a Plane (http://recmath.com/contest/Snakes/index.php). Там тоже надо было замкнутые туры найти. У Hugo Pfoertner есть сайт с новыми результатами: http://www.enginemonitoring.net/azpc/zz ... esults.htm. Советую с ним попробовать связаться, а также с Hermann Jurksch и Markus Sigg. Я может тоже подключусь когда появится время.

Кстати какие из результатов оптимальные, а какие еще можно (теоретически) улучшить? Просто не хочется зря терять время улучшая оптимальные результаты.

 Профиль  
                  
 
 Re: Knights Tours
Сообщение01.04.2015, 16:20 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
dimkadimon в сообщении #998926 писал(а):
Кстати какие из результатов оптимальные, а какие еще можно (теоретически) улучшить? Просто не хочется зря терять время улучшая оптимальные результаты.

Так ведь в БД все результаты есть. По крайней мере те, которые известны автору БД alexBlack.
Заходите в БД, смотрите результаты, добавляйте свои.

А, или вас интересует доказательство оптимальности? Ну, это вопрос сложный. Есть большая теория, есть на форуме ПЕН тема, где я, svb и alexBlack занимались теоретическим исследованием задачи. Но до конца мы вряд ли всё исследовали.

 Профиль  
                  
 
 Re: Knights Tours
Сообщение01.04.2015, 16:36 


02/05/10
26
dimkadimon в сообщении #998926 писал(а):
Кстати какие из результатов оптимальные, а какие еще можно (теоретически) улучшить? Просто не хочется зря терять время улучшая оптимальные результаты.

В таблицах на сайте белым цветом выделены доски для которых был сделан полный перебор.
Для квадратных досок есть A157416 и A003192.

 Профиль  
                  
 
 Re: Knights Tours
Сообщение02.04.2015, 01:17 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
alexBlack в сообщении #998943 писал(а):
dimkadimon в сообщении #998926 писал(а):
Кстати какие из результатов оптимальные, а какие еще можно (теоретически) улучшить? Просто не хочется зря терять время улучшая оптимальные результаты.

В таблицах на сайте белым цветом выделены доски для которых был сделан полный перебор.
Для квадратных досок есть A157416 и A003192.

Если у вас есть результаты полного перебора для квадратных досок (до n=31), то почему нельзя сделать полный перебор для остальных досок? Или для квадратных досок задачу легче решить?

Кстати можно добавить ваши результаты в A157416 и A003192.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 24 ]  На страницу 1, 2  След.

Модераторы: Karan, Toucan, PAV, maxal, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group