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

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

Какую змею вы сможите построить для, скажем, 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-ми мерного будет 128

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

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

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

Можно порассуждать таким вот образом:
граф вершин и рёбер N+1-мерного куба получается из двух графов N-мерных кубов попарным соединением соответствующих вершин. Так что пусть на обход N-мерного куба требуется K переходов, тогда на обход N+1-мерного куба примерно так:
K — на обход первой части,
1 — на переход из первой во вторую
K — на обход второй части. (*)
Итого 2K+1.. Насчёт (*) стоит поразмышлять — может, не K, а K-1 (последний переход может попасть в вершину, инцедентную вершине из первой части, так что такой переход уже запрещён)...

Короче, идея (и намечающаяся индукция) примерно понятна . Моя версия — для N-мерного куба длина змеи равняется 2^(N-1).

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

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

Хай!

Ох уж эти мне просто людишки... В массе своей они паталогически ленивы... Вечно их приходится пинать, чтобы хоть что-то сделали... Ты не согласен? Значит, ты никогда ими не руководил. Ладно, оставим лирику. Первая мысль, что приходит в голову в связи с задачей:

С ростом размерности гиперкуба число связей, приходящееся на одну вершину, растет. Следовательно, "коэффициент охвата" (т.е. доля вершин гиперкуба, через которые проходит "змея") будет, скорее всего, падать. С 2^(N-1) это не вяжется. Но пока это всего лишь соображение, абстрактная догадка.

В>Короче, идея (и намечающаяся индукция) примерно понятна . Моя версия — для N-мерного куба длина змеи равняется 2^(N-1).

А проверить догадку хотя бы для четырехмерного гиперкуба ты, разумеется, поленился? А минусы мне ставить, почему-то не поленился. Ладно, я не злопамятный. Твоя догадка неверна. Мне для выяснения этого факта потребовалось не более 30 сек. неспешных размышлений. Значит, ты бы смог уложиться минут в пять. Предъявляю: f(4)=7. Теперь выпишем первые члены последовательности (начиная с "0-мерного куба" — простой точки):

0, 1, 2, 4, 7, ...

Это тебе ничего не напоминает? Нет? Тогда прибавь к элементам последовательности по единице (и получишь число вершин в "змее"). А теперь? Идея понятна? Дарю. Проверяй. Если не справишься — помогу. Но позже. Ибо сейчас мне срочно надо думать мои ГЕНИАЛЬНЫЕ МЫСЛИ.

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

С математической точки зрения ето сложная (трудная) задача. Поетому ета
задача скорее етюд для программистов а не для математиков (если конечно
никто не претендует на медаль Филдса )

>С математической точки зрения ето сложная (трудная) задача. Поетому ета
>задача скорее етюд для программистов а не для математиков (если конечно
>никто не претендует на медаль Филдса )

ооо... значит, это задача для Просто Гения Ждём-с строгого доказательства его
> ГЕНИАЛЬНЫХ ДОГАДОК
...

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

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

Здравствуйте, 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ми мерного куба?


Интуитивная формула:

L0 | 0 - точка

L1 | 1 - отрезок
L2 | 2 - квадрат
L3 | 4 - куб

L4 | 7 - остальное разуму неподвластно
L5 | 11
L6 | 16
L7 | 23
L8 | 30
L9 | 38
..... 
Ln = 1+(1+2+3+....+(n-1)), для (n>0)

.

Прямо скажем не совсем. Даже для 5-мерного куба не правильно.

А вот для 5-мерного куба, решение уже не 12

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

C>Прямо скажем не совсем. Даже для 5-мерного куба не правильно.

Спорить не стану.
А сколько по-Вашему?



.

13

Здравствуйте, 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ми мерного куба?

Рост, очевидно, экспоненциальный. Вумудщзук почти это показал (две змеи на подкубах размерности N-1 плюс одно звено на переход). ПРОСТО ГЕНИЙ указал, что так делать нельзя, т.к. обход второго подкуба не является независимым. Можно, однако, выделить два подкуба размерности N-2 (00xx...xx и 11xx...xx). Обходы этих подкубов будут таки независимы , поэтому грубая оценка снизу:

L(N) > L(N-2) + 2

т.е. экспонента.

А вообще-то, первые же две ссылки...

