knight's tour problem

Angol

Főnév

knight's tour problem (tsz. knight's tour problems)

(informatika) A lóugrásos túra (Knight’s Tour) probléma a sakktáblán (általában 8×8-as, de tetszőleges ${\textstyle n\times n}$ méretű táblán is értelmezhető) a ló (knight) úgy mozgatásának feladata, hogy a táblán minden mezőt pontosan egyszer látogasson meg.

1. A probléma megfogalmazása

Tábla: ${\textstyle n\times n}$ mezőkből álló rács.
Ló lépése: az „L” alakú mozgás: két mezőt vízszintesen és egyet függőlegesen, vagy két mezőt függőlegesen és egyet vízszintesen.
Cél: találni egy olyan lépéssorozatot, mely az induló mezőről indulva pontosan egyszer jár be minden mezőt (összesen ${\textstyle n^{2}}$ lépés, vagyis ${\textstyle n^{2}-1}$ mozgás).

Két változat:

Open tour (nyílt túra): az utolsó lépés nem köt vissza az induló mezőre.
Closed tour (zárt túra): az utolsó lépés a kirajzott útvonalat visszaköti az induló mezőre is, így kör alakú utat alkot.

2. Megoldási módszerek

2.1 Backtracking (visszalépős keresés)

Legáltalánosabb, de exponenciális időigényű módszer:

Rekurzió: minden lépésnél kipróbáljuk a ló-mozgásokat azon mezőkre, amelyek még nem voltak látogatva.
Visszalépés: ha egy ponton már nincs hátralévő érvényes lépés, visszalépünk az előző állapotokra, és más irányt próbálunk.
Gyorsítás: mező-címkézés és bitműveletek a látogatottság követésére.

Ez az eljárás ${\textstyle O(8^{n^{2}})}$ natív gyökerek felé mozog, így 8×8-as táblán is nehéz, de modern számítógépen elérhető, különösen ha korai visszavágást alkalmazunk.

2.2 Warnsdorff-szabály (heurisztika)

Egy egyszerű, de gyakran működőgreedy szabály:

Minden lépésnél a ló onnan indulva azt a következő lépést választja, amely a lehetséges ugrások közül a legkevesebb további lépési lehetőséget hagy maga után („legkisebb szabadságfok”).
Ha több mezőhöz is tartozik minimális szabad ugrás, köztük tetszőlegesen választunk.

Ez a heuristika 8×8-as táblán zárt túrát ad 85–90 %-ban, és ha beüt a zsákutca, visszalépéssel ritkán kell korrigálni.

3. Speciális eredmények

Létezés
- Minden ${\textstyle n\times n}$ táblán, ahol ${\textstyle n\geq 5}$ , létezik zárt ló-túra.
- Az 1×1, 2×2, 2×3, 3×3 táblákon nincs teljes túra.
Számszerű eredmények
- Az 8×8-as táblán körülbelül ${\textstyle 26\times 10^{14}}$ (több mint 26 billiárd) nyílt túra, ezekből mintegy 1,6×10¹³ zárt túra exists.

4. Kapcsolódó problémák és alkalmazások

Hamilton-kör-probléma általános gráfokon: a ló-lépések gráfjaként a tábla mezői csúcsok, ugrások élek — a túra Hamilton-kör (zárt) vagy Hamilton-út (nyílt).
Routing, robotmozgás: hasonló problémák mobil robotok táblán történő bejárására.
Rekreatív programozás: algoritmusok tanítására és heuristikák összehasonlítására iskolarendszerben.

5. Összefoglaló

A ló-túra probléma egyszerűen megfogalmazható, de algoritmikus szempontból intractable backtracking nélkül. Warnsdorff-féle heurisztika és intelligens visszalépéses (backtracking) keresés együtt hatékonyan képes nagy táblákon is teljes túrát találni, miközben az általános gráf-Hamilton-út probléma NP-nehézsége is tükröződik ebben a speciális esetben.

További információk

knight's tour problem - Szótár.net (en-hu)
knight's tour problem - Sztaki (en-hu)
knight's tour problem - Merriam–Webster
knight's tour problem - Cambridge
knight's tour problem - WordNet
knight's tour problem - Яндекс (en-ru)
knight's tour problem - Google (en-hu)
knight's tour problem - Wikidata
knight's tour problem - Wikipédia (angol)