2014 dxdy logo

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

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




Начать новую тему Ответить на тему На страницу Пред.  1, 2, 3, 4, 5, 6, 7 ... 16  След.
 
 Re: Новый конкурс Зиммерманна
Сообщение23.11.2010, 11:23 
Заблокирован
Аватара пользователя


22/03/08

7154
Саратов
dvorkin_sacha в сообщении #379417 писал(а):
Алгоритм здесь может быть только один.


Позвольте с вами не согласиться.
Алгоритмов существует несколько. Уверена в этом.
Я высказала основную идею алгоритма: улучшение уже полученных последовательностей путём различных преобразований.
А вот способов улучшения существует очень много.
Знаю по крайней мере два. Одним из них сейчас пользуюсь.

У меня самый обыкновенный компьютер. Кроме того, я пишу программы на древнем языке Бейсик.
Не стремлюсь в верхние ряды. Мне нравится решать задачу.
Я уже приводила цитату из Высоцкого: "Тут кто как умеет", У Высоцкого продолжение такое: "...мне важно увидеть восход". А мне важно увидеть, что у меня тоже получается.

Участники моей команды пока занимаются теоретическими исследованиями, так что последние результаты только мои.
Отнюдь не считаю, что они хорошие, но главное - они есть. К тому же, они ведь ещё не окончательные. Вот завершу первый ряд улучшений и примусь за второй.

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

Вот сейчас получила для $n=61$ результат 3087 и очень рада. Предполагаемый максимум 3242, так это же уже совсем близко.
При этом я заметила, что этот алгоритм даёт с ростом $n$ не худшие, а даже лучшие результаты.
Сейчас буду решать задачу для $n=67$. Надеюсь на хороший результат.

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


04/11/10

141
Nataly-Mak в сообщении #379436 писал(а):
dvorkin_sacha в сообщении #379417 писал(а):
Алгоритм здесь может быть только один.


Позвольте с вами не согласиться.
Алгоритмов существует несколько. Уверена в этом.

Разумный на данной ступени человеческого развития - только один. А его реализаций - множество: этим лидеры конкурса и отличаются друг от друга (хотя отличие определяется в основном мощностью "железа"), и не более того. Еще раз повторюсь: конкурс нечестный, т.к. результаты зависят от мощности "железа". Ну, если кому-то доставляет удовольствие лозунг: "Самое главное - участие, а не результаты", то пожалуйста. И тогда Высоцкий здесь в самый раз.

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


22/03/08

7154
Саратов
Вот для $n=67$ решила задачу, результат 3506 (предполагаемый максимум 4200), имею 0,83 от максимума, тоже неплохо для первого приближения.
Перехожу к $n=71$.

А на конкурсе захватывающая борьба идёт за первое место. И это в самом начале конкурса! А что будет в конце?

Я "болею" за Jarek'а.

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


04/11/10

141
EtCetera в сообщении #374955 писал(а):
Самое забавное, что процесс вовсе не обязан заканчиваться на последовательности в естественном порядке (главное, чтобы сверху появлялась 1), но для колод длиной 2, 3, 5, 7, 11 и 13 (и 6, как в примере) это правило почему-то выполняется (не знаю, как дальше).

Если Вы достигли естественной последовательности, то ей соответствует результат близкий к максимальному или равный ему (конечно, если Вы находитесь в рамках оптимального алгоритма). Это хороший критерий для поиска.

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


22/03/08

7154
Саратов
Ну, вот, вполне довольна своими результатами на сегодня.
У меня остались две задачи: $n=89$ и $n=97$. Завтра дорешаю.
Пока имею 18,1 балла.

-- Вт ноя 23, 2010 18:35:17 --

dvorkin_sacha в сообщении #379494 писал(а):
Если Вы достигли естественной последовательности, то ей соответствует результат близкий к максимальному или равный ему

Вы хотите сказать, что если некоторая последовательность {a_n} приводит к тождественной перестановке, то это гарантирует максимум перекладываний? Я правильно поняла?

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


04/11/10

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

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


22/03/08

7154
Саратов
Вот эта последовательность для $n=18$

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

приводит к тождественной перестановке.
Значит ли это, что для n=18 в общем случае максимальный результат 191, как для приведённого варианта?

Мне кажется, что это не так, то есть в общем случае максимум может быть совсем другим.

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


22/03/08

7154
Саратов
Это очень увлекательное занятие! Хотела бросить уже на сегодня, но... решу ещё одну задачку :-)

Решила, тоже неплохой результат получился. Поднялась аж на 15-ое место. Так высоко мы в прошлом конкурсе не поднимались, у нас было самое высокое (оно же и окончательное) 18-ое место.
Ну, разумеется, меня завтра же отодвинут, а может, даже сегодня.

Теперь одна задачка осталась, с самым большим количеством перекладываний. Эту уж оставлю на завтра.

А количество участников всё растёт, уже за 200 перевалило. Появилась тёзка у меня, девушка из Италии, но с русской фамилией - Петрова, и звать её Наташа.

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


04/11/10

141
Я писал: "результат близкий к максимальному или равный ему". С чего Вы взяли, что у меня эти два понятия эквивалентны?

P.S.
А находясь в дружбе с такими товарищами, как Jarek, можно достичь еще больших высот, чем 15-ое.

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


22/03/08

7154
Саратов
dvorkin_sacha в сообщении #379627 писал(а):
P.S.
А находясь в дружбе с такими товарищами, как Jarek, можно достичь еще больших высот, чем 15-ое.

Jarek участвует в конкурсе индивидуально и не является членом моей команды.
Он не имеет права со мной сотрудничать, ибо это будет нарушением правил конкурса.
Боюсь, что вам придётся извиниться перед Jarek'ом за ваши сомнительные намёки.

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


04/11/10

141
Мне извиняться не за что: для людей, которые вникли в эту задачу, все видно невооруженным глазом. А почему я так написал, объясню за день до окончания конкурса. И я лично никого не называл, а написал "с такими товарищами, как".

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


04/11/10

141
Nataly-Mak в сообщении #379398 писал(а):
Придуманный алгоритм даёт неплохие результаты. Мне удалось улучшить результаты svb до $n=47$:

Код:
19 192
...
...
...


Как я понял, этот результат получен из опубликованной последовательности для n=18, содержащей ошибку. Но, наверное, позже Вы это поняли и результат стал 193 :D. Хотя с таким подходом многого не добьешься.

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


21/02/10
1594
Екатеринбург
Теорема. Существует перестановка из n чисел, для которой количество инверсий максимально и конечная перестановка является возрастающей последовательностью чисел от 1 до n.
Доказательство. Пусть у нас есть перестановка P, которая за m инверсий приходит к позиции с 1 вначале. Пусть в конечной перестановке на позиции n стоит число i. Это означает, что в начальной позиции число i тоже стояло на позиции n и в процессе инверсий своей позиции не меняло. Но тогда поменяв в начальной перестановке P местами число n и i, мы получим перестановку P’, которая приводит к перестановке с 1 впереди как минимум за m+1 инверсий.

 Профиль  
                  
 
 Re: Новый конкурс Зиммерманна
Сообщение03.12.2010, 14:40 
Заслуженный участник


04/05/09
4582
Это доказательство лишь того, что в первой и последней позициях будут 1 и n соответственно.

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


21/02/10
1594
Екатеринбург
venco в сообщении #383102 писал(а):
Это доказательство лишь того, что в первой и последней позициях будут 1 и n соответственно.


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 229 ]  На страницу Пред.  1, 2, 3, 4, 5, 6, 7 ... 16  След.

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



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

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


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

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