Főmenü megnyitása

Huszárvándorlás-probléma

huszár olyan lépéssorozata egy sakktáblán, melynek során minden mezőt pontosan egyszer érint

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.[1] 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életSzerkesztés

 
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.[2]

TörténeteSzerkesztés

 
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[3] (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

se
na le

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átan Á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ésSzerkeszté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:

  1. m és n értéke egyaránt páratlan
  2. m = 1, 2 vagy 4
  3. 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.[2][4]

Körutak száma Szerkesztés

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.[5]

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 Szerkesztés

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-algoritmusokSzerkesztés

 
A Warnsdorf-szabály alapján létrehozott hatalmas (130×130-as) négyzetes nyitott huszárvándorlás.

A brute force-módszer (kimerítő keresés) a gyakorlatban csak a legkisebb táblaméreteken alkalmazható;[6] például egy 8×8-as táblán mintegy 4×1051 lépéssorozat lehetséges,[7] 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ó."[6]

„Oszd meg és uralkodj” módszerekSzerkesztés

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ó.[4][8]

Megoldás neurális hálózattalSzerkesztés

 
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.[9] 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álySzerkesztés

 
 
               
               
               
               
               
               
               
               
 
 
A Warnsdorf-szabály grafikus ábrázolása. A mezőkre írt szám azt mondja meg, hány helyre léphet a huszár az adott mezőről. Ebben az esetben a szabály azt írja elő, hogy a legkisebb számot tartalmazó, tehát a 2-essel jelölt mezőre lépjünk.


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,[10] illetve a Squirrel és Cull[11] á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ó.[10] A huszárvándorlás-probléma ennek egy speciális esete.[12]

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.[12] 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.[13]

JegyzetekSzerkesztés

  1. Java How To Program Fifth Edition., 5th, Prentice Hall, 326–328. o. (2003. október 27.). ISBN 978-0131016217 
  2. a b Conrad, A. (1994). „Solution of the Knight's Hamiltonian Path Problem on Chessboards”. Discrete Applied Mathematics 50 (2), 125–134. o. DOI:10.1016/0166-218X(92)00170-Q.  
  3. Satyadev, Chaudhary. Kavyalankara of Rudrata (Sanskrit Text, with Hindi translation);. Delhitraversal: Parimal Sanskrit Series No. 30 
  4. a b Cull, P. (1978). „Knight's Tour Revisited”. Fibonacci Quarterly 16, 276–285. o.  
  5. Weisstein, Eric W.: Knight's Tour (angol nyelven). Wolfram MathWorld
  6. a b Simon, Dan (2013), Evolutionary Optimization Algorithms, John Wiley & Sons, pp. 449–450, ISBN 9781118659502, <https://books.google.com/books?id=gwUwIEPqk30C&pg=PA449>
  7. Enumerating the Knight's Tour
  8. Parberry, Ian (1997). „An Efficient Algorithm for the Knight's Tour Problem”. Discrete Applied Mathematics 73, 251–260. o. [2013. szeptember 27-i dátummal az eredetiből archiválva]. DOI:10.1016/S0166-218X(96)00010-8. (Hozzáférés ideje: 2017. április 5.)  
  9. Y. Takefuji, K. C. Lee. "Neural network computing for knight's tour problems." Neurocomputing, 4(5):249–254, 1992.
  10. a b Pohl, Ira (1967. július 1.). „A method for finding Hamilton paths and Knight's tours”. Communications of the ACM 10 (7), 446–449. o. DOI:10.1145/363427.363463.  
  11. Squirrel, Douglas: A Warnsdorff-Rule Algorithm for Knight's Tours on Square Boards, 1996. (Hozzáférés: 2011. augusztus 21.)
  12. a b Alwan, Karla (1992). „Finding Re-entrant Knight's Tours on N-by-M BoardsACM Southeast Regional Conference.: 377–382, New York, New York: ACM. doi:10.1145/503720.503806. Hozzáférés: 2008. október 28.. 
  13. Century/Acorn User Book of Computer Puzzles 

További információkSzerkesztés

A Wikimédia Commons tartalmaz Huszárvándorlás-probléma témájú médiaállományokat.

FordításSzerkesztés

Ez a szócikk részben vagy egészben a Knight's tour című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel.