Visszalépő keresés

Czirkos Zoltán · 2019.09.03.

Visszalépő keresés: a híres nyolckirálynő-problémát megoldó program.

Feladat: tegyük egy sakktáblára 8 királynőt úgy, hogy ne üssék egymást!

Húzd az egeret a királynők fölé!

Lőjünk le néhány kérdést előre! Első kérdésünk lehet, hogy van-e megoldás. A válasz: van, de ez a rajzról is kiderül. Húzd az egeret bármelyik királynőre, látszódni fognak a fogott mezők.

Második kérdés pedig, hogy hány megoldás van. Összesen 92, amiből csak 12 lényegesen különböző (a többi forgatással vagy tükrözéssel átvihető egymásba). A készülő programunkban most az összeset megkeressük majd, nem csak a lényegesen különbözőeket; megszámláljuk és ki is rajzoljuk a megoldásokat.

A harmadik kérdésünk az, hogy a feladat általánosítható-e: 9×9-es sakktáblára 9 királynő, vagy 7×7-esre 7 darab. A válasz erre is az, hogy igen. A 2×2-es és 3×3-as esetben nincs megoldás, az összes többi esetben van. A lehetséges megoldások száma igen gyorsan nő a tábla méretével, nagyjából exponenciálisan. 27×27-es táblára

234 907 967 154 122 528

elrendezést találhatunk – lásd a Wikipédia Nyolckirálynő-probléma szócikkét. Ez egyébként a legnagyobb tábla, amire sikerült a megoldások számát meghatároznia egy csapatnak 2016 szeptemberében; nagyobb táblákra a megoldások száma ismeretlen.

1. A mi problémánk

Első megoldási kísérletünk: próbáljuk végig a lehetséges megoldásokat!

Ehhez el kell tárolnunk, hogy melyik királynő hol van. Definiáljunk egy pozíció nevű típust, és hozzuk létre belőle a 8 elemű tömböt!

typedef struct Pozicio {
    int x;
    int y;
} Pozicio;

Pozicio kiralynok[8];
Pozicio kiralynok[8] = {
    {1, 5},
    {7, 6},
    {5, 3},
    /* ... */
};

Hány megoldást kell végigpróbálnunk? Összesen 8×8 = 64 mezőre kell 8 királynőt raknunk. Vagyis 64 mezőből 8-at kell választanunk, ahol lesz királynő, a többi mezőkön nem. Ez ugyanaz a probléma matematikailag, mint a lottósorsolás, ahol 90 számból kell 5 különbözőt választani. A kombinatorikában ezt ismétlés nélküli kombinációnak nevezik. Ezek számát, „64 alatt a 8-at” jópár faktoriális kiszámításával lehet meghatározni:

         64!
C = ──────────── = 4 426 165 368
     8!·(64-8)!

Ha a gépünk százezer állást tud végigpróbálni másodpercenként, akkor is fél napig fog futni a programunk: 100 000 próbálkozás / másodperc → 44 261 másodperc. Ezért másképp kell gondolkodni, még akkor is, ha valójában a mai asztali számítógépek sokkal gyorsabbak ennél (kb. 1–10 millió próbálkozás / másodperc is belefér).

2. Variációk, permutációk

Mivel nem lehet egy sorban két királynő (ütnék egymást vízszintesen), ezért biztosak lehetünk abban, hogy minden sorban pontosan egy királynő lesz (8 sor, 8 királynő).

5
2
4
7
3
8
6
1

Így felesleges a pozíciókat, x és y koordinátákat eltárolni. Lényegében elég csak azt megmondanunk a programunkban, hogy melyik sorban hol van a királynő. És ezt eltárolni is bőven elegendő; egy szimpla int poz[8] tömbre van csak szükségünk. Ha például poz[3] == 7, az azt jelenti, hogy a harmadik sor királynője a hetedik oszlopban van.

int poz[8] = { ... };

Ez a keresőalgoritmust is jelentősen megváltoztatja. Hogyan számítjuk ki így a végigpróbálandó esetek számát? A tömbelemek a 0...7 (1...8) értékeket vehetik fel. Ez 8n lehetőséget jelent, ahol n a tömbelemek száma; az pedig most szintén 8. A kombinatorikában ez az ún. ismétléses variáció. Vagyis így már csak 16,7 millió esetről van szó – az előzőek 260-adrészéről:

