Azərbaycanca AzərbaycancaБеларускі БеларускіDansk DanskDeutsch DeutschEspañola EspañolaFrançais FrançaisIndonesia IndonesiaItaliana Italiana日本語 日本語Қазақ ҚазақLietuvos LietuvosNederlands NederlandsPortuguês PortuguêsРусский Русскийසිංහල සිංහලแบบไทย แบบไทยTürkçe TürkçeУкраїнська Українська中國人 中國人United State United StateAfrikaans Afrikaans
Підтримка
www.wikidata.uk-ua.nina.az

Задача про змію в коробці в теорії графів і інформатиці розглядає пошук певного виду шляху вздовж ребер гіперкуба Цей шл

Задача про змію в коробці

Задача про змію в коробці

Задача про змію в коробці в теорії графів і інформатиці розглядає пошук певного виду шляху вздовж ребер гіперкуба. Цей шлях починається з одного кута і проходить уздовж ребер стільки кутів, скільки може досягти. Після того як досягається новий кут, попередній кут і всі його сусіди стають неприпустимими для використання. Шлях ніколи не повинен проходити через кут після того, як він позначений як неприпустимий.

image
Малюнок змії в тривимірному гіперкубі .

Іншими словами, змія з'єднана відкритим шляхом у гіперкубі, де кожен вузол шляху, за винятком голови (початок ланцюга) і хвоста (кінця ланцюга), має рівно двох сусідів, які також належать до змії. Хвіст і голова змії мають тільки по одному сусідові. Правило для утвороення змії полягає в тому, що вузол в гіперкубі може бути відвіданий, якщо він з'єднаний з поточним вузлом ребром і він не є сусідом будь-якого відвіданого вузла змії, відмінного від поточного положення.

В термінології теорії графів це називається знаходженням найдовшого можливого породженого шляху в гіперкубі. Це можна розглядати як спеціальний випадок [ru]. Існує схожа задача пошуку довгого породженого циклу в гіперкубах, що називається завданням про цикл у коробці.

Задачу про змію в коробці вперше описав Кауц і спонукальною причиною була теорія кодів, що виправляють помилки. Вершини розв'язку задачі про змію або про цикл у коробці можна використовувати як код Грея, який може виявити помилки в одному біті. Такі коди мають застосування в електротехніці, теорії кодування і комп'ютерних мережах. У цих застосуваннях важливо розробити якомога довший код для даної розмірності гіперкуба. Що довший код, то ефективніші його властивості.

Знайти найбільшу змію або цикл стає справді важко за зростання розмірності, а простір пошуку схильний до серйозного комбінаторного вибуху. Деякі техніки для визначення верхньої і нижньої меж для задачі про змію в кубі включають доведення, що використовують дискретну математику і теорію графів, повний перебір простору пошуку та евристичний пошук на основі еволюційних технік.

Відомі довжини і границі

Максимальна довжина змії в коробці відома для розмірностей від одиниці до восьми

1, 2, 4, 7, 13, 26, 50, 98 послідовність A099155 з Онлайн енциклопедії послідовностей цілих чисел, OEIS .

Вище восьмої розмірності точна довжина найбільшої змії не відома. Кращі знайдені довжини для розмірностей від дев'яти до тринадцяти

190, 370, 712, 1373 2687.

Цикли (в коробці) не можуть існувати в гіперкубі розмірності менше двох. Максимальні довжини можливих циклів рівні

0, 4, 6, 8, 14, 26, 48, 96 послідовність A000937 з Онлайн енциклопедії послідовностей цілих чисел, OEIS .

Поза цими розмірностями точні довжини найдовших циклів невідомі. Кращі знайдені довжини для розмірностей від дев'яти до тринадцяти

188, 366, 692, 1344, 2594.

Подвійний цикл є спеціальним випадком — це цикли, друга половина яких повторює структуру першої половини. Ці цикли відомі також як симетричні цикли. Для розмірностей від двох до семи довжини найбільших можливих подвійних циклів рівні

4, 6, 8, 14, 26, 46.

Крім цих величин кращими знайденими довжинами для розмірностей від восьми до тринадцяти є

94, 186, 362, 662, 1222, 2354.

Для обох завдань, змія в коробці і цикл в коробці, відомо, що найбільша довжина пропорційна 2n для n-вимірної коробки за зростання n і обмежена зверху значенням 2n-1. Однак константа пропорційності не відома, але для поточних кращих відомих значень спостерігається десь у межах 0,3 — 0,4.

