2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 12, 13, 14, 15, 16  След.
 
 Re: Новый конкурс Зиммерманна
Сообщение17.02.2011, 10:52 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
Так значит алгоритм наращивания даёт-таки рекордные последовательности?

А между тем продолжает пополняться таблица рекордов:

Код:
89 cards 11810 Hugo Pfoertner
Munich, Germany 16 Feb 2011 11:44
12, 57, 8, 42, 31, 52, 67, 27, 23, 44, 3, 19, 47, 64, 58, 68, 18, 49, 30, 38, 66, 53, 45, 48, 56, 13, 20, 15, 26, 14, 51, 5, 54, 63, 72, 70, 24, 35, 9, 2, 33, 28, 34, 43, 6, 4, 65, 32, 55, 36, 25, 60, 21, 41, 39, 10, 7, 50, 17, 16, 22, 69, 61, 74, 75, 59, 40, 62, 11, 73, 76, 46, 37, 29, 78, 71, 88, 80, 84, 77, 86, 83, 81, 82, 87, 79, 89, 1, 85

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #413939 писал(а):
Так значит алгоритм наращивания даёт-таки рекордные последовательности?

Рекордные в рамках текущего конкурса, но не теоретически максимальные. :-)

-- Чт фев 17, 2011 13:06:36 --

К тому же непонято какие перестановки брать в качестве базовой для наращивания. Скажем в примере, приведенном выше, для N=53, базовая перестановка:
28: С = 442: 12,8,14,19,9,2,22,15,17,13,16,3,6,5,11,4,7,21,10,26,24,20,27,18,28,1,23,25
Абосолютно рядовая перестановка и очень далеко от рекорда для перестановок порядка 28. Подобных перестановок миллионы.

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


22/03/08

7154
Саратов
Цитата:
Рекордные в рамках текущего конкурса, но не теоретически максимальные. :-)

Ну о максимальных вообще речь не идёт, никто пока не заявил, что найденная им последовательность (рекордная на конкурсе) является максимальной. Как я уже писала, даже для $n=19$ неизвестно, является ли результат 221 максимальным.

Цитата:
К тому же непонято какие перестановки брать в качестве базовой для наращивания. Скажем в примере, приведенном выше, для N=53, базовая перестановка:
28: С = 442: 12,8,14,19,9,2,22,15,17,13,16,3,6,5,11,4,7,21,10,26,24,20,27,18,28,1,23,25
Абосолютно рядовая перестановка и очень далеко от рекорда для перестановок порядка 28. Подобных перестановок миллионы.

А вот тут как раз и нужна программа тотальной проверки последовательностей. Она проверяет все последовательности для данного $n$, какие у вас есть и потом ещё все, какие она сама получит в результате работы (все они очень методично записываются в рабочий файл программы, прямо ничего не надо делать, запустил программу и сиди книжечку почитывай). Это классная программа! Не устаю повторять - это восторг! Спасибо Х!
И вот удивительно как раз то, что очень часто улучшение получается как раз и не от последовательности с бОльшим числом шагов, а от последовательности с гораздо меньшим числом шагов.
Проверяются все последовательности! Добавляется от 6 до $m$ карт, $m$ задаётся как параметр.
К сожалению, быстродействие моего компьютера не позволило мне добавлять даже 12 карт, у меня максимально добавлялось 11 карт.
А у кого мощные компьютеры, да с многоядерными процессорами, то вообще можно по этой программе найти очень высокие результаты.

-- Чт фев 17, 2011 12:46:57 --

Яркий пример помню. Обрабатывала последоватьельности $n=79$; программа обрабатывает последовательности в порядке убывания количества шагов (начинает с самого большого результата, она сама ранжирует результаты, если они во входном файле заданы вразноброд); вот работала программа долго, у меня много было последовательностей $n=79$, порядка 300, улучшения не находилось, уже пошли очень маленькие количества шагов, я уже потеряла надежду на улучшение в этих переходах, и вдруг уже в самом почти конце массива последовательностей улучшение появилось для $n=89$ - 10410.

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение17.02.2011, 11:55 


04/11/10

141
Pavlovsky в сообщении #413933 писал(а):
Забавно. Лидеры тоже пользовались алгоритмом наращивания!

Открыли Америку! Я об этом написал несколько дней назад и даже улучшил результат для n = 43. Вот Вы лучше попытайтесь найти принципиальные отличия в подходах 2-х первых лидеров. Но думаю, что эта задача Вам не "по зубам".

-- Чт фев 17, 2011 11:55:38 --

