Здравствуйте, andyJB, Вы писали:

JB>Здравствуйте, Cruelty, Вы писали:

C>>С математической точки зрения ето сложная (трудная) задача. Поетому ета
C>>задача скорее етюд для программистов а не для математиков
JB>Не скажи. Вот, на бумажке быстро научился змею длины 47 делать. Знаю, что есть "бумажное" решение для 54 (им нас ПРОСТО ГЕНИЙ, наверное, порадует). А как как разумно уменьшить перебор, чтобы при этом получить более-менее точный результат — задача вполне математическая.


Да! Порадует! Я, ПРОСТО ГЕНИЙ, всегда готов придти на помощь! Молодец, ты сделал правильную ставку, ибо ставить всегда надо на нас, ГЕНИЕВ!!!

Кстати, чего так мало запросил? Чего мелочиться? 75 Устроит? Лови:

1 2 3 1 4 2 1 5 2 3 1 4 6
1 3 2 1 4 3 1 5 2 3 7
2 1 3 2 4 3 5 4 6
2 3 1 4 3 2 8

3 1 2 3 7
1 3 4 1 5 2 7
3 1 2 3 6
2 5 1 2 3 1 4 5 1 3 7
1 2 3 1 4 2 1

Каждая цифра — это номер изменяемой на шаге координаты. Набросал минут за 10 — уж очень долго рисовать кубы. Если немного подумать, можно и побольше сделать. А когда я закончу работу над эвристической программой, там и субоптимальные решения генерить можно будет. Исходя из общих тенданций, максимум для 8-мерного гиперкуба ожидается где-то в районе 100.

Кстати, кто-нибудь разгадает метод?
Как и все, что делаю Я, ПРОСТО ГЕНИЙ, — он ПРОСТ и ГЕНИАЛЕН!

Здравствуйте, Кодт, Вы писали:

К>http://mathworld.wolfram.com/Snake.html
К>приводит значения ...2, 4, 8, 14, 26...
В этом вопросе в народе есть определенная путаница. Эти цифры относятся к максимальному ЦИКЛИЧЕСКОМУ подграфу. Для максимального ЛИНЕЙНОГО подграфа другая последовательность.

Здравствуйте, vnp, Вы писали:

vnp>Рост, очевидно, экспоненциальный.
Это очевидно с самого начала — по соображниям, которые ты (абсолютно справедливо) привел ниже. Впрочем, и моя первоначальная гипотеза (отвергнутая после рассмотрения случая N=5), этому не противоречит. F(n) ~ C*Ф^n.

vnp>Вумудщзук почти это показал (две змеи на подкубах размерности N-1 плюс одно звено на переход).
Нет! Он утверждал нечто другое: представлял это как ТОЧНЫЙ результат.

vnp>ПРОСТО ГЕНИЙ указал, что так делать нельзя, т.к. обход второго подкуба не является независимым.
И был совершенно прав!

vnp>Можно, однако, выделить два подкуба размерности N-2 (00xx...xx и 11xx...xx). Обходы этих подкубов будут таки независимы , поэтому грубая оценка снизу:

vnp>L(N) > L(N-2) + 2
vnp>т.е. экспонента.
Ну да, если добавить пропущенную двойку. Кстати, F(n) дает более сильную оценку, т.к. у тебя L(n+1)/L(n) ~ sqrt(2), а для F(n) — Ф (золотое сечение).


vnp>А вообще-то, первые же две ссылки...
У кого-нибудь вторая ссылка открылась? Пароль требуется.

Здравствуйте, Cruelty, Вы писали:

C>С математической точки зрения ето сложная (трудная) задача. Поетому ета
C>задача скорее етюд для программистов а не для математиков (если конечно
C>никто не претендует на медаль Филдса )
Это ДВЕ РАЗНЫЕ задачи. Обе интересные. Куда можно выложить ПРОСТОЕ, но ГЕНИАЛЬНОЕ решение той задачи, что для программистов?

Кстати, навряд ли решение для N=8 можно будет найти перебором. Имеет место радикальное увеличение сложности. Если для n=6 моя программа дает ответ меньше, чем за секунду, то над случаем n=7 она работает уже три часа, и пока результата нет. С учетом того, что ожидаемый результат для n=8 составляет примерно 100, дело это безнадежное. Можно попробовать эвристику, но тогда сразу пропадают все гарантии "окончательности" ответа.

