| http://dbpedia.org/ontology/abstract
|
Задача про змію в коробці в теорії графів … Задача про змію в коробці в теорії графів і інформатиці розглядає пошук певного виду шляху вздовж ребер гіперкуба. Цей шлях починається з одного кута і проходить уздовж ребер стільки кутів, скільки може досягти. Після того як досягається новий кут, попередній кут і всі його сусіди стають неприпустимими для використання. Шлях ніколи не повинен проходити через кут після того, як він позначений як неприпустимий. Іншими словами, змія з'єднана відкритим шляхом у гіперкубі, де кожен вузол шляху, за винятком голови (початок ланцюга) і хвоста (кінця ланцюга), має рівно двох сусідів, які також належать до змії. Хвіст і голова змії мають тільки по одному сусідові. Правило для утвороення змії полягає в тому, що вузол в гіперкубі може бути відвіданий, якщо він з'єднаний з поточним вузлом ребром і він не є сусідом будь-якого відвіданого вузла змії, відмінного від поточного положення. В термінології теорії графів це називається знаходженням найдовшого можливого породженого шляху в гіперкубі. Це можна розглядати як спеціальний випадок . Існує схожа задача пошуку довгого породженого циклу в гіперкубах, що називається завданням про цикл у коробці. Задачу про змію в коробці вперше описав Кауц і спонукальною причиною була теорія кодів, що виправляють помилки. Вершини розв'язку задачі про змію або про цикл у коробці можна використовувати як код Грея, який може виявити помилки в одному біті. Такі коди мають застосування в електротехніці, теорії кодування і комп'ютерних мережах. У цих застосуваннях важливо розробити якомога довший код для даної розмірності гіперкуба. Що довший код, то ефективніші його властивості. Знайти найбільшу змію або цикл стає справді важко за зростання розмірності, а простір пошуку схильний до серйозного комбінаторного вибуху. Деякі техніки для визначення верхньої і нижньої меж для задачі про змію в кубі включають доведення, що використовують дискретну математику і теорію графів, повний перебір простору пошуку та евристичний пошук на основі еволюційних технік.тичний пошук на основі еволюційних технік.
, The snake-in-the-box problem in graph theo … 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. search utilizing evolutionary techniques.
, Задача о змее в коробке в теории графов и … Задача о змее в коробке в теории графов и информатике имеет дело с поиском определённого вида пути вдоль рёбер гиперкуба. Этот путь начинается с одного угла и проходит вдоль рёбер столько углов, сколько он может достичь. После того как достигается новый угол, предыдущий угол и все его соседи делаются недопустимыми для использования. Путь никогда не должен проходить через угол после того, как он помечен как недопустимый. Другими словами, змея соединена открытым путём в гиперкубе, где каждый узел в пути, за исключением головы (начало цепи) и хвоста (конца цепи), имеет ровно два соседа, которые также принадлежат змее. Хвост и голова в змее имеют только по одному соседу. Правило для образования змеи состоит в том, что узел в гиперкубе может быть посещён, если он соединён с текущим узлом ребром и он не является соседом какого-либо посещённого узла в змее, отличного от текущего. В терминологии теории графов это называется нахождением самого длинного возможного порождённого пути в гиперкубе. Это можно рассматривать как специальный случай задачи изоморфизма порождённому подграфу. Существует похожая задача поиска длинного порождённого цикла в гиперкубах, называется задачей о цикле в коробке. Задачу о змее в коробке впервые описал Кауц и побудительной причиной была теория исправляющих ошибки кодов. Вершины решения задачи о змее или о цикле в коробке можно использовать как код Грея, который может обнаружить ошибки в одном бите. Такие коды имеют приложение в электротехнике, теории кодирования и компьютерных сетях. В этих приложениях важно разработать как можно более длинный код для данной размерности гиперкуба. Чем длиннее код, тем более эффективны его свойства. Нахождение наибольшей змеи или цикла становится откровенно трудным при росте размерности, а пространство поиска склонно к серьёзному комбинаторному взрыву. Некоторые техники для определения верхней и нижней границ для задачи о змее в кубе включают доказательства, использующие дискретную математику и теорию графов, полный перебор пространства поиска и эвристический поиск на основе эволюционных техник.еский поиск на основе эволюционных техник.
|
| rdfs:comment |
Задача про змію в коробці в теорії графів … Задача про змію в коробці в теорії графів і інформатиці розглядає пошук певного виду шляху вздовж ребер гіперкуба. Цей шлях починається з одного кута і проходить уздовж ребер стільки кутів, скільки може досягти. Після того як досягається новий кут, попередній кут і всі його сусіди стають неприпустимими для використання. Шлях ніколи не повинен проходити через кут після того, як він позначений як неприпустимий. того, як він позначений як неприпустимий.
, The snake-in-the-box problem in graph theo … 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.o a corner which has been marked unusable.
, Задача о змее в коробке в теории графов и … Задача о змее в коробке в теории графов и информатике имеет дело с поиском определённого вида пути вдоль рёбер гиперкуба. Этот путь начинается с одного угла и проходит вдоль рёбер столько углов, сколько он может достичь. После того как достигается новый угол, предыдущий угол и все его соседи делаются недопустимыми для использования. Путь никогда не должен проходить через угол после того, как он помечен как недопустимый.сле того, как он помечен как недопустимый.
|
