Новый конкурс программистов : Олимпиадные задачи (CS) - Страница 126 fixfix
2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 123, 124, 125, 126, 127, 128, 129, 130  След.
 
 Re: Новый конкурс программистов
Сообщение08.10.2012, 04:44 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Обрезала решение первого класса до квадрата 21х21, поставила два решения рядом:

Изображение

Распределение цветов в этих решениях:

Herbert Kociemba

A - 84
B - 84
C - 84
D - 84
E - 105

решение первого класса

A - 85
B - 85
C - 85
D - 101
E - 85

Мой вывод: данные решения неизоморфны.

-- Пн окт 08, 2012 06:37:49 --

А вот решение строго "ход конём", полученное из приведённого выше строго диагонального решения C5N21 Herbert Kociemba, обязано быть ему изоморфным:

Изображение

Весьма любопытный факт. Разобьём показанное решение на подквадраты 3х3, это будут блоки; блоки в первом ряду:

Изображение

Пронумеруем эти блоки 3х3 в порядке следования. Заполним этими блоками следующую базовую матрицу 7х7:

Код:
1 2 3 4 5 6 7
4 5 6 7 1 2 3
7 1 2 3 4 5 6
3 4 5 6 7 1 2
6 7 1 2 3 4 5
2 3 4 5 6 7 1
5 6 7 1 2 3 4

и получим готовое решение C5N21. Обратите внимание на базовую матрицу: блоки делают ход конём!
Снова матричный метод. Выше я показывала построение матричным методом строго диагонального решения.
Можно разбить решение C5N21 на подквадраты 7х7. Тогда блоков 7х7 будет всего 3, а базовая матрица 3х3 имеет вид:

Код:
1 2 3
2 3 1
3 1 2

И снова блоки делают ход конём!

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


22/03/08

7154
Саратов
Для тех, кто любит читать в формате pdf :D
Выкладываю вторую часть книги в этом формате:
http://narod.ru/disk/62163817001.f7fba5 ... 2.pdf.html

Уже писала: здесь две главы - 5,6.
Особый интерес, на мой взгляд, представляет глава 6 - "Расширение области применения теоремы 3.3".

Наконец-то, после долгого обдумывания, начала писать главу 7 - "Алгоритмы построения решений для С=10,12,14,18,20".

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #628167 писал(а):
Решения C5N21 я здесь привела оба: и построенное по CDS, и построенное по алгоритму первого класса. Давайте решим вопрос об их изоморфности.


Любое решение первого класса не пойдет. Из диагонального решения C5N21 надо выделить набор ортногональных ЛК. Решение первого класса строить на этом наборе ЛК.

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #628221 писал(а):
Любое решение первого класса не пойдет. Из диагонального решения C5N21 надо выделить набор ортногональных ЛК. Решение первого класса строить на этом наборе ЛК.

Так давайте это решение!
Проверим его изоморфность решению, построенному по CDS.
Это на всякий случай код решения, построенного по CDS:

(Оффтоп)


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


21/02/10
1594
Екатеринбург
Разностное множество (взято из книги Холла):
Код:
3,6,7,12,14

Диагональное решение
Строим диагональное решение. Алгоритм описан в статье Беляева. Я так понимаю у Herbert Kociemba алгоритм такой же.
Базовый вектор:
Код:
5,4,4,3,2,5,3,5,2,4,1,1,3,2,3,2,1,5,1,4,5

Решение C=5N21

(Оффтоп)



Решение первого класса
Алгоритм описан у Холла
Строим блок-схему:

(Оффтоп)


Выделяем набор ортогональных ЛК и строим сильноокрашенный прямоугольник 16х5 С=4.

(Оффтоп)



Из него легко получить прямоугольник 21х25 для С=5.

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


22/03/08

7154
Саратов
Последний шаг не сделали: не вижу решение C5N21 - по алгоритму первого класса.
Чтобы проверить потом изоморфность этого решения с решением, построенным по CDS.

Цитата:
Выделяем набор ортогональных ЛК и строим сильноокрашенный прямоугольник 16х5 С=4.

Прямоугольник проверила, он действительно 4-сильный.
Осталось реплицировать. Дальше из 21х25 как выделить решение 21х21? Произвольно отбрасываем 4 столбца?

Решение, построенное по CDS:

Изображение

Распределение цветов в этом решении:

A - 84
B - 84
C - 84
D - 84
E - 105

Точно такое же распределение и в решении Herbert Kociemba, приведённом мной выше:

Цитата:
Herbert Kociemba

A - 84
B - 84
C - 84
D - 84
E - 105

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


21/02/10
1594
Екатеринбург

(Оффтоп)



Изображение

-- Пн окт 08, 2012 18:31:31 --

Nataly-Mak в сообщении #628353 писал(а):
Дальше из 21х25 как выделить решение 21х21? Произвольно отбрасываем 4 столбца?


Ну это уже дело вкуса. Из набора ортогональных ЛК можно и решение второго класса сделать.

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


22/03/08

7154
Саратов
Нет, неизоморфны эти решения ни для какого вкуса :D

Я отбросила последние 4 столбца, получила решение C5N21, в котором распределение цветов такое:

A - 85
B - 85
C - 85
D - 101
E - 85

Как бы вы ни отбрасывали 4 столбца, вряд ли получится такое распределение цветов, как в решении, построенном по CDS.
Если у вас получится, покажите :wink:

Изображение

-- Пн окт 08, 2012 18:30:50 --

На 188 часу появилась четвёрка в четвёртой позиции. Ура! Осталась последняя, пятая позиция.

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

