Orm-i-lådan
Orm -in-the-box- problemet inom grafteori och datavetenskap handlar om att hitta en viss typ av väg längs kanterna på en hyperkub . Den här vägen börjar vid ett hörn och går längs kanterna till så många hörn som den kan nå. När den har kommit till ett nytt hörn måste det föregående hörnet och alla dess grannar markeras som oanvändbara. Stigen får aldrig gå till ett hörn som har markerats som oanvändbart.
orm är med andra ord en sammankopplad öppen bana i hyperkuben där varje nod är kopplad till bana, med undantag för huvudet (start) och svansen (slut), den har exakt två grannar som också finns i ormen. Huvudet och svansen har var och en bara en granne i ormen. Regeln för att generera en orm är att en nod i hyperkuben kan besökas om den är ansluten till den aktuella noden och den inte är granne till någon tidigare besökt nod i ormen, förutom den aktuella noden.
I grafteoretisk terminologi kallas detta att hitta den längsta möjliga inducerade vägen i en hyperkub ; det kan ses som ett specialfall av problemet med inducerad subgrafisomorfism . Det finns ett liknande problem med att hitta långa inducerade cykler i hyperkuber, kallat coil-in-the-box- problemet.
Problemet med orm-i-lådan beskrevs först av Kautz (1958) , motiverat av teorin om felkorrigerande koder . Toppen av en lösning på problem med ormen eller spolen i lådan kan användas som en grå kod som kan upptäcka enbitsfel. Sådana koder har tillämpningar inom elektroteknik , kodningsteori och datornätverkstopologier . I dessa applikationer är det viktigt att utforma en så lång kod som möjligt för en given dimension av hyperkub . Ju längre koden är, desto effektivare är dess kapacitet.
Att hitta den längsta ormen eller spolen blir notoriskt svårt eftersom dimensionstalet ökar och sökutrymmet drabbas av en allvarlig kombinatorisk explosion . Vissa tekniker för att bestämma de övre och nedre gränserna för orm-i-lådan-problemet inkluderar bevis med diskret matematik och grafteori , uttömmande sökning av sökutrymmet och heuristisk sökning med evolutionära tekniker.
Kända längder och gränser
Den maximala längden för problemet med orm-i-lådan är känd för dimensionerna ett till åtta; det är
Bortom den längden är den exakta längden på den längsta ormen inte känd; de bästa längderna som hittats hittills för dimensionerna nio till tretton är
- 190, 370, 712, 1373, 2687.
För cykler (problemet med spiral-i-lådan) kan en cykel inte existera i en hyperkub med dimension mindre än två. De maximala längderna för de längsta möjliga cyklerna är
Utöver den längden är den exakta längden av den längsta cykeln inte känd; de bästa längderna som hittats hittills för dimensionerna nio till tretton är
- 188, 366, 692, 1344, 2594.
Dubblade spolar är ett specialfall: cykler vars andra halva upprepar strukturen för deras första halva, även känd som symmetriska spolar . För dimensionerna två till sju är längden på de längsta möjliga dubbla spolarna
- 4, 6, 8, 14, 26, 46.
Utöver det är de bästa längderna hittills för dimensionerna åtta till tretton
- 94, 186, 362, 662, 1222, 2354.
För både problem med ormen och spolen i lådan är det känt att den maximala längden är proportionell mot 2 n för en n -dimensionell låda, asymptotiskt när n växer sig stor, och ovanför avgränsas av 2 n − 1 . Emellertid är proportionalitetskonstanten inte känd, men observeras vara i intervallet 0,3 - 0,4 för nuvarande mest kända värden.
Anteckningar
- Abbot, HL; Katchalski, M. (1988), "On the snake in the box problem", Journal of Combinatorial Theory, Series B , 45 : 13–24, doi : 10.1016/0095-8956(88)90051-2
- Abbot, HL; Katchalski, M. (1991), "On the construction of snake-in-the-box-koder", Utilitas Mathematica , 40 : 97–116
- Allison, David; Paulusma, Daniel (2016), New Bounds for the Snake-in-the-Box Problem , arXiv : 1603.05119 , Bibcode : 2016arXiv160305119A
- Bitterman, DS (2004), New Lower Bounds for the Snake-In-The-Box Problem: A Prolog Genetic Algorithm and Heuristic Search Approach ( PDF) (MS-avhandling), Institutionen för datavetenskap, University of Georgia
- Blaum, Mario; Etzion, Tuvi (2002), Användning av snake-in-the-box-koder för tillförlitlig identifiering av spår i servofält på en diskenhet , US Patent 6,496,312
- Casella, DA; Potter, WD (2005), "Using Evolutionary Techniques to Hunt for Snakes and Coils", 2005 IEEE Congress on Evolutionary Computation (CEC2005), vol. 3, s. 2499-2504
- Casella, DA (2005), New Lower Bounds for the Snake-in-the-Box and the Coil-in-the-Box Problems ( PDF) (MS-avhandling), Institutionen för datavetenskap, University of Georgia
- Danzer, L.; Klee, V. (1967), "Längd på ormar i lådor", Journal of Combinatorial Theory , 2 (3): 258–265, doi : 10.1016/S0021-9800(67)80026-7
- Davies, DW (1965), "Longest 'separated' paths and loops in an N -cube", IEEE Transactions on Electronic Computers , EC-14 (2): 261, doi : 10.1109/PGEC.1965.264259
- Deimer, Knut (1985), "En ny övre gräns för ormarnas längd", Combinatorica , 5 (2): 109–120, doi : 10.1007/BF02579373
- Diaz-Gomez, PA; Hougen, DF (2006), "The snake in the box problem: matematic conjecture and a genetic algorithm approach", Proceedings of the 8th Conference on Genetic and Evolutionary Computation , Seattle, Washington, USA, s. 1409–1410, doi : 10.1145 /1143997.1144219
- Douglas, Robert J. (1969), "Upper bounds on the length of circuits of even spread in the d -cube", Journal of Combinatorial Theory , 7 (3): 206–214, doi : 10.1016/S0021-9800(69) )80013-X
- Evdokimov, AA (1969), "Maximal längd av en kedja i en enhet n -dimensionell kub", Matematheskie Zametki , 6 : 309–319
- Kautz, William H. (juni 1958), "Unit-distance error-checking codes", IRE Transactions on Electronic Computers , EC-7 (2): 179–180, doi : 10.1109/TEC.1958.5222529 , S2CID 26649533
- Kim, S.; Neuhoff, DL (2000), "Snake-in-the-box-koder som robusta kvantiserare indexuppdrag", Proceedings of the IEEE International Symposium on Information Theory , sid. 402, doi : 10.1109/ISIT.2000.866700
- Kinny, D. (2012), "A New Approach to the Snake-In-The-Box Problem", Proceedings of the 20th European Conference on Artificial Intelligence, ECAI-2012, s. 462–467
- Kinny, D. (2012), "Monte-Carlo Search for Snakes and Coils", Proceedings of the 6th International WS on Multi-disciplinary Trends in Artificial Intelligence, MIWAI-2012, s. 271–283
- Klee, V. (1970), "What is the maximum length of a d -dimensional snake?", American Mathematical Monthly , 77 (1): 63–65, doi : 10.2307/2316860 , JSTOR 2316860
- Kochut, KJ (1996), "Snake-in-the-box-koder för dimension 7", Journal of Combinatorial Mathematics and Combinatorial Computing , 20 : 175–185
- Lukito, A.; van Zanten, AJ (2001), "A new non-asymptotic upper bound for snake-in-the-box codes", Journal of Combinatorial Mathematics and Combinatorial Computing , 39 : 147–156
- Paterson, Kenneth G.; Tuliani, Jonathan (1998), "Some new circuit codes", IEEE Transactions on Information Theory , 44 (3): 1305–1309, doi : 10.1109/18.669420
- Potter, WD; Robinson, RW; Miller, JA; Kochut, KJ; Redys, DZ (1994), "Using the genetic algorithm to find snake in the box codes", Proceedings of the Seventh International Conference on Industrial & Engineering Applications of Artificial Intelligence and Expert Systems, Austin, Texas, USA, s. 421–426
- Snevily, HS (1994), "The snake-in-the-box problem: a new upper bound", Diskret matematik , 133 (1–3): 307–314, doi : 10.1016/0012-365X(94)90039- 6
- Solov'eva, FI (1987), "En övre gräns för längden av en cykel i en n -dimensionell enhetskub", Metody Diskretnogo Analiza (på ryska), 45 : 71–76, 96–97
- Tuohy, DR; Potter, WD; Casella, DA (2007), "Searching for Snake-in-the-Box Codes with Evolved Pruning Models", Proceedings of the 2007 Int. Konf. om genetiska och evolutionära metoder (GEM'2007) , Las Vegas, Nevada, USA, s. 3–9
- Wojciechowski, J. (1989), "A new lower bound for snake-in-the-box codes", Combinatorica , 9 (1): 91–99, doi : 10.1007/BF02122688
- Yang, Yuan Sheng; Sol, Fang; Han, Song (2000), "A backward search algorithm for the snake in the box problem", Journal of the Dalian University of Technology , 40 (5): 509–511
- Zémor, Gilles (1997), "An upper bound on the size of the snake-in-the-box", Combinatorica , 17 (2): 287–298, doi : 10.1007/BF01200911
- Zinovik, I.; Kroening, D.; Chebiryak, Y. (2008), "Computing binary combinatorial grey codes via exhaustive search with SAT solvers", IEEE Transactions on Information Theory , 54 (4): 1819–1823, doi : 10.1109/TIT.2008.917695 , 01 hdl 5 .01 hdl 5 . /11304
externa länkar
- Kinny, David (2012), Snake-in-the-Box Research Page (Kyoto University)
- Potter, WD (2011), En lista över aktuella rekord för Snake-in-the-Box Problem (UGA)
- Weisstein, Eric W. , "Snake" , MathWorld