Див. також

Примітки

  1. Kautz, 1958.
  2. Для асимптотических нижних границ см. статьи Евдокимова (Евдокимов, 1969), Войсичовски (Wojciechowski, 1989), Аббота и Качальски (Abbot, Katchalski, 1991). Для верхних границ см. статьи Дугласа (Douglas, 1969), Демера (Deimer, 1985), Соловьёвой (Соловьёва, 1987), Аббота и Качальски (Abbot, Katchalski, 1988), Сневили (Snevily, 1994) и Земора (Zémor, 1997).

Література

  • Abbot H. L., Katchalski M. On the snake in the box problem // . — 1988. — Т. 45. — С. 13–24. — DOI:10.1016/0095-8956(88)90051-2.
  • Abbot H. L., Katchalski M. On the construction of snake-in-the-box codes // Utilitas Mathematica. — 1991. — Т. 40. — С. 97–116.
  • David Allison, Daniel Paulusma. New Bounds for the Snake-in-the-Box Problem. — 2016. — arXiv:1603.05119. — Bibcode: 2016arXiv160305119A.
  • Bitterman D. S. New Lower Bounds for the Snake-In-The-Box Problem: A Prolog Genetic Algorithm and Heuristic Search Approach. — Department of Computer Science, University of Georgia, 2004. — (M.S. thesis).
  • Mario Blaum, Tuvi Etzion. Use of snake-in-the-box codes for reliable identification of tracks in servo fields of a disk drive. — 2002.
  • Casella D. A., Potter W. D. Using Evolutionary Techniques to Hunt for Snakes and Coils // 2005 IEEE Congress on Evolutionary Computation (CEC2005). — 2005. — Т. 3. — С. 2499–2504.
  • Casella D. A. New Lower Bounds for the Snake-in-the-Box and the Coil-in-the-Box Problems. — Department of Computer Science, University of Georgia, 2005. — (M.S. thesis).
  • Danzer L., Klee V. Length of snakes in boxes // . — 1967. — Т. 2, вип. 3. — С. 258–265. — DOI:10.1016/S0021-9800(67)80026-7.
  • Davies D. W. Longest 'separated' paths and loops in an N-cube // IEEE Transactions on Electronic Computers. — 1965. — Т. EC-14, вип. 2. — С. 261. — DOI:10.1109/PGEC.1965.264262.
  • Knut Deimer. A new upper bound for the length of snakes // . — 1985. — Т. 5, вип. 2. — С. 109–120. — DOI:10.1007/BF02579373.
  • Diaz-Gomez P. A., Hougen D. F. The snake in the box problem: mathematical conjecture and a genetic algorithm approach // Proc. 8th Conf. Genetic and Evolutionary Computation. — Seattle, Washington, USA, 2006. — С. 1409–1410. — DOI:10.1145/1143997.1144219.
  • Robert J. Douglas. Upper bounds on the length of circuits of even spread in the d-cube // . — 1969. — Т. 7, вип. 3. — С. 206–214. — DOI:10.1016/S0021-9800(69)80013-X.
  • Евдокимов А. А. О максимальной длине цепи в единичном n-мерном кубе // Матем. заметки. — 1969. — Т. 6. — С. 309–319.
  • William H. Kautz. Unit-distance error-checking codes // IRE Transactions on Electronic Computers. — 1958. — Т. 7. — С. 177–180.
  • Kim S., Neuhoff D. L. Proceedings of the IEEE International Symposium on Information Theory. — 2000. — С. 402. — DOI:10.1109/ISIT.2000.866700.
  • Kinny D. Proceedings of the 20th European Conference on Artificial Intelligence, ECAI-2012 : [ 5 листопада 2013]. — 2012. — С. 462–467.
  • Kinny D. Proceedings of the 6th International WS on Multi-disciplinary Trends in Artificial Intelligence, MIWAI-2012 : [ 16 січня 2018]. — 2012. — С. 271–283.
  • Klee V. What is the maximum length of a d-dimensional snake? // American Mathematical Monthly. — 1970. — Т. 77, вип. 1. — С. 63–65. — DOI:10.2307/2316860. — JSTOR 2316860.
  • Kochut K. J. Snake-in-the-box codes for dimension 7 // Journal of Combinatorial Mathematics and Combinatorial Computing. — 1996. — Т. 20. — С. 175–185.
  • Lukito A., van Zanten A. J. A new non-asymptotic upper bound for snake-in-the-box codes // Journal of Combinatorial Mathematics and Combinatorial Computing. — 2001. — Т. 39. — С. 147–156.
  • Kenneth G. Paterson, Jonathan Tuliani. Some new circuit codes // . — 1998. — Т. 44, вип. 3. — С. 1305–1309. — DOI:10.1109/18.669420.
  • Potter W. D., Robinson R. W., Miller J. A., Kochut K. J., Redys D. Z. Proceedings of the Seventh International Conference on Industrial & Engineering Applications of Artificial Intelligence and Expert Systems. — Austin, Texas, USA, 1994. — С. 421–426.
  • Snevily H. S. The snake-in-the-box problem: a new upper bound // . — 1994. — Т. 133. — С. 307–314. — DOI:10.1016/0012-365X(94)90039-6.
  • Соловьёва Ф. И. Верхняя граница длины цикла в n-мерном единичном кубе // Методы дискретного анализа в решении комбинаторных задач: Сб. науч. Тр.. — Новосибирск : Ин-т математики СО АН СССР, 1987. — Т. 45. — С. 71–76, 96–97.
  • Tuohy D. R., Potter W. D., Casella D. A. Proceedings of the 2007 Int. Conf. on Genetic and Evolutionary Methods (GEM'2007). — Las Vegas, Nevada, USA, 2007. — С. 3–9.
  • Wojciechowski J. A new lower bound for snake-in-the-box codes // . — 1989. — Т. 9, вип. 1. — С. 91–99. — DOI:10.1007/BF02122688.
  • Yuan Sheng Yang, Fang Sun, Song Han. A backward search algorithm for the snake in the box problem // Journal of the . — 2000. — Т. 40, вип. 5. — С. 509–511.
  • Gilles Zémor. An upper bound on the size of the snake-in-the-box // . — 1997. — Т. 17, вип. 2. — С. 287–298. — DOI:10.1007/BF01200911.
  • Zinovik I., Kroening D., Chebiryak Y. Computing binary combinatorial gray codes via exhaustive search with SAT solvers // IEEE Transactions on Information Theory. — 2008. — Т. 54, вип. 4. — С. 1819–1823. — DOI:10.1109/TIT.2008.917695.

Посилання

  • Kinny, David. (2012). . Архів оригіналу за 3 березня 2016. Процитовано 18 лютого 2019.
  • Potter, W. D. (2011). . Архів оригіналу за 26 лютого 2015. Процитовано 31 січня 2020.
  • Weisstein, Eric W. Snake(англ.) на сайті Wolfram MathWorld.

Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет

Zadacha pro zmiyu v korobci v teoriyi grafiv i informatici rozglyadaye poshuk pevnogo vidu shlyahu vzdovzh reber giperkuba Cej shlyah pochinayetsya z odnogo kuta i prohodit uzdovzh reber stilki kutiv skilki mozhe dosyagti Pislya togo yak dosyagayetsya novij kut poperednij kut i vsi jogo susidi stayut nepripustimimi dlya vikoristannya Shlyah nikoli ne povinen prohoditi cherez kut pislya togo yak vin poznachenij yak nepripustimij Malyunok zmiyi v trivimirnomu giperkubi Inshimi slovami zmiya z yednana vidkritim shlyahom u giperkubi de kozhen vuzol shlyahu za vinyatkom golovi pochatok lancyuga i hvosta kincya lancyuga maye rivno dvoh susidiv yaki takozh nalezhat do zmiyi Hvist i golova zmiyi mayut tilki po odnomu susidovi Pravilo dlya utvoroennya zmiyi polyagaye v tomu sho vuzol v giperkubi mozhe buti vidvidanij yaksho vin z yednanij z potochnim vuzlom rebrom i vin ne ye susidom bud yakogo vidvidanogo vuzla zmiyi vidminnogo vid potochnogo polozhennya V terminologiyi teoriyi grafiv ce nazivayetsya znahodzhennyam najdovshogo mozhlivogo porodzhenogo shlyahu v giperkubi Ce mozhna rozglyadati yak specialnij vipadok ru Isnuye shozha zadacha poshuku dovgogo porodzhenogo ciklu v giperkubah sho nazivayetsya zavdannyam pro cikl u korobci Zadachu pro zmiyu v korobci vpershe opisav Kauc i sponukalnoyu prichinoyu bula teoriya kodiv sho vipravlyayut pomilki Vershini rozv yazku zadachi pro zmiyu abo pro cikl u korobci mozhna vikoristovuvati yak kod Greya yakij mozhe viyaviti pomilki v odnomu biti Taki kodi mayut zastosuvannya v elektrotehnici teoriyi koduvannya i komp yuternih merezhah U cih zastosuvannyah vazhlivo rozrobiti yakomoga dovshij kod dlya danoyi rozmirnosti giperkuba Sho dovshij kod to efektivnishi jogo vlastivosti Znajti najbilshu zmiyu abo cikl staye spravdi vazhko za zrostannya rozmirnosti a prostir poshuku shilnij do serjoznogo kombinatornogo vibuhu Deyaki tehniki dlya viznachennya verhnoyi i nizhnoyi mezh dlya zadachi pro zmiyu v kubi vklyuchayut dovedennya sho vikoristovuyut diskretnu matematiku i teoriyu grafiv povnij perebir prostoru poshuku ta evristichnij poshuk na osnovi evolyucijnih tehnik Vidomi dovzhini i graniciMaksimalna dovzhina zmiyi v korobci vidoma dlya rozmirnostej vid odinici do vosmi 1 2 4 7 13 26 50 98 poslidovnist A099155 z Onlajn enciklopediyi poslidovnostej cilih chisel OEIS Vishe vosmoyi rozmirnosti tochna dovzhina najbilshoyi zmiyi ne vidoma Krashi znajdeni dovzhini dlya rozmirnostej vid dev yati do trinadcyati 190 370 712 1373 2687 Cikli v korobci ne mozhut isnuvati v giperkubi rozmirnosti menshe dvoh Maksimalni dovzhini mozhlivih cikliv rivni 0 4 6 8 14 26 48 96 poslidovnist A000937 z Onlajn enciklopediyi poslidovnostej cilih chisel OEIS Poza cimi rozmirnostyami tochni dovzhini najdovshih cikliv nevidomi Krashi znajdeni dovzhini dlya rozmirnostej vid dev yati do trinadcyati 188 366 692 1344 2594 Podvijnij cikl ye specialnim vipadkom ce cikli druga polovina yakih povtoryuye strukturu pershoyi polovini Ci cikli vidomi takozh yak simetrichni cikli Dlya rozmirnostej vid dvoh do semi dovzhini najbilshih mozhlivih podvijnih cikliv rivni 4 6 8 14 26 46 Krim cih velichin krashimi znajdenimi dovzhinami dlya rozmirnostej vid vosmi do trinadcyati ye 94 186 362 662 1222 2354 Dlya oboh zavdan zmiya v korobci i cikl v korobci vidomo sho najbilsha dovzhina proporcijna 2n dlya n vimirnoyi korobki za zrostannya n i obmezhena zverhu znachennyam 2n 1 Odnak konstanta proporcijnosti ne vidoma ale dlya potochnih krashih vidomih znachen sposterigayetsya des u mezhah 0 3 0 4 Div takozhZadacha pro najdovshij shlyahPrimitkiKautz 1958 Dlya asimptoticheskih nizhnih granic sm stati Evdokimova Evdokimov 1969 Vojsichovski Wojciechowski 1989 Abbota i Kachalski Abbot Katchalski 1991 Dlya verhnih granic sm stati Duglasa Douglas 1969 Demera Deimer 1985 Solovyovoj Solovyova 1987 Abbota i Kachalski Abbot Katchalski 1988 Snevili Snevily 1994 i Zemora Zemor 1997 LiteraturaAbbot H L Katchalski M On the snake in the box problem 1988 T 45 S 13 24 DOI 10 1016 0095 8956 88 90051 2 Abbot H L Katchalski M On the construction of snake in the box codes Utilitas Mathematica 1991 T 40 S 97 116 David Allison Daniel Paulusma New Bounds for the Snake in the Box Problem 2016 arXiv 1603 05119 Bibcode 2016arXiv160305119A Bitterman D S New Lower Bounds for the Snake In The Box Problem A Prolog Genetic Algorithm and Heuristic Search Approach Department of Computer Science University of Georgia 2004 M S thesis Mario Blaum Tuvi Etzion Use of snake in the box codes for reliable identification of tracks in servo fields of a disk drive 2002 Casella D A Potter W D Using Evolutionary Techniques to Hunt for Snakes and Coils 2005 IEEE Congress on Evolutionary Computation CEC2005 2005 T 3 S 2499 2504 Casella D A New Lower Bounds for the Snake in the Box and the Coil in the Box Problems Department of Computer Science University of Georgia 2005 M S thesis Danzer L Klee V Length of snakes in boxes 1967 T 2 vip 3 S 258 265 DOI 10 1016 S0021 9800 67 80026 7 Davies D W Longest separated paths and loops in an N cube IEEE Transactions on Electronic Computers 1965 T EC 14 vip 2 S 261 DOI 10 1109 PGEC 1965 264262 Knut Deimer A new upper bound for the length of snakes 1985 T 5 vip 2 S 109 120 DOI 10 1007 BF02579373 Diaz Gomez P A Hougen D F The snake in the box problem mathematical conjecture and a genetic algorithm approach Proc 8th Conf Genetic and Evolutionary Computation Seattle Washington USA 2006 S 1409 1410 DOI 10 1145 1143997 1144219 Robert J Douglas Upper bounds on the length of circuits of even spread in the d cube 1969 T 7 vip 3 S 206 214 DOI 10 1016 S0021 9800 69 80013 X Evdokimov A A O maksimalnoj dline cepi v edinichnom n mernom kube Matem zametki 1969 T 6 S 309 319 William H Kautz Unit distance error checking codes IRE Transactions on Electronic Computers 1958 T 7 S 177 180 Kim S Neuhoff D L Proceedings of the IEEE International Symposium on Information Theory 2000 S 402 DOI 10 1109 ISIT 2000 866700 Kinny D Proceedings of the 20th European Conference on Artificial Intelligence ECAI 2012 5 listopada 2013 2012 S 462 467 Kinny D Proceedings of the 6th International WS on Multi disciplinary Trends in Artificial Intelligence MIWAI 2012 16 sichnya 2018 2012 S 271 283 Klee V What is the maximum length of a d dimensional snake American Mathematical Monthly 1970 T 77 vip 1 S 63 65 DOI 10 2307 2316860 JSTOR 2316860 Kochut K J Snake in the box codes for dimension 7 Journal of Combinatorial Mathematics and Combinatorial Computing 1996 T 20 S 175 185 Lukito A van Zanten A J A new non asymptotic upper bound for snake in the box codes Journal of Combinatorial Mathematics and Combinatorial Computing 2001 T 39 S 147 156 Kenneth G Paterson Jonathan Tuliani Some new circuit codes 1998 T 44 vip 3 S 1305 1309 DOI 10 1109 18 669420 Potter W D Robinson R W Miller J A Kochut K J Redys D Z Proceedings of the Seventh International Conference on Industrial amp Engineering Applications of Artificial Intelligence and Expert Systems Austin Texas USA 1994 S 421 426 Snevily H S The snake in the box problem a new upper bound 1994 T 133 S 307 314 DOI 10 1016 0012 365X 94 90039 6 Solovyova F I Verhnyaya granica dliny cikla v n mernom edinichnom kube Metody diskretnogo analiza v reshenii kombinatornyh zadach Sb nauch Tr Novosibirsk In t matematiki SO AN SSSR 1987 T 45 S 71 76 96 97 Tuohy D R Potter W D Casella D A Proceedings of the 2007 Int Conf on Genetic and Evolutionary Methods GEM 2007 Las Vegas Nevada USA 2007 S 3 9 Wojciechowski J A new lower bound for snake in the box codes 1989 T 9 vip 1 S 91 99 DOI 10 1007 BF02122688 Yuan Sheng Yang Fang Sun Song Han A backward search algorithm for the snake in the box problem Journal of the 2000 T 40 vip 5 S 509 511 Gilles Zemor An upper bound on the size of the snake in the box 1997 T 17 vip 2 S 287 298 DOI 10 1007 BF01200911 Zinovik I Kroening D Chebiryak Y Computing binary combinatorial gray codes via exhaustive search with SAT solvers IEEE Transactions on Information Theory 2008 T 54 vip 4 S 1819 1823 DOI 10 1109 TIT 2008 917695 PosilannyaKinny David 2012 Arhiv originalu za 3 bereznya 2016 Procitovano 18 lyutogo 2019 Potter W D 2011 Arhiv originalu za 26 lyutogo 2015 Procitovano 31 sichnya 2020 Weisstein Eric W Snake angl na sajti Wolfram MathWorld

Дата публікації:
Топ