Сравнивайте с английским: нажмите на абзац — оригинал откроется в окне. Кнопка EN под абзацем показывает его прямо в тексте.
Введение
Проблема «змеи в коробке» в теории графов и информатике связана с поиском определённого типа пути по рёбрам гиперкуба. Этот путь начинается в одной вершине и проходит по рёбрам к максимально возможному числу вершин. После достижения новой вершины, предыдущая вершина и все её соседи должны быть помечены как недоступные для использования. Путь не должен проходить через вершину, которая была помечена как недоступная. Иными словами, змея — это связный открытый путь в гиперкубе, где каждая вершина, соединённая с путём, за исключением головы (начала) и хвоста (конца), имеет ровно два соседа, которые также находятся на змее. Голова и хвост имеют только по одному соседу на змее. Правило генерации змеи заключается в том, что вершина в гиперкубе может быть посещена, если она соединена с текущей вершиной и не является соседом какой-либо ранее посещённой вершины на змее, кроме текущей. В терминологии теории графов это называется нахождением максимально возможного индуцированного пути в гиперкубе; это можно рассматривать как частный случай задачи изоморфизма индуцированных подграфов. Существует аналогичная задача поиска длинных индуцированных циклов в гиперкубах, называемая проблемой «катушки в коробке». Проблема «змеи в коробке» была впервые описана, что было мотивировано теорией кодов, исправляющих ошибки. Вершины решения задачи «змея» или «катушка в коробке» могут использоваться в качестве кода Грея, способного обнаруживать однобитовые ошибки. Такие коды находят применение в электротехнике, теории кодирования и топологиях компьютерных сетей. В этих приложениях важно разработать максимально длинный код для заданной размерности гиперкуба. Чем длиннее код, тем эффективнее его возможности. Поиск самой длинной змеи или катушки становится особенно сложным с увеличением числа измерений, а пространство поиска испытывает серьёзный комбинаторный взрыв. Некоторые методы определения верхней и нижней границ для задачи «змея в коробке» включают доказательства с использованием дискретной математики и теории графов, полный перебор пространства поиска и эвристический поиск с использованием эволюционных методов.
The snake in the box problem in graph theory and computer science deals with finding a certain kind of path along the edges of a hypercube. This path starts at one corner and travels along the edges to as many corners as it can reach. After it gets to a new corner, the previous corner and all of its neighbors must be marked as unusable. The path should never travel to a corner which has been marked unusable. In other words, a snake is a connected open path in the hypercube where each node connected with path, with the exception of the head (start) and the tail (finish), it has exactly two neighbors that are also in the snake. The head and the tail each have only one neighbor in the snake. The rule for generating a snake is that a node in the hypercube may be visited if it is connected to the current node and it is not a neighbor of any previously visited node in the snake, other than the current node. In graph theory terminology, this is called finding the longest possible induced path in a hypercube; it can be viewed as a special case of the induced subgraph isomorphism problem. There is a similar problem of finding long induced cycles in hypercubes, called the coil in the box problem. The snake in the box problem was first described by , motivated by the theory of error correcting codes. The vertices of a solution to the snake or coil in the box problems can be used as a Gray code that can detect single bit errors. Such codes have applications in electrical engineering, coding theory, and computer network topologies. In these applications, it is important to devise as long a code as is possible for a given dimension of hypercube. The longer the code, the more effective are its capabilities. Finding the longest snake or coil becomes notoriously difficult as the dimension number increases and the search space suffers a serious combinatorial explosion. Some techniques for determining the upper and lower bounds for the snake in the box problem include proofs using discrete mathematics and graph theory, exhaustive search of the search space, and heuristic search utilizing evolutionary techniques.