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

[Nataly-Mak]

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

Nataly-Mak

Вы не обижайтесь, но я и назвал алгоритм, о котором вы говорите, алгоритмом с тупым перебором. А что касается алгоритма для получения тождественной последовательности, то интересно посмотреть результат, например, для n = 22: я ведь привел результаты для n = 20 и n = 21. А так это голословное утверждение.

Я не обижаюсь, а уточняю: не занималась тупым перебором. Алгоритм использвания случайной генерации - это не совсем то, что называют тупым перебором. Да, случайная генерация комбинаций - это примитивный алгоритм, что я и говорила в своём сообщении. Но этот алгоритм давно оставлен, сейчас-то я пользуюсь другим алгоритмом, который, может быть, тоже довольно примитивный, но уже даёт лучшие результаты, чем первый алгоритм.

По поводу алгоритма получения последовательностей, приводящих к тождественной перестановке.
Вы очень невнимательно читаете сообщения!

Во-первых, этот алгоритм разработал svb.
Во-вторых, я приводила здесь последовательность для $n=15$, найденную мной по программе, присланной мне svb. Я её опробовала, она прекрасно работает (по крайней мере, для тех $n$, для которых я пробовала).
Так что, никакой голословности.

Однако меня не интересуют последовательности, приводящие к тождественной перестановке, так как я уже убедилась в том, что такие последовательности не дают максимальных результатов. Более того! Такие последовательности очень плохи для моего алгоритма наращивания последовательностей. Для этого алгоритма надо брать как раз последовательности, не приводящие к тождественной перестановке. Они дают гораздо лучшие результаты.

[svb]

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

svb

У Вас что-то с логикой. Вот мои слова: "в значительной своей части сводится к тупому перебору даже для хорошего алгоритма".

Отвечу в вашем стиле - тривиальная (в том смысле, что не сводится к тупому перебору). Может это вам и кажется странным, но все нетривиальные задачи требуют тупого перебора и не обязательно на компьютере. Единственное, что здесь обычно не применяют слово "тупого". Конечно, имеются люди, которые предполагают, что при решении задач им помогает нечто непостижимое, но опыт показывает, что все значительно проще. Сначала "загрузка" информации в мозг, в т.ч. загрузка различных методов (алгоритмов) решения, и только потом, если повезет, мозг после перебора ситуаций выдает решение.

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

-- Чт дек 09, 2010 19:33:30 --

Mathusic в сообщении #385396 писал(а):

Как видно, эта функция ведёт себя как $\frac{n!}{e}$ на бесконечности.

Самое смешное, что и не доходя до бесконечности эта формула дает возможность вычислять точные значения - см. мой пост.

[dvorkin_sacha]

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

Во-первых, этот алгоритм разработал svb.
Во-вторых, я приводила здесь последовательность для $n=15$, найденную мной по программе, присланной мне svb. Я её опробовала, она прекрасно работает (по крайней мере, для тех $n$, для которых я пробовала).
Так что, никакой голословности.

Для n = 15 ребенок на пальцах может сосчитать: у Вас и для $n = 19$ и для $n = 23$ (первые результаты, бросившиеся в глаза: хотел уточнить сегодня остальные, но Вы результаты "потерли") были вчера-позавчера приведены результаты, которые хуже для максимальных раскладок, приводящих к тождественной последовательности, так что не надо сказок. Ведь речь идет об алгоритме, который ищет не менее одной максимальной последовательности, приводящей к тождественной перестановке. Для любых других программу составить не составляет особого труда даже самому заядлому двоечнику. И потом, такая максимальная последовательность - это хорошая осмысленная оценка результата снизу (а может и сверху ).
Теперь что касается тупых перестановок: я имел в виду именно Ваше последнее предложение с наращиваемыми последовательностями, т.к. на самом деле существует более осмысленный алгоритм, использующий генерацию перестановок, и именно с ним можно добиться результата, но при одном условии: у Вас в руках суперкомп.

[Mathusic]

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

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

А вы не думали, что в этом и проблема? Вы нашли чудо-алгоритм (всего лишь за один какой-то вечер, так?), который по-вашему хорош, но будет эффективен для конкурса, только если у вас суперкомпьютер. Однако, почему-то вы не осмелились предположить, что другие участники в силах найти эвристические алгоритмы, эффективные на PC.

[Nataly-Mak]

Бред какой-то!

Я ничего не "тёрла":

Цитата:

n=19   220   202   
n =23   384   325   
n=29    662   584       
n=31    748   624    
n=37   1144     1029    
n=41   1422     1224     
n=43   1800     1325     
n=47    2171     1748     
n=53    2787     2158    
n=59    3809     2719 
n=61    4291     3449  
n=67    5270     3936  
n=71    6082     4912   
n=73    6477     5006  
n=79    8216     6345  
n=83    9032     6968  
n=89   11035     8711     
n=97   13230     10680

В последней колонке приведены полученные мной результаты.

Источник цитаты:

topic38394-60.html

Кстати, более осмысленный алгоритм, использующий генерацию перестановок, разработал профессор Кнут, о чём мне писал svb, разобравшийся в этом алгоритме.

Я уже писала здесь о том, что некоторые товарищи опробовали программу Кнута на обычных компьютерах. Она работает, но очень медленно. Так, например, один товарищ писал мне, что за несколько часов работы для больших $n$ эта программа даёт результаты в районе 500 шагов.

Очень может быть, что на кластере (или суперкомпьютере, что вроде бы одно и то же?) эта программа даст максимальные результаты за приемлемое время.

Да, и программа Кнута даёт разные последовательности, как приводящие, так и не приводящие к тождественной перестановке.
Здесь были приведены некоторые последовательности, найденные по этой программе.

И, наконец, самое интересное в том, что для моего примитивного алгоритма наращивания последовательностей не нужен суперкомпьютер, и результаты он даёт не за часы, а за минуты

[dvorkin_sacha]

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

Бред какой-то!

Я ничего не "тёрла":

Это не бред, а моя невнимательность: извиняюсь.

-- Пт дек 10, 2010 00:21:09 --

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

И, наконец, самое интересное в том, что для моего примитивного алгоритма наращивания последовательностей не нужен суперкомпьютер, и результаты он даёт не за часы, а за минуты

Да, конечно, мой алгоритм для нахождения произвольных последовательностей Вашему и в подметки не годится: например, тестовый пример с n = 17 он считал всю ночь, находя точное решение для "неправильной" поседовательности (при этом он прекрасно распараллелен).

[Nataly-Mak]

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

Так я не понимаю, в чём проблема?

Идите на конкурс и соревнуйтесь там со своими алгоритмами и результатами.

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

Я, например, ничего здесь не собираюсь доказывать, а участвую в конкурсе и выкладываю там свои результаты. И здесь выкладываю то, что разрешено правилами конкурса.

[dvorkin_sacha]

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

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

Так я не понимаю, в чём проблема?

Все последователности я не нашел даже для тождественных перестановок: на n = 31 мне стало жалко своих дисков. А об общем случае и говорить не приходится: с моим подходом к данной проблеме без хорошего железа на конкурсе делать нечего. Успехов: больше досаждать не буду.

[svb]

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

Кстати, более осмысленный алгоритм, использующий генерацию перестановок, разработал профессор Кнут, о чём мне писал svb, разобравшийся в этом алгоритме.

кхе-кхе ... до сих пор не разобрался. Львиная часть текста программы Кнута занимает вывод информации, который не имеет отношения к алгоритму поиска, но в начале в комментариях написано, что используется генератор перестановок. Но это не очень интересно, т.к. о генераторах перестановок хорошо написано у Липского. Один из вариантов я уже давно использую. Для достройки последовательностей я его слегка модифицировал, но это достаточно пустое занятие, т.к. выигрыш по времени ничтожный. Пустой генератор для $n=11$ на моем компьютере работает примерно 4 сек, т.е. основное время сжирают проверки последовательностей. Я не раскрою никакого секрета, если сообщу, что от любой последовательности можно двигаться вниз по единственному пути и вверх по нескольким (от 0 до $n-1$) путям. Т.е. все последовательности организуются в виде дерева. Обход дерева многократно описан в литературе и тоже не представляет секрета. Для данной задачи этот обход достаточно легко оптимизируется, но ... уже для $n=17$ ждать нужно очень долго, поэтому меня заинтриговали сообщения dvorkin_sacha о максимальных путях для $n=20,21$. То, что он рассматривает в качестве начальной последовательности упорядоченный набор, не имеет особого значения, т.к. именно они основные кандидаты на рекордсмены. Конечно, возможно он и блефует, но, если это не так, то снимаю шляпу перед ним даже в случае, если это не поможет ему для $n=97$. Об остальном я пока умолчу (хотя пока и говорить не о чем) до окончания конкурса. Кстати, соревнование даст пищу для оценки нижней границы - уже сейчас видно, что показатель при $n$ больше 2, кроме того, опыт получения квадратичной оценки нижней границы говорит о многом. Достаточно увеличить его до 3, чтобы выиграть конкурс

