![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/2/2c/Snake_in_the_box.svg/languk-640px-Snake_in_the_box.svg.png&w=640&q=50)
Задача про змію в коробці
задача в теорії графів і інформатиці / З Вікіпедії, безкоштовно encyclopedia
Шановний Wikiwand AI, Давайте зробимо це простіше, відповівши на ключові запитання:
Чи можете ви надати найпопулярніші факти та статистику про Задача про змію в коробці?
Підсумуйте цю статтю для 10-річної дитини
Задача про змію в коробці в теорії графів і інформатиці розглядає пошук певного виду шляху вздовж ребер гіперкуба. Цей шлях починається з одного кута і проходить уздовж ребер стільки кутів, скільки може досягти. Після того як досягається новий кут, попередній кут і всі його сусіди стають неприпустимими для використання. Шлях ніколи не повинен проходити через кут після того, як він позначений як неприпустимий.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/2/2c/Snake_in_the_box.svg/320px-Snake_in_the_box.svg.png)
Іншими словами, змія з'єднана відкритим шляхом у гіперкубі, де кожен вузол шляху, за винятком голови (початок ланцюга) і хвоста (кінця ланцюга), має рівно двох сусідів, які також належать до змії. Хвіст і голова змії мають тільки по одному сусідові. Правило для утвороення змії полягає в тому, що вузол в гіперкубі може бути відвіданий, якщо він з'єднаний з поточним вузлом ребром і він не є сусідом будь-якого відвіданого вузла змії, відмінного від поточного положення.
В термінології теорії графів це називається знаходженням найдовшого можливого породженого шляху в гіперкубі. Це можна розглядати як спеціальний випадок задачі про ізоморфізм породженому підграфу[ru]. Існує схожа задача пошуку довгого породженого циклу в гіперкубах, що називається завданням про цикл у коробці.
Задачу про змію в коробці вперше описав Кауц[1] і спонукальною причиною була теорія кодів, що виправляють помилки. Вершини розв'язку задачі про змію або про цикл у коробці можна використовувати як код Грея, який може виявити помилки в одному біті. Такі коди мають застосування в електротехніці, теорії кодування і комп'ютерних мережах. У цих застосуваннях важливо розробити якомога довший код для даної розмірності гіперкуба. Що довший код, то ефективніші його властивості.
Знайти найбільшу змію або цикл стає справді важко за зростання розмірності, а простір пошуку схильний до серйозного комбінаторного вибуху. Деякі техніки для визначення верхньої і нижньої меж для задачі про змію в кубі включають доведення, що використовують дискретну математику і теорію графів, повний перебір простору пошуку та евристичний пошук на основі еволюційних технік.