Здравствуйте, ПРОСТО ГЕНИЙ, Вы писали:

ПГ>Здравствуйте, vnp, Вы писали:

ПГ>Ну да, если добавить пропущенную двойку. Кстати, F(n) дает более сильную оценку, т.к. у тебя L(n+1)/L(n) ~ sqrt(2), а для F(n) — Ф (золотое сечение).

Да, двойка ушла в опечатку.

vnp>>А вообще-то, первые же две ссылки...
ПГ>У кого-нибудь вторая ссылка открылась? Пароль требуется.

Ну, у меня открылась. Предлагается эволюционная эвристика, основанная на первичном выборе по длине, и сортировке по tightness, с последующим турниром. Результаты (размернось — длина змеи — длина кольца)

8    97   90
9   186  180
10  358  344
11  680  630
12 1260 1236

Хай, vnp!

vnp>Ну, у меня открылась. Предлагается эволюционная эвристика, основанная на первичном выборе по длине, и сортировке по tightness, с последующим турниром. Результаты (размернось — длина змеи — длина кольца)
Очевидно, это не та ссылка. У меня она тоже открылась, но она — третья в приведенном тобой списке.
Вторая — вот эта.

Здравствуйте, Аноним, Вы писали:

А>Хай, vnp!

vnp>>Ну, у меня открылась. Предлагается эволюционная эвристика, основанная на первичном выборе по длине, и сортировке по tightness, с последующим турниром. Результаты (размернось — длина змеи — длина кольца)
А>Очевидно, это не та ссылка. У меня она тоже открылась, но она — третья в приведенном тобой списке.
А>Вторая — вот эта.

Чудеса. У меня она идет четвертой. Разные у нас Гуглы, однако...

Здравствуйте, Cruelty, Вы писали:

C>Какую змею вы сможите построить для, скажем, 8ми мерного куба?

Интересная задача. А что за неё дадут?
И кто-нибудь уже вывел общую формулу?

Здравствуйте, Cruelty, Вы писали:

C>Есть N-мерный единичный куб (все координаты вершин заданы бинарными числами).
C>Из вершины (0,0,...,0) начинает "расти змея". На каждом шаге змея смотрит на ребра графа идущие из текущей вершины. Змея может продолжить рост только в ту вершину, которая не инцидентна (не имеет общего ребра) ни с одной уже посещенной вершиной.

C>Так например для трехмерного куба решением является такая последовательность:
C>(0,0,0)-(1,0,0)-(1,1,0)-(1,1,1)-(0,1,1), то есть длина змеи будет 4.

C>Какую змею вы сможите построить для, скажем, 8ми мерного куба?

Я написал программу на Си++ с шаблонами.
Длина змеи для 8-ми мерного куба = 56.
Если надо, то могу путь указать.

Ну что, все, наверное, уже и думать забыли про наших змеек? Ничего не поделаешь, таковы людишки. Почти напрочь у них отсутствует такое важное качество, как упорство и трудолюбие. Чуть повозятся, увидят, что получается плохо, и бросают. Ну ничего, зато о наших змейках не забыл Я — ПРОСТО ГЕНИЙ.

ПГ>Это ДВЕ РАЗНЫЕ задачи. Обе интересные. Куда можно выложить ПРОСТОЕ, но ГЕНИАЛЬНОЕ решение той задачи, что для программистов?

ПГ>Кстати, навряд ли решение для N=8 можно будет найти перебором. Имеет место радикальное увеличение сложности. Если для n=6 моя программа дает ответ меньше, чем за секунду, то над случаем n=7 она работает уже три часа, и пока результата нет. С учетом того, что ожидаемый результат для n=8 составляет примерно 100, дело это безнадежное. Можно попробовать эвристику, но тогда сразу пропадают все гарантии "окончательности" ответа.

Вот я и дождался. Программа проработала почти ровно месяц (P4 3.2HGz HT) для случая N=7 и выдала вчера вот такой вот результат:

1 2 3
1 4 2
1 5 3 2
1 4 6
1 2 3 5
1 7 6
1 5 3
1 4 5
1 2 3 5
1 4 6
1 5 3
1 4 5
1 2 3
1 7 2
1 5 3 2
1