V = 88 = 16 777 216

Ez már sokkal inkább vállalhatónak tűnik, de még valamit észre kell vennünk. Kétszer nem szerepelhet ugyanaz a szám a tömbben. Ha kétszer szerepelne ugyanaz a szám, az azt jelentené, hogy két különböző királynő ugyanabban az oszlopban van. Akkor viszont ütnék egymást függőlegesen, ezért ezeket az eseteket is előre kizárhatjuk. Vagyis valójában nem egy ismétléses variációt keresünk, hanem a lenti, 1-8 számokat tartalmazó tömb permutációit:

int poz[8] = { 1, 2, 3, 4, 5, 6, 7, 8 };

Az tehát a kérdésünk, hogy ennek a tömbnek mely keverései, sorbaállításai adják a megoldást.

P = 8! = 40 320 !

A permutációk száma faktoriálissal határozható meg. A 8-elemű tömbünk lehetséges permutációinak száma 40320, vagyis az eredetileg kigondolt 4,4 milliárd megvizsgálandó esetet százezred részére tudtuk csökkenteteni!

Az így kialakított tömbben az ütési helyzetek felismerése is egyszerűbb. Mivel eleve minden sorba csak egy királynőt rakunk (a sor száma a tömbindex), és minden oszlopba is egyet (a tömbelemek egymástól különböző értékek), így már csak az átlós ütéseket kell vizsgálnunk majd, a függőlegeseket és a vízszinteseket nem.

3. Az ütések vizsgálata

Átlós ütés akkor van, ha ugyanannyi sort kell lépni az egyik királynőtől a másikig, mint ahány oszlopot.

  • 45 fokos átlón: Δx = Δy
  • –45 fokos átlón: Δx = –Δy
  • A kettő együtt: |Δx| = |Δy|

Figyelembe kell vennünk, hogy ez mindkét irányú átlón megtörténhet. De ha vesszük az ugrások abszolút értékét (hogy mindegy legyen, fel vagy le, illetve jobbra vagy balra kell menni), akkor egyetlen egy egyenlettel leírhatjuk, mikor van ütközés: ha |x1–x2| = |y1–y2|.

A vizsgálatot ez a függvény fogja végezni:

bool kiralyno_oke(int *poz, int meret) {
    for (int i = 0; i < meret-1; ++i)
        for (int j = i+1; j < meret; ++j)
            if (abs(poz[i] - poz[j]) == abs(i - j))
                return false;
    return true;
}

Az adatszerkezetünkben a tömbindexek a sorok, a tömbértékek pedig az oszlopok. Vagyis ha bármely két tömbelemre igaz az, hogy az indexek különbsége megegyezik az értékek különbségével, akkor ütést találtunk, és az nem megoldás. Ha sehol nincs ilyen, akkor a tömb egy helyes megoldást tartalmaz.

4. A permutációk előállítása

Ha ezek megvannak, a megoldások előállítása a permutációk végigpörgetéséből, és azok vizsgálatából áll.

A permutációk előállítása a gyakorlaton megismert módon történik. A rekurzív algoritmus gondolatmenetét egy négyelemű tömbön szemléltetjük: {1, 2, 3, 4}. Ennek permutációi négy csoportba oszthatóak:

  • {1, x, x, x}, az egyessel,
  • {2, x, x, x}, a kettessel,
  • {3, x, x, x}, a hármassal,
  • és {4, x, x, x}, a négyessel kezdődő permutációk.

Az x-szel jelzett helyeken pedig a többi elem van. A többi elemet szintén sorba lehet rakni különféle módokon. Pl. a {1, x, x, x} esetben ezek a {2, 3, 4}, amelyek lehetséges sorrendezései: {2, 3, 4}, {2, 4, 3}, {3, 2, 4} stb. Ezek pedig előállíthatók rekurzívan, hiszen itt egy háromelemű tömb permutációit keressük.

void kiralyno_keres(int *poz, int meret, int honnan) {
    if (honnan == meret) {
        if (kiralyno_oke(poz, meret))
            kiralyno_kiir(poz, meret);
        return;
    }
    for (int i = honnan; i < meret; ++i) {
        csere(&poz[honnan], &poz[i]);
        kiralyno_keres(poz, meret, honnan+1);
        csere(&poz[honnan], &poz[i]);
    }
}

