2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1 ... 11, 12, 13, 14, 15, 16  След.
 
 Re: Новый конкурс Зиммерманна
Сообщение15.02.2011, 23:51 


04/11/10

141

(Оффтоп)

Не я первый начал. Но если даже и не читаете, то это не повод для написания всякой несуразицы.

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #413399 писал(а):
Pavlovsky
вы поняли, как именно Кнут использует предыдущие рекордные последовательности? Это очень интересный вопрос.


Кнут исползует не предыдущие рекордные последовательности, а собственно рекордное число инверсий.

Вот фрагмент кода из алгоритма Кнута.
Код:
if (k==t) {
  for (t=1;a.q[t]==k-t;t++);
  if (c+score[k-t]<score[n]) goto infeas;
}@+else if (c+score[t]<score[n]) goto infeas;


Как он работает я не разобрался, но полагаю примерно следующее. Пусть мы ищем перестановку порядка N. И пусть после различных манипуляций, число N стало первым в перестановке. Тогда количество инверсий от этой перестановки до конца не может превышать рекорд для перестановки порядка N-1.

В коде Кнута смущает, что рекорды он проверяет дважды: c+score[k-t]<score[n] и c+score[t]<score[n]. Чего то я не догоняю.

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


22/03/08

7154
Саратов
Вот здесь все результаты, найденные ice00 по программе Кнута. Может быть, пригодятся при изучении алгоритма Кнута.

Стефано пишет мне, что народ на сайте Зиммерманна говорит о целесообразности опубликовать максимальные последовательности для всех $n$, а не только для простых.
В самом деле, это было бы неплохо.
У меня, например, в БД максимальные последовательности для всех $n$, так их находит программа Х, так они и записываются в файл result.txt.

Например, до сих пор неизвестна максимальная последовательность для $n=18$ (может, только мне неизвестна), не приводящая к тождественной перестановке. Предполагаю, согласно моей гипотезе, что результат для такой последовательности будет не меньше 191 шагов. И далее для n=20, 21, 22 тоже неизвестны максимальные последовательности для общего случая.

-- Ср фев 16, 2011 11:41:48 --

Вот небольшой фрагменn нашей БД:

Код:
20:[]:249: 2,8,11,6,19,17,13,7,18,3,9,20,15,1,12,4,10,14,5,16
21:[]:269: 4,7,16,6,17,3,10,13,8,5,21,15,11,12,2,9,14,20,18,1,19
22:[]:291: 2,9,16,3,13,5,10,15,7,21,14,18,22,20,12,6,19,4,8,1,11,17
23:[]:370: 4,17,5,12,11,14,19,22,6,21,9,15,10,7,2,13,1,23,20,16,3,8,18
24:[]:371: 4,17,5,12,11,14,19,22,6,21,9,15,10,7,2,13,24,23,20,16,3,8,18,1
25:[]:400: 8,16,13,7,14,12,15,3,2,4,23,10,5,22,6,9,1,24,20,11,25,19,17,21,18
26:[]:442: 3,18,12,15,17,16,20,22,26,11,14,13,4,8,19,5,2,7,21,6,10,9,25,1,23,24
27:[]:477: 2,7,8,19,16,12,5,9,13,17,20,18,10,11,14,3,4,26,6,15,23,27,24,25,1,21,22
28:[]:549: 8,17,24,1,18,9,10,2,13,11,3,14,12,4,16,23,5,20,6,7,25,28,26,15,27,22,21,19
29:[]:609: 7,16,17,18,9,21,6,22,20,11,13,2,8,10,4,15,5,12,27,3,14,19,28,26,1,29,25,24,23
30:[]:634: 3,6,4,7,17,11,9,22,13,14,10,8,2,5,19,24,15,23,21,16,18,12,26,20,30,29,28,1,25,27

Кстати, программа Х работала у меня буквально до последней минуты конкурса. В 18.58 выдала последнее улучшение для $n=58$ - 3567 шагов. В 19.00 я остановила программу и пошла смотреть финал конкурса.
Последнее улучшение для простого $n$ было найдено программой 3 февраля. Таким образом, мне хватило моего алгоритма на весь конкурс и возможности его далеко не исчерпаны. Можно было бы найти ещё немало улучшений, если добавлять не 10-11 карт максимально, как это делала я, а хотя бы 12-13.
В программе Х наращивание последовательностей хорошо оптимизировано с учётом первых-первых чисел, поэтому перебор идёт не тупо, что даёт значительный выигрыш времени.

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


21/02/10
1594
Екатеринбург
Nataly-Mak
Суть вашего алгоритма хорошо видна на примере перестановки:

29:[]:609: 7,16,17,18,9,21,6,22,20,11,13,2,8,10,4,15,5,12,27,3,14,19,28,26,1,29,25,24,23
Ниже представлена перестановка первых-первых для этой перестановки:
FFRONT()= (7,6,16,15,17,5,10,20,3,12,4,9,2,8,21,14,18,13,22,19,11)+(27,25,28,24,26,29,23)

