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:

(Оффтоп)

Код:
21,21,A,D,B,A,E,E,D,D,E,C,D,C,B,A,B,A,C,C,E,B,E,D,B,A,E,E,D,D,E,C,D,C,B,A,B,A,C,C,E,B,E,A,B,
A,E,E,D,D,E,C,D,C,B,A,B,A,C,C,E,B,E,A,D,A,E,E,D,D,E,C,D,C,B,A,B,A,C,C,E,B,E,A,D,B,E,E,D,D,E,C
,D,C,B,A,B,A,C,C,E,B,E,A,D,B,A,E,D,D,E,C,D,C,B,A,B,A,C,C,E,B,E,A,D,B,A,E,D,D,E,C,D,C,B,A,B,A,
C,C,E,B,E,A,D,B,A,E,E,D,E,C,D,C,B,A,B,A,C,C,E,B,E,A,D,B,A,E,E,D,E,C,D,C,B,A,B,A,C,C,E,B,E,A,D
,B,A,E,E,D,D,C,D,C,B,A,B,A,C,C,E,B,E,A,D,B,A,E,E,D,D,E,D,C,B,A,B,A,C,C,E,B,E,A,D,B,A,E,E,D,D,
E,C,C,B,A,B,A,C,C,E,B,E,A,D,B,A,E,E,D,D,E,C,D,B,A,B,A,C,C,E,B,E,A,D,B,A,E,E,D,D,E,C,D,C,A,B,A
,C,C,E,B,E,A,D,B,A,E,E,D,D,E,C,D,C,B,B,A,C,C,E,B,E,A,D,B,A,E,E,D,D,E,C,D,C,B,A,A,C,C,E,B,E,A,
D,B,A,E,E,D,D,E,C,D,C,B,A,B,C,C,E,B,E,A,D,B,A,E,E,D,D,E,C,D,C,B,A,B,A,C,E,B,E,A,D,B,A,E,E,D,
D,E,C,D,C,B,A,B,A,C,E,B,E,A,D,B,A,E,E,D,D,E,C,D,C,B,A,B,A,C,C,B,E,A,D,B,A,E,E,D,D,E,C,D,C,B,
A,B,A,C,C,E,E,A,D,B,A,E,E,D,D,E,C,D,C,B,A,B,A,C,C,E,B

 Профиль  
                  
 
 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

(Оффтоп)

Цитата:
5 4 4 3 2 5 3 5 2 4 1 1 3 2 3 2 1 5 1 4 5
4 4 3 2 5 3 5 2 4 1 1 3 2 3 2 1 5 1 4 5 5
4 3 2 5 3 5 2 4 1 1 3 2 3 2 1 5 1 4 5 5 4
3 2 5 3 5 2 4 1 1 3 2 3 2 1 5 1 4 5 5 4 4
2 5 3 5 2 4 1 1 3 2 3 2 1 5 1 4 5 5 4 4 3
5 3 5 2 4 1 1 3 2 3 2 1 5 1 4 5 5 4 4 3 2
3 5 2 4 1 1 3 2 3 2 1 5 1 4 5 5 4 4 3 2 5
5 2 4 1 1 3 2 3 2 1 5 1 4 5 5 4 4 3 2 5 3
2 4 1 1 3 2 3 2 1 5 1 4 5 5 4 4 3 2 5 3 5
4 1 1 3 2 3 2 1 5 1 4 5 5 4 4 3 2 5 3 5 2
1 1 3 2 3 2 1 5 1 4 5 5 4 4 3 2 5 3 5 2 4
1 3 2 3 2 1 5 1 4 5 5 4 4 3 2 5 3 5 2 4 1
3 2 3 2 1 5 1 4 5 5 4 4 3 2 5 3 5 2 4 1 1
2 3 2 1 5 1 4 5 5 4 4 3 2 5 3 5 2 4 1 1 3
3 2 1 5 1 4 5 5 4 4 3 2 5 3 5 2 4 1 1 3 2
2 1 5 1 4 5 5 4 4 3 2 5 3 5 2 4 1 1 3 2 3
1 5 1 4 5 5 4 4 3 2 5 3 5 2 4 1 1 3 2 3 2
5 1 4 5 5 4 4 3 2 5 3 5 2 4 1 1 3 2 3 2 1
1 4 5 5 4 4 3 2 5 3 5 2 4 1 1 3 2 3 2 1 5
4 5 5 4 4 3 2 5 3 5 2 4 1 1 3 2 3 2 1 5 1
5 5 4 4 3 2 5 3 5 2 4 1 1 3 2 3 2 1 5 1 4


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

