2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

Если Вы зададите новый вопрос в существующей теме, то в случае нарушения оформления или других правил форума Ваше сообщение и все ответы на него могут быть удалены без предупреждения.

Не ищите на этом форуме халяву, правила запрещают участникам публиковать готовые решения стандартных учебных задач. Автор вопроса обязан привести свои попытки решения и указать конкретные затруднения.

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



Начать новую тему Ответить на тему На страницу Пред.  1 ... 6, 7, 8, 9, 10, 11  След.
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение05.07.2015, 19:50 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
whitefox
вы в анализе типов покрытий исходили из того, чтобы два покрытия могли быть ортогональными :?:

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение05.07.2015, 19:59 
Заслуженный участник
Аватара пользователя


19/12/10
1539
Nataly-Mak в сообщении #1033883 писал(а):
вы в анализе типов покрытий исходили из того, чтобы два покрытия могли быть ортогональными :?:

Это все возможные типы покрытий. Теперь нужно рассмотреть какие из них могут быть ортогональны друг другу.

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение05.07.2015, 20:21 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Ну, это только вы можете рассмотреть.
У меня на это мозгов не хватает :?

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение05.07.2015, 20:26 
Заслуженный участник
Аватара пользователя


19/12/10
1539
Ну у Вас же есть программа которая для известного точного покрытия находит ортогональное. Здесь всё тоже самое только проще.

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение05.07.2015, 20:35 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
У меня программа тупо находит к данному покрытию ортогональное.
А в ваших типах ещё разобраться надо :-)

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение06.07.2015, 07:43 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Мысли вслух...
всего шаблонов 6814416. Если есть 16 симметрий, то не эквивалентных шаблонов 425901.
Каждому шаблону теоретически соответствует идеальный квадрат, а значит, комплект из 4-х точных попарно ортогональных покрытий. Следовательно, всего будет 425901 типов таких комплектов.

Таким образом, мы имеем модель каждого теоретически возможного (потенциального) комплекта из 4-х точных попарно ортогональных покрытий массива. Осталось проверить каждую модель на существование реального комплекта :-)

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение06.07.2015, 09:09 
Заслуженный участник
Аватара пользователя


19/12/10
1539
Некоторые из шаблонов могут оказаться самосимметричными, поэтому общее число существенно различных шаблонов может оказаться несколько больше. Зато типов различных комплектов будет существенно меньше, так как многим шаблонам будет соответствовать один и тоже набор типов покрытий.

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение06.07.2015, 22:12 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Nataly-Mak в сообщении #1034044 писал(а):
Таким образом, мы имеем модель каждого теоретически возможного (потенциального) комплекта из 4-х точных попарно ортогональных покрытий массива.

Пример модели комплекта из 4-х точных попарно ортогональных покрытий массива

Код:
#1
1 1 3 4 4 4 4 4 4
1 3 3 3 3 4 4 4 4
1 1 1 1 1 3 3 4 4
1 3 3 3 3 4 4 4 4
1 1 1 3 3 3 4 4 4
1 3 3 3 3 4 4 4 4
1 1 1 1 1 3 3 4 4
1 3 3 3 3 4 4 4 4
1 1 3 3 3 3 3 3 4

#2
1 3 3 3 3 4 4 4 4
1 1 1 1 4 4 4 4 4
1 1 3 4 4 4 4 4 4
1 1 1 3 3 3 4 4 4
1 3 3 3 3 4 4 4 4
1 1 1 3 3 3 4 4 4
1 1 3 3 3 3 3 3 4
1 1 1 1 3 3 3 3 3
1 3 3 3 3 4 4 4 4

#3
1 1 3 3 3 3 3 3 4
1 1 1 3 3 3 4 4 4
1 3 3 3 3 4 4 4 4
1 3 3 3 3 4 4 4 4
1 1 1 1 1 1 1 3 4
1 3 3 3 3 4 4 4 4
1 3 3 3 3 4 4 4 4
1 1 1 3 3 3 4 4 4
1 1 3 4 4 4 4 4 4

#4
1 1 1 3 3 3 4 4 4
1 1 1 3 3 3 4 4 4
1 1 1 3 3 3 4 4 4
1 3 3 3 3 4 4 4 4
1 3 3 3 3 4 4 4 4
1 3 3 3 3 4 4 4 4
1 1 1 3 3 3 4 4 4
1 1 1 3 3 3 4 4 4
1 1 1 3 3 3 4 4 4

Задача
найти реальный(е) комплект(ы) попарно ортогональных покрытий по приведённой модели (массив реальных чисел приведён выше, см. стартовый пост).

Данная модель покрытий соответствует реальному решению с $S=12249$ с дырками (то есть не все элементы в решении принадлежат заданному массиву).

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

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение07.07.2015, 06:34 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Найти реальное точное покрытие, соответствующее этому шаблону,

Код:
#1
1 1 3 4 4 4 4 4 4
1 3 3 3 3 4 4 4 4
1 1 1 1 1 3 3 4 4
1 3 3 3 3 4 4 4 4
1 1 1 3 3 3 4 4 4
1 3 3 3 3 4 4 4 4
1 1 1 1 1 3 3 4 4
1 3 3 3 3 4 4 4 4
1 1 3 3 3 3 3 3 4