Здравствуйте, 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ми мерного куба?

Попытался найти программно и получил следующие результаты.
(В скобках указаны все неизбыточные варианты — после проползания не осталось незадетых узлов).

0 — 0
1 — 1
2 — 2
3 — 4
4 — (6,7)
5 — (10-13)
6 — (19-25)
7 — (37-43)
8 — не дождался... разброс ребер после захождения в тупик (от 14 — до 72)

Сдается мне, что задача численного решения не имеет

А вот, собственно, и программа:

#include <vector>
#include <iostream>
#include <conio.h>

#define MAX_DIM 20

using namespace std;

/*
N        - размерность пространства
TryCount - максимальное число итераций

Возвращает длину змеи или -1, если за отведенное число итераций решение не найдено
*/
int foo(int N,int nTryCount)
{
    if(N>MAX_DIM) return -1;

    /*
    Вектор узлов.
    Если в узле стоит 1 - он доступен, 0 - он уже пройден или 'задет' пройденым соседом
    */
    vector<bool> Arr(1<<N,1);

    //Массив допустимых направлений
    int Vars[MAX_DIM];
    int nVarCount;

    //Текущая позиция,длина змеи
    int nPos,nLength;
    
    while(nTryCount--)
    {
        
        nPos=nLength=0;

        //Забиваем массив 1 (все узлы доступны)
        Arr.assign(1<<N,1);
        //Первая ячейка занята - ставим 0
        Arr.at(0)=0;

        while(1)
        {
            //Перебираем узлы, соседние с текущим
            nVarCount=0;
            for(int i=0,l=1,nOldPos=nPos;i<N;i++,l<<=1)
            {
                //Выбираем очередной узел, соседний с текущим (nOldPos)
                nPos=nOldPos^l;
                //Незадетые (допустимые для движения) узлы - запоминаем
                if(Arr[nPos]) Vars[nVarCount++]=nPos;
            }

            //Если нет допустимых узлов - выходим для проверки решения
            if(!nVarCount) break;
            //Увеличивем счетчик пройденых ребер 
            nLength++;
            //Случайным образом выбираем направление движения
            nPos=Vars[rand()%nVarCount];
            //Все соседние с текущим узлы помечаем как недопустимые
            for(i=0;i<nVarCount;Arr.at(Vars[i++])=0); 
        }
        
        //Проверка решения. Если остались незадетые узлы - начинаем новую итерацию
        for(int i=Arr.size()-1;i>0;i--)    if(Arr[i]) break;

        //Узлов не осталось - выходим
        if(!i) return nLength;
    }
    //Решение не найдено
    return -1;
}

void main()
{
    //Делаем 1000 попыток, чтобы убедиться в неуникальности решения
    for(int i=0;i<1000;i++)
        cout<<foo(5,10000)<<",";

    cout<<"\nPress any key"<<endl;
    getch();
};

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

Н>Попытался найти программно и получил следующие результаты.
Н>(В скобках указаны все неизбыточные варианты — после проползания не осталось незадетых узлов).

Н>0 — 0
Н>1 — 1
Н>2 — 2
Н>3 — 4
Н>4 — (6,7)
Н>5 — (10-13)
Н>6 — (19-25)
Н>7 — (37-43)
Н>8 — не дождался... разброс ребер после захождения в тупик (от 14 — до 72)

Н>Сдается мне, что задача численного решения не имеет

http://mathworld.wolfram.com/Snake.html
приводит значения ...2, 4, 8, 14, 26...

Н>>8 — не дождался... разброс ребер после захождения в тупик (от 14 — до 72)

Ещё бы, там примерно факториал от количества вершин.

Н>>Сдается мне, что задача численного решения не имеет

К>http://mathworld.wolfram.com/Snake.html
К>приводит значения ...2, 4, 8, 14, 26...

Набросал программу на питоне.

def adj(x,y) :
    """ adjacent, т.е. смежны ли вершины x,y """
    z = x^y # двоичный вектор расстояния
    return (z&(z-1)) == 0 # истина, если не более одного бита взведено

def offside(x,path) :
    """ проверка, что x не смежна ни с одной вершиной пути """
    for y in path :
        if adj(x,y) : return False
    return True


