Huszárvándorlás-probléma

A Wikipédiából, a szabad enciklopédiából
Ugrás a navigációhoz Ugrás a kereséshez

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élet[szerkeszté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énete[szerkeszté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és[szerkeszté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-algoritmusok[szerkeszté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ódszerek[szerkeszté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ózattal[szerkeszté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ály[szerkesztés]

Chess zhor 26.svg
Chess zver 26.svg
a8 b8 c8 d8 e8 f8 g8 h8
a7 b7 c7 d7 e7 f7 g7 h7
a6 b6 c6 d6 e6 f6 g6 h6
a5 b5 c5 d5 e5 f5 g5 h5
a4 b4 c4 d4 e4 f4 g4 h4
a3 b3 c3 d3 e3 f3 g3 h3
a2 b2 c2 d2 e2 f2 g2 h2
a1 b1 c1 d1 e1 f1 g1 h1
Chess zver 26.svg
Chess zhor 26.svg
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]

Jegyzetek[szerkesztés]

  1. Java How To Program Fifth Edition., 5th, Prentice Hall, 326–328. o. (2003. június 15.). 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ók[szerkesztés]

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

Fordítás[szerkeszté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.