просто. Таких покрытий будет очень много.
Например, возьмём решение с дырками, из которого получена модель комплекта из 4-х покрытий:

Код:
2699  281  809  1499  479  2633  389  911  2549
59  1571  2129  1493  2339  659  1613  2273  113
2591  1289  1901  191  1013  11  2693  101  2459
683  2069  1559  2411  2003  1439  773  743  569
1019*  179  431*  509  1361  2213  2291*  2543  1703*
2153  1979  1949  1283  719  311  1163  653  2039
263  2621  29  2711  1709  2531  821  1433  131
2609  449  1109  2063  383  1229  593  1151  2663
173  1811  2333  89  2243  1223  1913  2441  23

$K=2722$, $S=12249$
Заменим неправильные комплементарные пары (431,2291) и (1019,1703) на правильные пары соответственно - (641,2081) и (1619,1103). И нужное реальное покрытие готово.

Второе покрытие ортогональное заданному моя программа ищет тоже без проблем. Находит таких покрытий море.
Всё застопоривается на поиске третьего покрытия ортогонального каждому из двух покрытий. Не удалось ещё ни разу найти третье точное покрытие.

Сейчас попробую поиск по шаблонам покрытий (по модели комплекта из 4-х точных попарно ортогональных покрытий), начиная от показанного первого точного покрытия массива.

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение07.07.2015, 08:46 
Заслуженный участник
Аватара пользователя


19/12/10
1539
Вместо шаблонов точных покрытий можно взять шаблон квадрата. И постараться так назначить свободные переменные, чтобы десять из них были единицами, а троек и четвёрок было поровну (это обеспечит минимум вариантов для перебора). Тогда только для проверки одного этого шаблона потребуется проверить около $3{,}9\cdot10^{29}$ вариантов.

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение07.07.2015, 09:00 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
whitefox в сообщении #1034257 писал(а):
Вместо шаблонов точных покрытий можно взять шаблон квадрата.

Это я уже проходила. Было написано несколько программ по различным шаблонам (из вычетов по разным модулям).
Более того, в начале этой темы я показала, как можно "посадить" квадрат на 4 центральные цепочки; для этого была получена альтернативная общая формула идеального квадрата 9-го порядка. Увы! Это тоже не дало результатов.
Именно поэтому решила прибегнуть к поиску комплектов из 4-х точных попарно ортогональных покрытий массива.

Цитата:
Тогда только для проверки одного этого шаблона потребуется проверить около $3,9 \cdot 10^{29}$ вариантов.

Совсем немножко :-)

Нужна хорошая (!) программа проверки модели комплекта на предмет существования реального комплекта с такой моделью.
Повторюсь: если программа проверки одной модели будет работать порядка 10 секунд, тогда реально проверить все модели.
Конечно, сначала их надо ещё найти. Выше приведён пример одной модели.

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение07.07.2015, 23:07 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Уф! Что-то у меня сегодня программа не сразу получилась. А всё потому, что лень было писать заново и стала изменять старую программу, приспосабливая её к поиску по шаблону. Ну и вот: сколько раз убеждалась, что лучше написать программу с чистого листа, чем вносить изменения в старую программу.

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

Код:
#1
1 1 3 4 4 4 4 4 4
1 3 3 3 3 4 4 4 4
1 1 1 1 1 3 3 4 4
1 3 3 3 3 4 4 4 4
1 1 1 3 3 3 4 4 4
1 3 3 3 3 4 4 4 4
1 1 1 1 1 3 3 4 4
1 3 3 3 3 4 4 4 4
1 1 3 3 3 3 3 3 4

#2
1 3 3 3 3 4 4 4 4
1 1 1 1 4 4 4 4 4
1 1 3 4 4 4 4 4 4
1 1 1 3 3 3 4 4 4
1 3 3 3 3 4 4 4 4
1 1 1 3 3 3 4 4 4
1 1 3 3 3 3 3 3 4
1 1 1 1 3 3 3 3 3
1 3 3 3 3 4 4 4 4

Решение (показываю оба покрытия):

Код:
#1
2699  281  809  1499  479  2633  389  911  2549
59  1571  2129  1493  2339  659  1613  2273  113
2591  1289  1901  191  1013  11  2693  101  2459
683  2069  1559  2411  2003  1439  773  743  569
1619  179  641  509  1361  2213  2081  2543  1103
2153  1979  1949  1283  719  311  1163  653  2039
263  2621  29  2711  1709  2531  821  1433  131
2609  449  1109  2063  383  1229  593  1151  2663
173  1811  2333  89  2243  1223  1913  2441  23

#2
11  23  113  2213  2663  1499  1709  1949  2069
101  131  641  2441  449  1559  2039  2339  2549
311  1811  1433  569  809  1109  1619  2129  2459
191  821  1151  1493  2243  2543  389  1439  1979
29  89  659  719  1361  2003  2063  2633  2693
2531  1901  1571  1229  479  179  2333  1283  743
2411  911  1289  2153  1913  1613  1103  593  263
2621  2591  2081  281  2273  1163  683  383  173
2711  2699  2609  509  59  1223  1013  773  653