Примерно за сутки должно закончиться.

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #628392 писал(а):
Нет, неизоморфны эти решения ни для какого вкуса


Не стоит торопиться с выводами. Можно поковырять диагональное решение. Может там есть резервы и можно построить решение 21х25.

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


22/03/08

7154
Саратов
Я сделала вывод о предложенных для проверки на изоморфность двух решениях C5N21.
Диагональное решение 21х25 5-coloring вы мне ещё не показывали.

Не строго диагональное решение 21х25 5-coloring запросто можно построить: в строго диагональном решении C5N25 удалить 4 строки. Например:

Изображение

[из решения whitefox]

А вот чтобы строго диагональное 21х25 построить... что-то сомнительно. Да ещё по CDS.
Но... чем чёрт не шутит :D

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


01/06/12
1016
Adelaide, Australia
Nataly-Mak я прочитал вторую часть книги. Вот мои комментарии:

* В этой части немного мало структуры. В основном одни примеры. Первая часть была лучше написана.
* Я не заметил Лемму Макаровой-Беляева (или она там есть?). Кстати я даже написал отдельную программу для нахождения решений по этой Лемме, но ничего лучше strong решений не нашёл
* Как я уже писал, картинки очень нерезкие. Для больших решений совсем не видно отдельных цветов. Вам надо создать картинки в формате который не теряет качество.
* Для C10N100 у меня есть лучше решение в котором 740 ошибок:

(Оффтоп)


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


22/03/08

7154
Саратов
dimkadimon в сообщении #628664 писал(а):
Nataly-Mak я прочитал вторую часть книги. Вот мои комментарии:

* Я не заметил Лемму Макаровой-Беляева (или она там есть?). Кстати я даже написал отдельную программу для нахождения решений по этой Лемме, но ничего лучше strong решений не нашёл

Лемма Макаровой-Беляева, конечно, есть.

Цитата:
В общем, здесь уже всё рассказано. Был получен прямоугольник 7х12, который не является strong (6,2)-coloring прямоугольником. Тем не менее, к нему можно применить теорему 3.3. В результате получен прямоугольник 7х36 6-coloring.
Этот пример помог проанализировать на форуме С. Беляев. Поэтому мы назвали усиленный вариант леммы 4.3 леммой Макаровой-Беляева (полушутливое название). Хотя расширение области применения налицо, и можно говорить о новой лемме.

Видно, что вы читали по самой большой диагонали. :D

Почти вся глава 6 посвящена именно этой лемме. Приведены примеры расширения области применения теоремы 3.3. На мой вгляд, очень интересные примеры, начиная с самого первого, когда я очень удачно ошиблась при построении strong c-coloring прямоугольника, что и привело к возникновению леммы МБ. По этой лемме я получла все ршения первого класса, когда ещё не знала другой алгоритм. Это всё подробно описано.

Цитата:
* Как я уже писал, картинки очень нерезкие. Для больших решений совсем не видно отдельных цветов. Вам надо создать картинки в формате который не теряет качество.

Согласна, качество картинок плохое, но я пока не умею делать лучше. Возможно, попробую формат djv.
Хотя во всех примерах подробно описывается процесс построения, картинка - это просто иллюстрация к примеру. Желающие могут выполнить построение самостоятельно, получить код решения и увидеть в программе Эда картинку отличного качества.

Цитата:
* Для C10N100 у меня есть лучше решение в котором 740 ошибок:

Не поняла. 740 ошибок или 740 "дырок"? Это разные вещи.

Цитата:
На рис. 15 изображена 10-цветная раскраска 100х100, в которой 730 “дырок”.

Если в вашем решении 740 "дырок", то чем же оно лучше? :D
Если же в вашем примере 740 ошибок, то у меня приведено приближение к решению C10N100, в котором 423 ошибки.

Что касается структуры... На мой взгляд, во второй части больше оригинального материала, нежели в первой. Это и лемма МБ, и использование ортогональных ЛК для С=10,12, и использование нетрадиционных ЛК при построении решений с "дырками".
Ну, а обилие примеров - это оправдано: чтобы показать оригинальный метод, без примера не обойтись.

Кстати, вы писали, что статья alexBlack хороша тем, что в ней много примеров. :-)

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


01/06/12
1016
Adelaide, Australia
* А где описание метода для C10N93, C12N135, C14N185 итд ?

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


22/03/08

7154
Саратов
dimkadimon в сообщении #628683 писал(а):
* А где описание метода для C10N93, C12N135, C14N185 итд ?

Это глава 7 :D
Книга ещё не закончена. Я же сообщала здесь, что продолжаю писать книгу.
Глава 7 уже написана, вчера поставила в этой главе точку. Могу выложить :D

Обдумываю главу 8. Предположительно, это будет глава о построении решений для С=15,21.
Далее будет глава "Диагональные решения". Это будет большая глава, я много работала с диагональными решениями.

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


01/06/12
1016
Adelaide, Australia
Nataly-Mak в сообщении #628682 писал(а):
Если в вашем решении 740 "дырок", то чем же оно лучше? :D
Если же в вашем примере 740 ошибок, то у меня приведено приближение к решению C10N100, в котором 423 ошибки.


У меня регулярное решение где 740 ошибок, которое базируется на strong 100х10 где 74 ошибки. У вас регулярное решение где 730 дырок и нерегулярное где 423 дырки. Моё решение лучше потому что его можно превратить в решение где будет меньше чем 423 дырки.

Кстати вы не дали определение "регулярному решению" :))))

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 1937 ]  На страницу Пред.  1 ... 123, 124, 125, 126, 127, 128, 129, 130  След.

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



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

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


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

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