(Оффтоп)

Код:
3   6   7   12   14
4   7   8   13   15
5   8   9   14   16
6   9   10   15   17
7   10   11   16   18
8   11   12   17   19
9   12   13   18   20
10   13   14   19   0
11   14   15   20   1
12   15   16   0   2
13   16   17   1   3
14   17   18   2   4
15   18   19   3   5
16   19   20   4   6
17   20   0   5   7
18   0   1   6   8
19   1   2   7   9
20   2   3   8   10
0   3   4   9   11
1   4   5   10   12
2   5   6   11   13

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

(Оффтоп)

Код:
1   3   3   2   1
2   1   2   4   1
3   2   1   3   1
4   4   4   1   1
1   1   1   1   2
2   3   4   3   2
3   4   3   4   2
4   2   2   2   2
1   2   4   4   3
2   4   1   2   3
3   3   2   1   3
4   1   3   3   3
1   4   2   3   4
2   2   3   1   4
3   1   4   2   4
4   3   1   4   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
Екатеринбург

(Оффтоп)

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


Изображение

-- Пн окт 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
862
Adelaide, Australia
Nataly-Mak я прочитал вторую часть книги. Вот мои комментарии:

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

(Оффтоп)

11281844572239295568334A3A6679445141778A556252889166736399A2778474AA13889585112499A6962235AA17A73346
246A745367357185647846829675895793A7869A68A41897A1791529A8128A263A19239137412A34A2485231451359634256
A319898547142A9A96582531A1A769364212187A47532329815864343A9269754541A37A86565214819767632592A8787436
6A51A27A87716213819882732492A9938435A31AA49546142115A65725322617683643372879475448398A5865594A916976
424233369753534447A86464555819757566692A8686777A319797888142A8A89992531919AAA3642A2A1114753131222586
55A7279877661838A9887729491A99883A5A21AA9941613211AA52724322116383543322749465443385A576554496168766
79846569278A95767A3891A6878149A21798925A1328A9A36124391A1472354A212583465132369457624347A56873545816
879546213798A6573248A9176843591A2879546A21398A6571324A9176824351A2879354621398A4657324A9157684351A26
96765AA717A787611828189872293929A9833A4A3A1A9441514121A5526252321663736343277484745438859585654996A6
17A285AA6628139611773924A722884A3518339951462944AA62573A551173684166228479527733958A638844A691749955
285716664639682777574A79388868518A49997962915AAA8A73A261119184137222A29524833313A6359444241746A55535
A9417A28561A528139672163924A783274A35189438514629A54962573A165A73684127618479523872958A634983A691745
64752889967586399AA786974AA11897A8511229A81962233A192A7334412A3184455231429556634253A667745364177885
4386A44176549715528765A826639876193774A9872A48851A9831599621A9426AA7321A5371184321648229543275933A65
519439528662A54A639773165174A88427628519953873962AA64984A731175A9518422861A629533972173A644A83284175
721A529436832163A5479432741658A543852769165496387A2765A749813876185A9249872961A35A983A721461A9418325
85296373A6963A748417A741859528185296A6392963A7174A3A74182851418529396252963A4A7363A74151847418526295
9A68473526A179584637128A69574823917A685934A281796A4513928A715624A39182673514A29378462513A48957362415
1845A9932329561AA4343A6721154541783226565289433767639A54487874A16559898512766A9A96238771A1A734988212
29A63875333A1749864441285A9755523961A866634A7219777451832A8885629431999673A542AAA7841653111895276422
A7542434A3186535451429764656253A87576736419868784752A9798958631A8A9A69742191A17A8532A212819643132392
639A67A65374A1781764851289287596239A3986A734A14A9718451251A829562362193A6734732A41784584315289569542
61839695197294A7A62A83A51817319416292842A5273A39531638414A642749525175385A63628649617473975A728584A8
5488532A43659964315476AA75426587118653769822976487A933A875981A441986A921552A971A326631A8214377421932
75621A81838673219294978432A3A5A89543141619A65425272A176536383128764749423987585A534A9869616451A97A72
8A1775429391288653A4A239976415134AA87526245119863735622A9748467331A859578442196A6895532A7179A6643182
9221865973A332976A841443A8719525541982A636652A9317477631A4285887421539699853264A7AA9643751811A754862
1A892A5634219A31674532A142785643125389675423649A78653475A189764586129A87569723A19867A83412A978194523
2298A588A433A9169915441A27AA265521381137663249224877435A3359885461446A9965725571AA768366821187947793
A57A364A241681475135279258624638A369735749147A84685A25819579613692A68A7247A3179183581428A29469253913
69275931647A386A42758149715386925A826497A3619375A81472A48619258315972A369426A83147A53719425816482A53
4761689244587279A35569838A14667A9491257781A5A236889216134799A3272458AA14383569112549467A22365A578133
58124479546923558A657A34669176814577A2879256881398A3679924A91478AA351A2589114621369A22573247A1336843
715687239482679834A59378A94516A4891A5627159A21673826A1327849371243895A4823549A61593465A1726A45761283
844412A5749555231685A66634279617774538A728885649183999675A294AAA78613A511189724162229A83527333A19463
93A5931784A416A4289515271539A62638264A173749375128485A486239596159734A6A726A84517183719562829482A673
136456789A24756789A13586789A12469789A12357A89A12346819A12345792A1234568A312345679142345678A253456789
21156A3A7A3226714181433782529254489363A36559A47414766A1585258771269636988237A747A9934818581AA4592969
A42645968A153756A79126486718A23759782913486A893A2459719A41356A82A15246719312635782A42374689315348579
654884623A7659957341876AA684529871179563A98228A6741A9339178521A44A289632155139A74326624A185437735129
4AAA1929AA51112A3A116222314122733342523384445363449555647455A6667585661777869677288897A7883999A81899
525978A12A636A89123174719A23428582A134539693124564A7A4235675181534678629264578973A375689A84148679A19
789123456A89A23456719A13456782A12456789312356789A42346789A15345789A12645689A12375679A12348678A123459
8972A7544A9A83186551A19429766212A53A87732316419884342752A9954538631AA65649742117675A8532287861964339
978732835AA89843946119A954A5722A1A651683312176279442328738A553439849166454A95A2775651A61388676217249
195A4382782A61549389317265A49A42837615A1539487261264A59837237516A9483486271A59459738216A56A849327167
3739574989484A685A9A59517961A16A628A721271739183238284A29434939513A545A4A624165615173527672628463878
A8A862519819197362A92A2A84731A31319584214242A69532535317A6436464281754757539286586864A39769797514A87
61327615A87243872619835498372A9465A94831A5761A59421687216A53279832716438A9438275491A5493865A2165A497
44978A742855A89185396619A2964A772A13A75188312418629942352973AA53463A84116457419522756852A63386796317
53711533386482264449759337555A86A44866619715597772A8266A888319377199942A4882AAA53159931116426AA42227
7A2534A84881364519599247562A6AA3586731711469784282257A89539336819A64A44792A1751558A31286266914239737
3266291A5943773A216A5488413271659952438276AA63549387117465A49822857615A9339687261A44A79837215518A948
3514A82768462519387957362A498A6847315A9179584261A28A69537213917A648324A281759435139286A54624A3971657
1277642585238875369634998647A745AA9758185611A869296722197A3A78332A814189443192529A5542A363A166531474
258149A49536925A15A647A3612617581472372869258348397A3694594A8147A56A519258167162A369278273147A389384
AA9351137511A4622486221573359733268446A844379557195548A6682A6659177931776A288A42887139915399824AA264
671613582578272469368938357A479A49468158A15A579269126168A37A237279148134838A259245949136A356A5A24714
4634978A355745A89146685619A25779672A13688A78312479918942358AA29A53469113A16457A224127568133523867924
59658246A56A769357167187A46827829815793893A9268A49A41A37915A152148A261263259137237436A24834854713594
74A9A63255851A1743669621285477A73239658818434A769929545187AA3A65629811417673A9225287841A336398952144
83583A9965946941AA76A57A521187168163229827927433A938A385441A49149655215A25A7663261361877437247298854
914A257145A2513682561362479367247358A478358469158946957A269A57A68137A168179248127928A359238A39146A34
159672394126A7834A5237189451634829A56274593A1673856A4127849671523895A7826349A61893745A1729A48561283A
2A74839151318594A2624296A5137353A7162484641827359575293846A6863A49571797415A6828A8526179391963728A4A
A285177261139628837224A739948335184AA59446295116A5573A622716684173382779528449388A63955A499174A6615A
6869352471797A4635828A8157469391926857A4A2A379681513148A79262425918A373536A29148464713A259575824136A
491826A3815A29371492613A4825A3724159361483526A47259463715836A5748269471685937A582796A4816938A715927A
572AAA659168311176A279422287138A53339824916444A935A275551A461386662157249777326835A8884379461999548A
7347485AA1845859611295696A7223A67A7183341781829445289293A55639A3A416674A141527785125263889623637499A
81A15486219212659732A32376A84314348719542545982A653656A9317647671A4287587821539869893264A97A9A43751A
9452694831A5637A59421674816A5327859271643896A3827549A71493865A1825A49761293615A8723A472619834158372A
14113761A22522487213363359832447446A9435585571A54669668216577A779327688188A43879929915498AA3AA265A91
23222222223433333333454444444456555555556766666666787777777789888888889A99999999A1AAAAAAAA1211111111
A167A3A9321278141A432389252154349A36326545A14743765612585487672369659878347A76A9894581871A9A56929821
62A44A4342731551545384266265649537737675A6488487861759959897286AA6A9A83971171A194A8228212A5193393231
455555555256666666636777777774788888888589999999969AAAAAAAA7A1111111181222222229233333333A3444444441
5A466684626157779573726888A6848379991795948AAA28A6A59111391716A2224A282713335139382444624A4935557351
777879767288898A8783999A919894AAA1A2A9A51112131A16222324212733343532384445464349555657545A6667686561
883A8818129941992923AA52AA3A34116311414522742252563385336367449644747855A7558589661866969A772977A7A1
9999149A92AAAA25A1A3111136121422224723253333583436444469454755557A56586666816769777792787A8888A38981
9533A12669A64412377A175523488128663459923977456AA34A88567114519967822562AA789336731189A44784229A1558
3335736414444684752555579586366668A69747777917A858888A2819699991392A7AAAA24A3181111351429222246253A3
A69298637917A3A9748A28141A859139252196A24A3632A713514743182462585429357369653A46847A7641579581875268
368A813882479192499358A2A35AA469131461157A2425722681353683379246479448A35758A559146869166A25797A2771
866329675897743A7869A88541897A1996529A812AA763A19231187412A34229852314533A9634256441A745367552185647
38739AA2A74984A113185A9512242961A623353A721734464183284557529439566863A54A6779741651788A852762899196
4824718739593582984A6A4693A9517157A41A6282681521739379263284A48A37439515914854A626A259651737136A7628
2749914918385AA25A29496113613A5A722472416183358352729446946383A557A5749416681685A52779279616388A38A7
4179426863528A5379746391648A8574A2759196851386A2A79624971318A735A82429184619353A29572A46413A68315752
123456789A123456789A123456789A123456789A123456789A123456789A123456789A123456789A123456789A123456789A
23456789A123456789A123456789A123456789A123456789A123456789A123456789A123456789A123456789A123456789A1
3456789A123456789A123456789A123456789A123456789A123456789A123456789A123456789A123456789A123456789A12
456789A123456789A123456789A123456789A123456789A123456789A123456789A123456789A123456789A123456789A123
56789A123456789A123456789A123456789A123456789A123456789A123456789A123456789A123456789A123456789A1234
6789A123456789A123456789A123456789A123456789A123456789A123456789A123456789A123456789A123456789A12345
789A123456789A123456789A123456789A123456789A123456789A123456789A123456789A123456789A123456789A123456
89A123456789A123456789A123456789A123456789A123456789A123456789A123456789A123456789A123456789A1234567
9A123456789A123456789A123456789A123456789A123456789A123456789A123456789A123456789A123456789A12345678
A123456789A123456789A123456789A123456789A123456789A123456789A123456789A123456789A123456789A123456789

 Профиль  
                  
 
 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
862
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
862
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, PAV, Toucan, maxal, Супермодераторы



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

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


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

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