Nataly-Mak в сообщении #413954 писал(а):
[А вот тут как раз и нужна программа тотальной проверки последовательностей.

Неа.

-- Чт фев 17, 2011 11:55:57 --

Nataly-Mak в сообщении #413928 писал(а):
Существуют последовательности с результатом 207, не приводящие к тождественной перестановке, вот одна из них (результат svb):

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


Я уже 100 лет назад написал, что там два решения.

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


21/02/10
1594
Екатеринбург
Уважаемый dvorkin_sacha шел бы ты в жопу. Еще не хватало чтоб всякие недоноски терли об меня свои комплексы.

 !  Недельный бан за хамство!

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение17.02.2011, 12:56 


04/11/10

141
Pavlovsky в сообщении #413963 писал(а):
Уважаемый dvorkin_sacha шел бы ты в жопу. Еще не хватало чтоб всякие недоноски терли об меня свои комплексы.

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

 !  Предупреждение за оффтопик!

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение17.02.2011, 13:12 


24/11/10
48
dvorkin_sacha в сообщении #413968 писал(а):
Pavlovsky в сообщении #413963 писал(а):
Уважаемый dvorkin_sacha шел бы ты в жопу. Еще не хватало чтоб всякие недоноски терли об меня свои комплексы.

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

Сначала спровоцировать, а потом довольно хмыкать - классический тролль (par excellence!).

 !  Предупреждение за оффтопик!

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение17.02.2011, 13:36 


04/11/10

141
Vitaly12 в сообщении #413972 писал(а):
dvorkin_sacha в сообщении #413968 писал(а):
Pavlovsky в сообщении #413963 писал(а):
Уважаемый dvorkin_sacha шел бы ты в жопу. Еще не хватало чтоб всякие недоноски терли об меня свои комплексы.

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

Сначала спровоцировать, а потом довольно хмыкать - классический тролль (par excellence!).

Ваша логика сродни поинманию Вами задачи о картах: т.е. никакой.

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение17.02.2011, 14:12 


24/11/10
48
Цитата:
Сначала спровоцировать, а потом довольно хмыкать - классический тролль (par excellence!).


Цитата:
Ваша логика сродни поинманию Вами задачи о картах: т.е. никакой.


Ч.Т.Д.

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


19/12/10
1546
Pavlovsky в сообщении #413540 писал(а):
В коде Кнута смущает, что рекорды он проверяет дважды: c+score[k-t]<score[n] и c+score[t]<score[n]. Чего то я не догоняю.

Вы абсолютно правы. Проверка c+score[t]<score[n] излишняя.
Анализ алгоритма показывает, что всегда выполняется c+score[t]>=score[n].
Похоже Профессор перестраховался :-) .

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


22/03/08

7154
Саратов
Х пишет, что попробовал найти последовательность порядка 10000.

Цитата:
Часов через 5 программа дошла до 4633:[]:34014318: До 10000 нужно еще примерно 11 часов. Надоело ждать. Прервал.


Ещё он сообщил ссылку на интересную статью:

Цитата:
В статье http://habrahabr.ru/blogs/algorithm/102364/
показан интересный способ реверса массива.

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


22/03/08

7154
Саратов
Новый рекорд у Зиммерманна:

Код:
89 cards 11829 Hugo Pfoertner
34, 39, 19, 43, 58, 57, 20, 41, 31, 6, 67, 18, 14, 46, 48, 12, 37, 33, 26, 17, 36, 32, 49, 29, 50, 8, 38, 65, 61, 55, 54, 63, 5, 13, 59, 47, 27, 62, 35, 30, 51, 74, 75, 21, 28, 9, 4, 69, 56, 66, 42, 7, 23, 10, 60, 44, 52, 40, 64, 68, 2, 45, 3, 72, 70, 24, 25, 16, 11, 73, 76, 15, 22, 53, 78, 71, 88, 80, 84, 77, 86, 83, 81, 82, 87, 79, 89, 1, 85

Теперь, когда все алгоритмы известны, все "секреты" раскрыты, желающие могут попробовать найти новые рекорды. Особенно те, кто не участвовал в конкурсе и не устал от задачи.
Я, например, до предела сыта задачей :-) Уже вернулась к любимым квадратам. Он мне кажутся намного интересней этой задачи.

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #414539 писал(а):
В статье http://habrahabr.ru/blogs/algorithm/102364/
показан интересный способ реверса массива.


Реализовал эту структуру данных. Чего то ничего не получилось. Все это работает ну очень медленно.

Кстати есть сомнения в эффективности и алгоритма Rokicki.
Vitaly12 в сообщении #400205 писал(а):
Ага. Есть все же некоторое улучшение


Достаточно посчитать количество выполняемых элементарных операций.

Алгоритм svb
Код:
while j>i do begin
    b:=a[i];a[i]:=a[j];a[j]:=b;inc(i);dec(j)
  end;


Алгоритм Rokicki

Код:
b[first] += p ;
b[prev] -= p ;
b[p] += first - prev ;

prev = first ;
p = b[prev] ;
do {
next = b[p] - prev ;
prev = p ;
p = next ;
// this is a possible flip here
} until (p == N) ;

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


20/01/10
766
Нижний Новгород
Отправил для задачи 10K свое решение 203,216,214. На это понадобилось около 50 ч. работы моего "крутого" компьютера (Duron 1.8, RAM 256M). Для меньшей длины 166852535 удалось сократить время работы до 2.5 часов. В отличии от основного конкурса в 10K практически невозможно "дорабатывать" последовательности - даже простое вычисление длины цепочки кушает очень много времени.

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение26.02.2011, 01:05 


04/11/10

141
Nataly-Mak в сообщении #415329 писал(а):
Теперь, когда все алгоритмы известны, все "секреты" раскрыты...

Ой ли? Например, где написано, как за 16 часов на 4-х ядрах сделать наращивание для n = 30, используя 16!? Думаю, что до алгоритмов лидеров догадались многие участники конкурса, а вот до их грамотной реализации - нет.

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 229 ]  На страницу Пред.  1 ... 12, 13, 14, 15, 16  След.

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



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

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


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

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