Problema cu șarpele în cutie
Problema șarpelui într-o cutie în teoria graficelor și informatică se ocupă cu găsirea unui anumit tip de cale de-a lungul marginilor unui hipercub . Această potecă începe dintr-un colț și merge de-a lungul marginilor pentru câte colțuri poate ajunge. Odată ce se ajunge la un colț nou, colțul anterior și toți vecinii săi devin invalidi pentru utilizare. O potecă nu ar trebui să treacă niciodată printr-un colț după ce a fost marcată ca nevalidă.
Cu alte cuvinte, șarpele este conectat printr-o cale deschisă într-un hipercub, unde fiecare nod din cale, cu excepția capului (începutul lanțului) și a cozii (sfârșitul lanțului), are exact doi vecini care aparțin și șarpelui. Coada și capul la șarpe au un singur vecin fiecare. Regula pentru formarea șarpelui este că un nod din hipercub poate fi vizitat dacă este conectat la nodul curent printr-o margine și nu este vecin cu niciun nod vizitat al șarpelui, altul decât cel curent.
În terminologia teoriei grafurilor, aceasta se numește găsirea celei mai lungi căi posibile generate în hipercub . Acesta poate fi văzut ca un caz special al problemei izomorfismului pentru un subgraf generat . Există o problemă similară de a găsi un ciclu lung generat în hipercuburi, numită problema ciclului în cutie .
Problema șarpelui în cutie a fost descrisă pentru prima dată de Kautz [1] și motivul a fost teoria codurilor de corectare a erorilor . Vârfurile soluției la problema șarpelui sau ciclul din casetă pot fi folosite ca cod Gray care poate detecta erori într-un singur bit. Astfel de coduri au aplicații în inginerie electrică , teoria codificării și rețele de calculatoare . În aceste aplicații, este important să se dezvolte un cod cât mai lung posibil pentru o anumită dimensiune a hipercubului. Cu cât codul este mai lung, cu atât sunt mai eficiente proprietățile sale.
Găsirea celui mai mare șarpe sau ciclu devine sincer dificilă pe măsură ce dimensiunea crește, iar spațiul de căutare este predispus la o explozie combinatorie serioasă . Unele tehnici pentru determinarea limitelor superioare și inferioare pentru problema șarpelui cub includ dovezi care utilizează matematica discretă și teoria graficelor , căutarea exhaustivă în spațiul de căutare și căutarea euristică bazată pe tehnici evolutive.
Lungimi și limite cunoscute
Lungimea maximă a unui șarpe într-o cutie este cunoscută pentru dimensiuni de la unu la opt.
1, 2, 4, 7, 13, 26, 50, 98 secvența A099155 în
OEIS .
Deasupra celei de-a opta dimensiuni, lungimea exactă a celui mai mare șarpe nu este cunoscută. Cele mai bune lungimi găsite pentru dimensiunile nouă până la treisprezece
190, 370, 712, 1373, 2687.
Ciclurile (într-o cutie) nu pot exista într-un hipercub de dimensiune mai mică de două. Lungimile maxime ale ciclurilor posibile sunt
0, 4, 6, 8, 14, 26, 48, 96 secvență A000937 în
OEIS .
În afara acestor dimensiuni, lungimile exacte ale celor mai lungi cicluri sunt necunoscute. Cele mai bune lungimi găsite pentru dimensiunile nouă până la treisprezece
188, 366, 692, 1344, 2594.
Un ciclu dublu este un caz special - acestea sunt cicluri, dintre care a doua jumătate repetă structura primei jumătăți. Aceste cicluri sunt cunoscute și sub denumirea de cicluri simetrice . Pentru dimensiunile două până la șapte, lungimile celor mai mari cicluri duble posibile sunt
4, 6, 8, 14, 26, 46.
Pe lângă aceste valori, cele mai bune lungimi găsite pentru dimensiuni de la opt până la treisprezece sunt
94, 186, 362, 662, 1222, 2354.
Pentru ambele probleme, zmeu într-o cutie și ciclu într-o cutie, se știe că lungimea maximă este proporțională cu 2 n pentru o cutie n -dimensională pe măsură ce n crește și este mărginit de sus de 2 n-1 . Cu toate acestea, constanta de proporționalitate nu este cunoscută, dar pentru cele mai cunoscute valori curente se observă undeva în intervalul 0,3 - 0,4 [2] .
Note
- ↑ Kautz, 1958 .
- ↑ Pentru limitele inferioare asimptotice, a se vedea lucrările lui Evdokimov ( Evdokimov 1969 ), Wojciechowski ( 1989 ), Abbot și Katchalski ( Abbot, Katchalski 1991 ). Pentru limitele superioare, a se vedea lucrările lui Douglas ( Douglas 1969 ), Deimer ( Deimer 1985 ), Solovyova ( Solovyova 1987 ), Abbot și Katchalski ( Abbot, Katchalski 1988 ), Snevily ( 1994 ) și Zemor ( Zémor 1997 ).
Literatură
- Stareț HL, Katchalski M. Pe problema șarpelui în cutie // Journal of Combinatorial Theory, Series B . - 1988. - T. 45 . — S. 13–24 . - doi : 10.1016/0095-8956(88)90051-2 .
- Stareț HL, Katchalski M. Despre construcția codurilor șarpe-în-cutie // Utilitas Mathematica. - 1991. - T. 40 . — p. 97–116 .
- David Allison, Daniel Paulusma. Noi limite pentru problema Snake-in-the-Box . - 2016. - . - arXiv : 1603.05119 .
- Bitterman DS Noi limite inferioare pentru problema Snake-In-The-Box: Un algoritm genetic prolog și o abordare de căutare euristică . - Departamentul de Informatică, Universitatea din Georgia , 2004. - (teză de master).
- Mario Blaum, Tuvi Etzion. Utilizarea codurilor snake-in-the-box pentru identificarea fiabilă a pistelor în câmpurile servo ale unei unități de disc. — 2002.
- Casella DA, Potter WD Utilizarea tehnicilor evolutive pentru a vâna șerpi și bobine // 2005 Congresul IEEE privind calculul evolutiv (CEC2005). - 2005. - T. 3. - S. 2499–2504.
- Casella DA Noi limite inferioare pentru problemele Snake-in-the-Box și Coil-in-the-Box . - Departamentul de Informatică, Universitatea din Georgia , 2005. - (teză de master).
- Danzer L., Klee V. Length of snakes in boxes // Journal of Combinatorial Theory . - 1967. - Vol. 2 , numărul. 3 . — S. 258–265 . - doi : 10.1016/S0021-9800(67)80026-7 .
- Davies DW Cele mai lungi căi „separate” și bucle într-un cub N // Tranzacții IEEE pe computere electronice. - 1965. - T. EC-14 , nr. 2 . - S. 261 . doi : 10.1109 / PGEC.1965.264262 .
- Knut Deimer. O nouă limită superioară pentru lungimea șerpilor // Combinatorica . - 1985. - V. 5 , nr. 2 . — S. 109–120 . - doi : 10.1007/BF02579373 .
- Diaz-Gomez PA, Hougen DF Problema șarpelui în cutie: conjectura matematică și abordarea unui algoritm genetic // Proc. a 8-a Conf. Calcul genetic și evolutiv. - Seattle, Washington, SUA, 2006. - S. 1409-1410. - doi : 10.1145/1143997.1144219 .
- Robert J. Douglas. Limitele superioare ale lungimii circuitelor de răspândire uniformă în cubul d // Journal of Combinatorial Theory . - 1969. - T. 7 , nr. 3 . — S. 206–214 . - doi : 10.1016/S0021-9800(69)80013-X .
- Evdokimov A. A. Pe lungimea maximă a unui lanț dintr-un cub n-dimensional unitar // Matem. note. - 1969. - T. 6 . — S. 309–319 .
- William H. Kautz. Coduri de verificare a erorilor de distanță de unitate // Tranzacții IRE pe computere electronice. - 1958. - T. 7 . — S. 177–180 .
- Kim S., Neuhoff DL 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 . - 2012. - S. 462-467 . Arhivat din original pe 5 noiembrie 2013.
- Kinny D. Proceedings of the 6th International WS on Multi-disciplinary Trends in Artificial Intelligence, MIWAI-2012 . - 2012. - S. 271-283 . Arhivat din original pe 16 ianuarie 2018.
- Klee V. Care este lungimea maximă a unui șarpe d -dimensional? // American Mathematical Monthly . - 1970. - T. 77 , nr. 1 . — p. 63–65 . - doi : 10.2307/2316860 . — .
- Kochut KJ Codurile Snake-in-the-box pentru dimensiunea 7 // Journal of Combinatorial Mathematics and Combinatorial Computing. - 1996. - T. 20 . — S. 175–185 .
- Lukito A., van Zanten AJ O nouă limită superioară non-asimptotică pentru codurile snake-in-the-box // Journal of Combinatorial Mathematics and Combinatorial Computing. - 2001. - T. 39 . — S. 147–156 .
- Kenneth G. Paterson, Jonathan Tuliani. Câteva coduri de circuit noi // Tranzacții IEEE pe teoria informației . - 1998. - T. 44 , nr. 3 . - S. 1305-1309 . - doi : 10.1109/18.669420 .
- Potter WD, Robinson RW, Miller JA, Kochut KJ, Redys DZ Proceedings of the Seven International Conference on Industrial & Engineering Applications of Artificial Intelligence and Expert Systems. - Austin, Texas, SUA, 1994. - S. 421-426 .
- Snevily HS Problema șarpelui în cutie: o nouă limită superioară // Matematică discretă . - 1994. - T. 133 . — S. 307–314 . - doi : 10.1016/0012-365X(94)90039-6 .
- Solovieva F. I. Limită superioară a lungimii unui ciclu într-un cub unitar n - dimensional // Metode de analiză discretă în rezolvarea problemelor combinatorii: Sat. științific Proceedings.- Novosibirsk: Institutul de Matematică, Filiala Siberiană a Academiei de Științe a URSS, 1987. - T. 45 . — S. 71–76, 96–97 .
- Tuohy DR, Potter WD, Casella DA Proceedings of the 2007 Int. Conf. privind metodele genetice și evolutive (GEM'2007). — Las Vegas, Nevada, SUA, 2007. — p. 3–9 .
- Wojciechowski J. O nouă limită inferioară pentru codurile snake-in-the-box // Combinatorica . - 1989. - T. 9 , nr. 1 . — S. 91–99 . - doi : 10.1007/BF02122688 .
- Yuan Sheng Yang, Fang Sun, Song Han. Un algoritm de căutare înapoi pentru problema șarpelui în cutie // Journal of the Dalian University of Technology . - 2000. - T. 40 , nr. 5 . — S. 509–511 .
- Gilles Zemor. O limită superioară a mărimii șarpelui-în-cutie // Combinatorică . - 1997. - T. 17 , nr. 2 . — S. 287–298 . - doi : 10.1007/BF01200911 .
- Zinovik I., Kroening D., Chebiryak Y. Calcularea codurilor gri combinatorii binare prin căutare exhaustivă cu soluții SAT // IEEE Transactions on Information Theory. - 2008. - T. 54 , nr. 4 . — S. 1819–1823 . - doi : 10.1109/TIT.2008.917695 .
Link -uri