A huszárvándorlás-probléma, huszárkörút vagy sakktábla bejárása huszárral egy huszár lépéssorozata a sakktáblán, amely alatt a huszár a tábla minden mezőjét pontosan egyszer érinti. Ha az utolsó mező megegyezik a kiinduló mezővel, a körút zárt, másképp a körút nyitott.
A sakktábla bejárása huszárral matematikai probléma. Olyan algoritmus létrehozása, mely megkeresi ezt a bejárást, ismert számítástechnikai feladat. A huszárkörút problémája különböző méretű sakktáblákon fennáll, nemcsak a 8×8-ason, sőt a szabálytalan (nem téglalap) alakú táblákon is.
Elmélet balra|bélyegkép|270x270px|A grafikon megmutatja a huszárkörút minden lehetséges változatát egy szabványos 8x8-as sakktáblán. A csomópontok számai a lehetséges lépések számát jelzik abból a pozícióból. A huszárkörút-probléma egy sajátos Hamilton-út-probléma a gráfelméletből. A zárt huszárkörút megtalálása hasonló a Hamilton-kör problémájához. A Hamilton-út problémájától eltérően a huszárkörutat meg lehet oldani lineáris időben.
Története bélyegkép|250x250px|A huszár útja, Turk megoldása. Ez az egyéni megoldás zárt típusú (kör típusú), és így a tábla bármely pontján befejezhető A legkorábbi ismert említése a huszárkörút problémájának a 9. századba nyúlik vissza. Rudrata Kavyalankara (5.15) c., szanszkrit nyelvű költészeti munkájában egy huszárkörút mintája egy fél táblán úgy van ábrázolva, mint bonyolult poétikai ábra (citra-alaṅkāra), turagapadabandha vagy rendezés huszárlépésben néven. Ugyanazt a verset négy, egyenként nyolc szótagos sorban el lehet olvasni balról jobbra vagy követve a huszárkörút vonalát. Mivel a szanszkrit átírására használt indiai írásrendszer szótag alapú, minden szótag egy mezőt jelenthet a sakktáblán. Rudrata példája a következő: सेनालीलीलीनानालीलीनानानानालीलीलीनलीनालीलेनालीनालीलीलीनानानानाली
átírva
senālīlīlīnānālīlīnānānānālīlīlīnalīnālīlenālīnālīlīlīnānānānālī
Például az első sor olvasható balról jobbra vagy az első négyzetből a 2. sor 3. szótagjára (2.3) lépve, majd 1.5 – 2.7 – 4.8 – 3.6 – 4.4 – 3.2.
Az első matematikusok egyike, aki a huszárkörúttal kísérletezett, Leonhard Euler volt. Az első eljárás a huszárkörút megtalálására a Warnsdorf-szabály volt, amelyet 1823-ban írt le H. C. von Warnsdorf.
A 20. században többek között az Oulipo írók csoportja is használta. A legjelentősebb példa a 10×10-es huszárkörút, amely meghatározza a fejezetek sorrendjét Georges Perec La Vie mode d’emploi regényében. A 2010-es sakkvilágbajnokság döntőjében, Visuvanádan Ánand és Veszelin Topalov között, a 6. játszmában Anand 13 egymást követő huszárlépést tett (igaz, mindkét huszárt használva); online kommentátorok azon tréfálkoztak, hogy Anand a játék során a huszárkörút problémáját próbálta megoldani.
Létezés Schwenk bebizonyította, hogy minden m×n-es táblán, ahol m≤n, mindig létezik egy zárt huszárkörút, kivéve, ha az alábbi feltételek valamelyike igaz: m és n értéke egyaránt páratlan m = 1, 2 vagy 4 m = 3 és n = 4, 6 vagy 8. Cull és munkatársai, valamint Conrad és munkatársai bebizonyították, hogy minden téglalap alakú táblán, amelynek a kisebbik mérete legalább 5, létezik egy (esetleg nyitott) huszárkörút.
Körutak száma Egy 8×8-as táblán pontosan 26 534 728 821 064 irányított zárt körút létezik. Az irányítatlan zárt körutak száma ennek a fele, mivel mindegyik körút fordítva is bejárható. Egy 6×6-os táblán 9862 irányítatlan zárt körút van.
Az irányított nyitott körutak száma egy n×n-es táblán, ahol n = 1, 2, ... : 1; 0; 0; 0; 1728; 6 637 920; 165 575 218 320; 19 591 828 170 979 904.
Körutak megtalálása számítógéppel Számos módszer létezik a huszárvándorlás-probléma adott méretű táblán történő megoldására. Egyes módszerek algoritmikusak, mások csak heurisztikák.
Brute force-algoritmusok
A brute force-módszer (kimerítő keresés) a gyakorlatban csak a legkisebb táblaméreteken alkalmazható; például egy -as táblán mintegy 4 lépéssorozat lehetséges, ami jóval meghaladja a modern számítógépek (vagy akár számítógép-hálózatok) lehetőségeit. Ennek a számnak a mérete azonban megtévesztő a feladat nehézségére nézve, ami „az emberi belátás és találékonyság segítségével […] különösebb nehézség nélkül megoldható."
„Oszd meg és uralkodj” módszerek Oszd meg és uralkodj-algoritmus segítségével, tehát a tábla kisebb részekre való osztásával, a kisebb részeken a huszárkörút megszerkesztésével, majd ezek összefűzésével, a feladat a legtöbb téglalap alakú táblán polinom időben megoldható.
Megoldás neurális hálózattal bélyegkép|250x250px|Neurális hálózattal talált, zárt huszárkörút egy 24×24-es táblán A huszárvándorlás-probléma jól megoldható neurális hálózat segítségével is.Y. Takefuji, K. C. Lee. "Neural network computing for knight's tour problems." Neurocomputing, 4(5):249–254, 1992. A hálózat úgy van összerakva, hogy minden érvényes huszárlépést egy mesterséges neuron reprezentál, melyek kezdeti állapota véletlenszerűen „aktív” vagy „inaktív” (1 vagy 0 kimenet), ahol az 1 érték arra utal, hogy a neuron része a végső megoldásnak. Minden neuron rendelkezik egy (alább leírt) állapotfüggvénnyel, melynek kezdeti értéke 0.
A hálózat futtatásakor minden neuron megváltoztathatja az állapotát a (pontosan egy huszárlépésre lévő) szomszédai állapotai és kimenetei alapján, a következő szabályok szerint:
ahol diszkrét időintervallumot jelképez, pedig az mezőt mezővel összekötő neuron állapota, az -t -vel összekötő neuron kimenete, pedig a neuron szomszédainak halmaza.
Bár divergáló esetek elvileg elképzelhetők, a hálózatnak végül konvergálnia kell; ez akkor történik meg, ha és között egy neuron sem változtat állapotot. Ha a hálózat konvergált, az eredményül kapott hálózat vagy huszárvándorlást kódol, vagy két (esetleg több) egymástól független huszárvándorlást ugyanazon a táblán.
Warnsdorf-szabály
A Warnsdorf-szabály a huszárvándorlás megtalálására alkalmazott heurisztika. A huszárral mindig olyan mezőre igyekszünk lépni, melyre a lehető legkevesebbféleképpen lehet lépni. Amikor a szóba jövő mezők lehetséges bejövő lépéseinek számát kalkuláljuk, nem vesszük figyelembe a már meglátogatott mezőkről kiinduló lépéseket. Természetesen kialakulhatnak döntetlenek, ezek feloldására több módszer létezik, köztük a Pohl, illetve a Squirrel és Cull által kidolgozottak.
A szabály általánosabban bármely gráfra alkalmazható. Gráfelméleti fogalmakkal operálva, minden lépés a legalacsonyabb fokszámú szomszédos csúcsra történik. Bár a Hamilton-út probléma általánosságban NP-nehéz, számos, a gyakorlatban előforduló gráfon ezzel a heurisztikával lineáris időben megoldható. A huszárvándorlás-probléma ennek egy speciális esete.
A heurisztikát elsőként H. C. von Warnsdorf írta le 1823-ban megjelent "Des Rösselsprungs einfachste und allgemeinste Lösung" c. írásában. A problémát tetszőleges kiindulási helyzetből a Warnsdorf-szabályt használva megoldó számítógépi programot Gordon Horsington publikálta 1984-ben a Century/Acorn User Book of Computer Puzzles c. könyvben.
Jegyzetek
További információk
H. C. von Warnsdorf 1823 in Google Books Introduction to Knight's tours by George Jelliss Knight's tours complete notes by George Jelliss
Fordítás
Kategória:Sakktörténelem Kategória:Gráfelmélet Kategória:Gráfalgoritmusok Kategória:Hamilton-utak és -körök Kategória:Matematikai problémák