Перестановка первых-первых разбивается на две части. Сначала в последовательности первых чисел появляются числа от 2 до 22. А затем к полученной перестановке добавляются числа от 23 до 29.
Парадоксально, но факт такой алгоритм дал хорошие результаты. Почему? Для меня до-сих пор загадка.

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

Гипотеза. Перестановку первых-первых чисел рекордной перестановки нельзя разбить на две части: (перестановка чисел от 2 до к)+(перестановка чисел от k+1 до n).

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


22/03/08

7154
Саратов
Pavlovsky в сообщении #413567 писал(а):
Парадоксально, но факт такой алгоритм дал хорошие результаты. Почему? Для меня до-сих пор загадка.

А почему парадоксально?
Цитата:
Анализ лучших результатов показывает что рекордные перестановки нельзя разбить подобным образом. Более того правдободбной выглядит гипотеза.

Гипотеза. Перестановку первых-первых чисел рекордной перестановки нельзя разбить на две части: (перестановка чисел от 2 до к)+(перестановка чисел от k+1 до n).

Это интересная гипотеза. Исходя из этой гипотезы, можно утверждать, что алгоритм наращивания последовательностей не может дать максимальную перестановку. Я правильно поняла?
А если этот алгоритм работает вместе с алгоритмом поиска вглубь?
----------
Tomas Rokicki продолжает побивать рекорды:

Код:
43 cards 2009 Tomas Rokicki
12, 28, 13, 21, 26, 11, 15, 22, 2, 4, 20, 18, 23, 9, 24, 7, 27, 3, 16, 14, 25, 5, 8, 6, 17, 30, 19, 10, 33, 34, 38, 42, 41, 37, 39, 32, 29, 31, 36, 43, 35, 1, 40
61 cards 4858 Tomas Rokicki
4, 54, 7, 25, 28, 17, 35, 42, 15, 31, 46, 51, 1, 56, 58, 21, 47, 2, 37, 9, 3, 12, 49, 43, 19, 50, 36, 30, 8, 38, 23, 33, 13, 24, 20, 41, 16, 27, 45, 39, 11, 6, 52, 14, 29, 34, 10, 55, 22, 40, 44, 60, 32, 48, 18, 5, 59, 26, 61, 57, 53

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


21/02/10
1594
Екатеринбург
Pavlovsky в сообщении #413567 писал(а):
А если этот алгоритм работает вместе с алгоритмом поиска вглубь?


Вот примеры луших результатов нашей команды.
29: 7,16,17,18,9,21,6,22,20,11,13,2,8,10,4,15,5,12,27,3,14,19,28,26,1,29,25,24,23
FFRONT= (7,6,16,15,17,5,10,20,3,12,4,9,2,8,21,14,18,13,22,19,11)+(27,25,28,24,26,29,23)

31: 4,17,5,12,11,14,19,22,6,21,9,15,10,7,2,13,26,23,20,16,3,8,18,28,1,29,31,30,25,24,27
FFRONT=(4,12,15,2,7,6,11,5,10,14,9,22,8,19,20,3,21,16,13,17,23,18)+(26,29,25,31,27,28,24,30)

37: 8,16,13,7,14,12,15,3,2,4,23,10,5,22,6,9,30,24,20,11,25,19,17,21,18,33,36,29,1,34,26,28,35,31,32,37,27
FFRONT=(8,3,12,10,7,2,4,16,9,6,5,14,13,15,22,19,20,23,17,11,24,21,25,18)+(30,34,31,36,37,27,33,29,26,28,35,32)

Как видите поиск в глубину ничего дополнительного не дал.

-- Ср фев 16, 2011 15:28:27 --

Nataly-Mak в сообщении #413588 писал(а):
Это интересная гипотеза. Исходя из этой гипотезы, можно утверждать, что алгоритм наращивания последовательностей не может дать максимальную перестановку. Я правильно поняла?

Поняли правильно. Только уточню это всего лишь гипотеза.

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


22/03/08

7154
Саратов
Вот посмотрите на последовательность, которая получена по программе наращивания последовательностей (как раз это было последнее, полученное мной улучшение, работала от последовательностей $n=50$, добавляла максимально 9 карт):

Код:
58:[]:3542: 56,52,51,57,55,58,47,54,46,50,43,41,36,44,30,32,37,45,42,48,49,11,5,10,22,23,21,15,17,28,24,19,7,14,16,12,2,3,6,4,9,13,8,27,33,20,26,18,25,35,40,34,38,31,39,29,1,53

Здесь результат 3542, потом с помощью отдельной программы поиска вглубь этот результат был улучшен до 3567 шагов.

Я не вижу в приведённой последовательности привычного для наращенных последовательностей окончания. Будет ли для этой последовательности выполняться разделение перестановки первых-первых чисел на две группы, как вы показали выше?

-- Ср фев 16, 2011 15:08:48 --

Это окончательный результат (улучшение при помощи отдельной программы поиска вглубь):

Код:
58:[]:3567: 42,48,33,20,26,18,25,31,39,37,23,6,32,16,10,5,27,9,13,12,8,35,40,34,38,49,56,52,51,57,55,58,47,54,46,50,43,29,41,36,44,30,45,19,24,28,21,7,22,17,15,11,2,4,14,3,1,53