Таким образом, длина 50 при N=7 подтверждена. Лично мной. Для случаев N=7 и 6 соотношение времени работы программы составляет примерно 2.6E6, для N=8 это время будет примерно на 12 порядков больше, чем для N=7. Иными словами, без эвристик не обойтись. Ну что, есть желающие мериться эвристиками? Впрочем, это лишнее. Исход ясен и без этого. У меня — самая мощная, толстая и длинная

Здравствуйте, ПРОСТО ГЕНИЙ, Вы писали:

ПГ>Ну что, все, наверное, уже и думать забыли про наших змеек? Ничего не поделаешь, таковы людишки. Почти напрочь у них отсутствует такое важное качество, как упорство и трудолюбие. Чуть повозятся, увидят, что получается плохо, и бросают. Ну ничего, зато о наших змейках не забыл Я — ПРОСТО ГЕНИЙ.

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

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

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

Что такое "гнать прогу"? Это не тоже самое, что "гнать пургу"? В любом случае, я никого не гнал. Она сама работала.


А вот если бы ты был более внимательным, то в одном из моих предыдущих гениальных сообщений в этой теме ты нашел бы слова о том, что Я ПРОСТО ГЕНИЙ, от душевной своей щедроты предложил безвозмездно, то есть даром, раздавать СВОЮ гениальную программу всем желающим. Даже спросил, куда выложить можно. Перебор у меня гениально-сокращенный, т.е. сокращенный таким образом, что можно формально доказать, что в отброшенной части вариантов гарантированно нет лучшего решения. Также я использовал несколько других интересных приемов оптимизации, которые... Иными словами: скажи мне, как ты собираешься организовать перебор в этой задаче, и я скажу тебе, чего ты стоишь как программист. Ведь большинство местных жителей считают, что они — больше чем кодеры-ремесленники? Тогда им и клаву в руки. Но что-то немного нашлось желающих. Точнее — никого кроме меня. Как думаешь, они боятся чего-то? Или оскудела земля русская?

Да, пока не забыл. ПЭВМ тоже мне не чужая. По крайней мере, я несу за неё ответсвенность. Персонально-материальную.

Здравствуйте, ПРОСТО ГЕНИЙ, Вы писали:

ПГ>Ну что, все, наверное, уже и думать забыли про наших змеек? Ничего не поделаешь, таковы людишки. Почти напрочь у них отсутствует такое важное качество, как упорство и трудолюбие. Чуть повозятся, увидят, что получается плохо, и бросают. Ну ничего, зато о наших змейках не забыл Я — ПРОСТО ГЕНИЙ.

ПГ>>Это ДВЕ РАЗНЫЕ задачи. Обе интересные. Куда можно выложить ПРОСТОЕ, но ГЕНИАЛЬНОЕ решение той задачи, что для программистов?

ПГ>>Кстати, навряд ли решение для N=8 можно будет найти перебором. Имеет место радикальное увеличение сложности. Если для n=6 моя программа дает ответ меньше, чем за секунду, то над случаем n=7 она работает уже три часа, и пока результата нет. С учетом того, что ожидаемый результат для n=8 составляет примерно 100, дело это безнадежное. Можно попробовать эвристику, но тогда сразу пропадают все гарантии "окончательности" ответа.

ПГ>Вот я и дождался. Программа проработала почти ровно месяц (P4 3.2HGz HT) для случая N=7 и выдала вчера вот такой вот результат:

ПГ>1 2 3
ПГ>1 4 2
ПГ>1 5 3 2
ПГ>1 4 6
ПГ>1 2 3 5
ПГ>1 7 6
ПГ>1 5 3
ПГ>1 4 5
ПГ>1 2 3 5
ПГ>1 4 6
ПГ>1 5 3
ПГ>1 4 5
ПГ>1 2 3
ПГ>1 7 2
ПГ>1 5 3 2
ПГ>1

ПГ>Таким образом, длина 50 при N=7 подтверждена. Лично мной. Для случаев N=7 и 6 соотношение времени работы программы составляет примерно 2.6E6, для N=8 это время будет примерно на 12 порядков больше, чем для N=7. Иными словами, без эвристик не обойтись. Ну что, есть желающие мериться эвристиками? Впрочем, это лишнее. Исход ясен и без этого. У меня — самая мощная, толстая и длинная

Воля вашв, профессор, но вы что-то неладное придумали. Над вами же смеяться будут. Во-первых, змеи не вижу. Во-вторых, 50 для N=7 маловато будет, не находите? В-третьих, у вас здесь на rsdn есть персональное место (форумы -> мой профиль -> файлы -> загрузить). Ждем с нетерпением.

Hi, vnp!

vnp>Воля вашв, профессор,
Ну вот, сразу начинаем с оскорбления. Меня, ПРОСТО ГЕНИЯ, назвать каким-то жалким профессоришкой... Нет слов...

vnp>но вы что-то неладное придумали. Над вами же смеяться будут.
Пусть смеются. Ничего не поделаешь. Чернь — она такова. Травит своих гениев постоянно. "Другого народа у меня для вас нет" (c) И.В.С.(Д.) Поэтому будем работать с тем, который есть.

vnp>Во-первых, змеи не вижу.
Ах да, моя ошибка. Вечно забываю, что простому народу все необходимо разжевать и на ложечке в рот положить. Приведенная последовательность чисел — это номера инвертируемых на очередном шаге координат. Именно в таком виде спецы, занимающиеся данной проблемой, обмениваются своими результатами. Да я же уже в такой форме приводил результат

Автор: ПРОСТО ГЕНИЙ
Дата: 05.09.05

. Чтобы получить последовательность вершин (в двоичной форме представления), скорми мою моследовательность моей программе (см. здесь), что завется "...checker". Кстати, именно этой программой очень удобно проверять "ручные" решения — для этого я ее и набросал.

vnp>Во-вторых, 50 для N=7 маловато будет, не находите?
Не нахожу. Для специалистов — вполне достаточно.

vnp>В-третьих, у вас здесь на rsdn есть персональное место (форумы -> мой профиль -> файлы -> загрузить). Ждем с нетерпением.
Наконец-то начался конструктив. Вот за это спасибо. Загрузил. Ссылка выше. Пользуйтесь и наслаждайтесь. Ведь Я — ПРОСТО ГЕНИЙ, всегда готов придти на помощь братьям своим... Впрочем, и сёстрам тоже.

Здравствуйте, ПРОСТО ГЕНИЙ, Вы писали:

ПГ>Hi, vnp!

vnp>>В-третьих, у вас здесь на rsdn есть персональное место (форумы -> мой профиль -> файлы -> загрузить). Ждем с нетерпением.
ПГ>Наконец-то начался конструктив. Вот за это спасибо. Загрузил. Ссылка выше. Пользуйтесь и наслаждайтесь. Ведь Я — ПРОСТО ГЕНИЙ, всегда готов придти на помощь братьям своим... Впрочем, и сёстрам тоже.

Ай-яй-яй. Никак не ожидал такого от ПРОСТО ГЕНИЯ. От обычного гения и то не ожидал бы. Ну кто же будет меряться exe? Кто же будет запускать неведомое чудо на родной системе? Особенно если на ней не то, что win, а и wine рядом не лежал. Беда, короче.

Hi, vnp!

vnp>Ай-яй-яй. Никак не ожидал такого от ПРОСТО ГЕНИЯ. От обычного гения и то не ожидал бы.
Хе-хе. Как учили нас разные дядьки и тётьки психологи, я не обязан оправдывать твои ожидания.

vnp>Ну кто же будет меряться exe?
Кто хочет — ищет способ. Кто не хочет — ищет повод.

vnp>Кто же будет запускать неведомое чудо на родной системе?
Не хочешь на родной — запусти на чужой. Наиболее опасные опыты — на наименее ценных членах экипажа. Или на виртуальной, как иногда делаю я. Можно и на тестовой, если есть, — тем более, что на ней вся система при необходимости восстанавливается за 10 минут.

vnp>Особенно если на ней не то, что win, а и wine рядом не лежал. Беда, короче.
Аяяй. Действительно беда. Но ничем не могу помочь. Впрочем... Хочешь откомпилю под HP UX 11, под какой-нибудь девятитысячник? Настоящий, панимаешь, UNIX, а не какое-нибудь unix-подобие. Или ты линуксоид? Линуксов, звиняй, нет. Не держим-с. Может, под фришку? По моему, у кого-то из наших она была. Если надо — ты скажи, я поищу.

PS. Время отдавать исходники пока не пришло.

ПРОСТО ГЕНИЙ wrote:

> PS. Время отдавать исходники пока не пришло.

На таких гениев есть IDA

--
С уважением,
Alex Besogonov (alexy@izh.com)