int main(void) {
    int poz[8] = {1, 2, 3, 4, 5, 6, 7, 8};
    kiralyno_keres(poz, 8, 0);
}

A permutációk előállításának módszere tehát az alábbi:

  • Menjünk végig a tömbön (ezt csinálja a ciklus). Tegyük a tömb minden elemét annak elejére, az eredeti elemet tegyük hátra (első csere).
  • Az így kapott tömbnek a fennmaradó részét permutáljuk (rekurzív hívás).
  • Végül az előrehozott elemet tegyük vissza a helyére (második csere), hogy egy újabb elemet vehessünk majd előre.

A rekurzív hívásban mindig csak a tömb fennmaradó részét kell permutálni, ezért a tömbméret mellett átveszünk egy honnan nevű paramétert is. A cserék innen indulnak, a rekurzív hívásban pedig honnan + 1 lesz a következő paraméter (a fennmaradó rész). Amikor eljutunk a honnan == meret értékig, akkor előállt egy permutáció, tehát ez a báziskritérium. Ekkor megvizsgáljuk a tömböt, és ha megoldása a nyolckirálynő-problémának, kirajzoljuk azt.

Az elkészült program letölthető innen: 8kiralyno_perm.c.

5. Feleslegesen kipróbált megoldások?

1
2
?
?
?
?
?
?

Valójában most is rengeteg feleslegesen kipróbált megoldás van. Tegyük fel, hogy az első királynőt leraktuk az első oszlopba, a másodikat a második oszlopba (mint a rajzon). Ezek biztosan ütik egymást, tehát a maradék hatot hiába próbáljuk meg elhelyezni bárhogyan, helytelen lesz a megoldásunk. A maradék 6 királynő elhelyezésére 6! = 720 lehetőség van, tehát ennyi állás vizsgálatát kihagyhatnánk.

És nem ez az egyetlen ilyen eset. Figyeljük meg az alábbi tömböket! Ezek a megoldáskezdemények mind olyan elhelyezéseket mutatnak, ahol a kérdőjelek helyére bármi is kerül, biztosan rossz a megoldás.

int poz[8] = {1, 2, ???};
int poz[8] = {3, 2, ???};
int poz[8] = {1, ?, 3, ???};
int poz[8] = {6, ?, 4, ???};

Tehát a nyolckirálynő-problémában:

  • Részmegoldások vizsgálhatók (első n sor).
  • Ezek vizsgálatával sok lehetőség kizárható.

Vannak olyan feladatok, ahol egy lehetséges megoldást egyben kell látnunk, és csak akkor tudjuk eldönteni, hogy helyes-e. A nyolckirálynő-probléma azonban nem ilyen. Itt egy részmegoldást is tudunk vizsgálni. Vagyis egy még nem teljesen kitöltött táblára kétféle állítást tehetünk:

  1. ez még lehet jó, próbáljuk meg kitölteni az alját,
  2. ez már biztosan nem lesz jó.

Vagyis hasznos megvizsgálnunk a részmegoldást is, mert az ki fog zárni egy csomó esetet.

6. Nyolckirálynő-probléma: új algoritmus

Írjuk át a fentiek alapján az algoritmust!

Az algoritmus működése:

  • Tekintsük a következő üres sort.
  • Próbáljuk végig az összes oszlopot a sorban.
    • Tegyük a táblára a királynőt.
    • Ha üti az eddigieket, vegyük le.
    • Ha nem üti, akkor viszont:
      • Próbáljuk elhelyezni a többit.
      • Végül vegyük le, hogy a megadott sorban a többi oszlopot is kipróbálhassuk.
  • Ha közben megtelik a tábla, megoldást találtunk.

A kiemelt műveleteket („ha üti, vegyük le”) nevezzük visszalépésnek, ezért az algoritmus neve: visszalépő keresés (backtracking search).

7. Az ütések vizsgálata: csak az n-edik

