Конкурс Зиммерманна о перекладывании карт

[Nataly-Mak]

dvorkin_sacha в сообщении #379417 писал(а):

Алгоритм здесь может быть только один.

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

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

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

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

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

[dvorkin_sacha]

Nataly-Mak в сообщении #379436 писал(а):

dvorkin_sacha в сообщении #379417 писал(а):

Алгоритм здесь может быть только один.

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

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

[Nataly-Mak]

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

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

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

[dvorkin_sacha]

EtCetera в сообщении #374955 писал(а):

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

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

[Nataly-Mak]

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

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

dvorkin_sacha в сообщении #379494 писал(а):

Если Вы достигли естественной последовательности, то ей соответствует результат близкий к максимальному или равный ему

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

[dvorkin_sacha]

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

[Nataly-Mak]

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

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

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

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

[Nataly-Mak]

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

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

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

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

[dvorkin_sacha]

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

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

[Nataly-Mak]

dvorkin_sacha в сообщении #379627 писал(а):

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

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

[dvorkin_sacha]

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

[dvorkin_sacha]

Nataly-Mak в сообщении #379398 писал(а):

Придуманный алгоритм даёт неплохие результаты. Мне удалось улучшить результаты svb до $n=47$:

19 192
...
...
...

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

[Pavlovsky]

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

[venco]

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

[Pavlovsky]

venco в сообщении #383102 писал(а):

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

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