Новый конкурс программистов

[Nataly-Mak]

Такой пример нашла очень легко (за 3 минуты ) среди строго диагональных решений C3N7, найденных по программе svb.
Вот он:

1,1,2,1,2,2,3,
1,2,1,2,2,3,1,
2,1,2,2,3,1,1,
1,2,2,3,1,1,2,
2,2,3,1,1,2,1,
2,3,1,1,2,1,2,
3,1,1,2,1,2,2

1,1,2,1,3,3,2,
1,2,1,3,3,2,1,
2,1,3,3,2,1,1,
1,3,3,2,1,1,2,
3,3,2,1,1,2,1,
3,2,1,1,2,1,3,
2,1,1,2,1,3,3

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

1,2,1,1,3,2,2

для второго решения:

1,2,3,3,1,2,2

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

[whitefox]

Nataly-Mak в сообщении #627615 писал(а):

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

Нет Вы не ошиблись, все Ваши вычисления верны.

Термин "наименьшее" выбран мной не удачно.
Но это всего лишь рабочий вариант.

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

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

Но строить вектора всё таки надо.

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

[Nataly-Mak]

whitefox в сообщении #627725 писал(а):

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

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

Интересно было бы узнать, как Tom Sirgedas определяет изоморфность решений.
Я выложила на форуме конкурса два решения C4N13 строго "ход конём" и попросила определить их изоморфность. Tom ответил, что решения уникальны. Что он сказал во второй фразе, я не поняла (такой корявый перевод).

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

Вот что ответил Tom Sirgedas о приведённых мной решениях:

Цитата:

They're unique. The color counts don't match.

Что говорится во второй фразе?

Вот два решения, которые проверил Tom; только они теперь не в виде "ход конём", а в виде строго диагональных решений:



Теперь и я вижу, что решения уникальны. У них не равны вектора длин блоков.
Впрочем, я и в этом примере верно угадала.
Интересно заметить, что, ничего не зная о векторе длин блоков, я именно эти вектора и сравнивала визуально!
В приведённом примере рассуждала так: в моём решении есть один блок, в котором два цвета рядом, а в решении Herbert Kociemba таких блоков два.
Такая вот интуиция

Извиняюсь, я на картинку скопировала не то своё решение, это не строго диагональное решение С4N13.
Сейчас приведу строго диагональное.
Ох, спать пора

Правильная картинка:



В решении Герберта есть два блока, в которых два цвета рядом, а в моём решении таких блоков три.

[whitefox]

Nataly-Mak в сообщении #627769 писал(а):

Что говорится во второй фразе?

Что эти решения имеют различные числа цветов.
По всей видимости у них разное число одноцветных клеток.

[Nataly-Mak]

Не поняла. Как это различное число цветов? Они оба 4-цветные.

А, теперь поняла
Так, может, именно по этому критерию Tom и определяет изоморфность решений?

[whitefox]

Nataly-Mak в сообщении #627788 писал(а):

Так, может, именно по этому критерию Tom и определяет изоморфность решений?

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

-- 07 окт 2012, 00:03 --

Nataly-Mak в сообщении #627769 писал(а):

В решении Герберта есть два блока, в которых два цвета рядом, а в моём решении таких блоков три.

Да Том прав.
В первом базовом векторе набор цветов: 2, 3, 4, 4.
А во втором: 4, 3, 3, 3.

[Nataly-Mak]

whitefox в сообщении #627794 писал(а):

Nataly-Mak в сообщении #627788 писал(а):

Так, может, именно по этому критерию Tom и определяет изоморфность решений?

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

Уже хорошо! Ещё одно необходимое условие изоморфности. А это условие очень легко ведь проверить.
Так, в приведённом примере распределение цветов такое:

решение Herbert Kociemba

A - 26
B - 39
C - 52
D - 52

моё решение

A - 52
B - 39
C - 39
D - 39

-- Вс окт 07, 2012 01:08:39 --

whitefox в сообщении #627794 писал(а):

Да Том прав.
В первом базовом векторе набор цветов: 2, 3, 4, 4.
А во втором: 4, 3, 3, 3.

А, вы вот как рассуждаете.
А я по-другому поняла (см. выше).

Ушла прерывать программу, которая работает уже 157 часов, и выключать машину, она у меня уже запарилась, бедняжка

[Nataly-Mak]

Nataly-Mak в сообщении #627795 писал(а):

Так, в приведённом примере распределение цветов такое:

решение Herbert Kociemba

A - 26
B - 39
C - 52
D - 52

моё решение

A - 52
B - 39
C - 39
D - 39

-- Вс окт 07, 2012 01:08:39 --

whitefox в сообщении #627794 писал(а):

Да Том прав.
В первом базовом векторе набор цветов: 2, 3, 4, 4.
А во втором: 4, 3, 3, 3.

А собственно, одно и то же получается. В базовом векторе набор цветов 2, 3, 4, 4 и даёт распределение цветов:

А - 26
B - 39
C - 52
D - 52