Az új algoritmushoz egy egyszerűbb tesztelőfüggvény tartozik, mint az előzőhöz. Mivel most egyesével rakjuk majd a királynőket, mindig csak a legutóbbit kell megnézni, hogy jó-e, nem üti-e a többit. Az összes előzőre nem figyelünk: úgy jutunk mindig ide, hogy azok már ellenőrizve vannak. A függvény paramétere a tömb mellett a sornak a száma, amelyik királynőt ellenőrizni kell.

Ütésben vannak, ha

  • Azonos oszlopban vannak: x1 = x2
  • Azonos átlón vannak: |dx| = |dy|
bool kiralyno_nedik_oke(int *poz, int n) {
    for (int i = 0; i < n; ++i) {
        if (poz[i] == poz[n]
            || abs(poz[i] - poz[n]) == abs(i - n))
            return false;
    }
    return true;
}

Ügyelni kell arra, hogy most nem csak az átlót kell vizsgálni, hanem azt is, hogy az új királynő nem került-e valamelyikkel azonos oszlopba: poz[i] == poz[n]. A tömbbe ugyanis most nem permutációk kerülnek, hanem minden sorban végigpróbáljuk az összes oszlopot, és oszlopok szerinti ütés is előfordulhat. De ez csak egy újabb feltétel; az algoritmus még így is egyszerűbb, egyetlen egy ciklus vizsgálja az új királynő sora előtti sorokat.

8. Algoritmus visszalépő kereséssel (félkész)

Az alábbi függvény valósítja meg a visszalépő keresést a probléma megoldására. Ez nem a klasszikus megvalósítás, még később finomítjuk majd, de előbb lássuk a működését!

void kiralyno_keres(int *poz, int meret, int n) {
    if (n == meret) {
        kiralyno_kiir(poz, meret);
        return;
    }
    for (int uj = 1; uj <= meret; ++uj) {
        poz[n] = uj;
        if (!kiralyno_nedik_oke(poz, n)) {
            poz[n] = 0;    // visszalépés
            continue;
        }
        kiralyno_keres(poz, meret, n+1);
        poz[n] = 0;
    }
}

A függvénynek most is paramétere a kitöltendő tömb mérete. Paramétere továbbá az n, amely azt mutatja, hogy épp hányadik sorban fogunk megoldást keresni.

A ciklus az, amely az adott sorban megpróbálja elhelyezni az új királynőt. Ez végigpróbálja 1-től 8-ig a lehetséges értékeket, amelyek abba a tömbelembe kerülhetnek, vagyis a lehetséges oszlopokat. Az a hipotézis, hogy az új oszlop a királynő számára jó lesz, ezért be is teszi oda: poz[n] = uj. Utána pedig megnézi, hogy a hipotézis jó-e. A kiralyno_nedik_oke() függvénynek ezt az egy új királynőt kell néznie, mivel az összes eddigi biztosan nem üti egymást. Ha kiderül, hogy ez ütésben van az eddigiekkel, akkor kiveszi a tömbből, és próbálkozik tovább. Ha rendben van, akkor pedig a rekurzív hívással megpróbálja elhelyezni a többit.

Valójában egyébként a poz[n] = 0 értékadások feleslegesek, csak az érthetőség kedvéért szerepelnek. Egyrészt mert a következő iteráció úgyis felülírja azt az elemet, másrészt pedig a vizsgáló függvény úgyis csak az első n elemmel foglalkozik – tehát ha nem írjuk felül újra 0-val az adott elemet, az sem baj.

9. Permutáló algoritmus visszalépéssel

Az előbbi magyarázatban a visszalépő keresés tisztázása kedvéért szerepelt egy egyszerűsítés: ismétléses variációkat vizsgáltunk, nem pedig permutációkat. Vagyis nem az {1, 2, 3, 4, 5, 6, 7, 8} tömböt permutáltuk, hanem minden sorban az összes oszlopba próbáltunk királynőt tenni.

Valójában a permutációkat előállító algoritmus beilleszthető a visszalépő keresésbe. Vegyük szemügyre csak a permutációkat előállító kódot egy pillanatra! Ez így fest:

void permutacio(int *poz, int meret, int n) {
    if (n == meret)
        return;

    for (int i = n; i < meret; ++i) {
        csere(&poz[n], &poz[i]);
        permutacio(poz, meret, n+1);
        csere(&poz[n], &poz[i]);
    }
}

