| Математический форум Math Help Planet http://mathhelpplanet.com/ |
|
| Ортогональные латинские квадраты 10-го порядка http://mathhelpplanet.com/viewtopic.php?f=57&t=46638 |
Страница 45 из 421 |
| Автор: | Nataly-Mak [ 28 фев 2016, 20:41 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
Предлагаю начать с простой задачки. Берём в качестве исходного ДЛК Брауна 0 8 5 1 7 3 4 6 9 2 Нет у нас пока всех его трансверсалей. Сколько всех, мы не знаем. Надо их искать, но я пока не знаю, как писать программу, хотя знаю, как их искать вручную. Зато могу предложить набор из 46 трансверсалей, тут есть найденные мной вручную и найденные по программе Алексея (по известным ортогональным парам). Вот эти трансверсали: ▼
Вот такой небольшой набор, всего 46 трансверсалей. Попробуйте написать программу, которая выберет из этого набора ровно 4 комплекта из 10 непересекающихся трансверсалей. Они тут есть. На простой задаче легче просекать пути решения. Надо придумать методу и не одну. И каждую опробовать на этом простом примере. Посмотреть, какая будет лучше работать. Первый этап - нахождение всех трансверсалей пока пропустила. Но там, как мне кажется, проще. Я вот даже визуально нашла 8 трансверсалей. Это же и вручную понятно, как искать. Двигаемся по строкам сверху вниз и выбираем элементы в лексикографическом порядке. Или же выбор удачно завершится до последней строки, или же зайдём в тупик. |
|
| Автор: | ivashenko [ 28 фев 2016, 20:45 ] | |||||||||||||||||||||||||
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка | |||||||||||||||||||||||||
Есть ЛК: 1,2,3,4 2,1,4,3 3,4,1,2 4,3,2,1 и ортогональный ему: 1,2,3,4 3,4,1,2 4,3,2,1 2,1,4,3 Выпишем все трансверсали первого ОЛК: 1,3,4,2 1,4,2,3 2,4,3,1 2,3,1,4 3,1,2,4 3,2,4,1 4,2,1,3 4,1,3,2 Всего нашлось их 8, поправьте если не так. Нетрудно найти непересекающиеся трансверсали: 1,3,4,2 3,1,2,4 2,4,3,1 4,2,1,3 Однако нам необходимо найти их с помощью метода, а не простым перебором. Точнее необходимо придумать эффективный метод. Рассортируем все 8 трансверсалей следующим образом: В первый столбец поместим трансверсали отсортированные по первому разряду, а в первую строку- отсортированные по значениям второго разряда, на пересечении строк и столбцов запишем пересечение множеств в соответствующих ячейках:
На второстепенной диагонали 4 непересекающиеся трансверсали, вне нее еще одно множество из 4-х непересекающихся трансверсалей. На главной диагонали располагаются тривиальные нули. Нужно пробовать еще для других квадратов и искать закономерность. Может это конечно и просто совпадение. |
||||||||||||||||||||||||||
| Автор: | Nataly-Mak [ 28 фев 2016, 21:00 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
ivashenko у вас неплохо получилось с ЛК 4-го порядка. Вы видели ссылку на книгу Кнута на русском языке? (svb выложил) Мне коллега Белышев пишет, чтобы я смотрела в этой книге алгоритм "танцующих связей". Там описывается, как из всех 808 трансверсалей выбрать 10 непересекающихся. Это быстро делается. И в этом наборе из 808 трансверсалей есть только один комплект из 10 непересекающихся трансверсалей. Значит, есть только один ЛК ортогональный данному. Но я и сама ещё не начинала разбираться с этим алгоритмом. Посмотрите, я думаю, у вас получится. Avgust, bimol и вы тоже посмотрите. Ну, должны же мы осилить этот метод. Паркер за 45 минут решал эту задачу на машине 50 лет назад. |
|
| Автор: | bimol [ 28 фев 2016, 21:10 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
Стал смотреть как в книге Кнута строится первая трансверсаль 0214365897. Если строить слева направо как в книге то 5 и 7 в одной строке, если сверху вниз то 14 в одном столбце. Что за выверт. Возвращаюсь к построению Т у Брауна |
|
| Автор: | Nataly-Mak [ 28 фев 2016, 21:14 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
svb писал(а): Приятное чтение (на русском) для вхождения в историю латинских квадратов: Д.Кнут, т.4А Я скачала книгу, пошла читать Да, сейчас ещё выложу ссылку, которую мне Алексей прислал, на алгоритм "танцующих связей" в Википедии. Потанцуем?
|
|
| Автор: | bimol [ 28 фев 2016, 21:22 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
Вот что выдает моя корявая программа для Брауна Может на этот раз хоть трансверсали правильные |
|
| Автор: | Nataly-Mak [ 28 фев 2016, 21:23 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
bimol писал(а): Стал смотреть как в книге Кнута строится первая трансверсаль 0214365897. Если строить слева направо как в книге то 5 и 7 в одной строке, если сверху вниз то 14 в одном столбце. Что за выверт. Возвращаюсь к построению Т у Брауна Да, плохо, что у Кнута трансверсали строятся по столбцам. Я уже привыкла двигаться по строкам сверху вниз и перепривыкать трудно Буду и дальше так искать.Но, в принципе, от этого ничего не должно измениться, трансверсалей должно быть столько же. Ну, а потом из них выбираем непересекающиеся. |
|
| Автор: | Nataly-Mak [ 28 фев 2016, 21:26 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
bimol писал(а): Вот что выдает моя корявая программа для Брауна Уточните, пожалуйста, какой у вас Браун - нормализованный или нет? Я проверю трансверсали. |
|
| Автор: | bimol [ 28 фев 2016, 21:28 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
Чтобы не путаться, стал искать как на этой странице, изначальный не нормализованный. |
|
| Автор: | Nataly-Mak [ 28 фев 2016, 21:30 ] |
| Заголовок сообщения: | Re: Ортогональные латинские квадраты 10-го порядка |
Здесь алгоритм "танцующих связей" https://en.wikipedia.org/wiki/Dancing_Links Здесь пример реализации https://github.com/blynn/dlx Эх-ма, всё на английском Ну, тут все вроде читают по-английски, кроме меня. |
|
| Страница 45 из 421 | Часовой пояс: UTC + 3 часа [ Летнее время ] |
| Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group http://www.phpbb.com/ |
|