2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 107, 108, 109, 110, 111, 112, 113 ... 130  След.
 
 Re: Новый конкурс программистов
Сообщение21.09.2012, 09:39 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Nataly-Mak в сообщении #621729 писал(а):
whitefox говорит, что полный перебор завершится тогда, когда начало базового вектора будет таким:

Код:
1,2,3,4,5,...

Ждём :roll:

Два базовых вектора будем называть изоморфными если существует перестановка чисел 1 2 3 ... N переводящая один вектор в другой.

Например, вектора
Код:
1 1 2 1 2 2 3 3 1 1 2 1 3 2 2
2 2 1 2 1 1 3 3 2 2 1 2 3 1 1
изоморфны так как перестановка 2 1 3 переводит их друг в друга.

Напротив, вектора
Код:
1 1 2 1 2 2 3 3 1 1 2 1 3 2 2
1 1 2 1 2 2 3 3 1 1 2 3 1 2 2
не изоморфны так как ни одна перестановка не переводит первый вектор во второй или второй в первый.

Очевидно, что это отношение разбивает всё множество базовых векторов на не пересекающиеся классы изоморфных векторов.

Будем называть базовый вектор каноническим если каждое число появляется в нём первый раз только после того как уже появились все меньшие числа. Иными словами, если в каноническом векторе вычеркнуть все повторы всех чисел кроме их самого первого появления, то останется начальный отрезок натурального ряда 1 2 3 ... N. Например вектора
Код:
1 1 2 1 2 2 3 3 1 1 2 1 3 2 2
1 1 2 1 2 2 3 3 1 1 2 3 1 2 2
канонические.

Очевидно, что канонические вектора не изоморфны, и поэтому являются представителями своего класса изоморфизма.

Моя программа проверяет все канонические базовые вектора, причём делает это в лексикографическом порядке. Поэтому последний вектор, проверенный программой, будет иметь вид 1 2 3 4 5 ...

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение21.09.2012, 10:33 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
dimkadimon в сообщении #621730 писал(а):
Nataly-Mak в сообщении #621729 писал(а):
Может быть, у кого-то есть не переборное доказательство несуществования не строго диагонального решения C5N25?

Я нашёл 200 случайных строго диагональных. По крайней мере можно сказать что не строго 25х25 диагональные встречаются в 200 реже чем строго диагональные. Это конечно не доказательство...

Решил заново запустить программу. Уже нашёл 3660 случайных строго диагональных 25х25. Шансы найти не строго диагональное падают... думаю его нет

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение21.09.2012, 11:20 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
У меня программа работает уже 8 часов.
Базовый вектор сейчас:

Код:
1,1,2,2,3,4,3,4,...

Похоже, что полный перебор здесь будет выполняться 2-3 суток.

Надо разбивать процесс на части. Я не рискую крутить программу столько времени без перерыва. У нас часто отключают электричество, в этом случае всё вообще полетит собаке под хвост.

-- Пт сен 21, 2012 12:47:02 --

Выложила сейчас на форуме конкурса начало своей книги (4 главы) "Monochromatic Squares или Математическая раскраска":
http://infinitesearchspace.dyndns.org/c ... -aftermath

Да что-то на том форуме полнейшая тишина. Похоже, там задача больше вообще никого не интересует :-)

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение21.09.2012, 16:30 
Аватара пользователя


01/06/12
1016
Adelaide, Australia
На форуме сайта я написал как задачу можно представить как граф. Допустим у нас есть решение NxN, матрица А. Если А(i,k) имеет цвет с тогда рисуем ребро от i до k с цветом с. Теперь задача становится такой: надо раскрасить ребра так чтобы не было циклов одного цвета длиной 4. Если матрица симметричная то получаем ребра без направления и задача вроде проще. 

Вот решение C2N4:

  0123
0 1122
1 1221
2 2211
3 2112

Если нарисовать граф то можно увидеть очень красивое и симметричное решение. Путь цвета 1 такой же как путь цвета 2 только повернут на 90 градусов. Можно ли этим подходом найти хорошие решения?

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение21.09.2012, 17:04 
Аватара пользователя


21/02/10
1594
Екатеринбург
Задачу можно переформулировать до бесконечности. Как вам такой вариант?!

Задача построения C-coloring прямоугольника MxN эквивалентна:

Задача. Построить конечную геометрию из M точек и N*C прямых такую, что в ней существует ровно С групп параллельных прямых (по N прямых в каждой группе), покрывающих все M точек.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение21.09.2012, 18:51 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
dimkadimon в сообщении #621842 писал(а):
На форуме сайта я написал как задачу можно представить как граф.

К сожалению, совсем не знаю теорию графов.

Цитата:
Вот решение C2N4:

0123
0 1122
1 1221
2 2211
3 2112

Решение-то диагональное! Правда, строго диагональное. А не строго диагональное можно получить таким методом?

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение21.09.2012, 20:11 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Да, теперь уже очевидно, что перебор для решения C5N25 будет очень долгий.
Вот таким был базовый вектор где-то в самом начале работы программы:

Код:
1,1,2,1,3,4,5,5,3,4,5,...

Вот такой он сейчас, после 17 часов работы программы:

Код:
1,1,2,3,1,2,3,4,5,4,5,5,...

Первые три позиции пока не изменяются.
Нереально :-(

Вопрос существования не строго диагонального решения C5N25 остаётся открытым.
Ну, и решения C5N26 тоже.
А также всех следующих за С=5 не строго диагональных решений C^2xC^2 и со строной квадрата N>C^2.
Мало, очень мало знаем о диагональных решениях! Даже для С=5 не можем полностью решить вопрос. Решателей у нас раз-два и... нету :-(

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение22.09.2012, 05:10 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Слабая идея...
Есть строго диагональные решения, которые легко превращаются в не строго диагональные путём окрашивания одной из разломанных диагоналей в два цвета.

Пример для решения C2N3
строго диагональное решение:

Изображение

Окрашиваем одну из разломанных диагоналей в два цвета и получаем не строго диагональное решение:

Изображение

Что если поискать такую возможность среди строго диагональных решений C5N25 :?:

Высказываем идеи: слабые, сильные, бредовые :D
Неужели слабо нам найти решение даже для 5 цветов? Что же тогда говорить о решении C10N100!
Вот и ещё один вызов человеческому интеллекту :wink:

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение22.09.2012, 09:04 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Решила попытать удачу на не строго диагональном решении C6N36 в надежде на то, что таких решений может оказаться очень много и решение найдётся достаточно быстро.
Увы, надежда не оправдывается :-(
Два часа работает программа, даже и близко ничего нет. Базовый вектор заполняется максимум 37 числами. Значит, и такого решения нет :?:

-- Сб сен 22, 2012 10:07:49 --

alexBlack писал: "критикуют, значит хотя бы прочитали".
Начало моей книги никто не критикует. Значит, не читают? :D

-- Сб сен 22, 2012 10:20:56 --

whitofox пишет:

Цитата:
Так для C4N15 не строго диагональных решений существует 37622.

Он нашёл их все по своей программе и прислал мне. Имеются в виду только неизоморфные решения.
Очень интересный факт! Огромное количество не строго диагональных 4-цветных раскрасок 15х15 и ни одной не срого диагональной раскраски C4N16. Невероятно! Неужели ни одна раскраска 15х15 из такого огромного количества не может быть достроена до не строго диагональной раскраски 16х16 путём добавления строки и столбца?

[хотя... программа whitefox говорит, что не строго диагональных решений C4N16 не существует; невероятно, но факт :-) ]

-- Сб сен 22, 2012 10:47:42 --

Беру первое не строго диагональное решение C4N15 из файла, присланного whitefox.

Изображение

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

Изображение

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

Строго диагональных решений C5N25 наверняка очень много. Не найдётся ли среди них такой экземпляр?

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение22.09.2012, 10:32 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Что-то промелькнуло... решение C4N15 отличается от решения C5N25 тем, что у него сторона квадрата не равна C^2. Поэтому подобный экземпляр (см. пример выше) среди решений C5N25 может и не существовать.

Сейчас взяла строго диагональное решение C5N25 и попробовала перекрасить часть хотя бы одной разломанной диагонали. Увы! Это не удалось.

-- Сб сен 22, 2012 11:58:30 --

Нашла среди строго диагональных решений C3N9 подобный пример!
Вот строго диагональное решение C3N9:

Изображение

Перекрашиваю части двух разломанных диагоналей (см. нижний правый уголок) и получаю не строго диагональное решение C3N9:

Изображение

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

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение22.09.2012, 11:17 
Заслуженный участник
Аватара пользователя


19/12/10
1546
Nataly-Mak в сообщении #621961 писал(а):
Вот таким был базовый вектор где-то в самом начале работы программы:

Код:
1,1,2,1,3,4,5,5,3,4,5,...

Вот такой он сейчас, после 17 часов работы программы:

Код:
1,1,2,3,1,2,3,4,5,4,5,5,...

То есть за 17 часов четвёртая позиция увеличилась на две единицы.
Тогда, примерно, ещё через 8 часов должен получиться вектор:
Код:
1,2,1,1,...

А ещё через сутки перебор должен закончиться. :D

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение22.09.2012, 11:40 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
whitefox
значит, по вашим подсчётам примерно за 2 суток перебор должен выполниться.
Осталось найти желающего 2 суток покрутить программу :D
Я могу покрутить и больше 2 суток, но с перерывом. Идею организовать перерыв я вам изложила.

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение22.09.2012, 11:52 
Аватара пользователя


21/02/10
1594
Екатеринбург
Перебор можно сильно ускорить если применить следующий прием:
Преамбула. Для каждой ячейки ввести список доступных цветов (как это обычно делают решая судоку). Когда в текущем узле перебора вы присваиваете очередной цвет диагонали, необходимо вычеркнуть из списка доступных некоторые цвета. Если появляется ячейка базового вектора где нет доступных цветов, то дальнейший перебор бессмысленен, надо возвращаться назад. Реализовать подобную процедуру достаточно сложно, поэтому я, при реализации диагональных алгоритмов, пошел по более простому пути.

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

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


19/12/10
1546
Pavlovsky в сообщении #622261 писал(а):
Для каждой ячейки ввести список доступных цветов (как это обычно делают решая судоку). Когда в текущем узле перебора вы присваиваете очередной цвет диагонали, необходимо вычеркнуть из списка доступных некоторые цвета. Если появляется ячейка базового вектора где нет доступных цветов, то дальнейший перебор бессмысленен, надо возвращаться назад. Реализовать подобную процедуру достаточно сложно

Напротив, совсем не сложно.
Вместо списка доступных цветов я использую битовый вектор, где каждому доступному цвету соответствует -- 1, а запрещённому -- 0. Так как максимальное число цветов 21, то 32-х битного слова вполне достаточно.
Проверка, сброс и установка одного бита выполняются простыми машинными командами (на С и С++ средствами языка).

 Профиль  
                  
 
 Re: Новый конкурс программистов
Сообщение22.09.2012, 12:56 
Аватара пользователя


21/02/10
1594
Екатеринбург
Обобщение теоремы 3.3. Репликация

В http://www.cs.umd.edu/~gasarch/papers/grid.pdf (теорема 3.3 хм автор доработал статью раньше это была лемма 4.3) дается такой способ преобразования цветов при репликации: χi (a, b) = χ(a, b) + i (mod c).
Это преобразование можно записать в виде матрицы СхС (пример для С=5):
12345
23451
34512
45123
51234
Где первая колонка цвета исходного сильноокрашенного прямоугольника. Следующие колонки матрицы задают преобразование цвета исходного прямоугольника на i шаге репликации. Получился латинский квадрат, полученный циклическим сдвигом первой колонки.
Преобразование можно записать и в виде двух перестановок:
12345
23451
Вторая перестановка задает преобразование цвета на текущем шаге репликации из цветов ячеек прямоугольника полученного на предыдущем шаге репликации.

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

Что то подобное есть и у Сергея Беляева.
Цитата:
Теорема
Пусть $L\left( {k,l} \right)$ - латинский квадрат, $G$ - поле из $c$ элементов с операциями $\otimes$ и $\oplus$, тогда
1. раскраска $R\left( {x,y,k,l} \right) = L\left( {x \otimes y \oplus k,l} \right)$ правильная;
2. раскраска $R\left( {x,y,k,l} \right) = L\left( {k \otimes l \oplus x,y} \right)$ правильная.
Собственно $L\left( {k,l} \right)$ и есть способ преобразования цветов при репликации.

Обобщение теоремы 3.3. Любой ЛК задает корректное преобразование цветов при репликации сильноокрашенного прямоугольника.

-- Сб сен 22, 2012 15:22:08 --

В свете последних идей изучаю тему классы изоморфизмов латинских квадратов. Или как пишется в литературе изотопные классы.

http://cs.anu.edu.au/~bdm/data/latin.html
Вводится поянтие "main class"
Цитата:
To be in the same main class, one is in addition permitted to permute the three roles "row", "column" and "symbol" (for example, symbol s in row r and column c might become symbol r in row c and column s)


Как я поянл, задается преобразование: каждой ячейке ЛК сопостовляется тройка чисел (s,r,c), s-цвет ячейки, r-номер строки ячейки, c-номер колонки ячейки. Тогда преобразования
(s,r,c)->(s,c,r) (зеркальное отражение относительно диагонали)
(s,r,c)->(r,s,c)
(s,r,c)->(r,c,s)
(s,r,c)->(c,s,r)
(s,r,c)->(c,r,s)
Преобразовывают ЛК в ЛК.

Тщательно изучил списки литературы. Но увы первоисточников не нашел. Появились вопросы.
1) Доказать, что эти преобразования преобразуют ЛК в ЛК.
2) Доказать, что эти преобразования нельзя получить перестановкой строк, колонок и символов.

Количество "main class" ЛК описано в http://oeis.org/A003090

Долго пытался вникнуть в этот текст:
Цитата:
"We start by showing a one to one correspondence between arrangements of d lines in P^2 and lines in P^{d-2}. Then we apply this to classify (3,q)-nets on P^2 for all 2 <= q <= 6. For the new case q=6, we have a priori twelve possible cases, but we obtain that only six of them are realizable on P^2 over C. We give equations for the lines defining these nets. We also construct a three dimensional family of (3,8)-nets corresponding to the multiplication table of the Quaternion group. After that, we define more general arrangements of curves and relate them, via moduli spaces of pointed stable curves of genus zero, to curves in P^{d-2}. Then, we prove that there is a one to one correspondence between these more general arrangements of d curves and certain curves in P^{d-2}. As a corollary, we recover the one to one correspondence for line arrangements. This more general setting not only generalizes line arrangements but also shows the ideas behind what we did in that case." - Jonathan Vos Post, Apr 05 2007


Увы пока ничего не понял.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1937 ]  На страницу Пред.  1 ... 107, 108, 109, 110, 111, 112, 113 ... 130  След.

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



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

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


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

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