Надеюсь, что теперь всё правильно, тщательно не проверяла.

Второе покрытие нашлось быстро, примерно минут 5 (ну, вообще-то в свете обозначенных выше 10 секунд на проверку всей модели комплекта это безобразно долго :? ).
Завтра уже буду делать программу поиска третьего покрытия ортогонального каждому из этих двух.
У меня, как уже говорила, на каждый этап отдельная программа. А по-хорошему надо делать одну программу, причём так, чтобы работала она очень быстро.

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение08.07.2015, 07:47 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Ассоциативный квадрат

Код:
1499  2549  809  389  2633  479  911  281  2699
113  2339  2129  1493  659  1571  1613  2273  59
11  101  2459  191  2693  1901  1289  2591  1013
2069  1559  569  1439  2003  743  2411  683  773
2213  641  1619  2543  1361  179  1103  2081  509
1949  2039  311  1979  719  1283  2153  1163  653
1709  131  1433  821  29  2531  263  2621  2711
2663  449  1109  1151  2063  1229  593  383  2609
23  2441  1811  2243  89  2333  1913  173  1223

$K=2722$, $S=12249$

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

Итак, сейчас отправляюсь в поиск третьего точного покрытия ортогонального каждому из найденных двух и соответствующего следующему шаблону:

Код:
#3
1 1 3 3 3 3 3 3 4
1 1 1 3 3 3 4 4 4
1 3 3 3 3 4 4 4 4
1 3 3 3 3 4 4 4 4
1 1 1 1 1 1 1 3 4
1 3 3 3 3 4 4 4 4
1 3 3 3 3 4 4 4 4
1 1 1 3 3 3 4 4 4
1 1 3 4 4 4 4 4 4

Напомню: ещё ни разу мне не удалось в многочисленных экспериментах найти третье покрытие. До поиска четвёртого вообще дело не доходило (для заданного массива чисел). Но я ещё не искала 4 точных попарно ортогональных покрытия по модели (по четырём шаблонам комплекта).

И ещё раз для всех:
нужно сделать хорошую программу, которая будет очень быстро проверять модель комплекта на существование реальных 4-х покрытий, соответствующих этой модели.

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение09.07.2015, 00:05 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Ну вот и всё: данный вариант проверен полностью - третье покрытие не найдено (если не ошиблась в программе).
Но это только один вариант (одно первое точное покрытие --> одно второе точное покрытие --> третье точное покрытие; попарно ортогональные). А таких вариантов будет достаточно много.

Вывод: поиск комплекта покрытий по модели выполняется значительно быстрее и выполнить проверку модели комплекта можно за приемлемое время.

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

 Профиль  
                  
 
 Re: Метод точных попарно ортогональных покрытий массива
Сообщение09.07.2015, 10:29 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Решила протестировать программу поиска третьего покрытия.

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

Код:
#1
2699 281 809 1499 479 2633 389 911 2549
59 1571 2129 1493 2339 659 1613 2273 113
2591 1289 1901 191 1013 11 2693 101 2459
683 2069 1559 2411 2003 1439 773 743 569
1019 179 431 509 1361 2213 2291 2543 1703
2153 1979 1949 1283 719 311 1163 653 2039
263 2621 29 2711 1709 2531 821 1433 131
2609 449 1109 2063 383 1229 593 1151 2663
173 1811 2333 89 2243 1223 1913 2441 23

#2
173  2609  263  2153  1019  683  2591  59  2699
1811  449  2621  1979  179  2069  1289  1571  281
2333  1109  29  1949  431  1559  1901  2129  809
89  2063  2711  1283  509  2411  191  1493  1499
2243  383  1709  719  1361  2003  1013  2339  479
1223  1229  2531  311  2213  1439  11  659  2633
1913  593  821  1163  2291  773  2693  1613  389
2441  1151  1433  653  2543  743  101  2273  911
23  2663  131  2039  1703  569  2459  113  2549

Эти реальные покрытия соответствуют тестируемой модели комплекта.
Программа выполняется полностью (полный перебор!) и выдаёт несколько эквивалентных третьих покрытий, то есть фактически всего одно:

Код:
#3
191  281  173  1163  1433  2003  2213  2663  2129
131  1811  2291  653  1013  1493  809  1439  2609
11  263  773  2333  2543  449  1499  2039  2339
101  1613  2063  2243  2633  29  569  1019  1979
23  311  821  1151  1361  1571  1901  2411  2699
2621  1109  659  479  89  2693  2153  1703  743
2711  2459  1949  389  179  2273  1223  683  383
2591  911  431  2069  1709  1229  1913  1283  113
2531  2441  2549  1559  1289  719  509  59  593

Теперь осталось написать программу поиска четвёртого точного покрытия по заданным трём и заданной модели покрытия и довести тестирование до конца.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 153 ]  На страницу Пред.  1 ... 6, 7, 8, 9, 10, 11  След.

Модераторы: Модераторы Математики, Супермодераторы



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

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


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

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