Алгоритм поиска псевдотроек


Advanced search

Message boards : Science : Алгоритм поиска псевдотроек

AuthorMessage
Nataly-Mak
Send message
Joined: Jan 25 16
Posts: 26
Credit: 1,050
RAC: 0
Message 853 - Posted 26 Jan 2016 17:22:47 UTC

    Last modified: 26 Jan 2016 17:27:28 UTC

    Здравствуйте!

    В 2009 году я разработала алгоритм поиска пар ортогональных латинских квадратов 10-го порядка, основанный на квази-разностных матрицах.
    Алгоритм изложен на форуме dxdy.ru
    http://dxdy.ru/post202706.html#p202706

    Одним форумчанином был выполнен эксперимент по данному алгоритму. Он выложил отчёт об эксперименте:
    http://dxdy.ru/post202837.html#p202837

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

    Недавно я посмотрела на выложенные форумчанином результаты эксперимента с точки зрения псевдотроек и обнаружила, что псевдотройки в нашем эксперименте были получены. Но результатов выложено всего два. И оба они дали две замечательные псевдотройки с ортогональностью в не ортогональной паре ЛК в 82 ячейках из 100.
    Я решила полностью повторить этот эксперимент и проверить все псевдотройки. Пока пишу программу для эксперимента. Эксперимент довольно сложный, у меня технические трудности полной программной реализации алгоритма поиска и проверки всех псевдотроек. Есть отдельные программки для каждого этапа эксперимента, а нужно всё это собрать в одну программу.

    Сейчас открыта новая тема «Ортогональные латинские квадраты 10-го порядка» на другом форуме
    http://mathhelpplanet.com/viewtopic.php?f=57&t=46638

    В этой теме можно посмотреть подробное описание данного алгоритма и все уже найденные и проверенные псевдотройки.
    Здесь покажу три псевдотройки с ортогональностью в 82 ячейках из 100. В каждой псевдотройке ЛК №1 и №2 ортогональны, ЛК №1 и №3 ортогональны, а ЛК №2 и №3 не ортогональны.

    Псевдотройка #1

    ЛК №1

    9 5 8 3 2 7 0 6 4 1
    5 9 6 0 4 3 8 1 7 2
    8 6 9 7 1 5 4 0 2 3
    3 0 7 9 8 2 6 5 1 4
    2 4 1 8 9 0 3 7 6 5
    7 3 5 2 0 9 1 4 8 6
    0 8 4 6 3 1 9 2 5 7
    6 1 0 5 7 4 2 9 3 8
    4 7 2 1 6 8 5 3 9 0
    1 2 3 4 5 6 7 8 0 9

    ЛК №2

    5 8 3 2 7 0 6 4 9 1
    9 6 0 4 3 8 1 7 5 2
    6 9 7 1 5 4 0 2 8 3
    0 7 9 8 2 6 5 1 3 4
    4 1 8 9 0 3 7 6 2 5
    3 5 2 0 9 1 4 8 7 6
    8 4 6 3 1 9 2 5 0 7
    1 0 5 7 4 2 9 3 6 8
    7 2 1 6 8 5 3 9 4 0
    2 3 4 5 6 7 8 0 1 9

    ЛК №3

    3 9 4 7 2 1 6 8 5 0
    6 4 9 5 8 3 2 7 0 1
    1 7 5 9 6 0 4 3 8 2
    0 2 8 6 9 7 1 5 4 3
    5 1 3 0 7 9 8 2 6 4
    7 6 2 4 1 8 9 0 3 5
    4 8 7 3 5 2 0 9 1 6
    2 5 0 8 4 6 3 1 9 7
    9 3 6 1 0 5 7 4 2 8
    8 0 1 2 3 4 5 6 7 9

    Псевдотройка #2

    ЛК №1

    9 7 5 2 4 0 8 3 6 1
    7 9 8 6 3 5 1 0 4 2
    5 8 9 0 7 4 6 2 1 3
    2 6 0 9 1 8 5 7 3 4
    4 3 7 1 9 2 0 6 8 5
    0 5 4 8 2 9 3 1 7 6
    8 1 6 5 0 3 9 4 2 7
    3 0 2 7 6 1 4 9 5 8
    6 4 1 3 8 7 2 5 9 0
    1 2 3 4 5 6 7 8 0 9

    ЛК №2

    7 9 8 6 3 5 1 0 4 2
    5 8 9 0 7 4 6 2 1 3
    2 6 0 9 1 8 5 7 3 4
    4 3 7 1 9 2 0 6 8 5
    0 5 4 8 2 9 3 1 7 6
    8 1 6 5 0 3 9 4 2 7
    3 0 2 7 6 1 4 9 5 8
    6 4 1 3 8 7 2 5 9 0
    9 7 5 2 4 0 8 3 6 1
    1 2 3 4 5 6 7 8 0 9

    ЛК №3
    6 4 1 3 8 7 2 5 9 0
    9 7 5 2 4 0 8 3 6 1
    7 9 8 6 3 5 1 0 4 2
    5 8 9 0 7 4 6 2 1 3
    2 6 0 9 1 8 5 7 3 4
    4 3 7 1 9 2 0 6 8 5
    0 5 4 8 2 9 3 1 7 6
    8 1 6 5 0 3 9 4 2 7
    3 0 2 7 6 1 4 9 5 8
    1 2 3 4 5 6 7 8 0 9

    Псевдотройка #3

    ЛК №1

    9 6 5 7 3 2 4 8 1 0
    2 9 7 6 8 4 3 5 0 1
    1 3 9 8 7 0 5 4 6 2
    7 2 4 9 0 8 1 6 5 3
    6 8 3 5 9 1 0 2 7 4
    8 7 0 4 6 9 2 1 3 5
    4 0 8 1 5 7 9 3 2 6
    3 5 1 0 2 6 8 9 4 7
    5 4 6 2 1 3 7 0 9 8
    0 1 2 3 4 5 6 7 8 9

    ЛК №2

    7 3 6 2 5 1 9 4 8 0
    0 8 4 7 3 6 2 9 5 1
    6 1 0 5 8 4 7 3 9 2
    9 7 2 1 6 0 5 8 4 3
    5 9 8 3 2 7 1 6 0 4
    1 6 9 0 4 3 8 2 7 5
    8 2 7 9 1 5 4 0 3 6
    4 0 3 8 9 2 6 5 1 7
    2 5 1 4 0 9 3 7 6 8
    3 4 5 6 7 8 0 1 2 9

    ЛК №3

    3 2 9 8 6 4 1 7 5 0
    6 4 3 9 0 7 5 2 8 1
    0 7 5 4 9 1 8 6 3 2
    4 1 8 6 5 9 2 0 7 3
    8 5 2 0 7 6 9 3 1 4
    2 0 6 3 1 8 7 9 4 5
    5 3 1 7 4 2 0 8 9 6
    9 6 4 2 8 5 3 1 0 7
    1 9 7 5 3 0 6 4 2 8
    7 8 0 1 2 3 4 5 6 9

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

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

    Nataly-Mak
    Send message
    Joined: Jan 25 16
    Posts: 26
    Credit: 1,050
    RAC: 0
    Message 855 - Posted 1 Feb 2016 14:54:06 UTC - in response to Message 853.

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

      Из всех найденных псевдотроек отбираю только с характеристикой 82 (есть ещё с характеристиками 59 и 73, но это уже мало интересные псевдотройки).
      На данный момент по псевдотройкам проверено две порции КРМ (по 225 штук), в которых выбраны для проверки только КРМ с двумя вариантами четвёртой строки. Найдено 21 псевдотроек с характеристикой 82.

      Я преложила на форуме boinc.ru внести найденные мной псевдотройки в общую копилку результатов проекта.
      Возможно, предложение будет реализовано в той или иной форме.

      Думаю, что ещё будут псевдотройки с характеристикой 82.
      Но вот с более высокой характеристикой псевдотройки упорно не находятся, что всё больше убеждает меня в верности моей рабочей гипотезы: характеристика 82 максимальная для данного вида КРМ.

      Post to thread

      Message boards : Science : Алгоритм поиска псевдотроек


      Home | My Account | Message Boards


      Copyright © 2019 Institute for System Dynamics and Control Theory of SB RAS and Institute for Information Transmission Problems of RAS