[Nataly-Mak]

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

...с моим подходом к данной проблеме без хорошего железа на конкурсе делать нечего.

А вы можете писать программы для "хорошего железа"?

На одном форуме (если интересно, ссылку дам) админ предлагал мне подключение к кластеру. Я, конечно, отказалась.
Но там была очень интересная дискуссия по этому вопросу, из которой я поняла, что для кластера программа нужна не абы какая, а написанная специальным образом, чтобы это самое распараллеливание происходило.

Вы пишете, что для $n=17$ у вас процесс прекрасно распараллелен. Значит, вы имеете об этом весьма чёткое представление. Там ещё должен быть какой-то специальный код (в программе для кластера), вот забыла сейчас, что-то вроде mpi-код (могу наврать, не помню).

[Pavlovsky]

Наличе кластеров, разжижает мозги и отучивает человечество думать. Посмотрите на математиков прошлого. Они без всяких компьютеров выдвали выдающиеся результаты. Например Россер с его статьей по дьявольским магическим квадратам.

[dvorkin_sacha]

Pavlovsky в сообщении #385645 писал(а):

Наличе кластеров, разжижает мозги и отучивает человечество думать. Посмотрите на математиков прошлого. Они без всяких компьютеров выдвали выдающиеся результаты. Например Россер с его статьей по дьявольским магическим квадратам.

Вот такой математик прошлого, как Гаусс, без численного эксперимента жить не мог: ему бы кластер уж точно мозги не разжижил, т.к. он рассматривал бы его как тупое, но необходимое подспорье. А вот еще один пример: ЗДЕСЬ я применил комп. (не кластер ) для нахождения коэффициентов в уравнении.

-- Пт дек 10, 2010 13:32:20 --

Nataly-Mak

О программировании под кластер имею самые смутные представления.

[Vitaly12]

Цитата:

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

Не обязательно. В конкурсах такого вида, когда есть набор независимых задач, можно каждому компьютеру из кластера задать поиск для другого "n". Это тоже распараллеливание.

[Nataly-Mak]

Дело в том, что современные суперкомпьютеры пока ещё всё-таки не могут заменить этап "придумывания алгоритма".
Прежде чем применить суперкомпьютер, надо написать хорошую программу, а для этого надо придумать хороший алгоритм.
Если, скажем, в данной задаче Зиммерманна, сунуть на кластер тупой перебор всех комбинаций, то, нверное, и кластер будет бессилен, например, уже для $n=41$.
Вот Кнут придумал некий алгоритм. Однако неясно, насколько он пригоден для кластера, можно ли из него сделать то самое распараллеливание, о котором все говорят, когда речь заходит о кластере.

-- Пт дек 10, 2010 14:41:18 --

Vitaly12 в сообщении #385698 писал(а):

Цитата:

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

Не обязательно. В конкурсах такого вида, когда есть набор независимых задач, можно каждому компьютеру из кластера задать поиск для другого "n". Это тоже распараллеливание.

Речь идёт не о таком распараллеливании, как поиск для различных $n$.
Распраллеливание имеется в виду в решении задачи для одного конкретного $n$.
И на том форуме однозначно было сказано, что для кластера нужна специальная программа.

-- Пт дек 10, 2010 14:48:02 --

Цитата:

когда я говорил про автоматическое распаралеливание, я имел в виду только то, что программу, написанную, так сказать, как mpi-aware, планировщик разбрасывает...

Цитата:

мы на это и пытаемся обратить твоё внимание: программу изначально надо писать как "mpi-aware"

Кроме того, как показывает опыт решения задачи, эти задачи для разных $n$ не являются совсем независимыми. Вполне можно засунуть в кластер алгоритм наращивания последовательностей; собирая данные о последовательностях для разных $n$ с различных узлов, центральный процессор будет выполнять наращивание этих последовательностей, что тоже даёт очень неплохие результаты.

[Vitaly12]

Цитата:

Распараллеливание имеется в виду в решении задачи для одного конкретного $n$.
И на том форуме однозначно было сказано, что для кластера нужна специальная программа.

Такое распараллеливание действительно имеет смысл, но лишь когда число компьютеров в кластере больше чем $n$.