И так же для второго решения.

[whitefox]

Nataly-Mak в сообщении #627795 писал(а):

А, вы вот как рассуждаете.
А я по-другому поняла (см. выше).

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

-- 07 окт 2012, 08:23 --

Nataly-Mak в сообщении #627795 писал(а):

Уже хорошо! Ещё одно необходимое условие изоморфности.

Таких условий можно придумать много. Для этого годится любой инвариант (свойство сохраняющееся при любом изоморфном преобразовании).

Вот, например, ещё один инвариант:
1. для каждой строки подсчитываем распределение цветов;
2. в полученной матрице элементы всех колонок отсортируем в неубывающем порядке;
3. сами колонки отсортируем в лексикографическом порядке.

Определим этот инвариант для раскраски:

3  2  1  2  1  1  1  3  2  3
3  1  2  1  2  1  3  1  3  2
1  2  3  3  2  2  1  1  3  3
1  2  2  1  1  3  3  2  1  3
3  1  3  2  3  2  1  2  1  2
2  2  1  3  3  3  2  1  1  2
1  1  1  2  2  3  2  3  3  1
2  3  3  1  2  3  1  2  2  1
3  3  2  3  1  2  2  1  2  1
2  3  2  2  3  1  3  3  1  1

На первом шаге получим:

4,3,3
4,3,3
3,3,4
4,3,3
3,4,3
3,4,3
4,3,3
3,4,3
3,4,3
3,3,4

На втором шаге получим (ради удобства матрицу транспонировал):

3,3,3,3,3,3,4,4,4,4
3,3,3,3,3,3,4,4,4,4
3,3,3,3,3,3,3,3,4,4

На третьем шаге получим:

3,3,3,3,3,3,3,3,4,4
3,3,3,3,3,3,4,4,4,4
3,3,3,3,3,3,4,4,4,4

Подсчитать этот инвариант не сложнее чем инвариант Тома, но критерий неизоморфности по нему точнее.

[Nataly-Mak]

whitefox
как я понимаю, вы уже плавно переходите к проверке изоморфности произвольных решений, а не только диагональных

И что? Если мы для двух решений получим несовпадающие инварианты, о которых вы написали, значит, эти решения неизморфны?

И что значит, "критерий неизоморфности по нему точнее"?

[whitefox]

Nataly-Mak в сообщении #627878 писал(а):

И что? Если мы для двух решений получим несовпадающие инварианты, о которых вы написали, значит, эти решения неизморфны?

Именно.

Nataly-Mak в сообщении #627878 писал(а):

И что значит, "критерий неизоморфности по нему точнее"?

Это значит, что возможна ситуация, когда два неизоморфных решения имеют одинаковые инварианты Тома, но различные инварианты, указанные мной.

[Nataly-Mak]

Ага, поняла.
Но, может быть, для строго диагональных решений и критерий Тома вполне годится?
Или может подвести?

[whitefox]

Для строго диагональных решений это условие тоже всего лишь необходимое условие изоморфности. Оно удобно для быстрой проверки неизоморфности, но изоморфизма не доказывает.

[Nataly-Mak]

Наконец-то, на 169 часу работы программы (поиск не строго диагонального решения C5N25), появилась тройка в четвёртой позиции базового вектора:

1 2 3 3 1 1 4 5 3 2 3 ...

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

[Nataly-Mak]

[quote name='Pavlovsky' date='7.10.2012, 14:02' post='374824']
О теореме Зингера.

Пусть у нас есть разностное множество, определяющее блок-схему v=q^2+q+1 k=q+1 lymda=1.

1) По теореме Зингера мы можем построить диагональное решение C=q+1 N=q^2+q+1.

2) С другой стороны из блок-схемы v=q^2+q+1 k=q+1 lymda=1 мы можем построить набор из q-1 ортогональных латинских квадратов размером q. Из этого набора ортоганальных ЛК, в свою очередь, легко строится решение C=q+1 N=q^2+q+1. Так называемый алгоритм первого класса.

Получается что эти алгоритмы эквивалентны. При одинаковых исходных данных мы получаем решения с одинаковыми C и N. Являются ли эти решения изоморфными, вопрос открытый. В некотором смысле они изоморфны, так как построены из одного разностного множества.
[/quote]
[цитата с форума ПЕН]

А почему вопрос об изоморфности этих решений открытый?
Решения C5N21 я здесь привела оба: и построенное по CDS, и построенное по алгоритму первого класса. Давайте решим вопрос об их изоморфности.

whitefox
вы нам поможете?

-- Пн окт 08, 2012 00:17:14 --

Nataly-Mak в сообщении #626767 писал(а):

Реплицировала 4-сильный прямоугольник 16х5 до прямоугольника 16х25 5-coloring, добавила 5 строк, получила решение 21х25 5-coloring.



...

Вот строго диагональное решение C5N21, построенное по CDS (Herbert Kociemba):

Первое решение - 21х25 - надо обрезать до квадрата 21х21.