Ugrás a tartalomhoz

Huszárvándorlás-probléma

A Wikipédiából, a szabad enciklopédiából

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]
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
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úlius 1.). 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: 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 Boards”. ACM 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. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.