class snake :
    """ решатель задачи о змее на гиперкубе """
    #
    dim = 5   # размерность гиперкуба
    orts = [] # множество ортов (пригодится ниже)
    #
    def init_orts(self) :
        """ инициализация ортов """
        self.orts = [1<<i for i in range(self.dim)]
    #
    def __init__(self,d) :
        """ параметр змеи - размерность """
        self.dim = d
        self.init_orts()
    #
    maxbet = 0 # длина наилучшего найденного решения
    #
    def nexts(self,x) :
        """ множество вершин, смежных с x """
        return [x^o for o in self.orts]
    #
    def step(self,path) :
        """ множество (генератор) поползновений змеи на одно ребро """
        tail = path[0:-1] # хвост змеи (первые n-1 элементов)
        head = path[-1]   # голова змеи (последний элемент)
        for x in self.nexts(head) : # куда змея в принципе может ползти
            if offside(x,tail) : # условие несмежности с хвостом
                yield path+[x]
    #
    def walk(self,path) :
        """ генератор поползновений змеи (поиск вглубь); условие: каждое новое длиннее предыдущих """
        bet1 = len(path)+1
        for path1 in self.step(path) : # проползли на один шаг...
            for path2 in self.walk(path1) : # и с этого места до упора
                yield path2 # докуда доползли, это и вернули
            if self.maxbet < bet1 : # если path1 лучше предыдущих решений (фактически, если не доползли)
                self.maxbet = bet1
                print "....<",bet1,">",path1
                yield path1 # то запомним это решение как лучшее, и вернём
    #
    def run(self) :
        self.maxbet = 0
        best = []
        for path in self.walk([0,1,3,7]) : # первая часть пути - однозначна
            if len(best)<len(path) : # будем запоминать наилучшее из найденных решений
                best = path
        return best

snake(3).run()
#....< 5 > [0, 1, 3, 7, 6]

snake(4).run()
#....< 8 > [0, 1, 3, 7, 6, 14, 12, 13]

snake(5).run()
#....< 13 > [0, 1, 3, 7, 6, 14, 12, 13, 29, 31, 27, 26, 24]
#....< 14 > [0, 1, 3, 7, 15, 14, 12, 28, 29, 25, 27, 26, 18, 22]

snake(6).run()
#....< 22 > [0, 1, 3, 7, 6, 14, 12, 13, 29, 31, 27, 26, 24, 56, 57, 49, 51, 50, 54, 52, 36, 37]
#....< 24 > [0, 1, 3, 7, 6, 14, 12, 13, 29, 31, 27, 26, 24, 56, 57, 49, 53, 52, 54, 50, 34, 42, 43, 47]
#....< 25 > [0, 1, 3, 7, 6, 14, 12, 13, 29, 31, 27, 26, 24, 56, 57, 41, 43, 42, 34, 50, 51, 55, 53, 52, 36]
#....< 26 > [0, 1, 3, 7, 6, 14, 12, 13, 29, 25, 27, 26, 18, 50, 51, 55, 63, 47, 43, 42, 40, 56, 60, 52, 36, 37]
#....< 27 > [0, 1, 3, 7, 15, 13, 12, 28, 20, 21, 53, 37, 36, 38, 46, 62, 63, 59, 43, 41, 40, 56, 48, 50, 18, 26, 10]

