Есть 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-мерного гиперкуба точная цифра ПОКА еще неизвестна? Ничего, это временно, ибо за дело взялся Я — ПРОСТО ГЕНИЙ.