Тут уже вообще не видно, что к чему добавлялось.

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


21/02/10
1594
Екатеринбург
Код:
58:[]:3542: 56,52,51,57,55,58,47,54,46,50,43,41,36,44,30,32,37,45,42,48,49,11,5,10,22,23,21,15,17,28,24,19,7,14,16,12,2,3,6,4,9,13,8,27,33,20,26,18,25,35,40,34,38,31,39,29,1,53

Здесь какая то ошибка эта перестановка не является результатом наращивания. Число 56 при наращивании никак не может быть на первом месте.


58:[]:3567: 42,48,33,20,26,18,25,31,39,37,23,6,32,16,10,5,27,9,13,12,8,35,40,34,38,49,56,52,51,57,55,58,47,54,46,50,43,29,41,36,44,30,45,19,24,28,21,7,22,17,15,11,2,4,14,3,1,53
FFRONT=42,30,32,23,35,31,49,22,6,9,10,16,19,48,56,3,4,2,14,13,11,8,17,7,12,5,27,45,29,28,41,15,21,18,25,20,26,24,33,38,37,34,40,36,39,44,46,43,50,47,54,51,55,52,58,53,57

В этой перестановке, число 56 улетело куда то в середину. И поэтому перестановку первых-первых нельзя разделить. Хотя огрызки наращивания видны четко.

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


22/03/08

7154
Саратов
Ещё раз копирую из рабочего файла программы эту последовательность (благо рабочий файл у меня ещё жив):

Код:
58:[]:3542: 56,52,51,57,55,58,47,54,46,50,43,41,36,44,30,32,37,45,42,48,49,11,5,10,22,23,21,15,17,28,24,19,7,14,16,12,2,3,6,4,9,13,8,27,33,20,26,18,25,35,40,34,38,31,39,29,1,53


Никакой ошибки быть не может!
Насколько я поняла автора программы Х, у него работает только алгоритм наращивания (второй алгоритм я блокирую в этой программе, потому что у меня только одно ядро в процессоре), то есть добавление к исходной последовательности $m$ карт.
Но вот перебор он делает, как я уже сказала, не так тупо, как это делала я, а как-то хитро (с учётом первых-первых чисел).

Почему же число 56 по-вашему не может быть на первом месте?
К исходной последовательности для $n=50$ добавляется 8 карт: 51, 52, 53, 54, 55, 56, 57, 58.

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


04/11/10

141
Я уже писал по поводу n = 43. Выдалась свободная минута - посмотрел на рекордное решение более внимательно и обнаружил прокол. Через 20 минут получил 2 решения с числом перекладываний 2009.

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


21/02/10
1594
Екатеринбург
Nataly-Mak в сообщении #413643 писал(а):
Код:
58:[]:3542: 56,52,51,57,55,58,47,54,46,50,43,41,36,44,30,32,37,45,42,48,49,11,5,10,22,23,21,15,17,28,24,19,7,14,16,12,2,3,6,4,9,13,8,27,33,20,26,18,25,35,40,34,38,31,39,29,1,53


Понял эту перестановку надо перелистнуть на шаг вперед.
58: 29,39,31,38,34,40,35,25,18,26,20,33,27,8,13,9,4,6,3,2,12,16,14,7,19,24,28,17,15,21,23,22,10,5,11,49,48,42,45,37,32,30,44,36,41,43,50,46,54,47,58,55,57,51,52,56,1,53
FFRONT = 29,15,13,28,39,45,41,11,7,23,8,3,4,9,2,6,12,14,5,10,17,16,22,21,19,18,25,20,26,27,24,33,38,30,37,34,32,35,31,40,36,44,42,48,46,43,50,47,49,54,51,55,52,58,53,57,56

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


22/03/08

7154
Саратов
Цитата:
Понял эту перестановку надо перелистнуть на шаг вперед.

Ну вот, значит всё чётко и у меня, и у вас, что очень приятно :-)

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


22/03/08

7154
Саратов
В OEIS добавлен результат 207 последовательности для $n=19$.
A000376

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


22/03/08

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

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

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

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

А вот по поводу того, является ли максимумом результат 221 для $n=19$, "молчит наука" :-)

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


21/02/10
1594
Екатеринбург
Забавно. Лидеры тоже пользовались алгоритмом наращивания!
53: 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,34,23,25,32,33,29,41,30,31,40,38,44,39,49,43,35,37,36,51,42,53,1,52,50,45,46,48,47

FFRONT=12,3,13,6,9,15,11,2,16,4,5,17,7,14,8,19,10,(21,24,18,20,22,27,23,26,28,25),(34,31,32,33,29,30),(41,35,43,36,37,39,40,38,44,51,46,50,45,42,49,52,48,53,47)

Можно видеть аж две процедуры наращивания в чистом виде и одну немного сглаженную(выпадает число 19). При последней процедуре наращивания добавлено аж 19 чисел!

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

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



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

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


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

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