Wąż w pudełku
Problem węża w pudełku w teorii grafów i informatyce polega na znalezieniu pewnego rodzaju ścieżki wzdłuż krawędzi hipersześcianu . Ta ścieżka zaczyna się w jednym rogu i biegnie wzdłuż krawędzi do tylu rogów, ile może osiągnąć. Po dotarciu do nowego rogu poprzedni róg i wszyscy jego sąsiedzi muszą zostać oznaczeni jako niezdatni do użytku. Ścieżka nigdy nie powinna prowadzić do rogu, który został oznaczony jako niezdatny do użytku.
Innymi słowy, wąż jest połączoną otwartą ścieżką w hipersześcianie, gdzie każdy węzeł połączony ze ścieżką, z wyjątkiem głowy (początek) i ogona (koniec), ma dokładnie dwóch sąsiadów, którzy również są w wężu. Głowa i ogon mają tylko jednego sąsiada w wężu. Zasada generowania węża jest taka, że węzeł w hipersześcianie może być odwiedzany, jeśli jest połączony z bieżącym węzłem i nie jest sąsiadem żadnego wcześniej odwiedzonego węzła w wężu, innego niż bieżący węzeł.
W terminologii teorii grafów nazywa się to znalezieniem najdłuższej możliwej ścieżki indukowanej w hipersześcianie ; można to postrzegać jako szczególny przypadek problemu indukowanego izomorfizmu podgrafu . Istnieje podobny problem znajdowania długich indukowanych cykli w hipersześcianach, zwany problemem cewki w pudełku .
Problem węża w pudełku został po raz pierwszy opisany przez Kautza (1958) , motywowany teorią kodów korygujących błędy . Wierzchołki rozwiązania problemu węża lub cewki w pudełku mogą być użyte jako kod Graya , który może wykrywać błędy jednobitowe. Takie kody mają zastosowanie w elektrotechnice , teorii kodowania i topologiach sieci komputerowych . W tych aplikacjach ważne jest, aby wymyślić jak najdłuższy kod dla danego wymiaru hipersześcianu . Im dłuższy kod, tym bardziej efektywne są jego możliwości.
Znalezienie najdłuższego węża lub zwoju staje się niezwykle trudne, gdy liczba wymiarów wzrasta, a przestrzeń poszukiwań ulega poważnej eksplozji kombinatorycznej . Niektóre techniki określania górnych i dolnych granic problemu węża w pudełku obejmują dowody z wykorzystaniem matematyki dyskretnej i teorii grafów , wyczerpujące przeszukiwanie przestrzeni poszukiwań oraz przeszukiwanie heurystyczne z wykorzystaniem technik ewolucyjnych.
Znane długości i granice
Maksymalna długość problemu węża w pudełku jest znana dla wymiarów od jednego do ósmego; to jest
Poza tą długością dokładna długość najdłuższego węża nie jest znana; najlepsze długości znalezione do tej pory dla wymiarów od dziewiątego do trzynastego to
- 190, 370, 712, 1373, 2687.
W przypadku cykli (problem cewki w pudełku) cykl nie może istnieć w hipersześcianie o wymiarze mniejszym niż dwa. Maksymalne długości najdłuższych możliwych cykli to
Poza tą długością dokładna długość najdłuższego cyklu nie jest znana; najlepsze długości znalezione do tej pory dla wymiarów od dziewiątego do trzynastego to
- 188, 366, 692, 1344, 2594.
Podwojone cewki to szczególny przypadek: cykle, których druga połowa powtarza strukturę pierwszej połowy, znane również jako cewki symetryczne . Dla wymiarów od drugiego do siódmego długości najdłuższych możliwych podwojonych cewek wynoszą
- 4, 6, 8, 14, 26, 46.
Poza tym najlepsze znalezione dotychczas długości dla wymiarów od ósmego do trzynastego to
- 94, 186, 362, 662, 1222, 2354.
Zarówno w przypadku węża, jak i cewki w pudełku wiadomo, że maksymalna długość jest proporcjonalna do 2 n dla n -wymiarowego pudełka, asymptotycznie, gdy n rośnie i jest ograniczona powyżej przez 2 n - 1 . Jednak stała proporcjonalności nie jest znana, ale obserwuje się, że mieści się w zakresie 0,3 - 0,4 dla obecnie najbardziej znanych wartości.
Notatki
- Opat, HL; Katchalski, M. (1988), "O problemie węża w pudełku", Journal of Combinatorial Theory, Seria B , 45 : 13–24, doi : 10.1016/0095-8956 (88) 90051-2
- Opat, HL; Katchalski, M. (1991), "O konstrukcji kodów typu snake-in-the-box", Utilitas Mathematica , 40 : 97–116
- Allison, Dawid; Paulusma, Daniel (2016), Nowe granice problemu węża w pudełku , 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) (praca magisterska), Wydział Informatyki, University of Georgia
- Blaum, Mario; Etzion, Tuvi (2002), Wykorzystanie kodów węża w pudełku do niezawodnej identyfikacji ścieżek w polach serwonapędu dysku , patent USA 6,496,312
- Casella, DA; Potter, WD (2005), „Używanie technik ewolucyjnych do polowania na węże i cewki”, 2005 IEEE Congress on Evolutionary Computation (CEC2005) , tom. 3, s. 2499–2504
- Casella, DA (2005), New Lower Bounds for the Snake-in-the-Box and the Coil-in-the-Box Problems (PDF) (praca magisterska), Wydział Informatyki, University of Georgia
- Danzer, L.; Klee, V. (1967), „Długość węży w pudełkach”, Journal of Combinatorial Theory , 2 (3): 258–265, doi : 10.1016 / S0021-9800 (67) 80026-7
- Davies, DW (1965), „Najdłuższe 'oddzielone' ścieżki i pętle w kostce N ”, IEEE Transactions on Electronic Computers , EC-14 (2): 261, doi : 10.1109/PGEC.1965.264259
- Deimer, Knut (1985), „Nowa górna granica długości węży”, Combinatorica , 5 (2): 109–120, doi : 10.1007 / BF02579373
- Diaz-Gomez, Pensylwania; Hougen, DF (2006), „Problem węża w pudełku: przypuszczenia matematyczne i podejście do algorytmu genetycznego”, 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), „Górne granice długości obwodów o równym rozkładzie w kostce d ”, Journal of Combinatorial Theory , 7 (3): 206–214, doi : 10,1016 / S0021-9800 (69 )80013-X
- Evdokimov, AA (1969), „Maksymalna długość łańcucha w jednostce n -wymiarowej sześcianie”, Matematicheskie Zametki , 6 : 309–319
- Kautz, William H. (czerwiec 1958), „Kody sprawdzania błędów na odległość jednostek”, IRE Transactions on Electronic Computers , EC-7 (2): 179–180, doi : 10.1109 / TEC.1958.5222529 , S2CID 26649532
- Kim, S.; Neuhoff, DL (2000), „Kody węża w pudełku jako solidne przypisania indeksu kwantyzatora”, Proceedings of the IEEE International Symposium on Information Theory , s. 402, doi : 10.1109/ISIT.2000.866700
- Kinny, D. (2012), „Nowe podejście do problemu węża w pudełku”, 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 6th International WS on Multi-dyscyplinarne trendy w sztucznej inteligencji, MIWAI-2012 , s. 271–283
- Klee, V. (1970), „Jaka jest maksymalna długość d -wymiarowego węża?”, American Mathematical Monthly , 77 (1): 63–65, doi : 10,2307/2316860 , JSTOR 2316860
- Kochut, KJ (1996), „Kody węża w pudełku dla wymiaru 7”, Journal of Combinatorial Mathematics and Combinatorial Computing , 20 : 175–185
- Lukito, A.; van Zanten, AJ (2001), „Nowa nieasymptotyczna górna granica kodów węża w pudełku”, Journal of Combinatorial Mathematics and Combinatorial Computing , 39 : 147–156
- Paterson, Kenneth G.; Tuliani, Jonathan (1998), „Niektóre nowe kody obwodów”, 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), „Używanie algorytmu genetycznego do znajdowania kodów węża w pudełku”, Proceedings of the Seventh International Conference on Industrial & Engineering Applications of Artificial Intelligence and Expert Systems , Austin, Teksas, USA, s. 421–426
- Snevily, HS (1994), „Problem węża w pudełku: nowa górna granica”, Matematyka dyskretna , 133 (1–3): 307–314, doi : 10,1016 / 0012-365X (94) 90039- 6
- Solov'eva, FI (1987), „Górna granica długości cyklu w n -wymiarowym sześcianie jednostkowym”, Metody Diskretnogo Analiza (po rosyjsku), 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. on Genetic and Evolutionary Methods (GEM'2007) , Las Vegas, Nevada, USA, s. 3–9
- Wojciechowski, J. (1989), „Nowa dolna granica kodów węża w pudełku”, Combinatorica , 9 (1): 91–99, doi : 10.1007 / BF02122688
- Yang, Yuan Sheng; Słońce, Kieł; Han, Song (2000), „Algorytm wyszukiwania wstecznego dla problemu węża w pudełku”, Journal of the Dalian University of Technology , 40 (5): 509–511
- Zémor, Gilles (1997), „Górna granica wielkości węża w pudełku”, Combinatorica , 17 (2): 287–298, doi : 10.1007 / BF01200911
- Zinowik, I.; Kroening, D.; Chebiryak, Y. (2008), „Obliczanie binarnych kombinatorycznych kodów szarości poprzez wyczerpujące wyszukiwanie za pomocą solwerów SAT”, IEEE Transactions on Information Theory , 54 (4): 1819–1823, doi : 10.1109 / TIT.2008.917695 , hdl : 20.500.11850 /11304
Linki zewnętrzne
- Kinny, David (2012), Strona badawcza węża w pudełku (Uniwersytet w Kioto)
- Potter, WD (2011), Lista aktualnych zapisów dotyczących problemu węża w pudełku (UGA)
- Weisstein, Eric W. , „Snake” , MathWorld