snake(7).run()
#....< 35 > [0, 1, 3, 7, 6, 14, 12, 13, 29, 31, 27, 26, 24, 56, 57, 49, 51, 50, 54, 52,
#            36, 37, 101, 103, 102, 98, 96, 104, 105, 107, 123, 122, 126, 124, 125]
#....< 40 > [0, 1, 3, 7, 6, 14, 12, 13, 29, 31, 27, 26, 24, 56, 57, 49, 51, 50, 54, 52,
#            36, 37, 101, 103, 102, 98, 96, 104, 105, 107, 123, 122, 126, 124, 92, 84,
#            85, 87, 83, 82]
#....< 41 > [0, 1, 3, 7, 6, 14, 12, 13, 29, 31, 27, 26, 24, 56, 57, 49, 51, 50, 54, 52,
#            36, 37, 101, 103, 102, 98, 96, 104, 105, 107, 123, 122, 126, 124, 92, 84,
#            86, 87, 83, 81, 89]
#....< 42 > [0, 1, 3, 7, 6, 14, 12, 13, 29, 31, 27, 26, 24, 56, 57, 49, 51, 50, 54, 52,
#            36, 37, 101, 103, 102, 98, 96, 104, 105, 73, 89, 81, 80, 82, 86, 94, 92,
#            124, 125, 127, 123, 122]
#....< 43 > [0, 1, 3, 7, 6, 14, 12, 13, 29, 31, 27, 26, 24, 56, 57, 49, 51, 50, 54, 52,
#            36, 37, 101, 103, 102, 98, 96, 104, 108, 124, 125, 127, 123, 107, 75, 73,
#            89, 81, 83, 82, 86, 84, 68]
#....< 44 > [0, 1, 3, 7, 6, 14, 12, 13, 29, 31, 27, 26, 24, 56, 57, 49, 51, 50, 54, 52,
#            36, 37, 101, 103, 102, 98, 96, 104, 72, 73, 89, 81, 80, 82, 86, 94, 92,
#            124, 125, 127, 123, 107, 43, 42]
#....< 45 > [0, 1, 3, 7, 6, 14, 12, 13, 29, 31, 27, 26, 24, 56, 57, 49, 51, 50, 54, 52,
#            36, 37, 101, 97, 96, 112, 80, 81, 89, 73, 72, 74, 106, 42, 43, 47, 111,
#            127, 119, 87, 86, 94, 92, 124, 108]
#....< 46 > [0, 1, 3, 7, 6, 14, 12, 13, 29, 31, 27, 26, 24, 56, 57, 49, 51, 50, 54, 52,
#            36, 37, 101, 69, 68, 84, 86, 87, 83, 81, 89, 73, 72, 74, 66, 98, 102, 110,
#            108, 124, 125, 127, 123, 107, 43, 42]

(дальше стало лень ждать; всё-таки питон это не С++, да и способ работы выбран не самый быстрый).

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

К>Здравствуйте, Нэчер, Вы писали:

Н>>Попытался найти программно и получил следующие результаты.
Н>>(В скобках указаны все неизбыточные варианты — после проползания не осталось незадетых узлов).

Н>>0 — 0
Н>>1 — 1
Н>>2 — 2
Н>>3 — 4
Н>>4 — (6,7)
Н>>5 — (10-13)
Н>>6 — (19-25)
Н>>7 — (37-43)
Н>>8 — не дождался... разброс ребер после захождения в тупик (от 14 — до 72)

Н>>Сдается мне, что задача численного решения не имеет

К>http://mathworld.wolfram.com/Snake.html
К>приводит значения ...2, 4, 8, 14, 26...
Если быть точнее, то там выходит ...2,4,6,8,14,26...

Рассмотрим случай 4-х мерного пространства, где змея, согласно неравенствам, имее длину <=6, но на самом деле имеет длину 7:

0000 — 0010 — 0110 — 1110 — 1100 — 1101 — 1001 — 1011

Путем несложных вычислений можно убедиться в верности решения:

0000 (исключаем 0001,0100,1000)
0010 (исключаем 0011,1010)
0110 (исключаем 0111)
1110 (исключаем 1111)
1100 (исключаем — )
1101 (исключаем 0101)
1001 (исключаем — )
1011 (исключаем — )

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

К>>Здравствуйте, Нэчер, Вы писали:

Н>Если быть точнее, то там выходит ...2,4,6,8,14,26...

Посмотрел не внимательно: для 4-х мерного просранства согласно неравенствам будет s(4)<=8. А для 3-х мерного то ли s(3)<=6, если верить этому, толи <=5 если верить формуле s(d)=3^(d-3)+2. Оба варианта бесспорно верны, к ним остается только добавить s(d)>=-10 ...

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

C>А вот для 5-мерного куба, решение уже не 12

Значит, гипотеза не подтвердилась. Совершенно рядовой момент. МЫ, ГЕНИИ, в ходе решения СЛОЖНЫХ ПРОБЛЕМ генерируем, проверяем и отвергаем подобные гипотезы сотнями. Как я понимаю, для 8-мерного гиперкуба точная цифра ПОКА еще неизвестна? Ничего, это временно, ибо за дело взялся Я — ПРОСТО ГЕНИЙ.

Здравствуйте, 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)