Ebben a cserékkel minden tömbelem előre jön, utána a rekurzióban csak a tömb fennmaradó részét permutáljuk. A nyolckirálynő-probléma és a visszalépő keresés esetében ez éppen jó nekünk: a cserével előre hozott szám (oszlop index) lesz a vizsgálandó elem a báziskritériumban. Ha az rendben van, akkor a tömb végét permutáljuk utána csak, vagyis csak ott rendezgetjük a királynőket; az eddig elhelyezettek közötti ütközéseket azok már nem fogják módosítani.

void kiralyno_keres(int *poz, int meret, int n) {
    if (!kiralyno_nedik_oke(poz, n-1)) {   // !
        return;
    }
    if (n == meret) {
        kiralyno_kiir(poz, meret);
        return;
    }
    
    for (int i = n; i < meret; ++i) {
        csere(&poz[n], &poz[i]);
        kiralyno_keres(poz, meret, n+1);
        csere(&poz[n], &poz[i]);
    }
}

A végleges megoldásunk így fest. Valójában ez alig különbözik az első, permutáló megoldástól. Az egyetlen különbség abban rejlik, hogy ez részmegoldásokat is megvizsgál, és azokat nagyon hamar visszautasítja, ha nem jók. Ezt mutatja a jelölt rész. A teljes program letölthető innen: 8kiralyno_bt_perm.c.

10. Hatékonyság: permutáló és visszalépő

Az alábbi táblázat azt mutatja, hogy táblaméret függvényében hány pályaállást kell megvizsgálni akkor, ha a permutáló módszert, illetve a visszalépő keresést alkalmazzuk a probléma megoldására.

méretpermutációvalvisszalépővelgyorsulás
84032055097,3×
93628802401215,1×
10362880011000533,0×
113991680054635873,1×
124790016002915741164,3×
13622702080016469570378,1×
148717829120099280505878,1×

Látható, hogy a visszalépő keresés sokkal gyorsabb; a hibás részmegoldások (és azok befejezéseinek) eliminálásával a gyorsulás a táblamérettel meredeken nő. 14×14-es tábla megoldásainak keresésekor már majdnem 900-ad részére csökken a megvizsgált esetek száma.

Ez az algoritmus azért is sokkal gyorsabb, mert az egyes esetek vizsgálata egyszerűbb. Míg a permutáló algoritmusnál teljes játékállásokat kellett vizsgálni (minden királynőt mindegyikkel párba állítva), itt egy hipotézis vizsgálatához elég csak az újonnan felrakottat figyelembe venni. Egy i5-8250U processzorral rendelkező gépen a 14×14-es pályára a megoldások megkeresése mindössze 1,6 másodpercig tart.

11. A visszalépő keresés általános alakja

Lent látható a visszalépő keresés általános megfogalmazása pszeudokód formájában. Ez annyiban különbözik az előbb látott nyolckirálynő-megoldótól, hogy itt a hipotézis helyességének a vizsgálata is báziskritériumként szerepel. Vagyis a ciklus feltétel nélkül elindítja a rekurziót a kiegészített megoldás vizsgálatára; aztán a rekurzív hívás dönti el, hogy elfogadja vagy visszautasítja azt a megoldást, amit éppen lát.

függvény: visszalépő_keresés(megoldás)

    ha a (rész)megoldás hibás báziskritériumok
        vissza
    ha megoldás teljes (és elfogadható)
        kiírás
        vissza

    ciklus a következő részmegoldásokkal egyszerűsítés
        megoldás kiegészítése
        visszalépő_keresés(megoldás)

12. Visszalépő keresés: csak egy megoldás

A fenti algoritmus az összes megoldást kilistázza. De a visszalépő keresés könnyedén módosítható olyan feladatok megoldására, ahol csak egy megoldást keresünk, vagy esetleg meg akarunk állni az első egynéhány megoldás megtalálása után.

Ha egy megoldás keresése a feladat, akkor ahhoz bevezetünk a függvénynek egy visszatérési értéket. Ez fogja azt mutatni, sikerült-e megoldást találni vagy nem.

bool kiralyno_keres(int *poz, int meret, int n) {
    if (!kiralyno_nedik_oke(poz, n-1))
        return false;
    if (n == meret)
        return true;

    for (int i = n; i < meret; ++i) {
        csere(&poz[n], &poz[i]);
        if (kiralyno_keres(poz, meret, n+1))
            return true;
        csere(&poz[n], &poz[i]);
    }
    return false;
}
int poz[8] = {1, 2, 3, 4, 5, 6, 7, 8};
bool talalt = kiralyno_keres(poz, 8, 0);
if (talalt)
    kiralyno_kiir(poz, 8);

Ha true értéket kapunk a függvényből, akkor sikerült egy megoldást találni, és azt betette a tömbbe. Ha false, akkor nem volt megoldás, és a tömbben nincs hasznos adat.

A függvény belsejében elő kell állítani ezt az értéket. Egyrészt a báziskritériumoknál: ha rossz helyre került a királynő, akkor false, ha tele a tábla, akkor jó helyen vannak, és true.

Másrészt pedig magában a keresésben. A leglényegesebb rész az, ahol a rekurzív hívás van. Ha az igazzal tér vissza, azt azt jelenti, hogy a tömb egy teljes megoldást tartalmaz; ilyenkor a hívó is visszatér igazzal. Ez az, ami megszakítja a keresést az első megoldás megtalálása után, ugyanis ilyenkor megáll egyrészt a ciklus is, másrészt pedig a rekurzív hívók is mind igazzal fognak visszatérni. A függvény legalján hamis értékkel kell visszatérni. Ugyanis ha lefutott a ciklus teljes egészében, az azt jelenti, hogy a szóba jövő oszlopok közül egyik se vezetett megoldáshoz.

Így működik a rekurzió kapcsán bemutatott labirintus megoldó is. Ott tudjuk előre, hogy egyetlen egy megoldás van, és azt kell megtalálni; zsákutca esetén pedig visszajönni.

13. Visszalépő keresés: alkalmazások

A visszalépő keresés alkalmazásai:

  • Rejtvények: nyolc királynő, sudoku, keresztrejtvény, labirintus
  • Nyelvi elemzés (fordítóban)
  • Optimalizálási feladatok, pl. hátizsák-probléma, pénzosztás

Lássunk néhány példát a visszalépő keresés alkalmazására!

Nyelvi elemzés. A fordítóprogramnak a megkapott forráskódot elemeznie kell, és az elemzés közben könnyen zsákutcába futhat. Például az x = (double) y; kifejezés értelmezésekor rá kell jönnie, hogy a zárójel mit jelent. Ha elindul abba az irányba, hogy precedenciamódosító zárójelet feltételez (mint pl. az 5 + (2*3) kifejezésben), akkor ellentmondásra jut, mert a zárójelben nem kifejezés van. Ezért visszalép, és megpróbálkozik mással: cast operátornak feltételezve a zárójelet, kiderül hogy a teljes kifejezés értelmezhető.

Optimalizálási feladatok. Ezek közül a legismertebb a hátizsák-probléma, amit a rajz is szemléltet. Adott egy hátizsák, amelynek a teherbírása véges. Adott egy csomó tárgy, amelyeknek ismerjük az értékét és a súlyát. Kérdés, mely tárgyakat kell kiválasztanunk, hogy a legnagyobb összértéket állítsuk össze, figyelembe véve a hátizsák teherbírását. A rajz példáját tekintve, a két legértékesebb tárggyal 10+4 = 14 dolláros csomagot állíthatnánk össze, ezeknek a súlya azonban 12+4 = 16 kg, ami túllépi a limitet. Valamelyiket el kell hagynunk, és könnyebbet keresni helyette.

Szintén visszalépő kereséssel oldható meg helyesen egy bankautomata feladata is, amelynek ki kell adnia egy adott összeget, figyelembe véve, hogy milyen címletekből mennyi áll rendelkezésre. Ha a bankautomata rekeszei ezeket a bankjegyeket tartalmazzák:

címletdarabszám
5000137
2000275
10000

Akkor egy mohó algoritmus, amely a legnagyobb címletekkel próbálkozik, a 6000 forint kifizetéséhez nem tudna megoldást találni. Elakadna ott, hogy ad egy 5000-est, és utána 1000-esből meg nincsen. Viszont ezen a ponton visszalépve, úgy döntve, hogy mégsem ad ki 5000-est, rájöhet, hogy a 3×2000 megoldása a feladatnak.