Adventi naptár

Visszalépő keresés

A gyakon, a ciklusok és a tömbök magasságában szerepelt egy program, amely egy egyszerű bankautomatát valósít meg. Az automata a megadott összeget úgy próbálja meg kiadni, hogy minél kevesebb bankjegyet használjon közben. Vagyis úgy, hogy a nagyobb címleteket részesíti előnyben:

CIKLUS, AMÍG összeg > 0 ÉS van még címlet
    db = összeg/címlet      (egész osztás, lefelé kerekít)
    HA db > amennyi van
        db = amennyi van
    kiír: "kiadva", db, címlet
    összeg = összeg - db * címlet
    következő iterációban: következő kisebb címlet
CIKLUS VÉGE

HA összeg > 0
    kiír: "nem lehetett kiadni"
FELTÉTEL VÉGE

Ha nincsen végtelen sok bankjegy, akkor ez az algoritmus hibázhat. Tegyük fel, hogy 6000 forintot kell kiadni, és van egy rakat 5000-es, egy rakat 2000-es, de nincs 1000-es (lásd a táblázatot). Ilyenkor a program azt írja ki, hogy egy 5000-est kiad, és utána kiírja, hogy nem tudja kiadni a többit. Pedig megoldható lenne a feladat 3×2000 Ft kiadásával. Többen meg is oldották ezt a feladatot szorgalmiként – nézzük meg, hogyan!

Hogyan javítható a program? Az alábbi ötlettel.

Tegyük fel, hogy kiadtunk egy 5000-est, ezek után kiderül, hogy úgy nem oldható meg a probléma. Vegyük akkor vissza azt az 5000-est, és próbáljuk meg újra úgy, hogy abból nem adunk. Akkor a következő címlet a 2000-es. Abból van bőven, 6000/2000=3, kiadunk hármat, és kész is vagyunk.

Ez az algoritmus mindannyiunk fejében lejátszódhat, csak nem nagyon figyelünk rá. A keresésnek ezt a módszerét úgy nevezik, hogy backtrack (backtracking search), magyarul visszalépő keresés. Megvalósítani ezt is rekurzióval lehet.

FÜGGVÉNY backtrack(részmegoldás)
    HA a részmegoldás teljes, és helyes 1
        kiír: megoldás
        VISSZATÉRÉS a fv-ből.
    FELTÉTEL VÉGE
    HA a részmegoldás nem jó               2
        VISSZATÉRÉS a fv-ből.
    FELTÉTEL VÉGE

    CIKLUS, AMÍG (tippek halmaza)
        backtrack(részmegoldás + tipp)   3
    CIKLUS VÉGE
FÜGGVÉNY VÉGE

A fenti függvény egy általános séma a visszalépő kereséssel megoldható problémák megoldására. Működésének lényege a következő. Paraméterként egy részmegoldást kap, amelyet be kell fejezni. (Részmegoldás természetesen az el sem kezdett megoldás, és a teljes megoldás is.) Először megnézi, hogy a részmegoldás teljes és helyes megoldása-e a feladatnak; 1 ha igen, akkor kiírja azt. Ha a részmegoldáson látszik, hogy nem vezet majd eredményre, 2 akkor nem ír ki semmit, csak visszatér a függvényből.

Ha ezen a két feltételen túljutunk, akkor az azt jelenti, hogy van egy részmegoldásunk, amiről még nem tudjuk, hogy végül lehet-e helyes. Ezért sorba vesszük a tippjeinket, amelyek közelebb vezethetnek a célhoz, és végigpróbáljuk mindegyiket. 3 Ehhez a paraméterként kapott részmegoldást kiegészítjük a tippünkkel, és meghívjuk a függvényt saját magát, hogy ellenőrizze azt, és egészítse ki további lépésekkel (tippekkel), ha kell.

Hogyan adaptálható ez a bankautomatás példára? 6000 forintot kell kiadni. A tipp az, hogy ha adunk egy 5000-est, az eredményre vezethet, hiszen közelebb kerülünk a megoldáshoz (már csak 1000-et kell majd kiadni). Vagyis a backtrack(6000) függvényhívás után lesz egy backtrack(1000) függvényhívás. Ez azonban nem fog eredményre vezetni, mivel nincs 1000-es az automatában. Ezért meg kell próbálnunk úgy, hogy nem adjuk ki az 5000-est. Végülis ennyi az egész.

Annyiban más a helyzet, hogy most nem az összes lehetséges megoldást keressük, hanem a legegyszerűbbet. Pl. nem lényeges, 100000 forint kiadható 100 darab 1000 forintossal, ha van 5 darab 20000-es is. Ha a függvénynek adunk visszatérési értéket is (IGAZ: helyes megoldás, HAMIS: helytelen megoldás), akkor meg tudjuk azt is oldani, hogy a megoldás megtalálása esetén rögtön leálljon a keresés. Ha a preferált megoldásoktól (tippektől) haladunk a kevésbé preferáltak felé, akkor pont a számunkra legkedvezőbbet fogjuk megkapni először.

FÜGGVÉNY fizet(összeg, rekesz)
    HA összeg=0, AKKOR
        VISSZATÉRÉS: sikerült!
    HA nincs több címlet
        VISSZATÉRÉS: ebből nem lesz megoldás.
        
    db=összeg/címlet
    HA db > amennyi van abból a címletből
        db = amennyi van
    FELTÉTEL VÉGE
    
    sikerült = fizet(összeg - db * címlet, következő rekesz) rekurzió
    AMÍG nem sikerült ÉS db >= 0
        db = db - 1
        sikerült = fizet(összeg - db * címlet, következő rekesz)  rekurzió
    CIKLUS VÉGE
    
    HA sikerült ÉS db > 0
        kiír: "kiadva: db, címlet"
        rekeszben bankjegyek = bankjegyek - db
    FELTÉTEL VÉGE
FÜGGVÉNY VÉGE

A visszatérési érték azért is hasznos, mert a függvény meghívása után a legfelső szinten is látjuk, hogy a feladat megoldható-e. Pl. az 5000 forintos kiadása után a „sikerült” változó értéke hamis lesz, ezért nem írunk ki semmit, és az adott rekeszben lévő bankjegyek számát sem csökkentjük le. Ha igazzal tért volna vissza, akkor kiírhatnánk, hogy ki lett adva; a függvény ezen a ponton nem tudja, hogy a fennmaradó pénzösszeg hogyan lett kifizetve, csak azt, hogy az 5000-es kiadása jó tipp volt. A maradék pénz kifizetésének módját a rekurzió lentebbi szintjein már kiírta, ezért itt nem is kell vele foglalkozni.

Egyéb, backtrackkel megoldható problémák:

• Nyolc királynő: hogyan lehet sakktáblán elhelyezni nyolc királynőt úgy, hogy azok ne üssék egymást?
• Sudoku: a legnehezebb sudoku feladványok nem oldhatók meg szisztematikusan, hanem elérkezünk néha egy olyan ponthoz, ahol tippelnünk kell. Ilyenkor tippelünk, és folytatjuk a megoldást; ha a tipp rossz volt, akkor kiradírozunk mindent a tippelés pontjáig visszamenőleg, és mással próbálkozunk.
• Keresztrejtvények (megoldása és kitalálása is).
• Útkereső algoritmusok.

A lenti program kétszer ad ki 6000 forintot. A bankautomatában 1 db 1000-es van, ezért először az 5000+1000 még megoldás, másodjára már nem az, csak a 3×2000. Harmadjára pedig már sehogyan nem lehet kiadni 6000 forintot.

#include <stdio.h>
#include <stdbool.h>

typedef struct {
    int ft;
    int db;
} Rekesz;

bool kifizet(int osszeg, Rekesz rekeszek[], int melyiktol) {
    /* ha nem kell fizetni semmit, akkor sikerult, ki van fizetve. */
    if (osszeg == 0)
        return true;
    /* ha kene meg fizetni, de nincs tobb lehetseges banjegy, akkor nem megy */
    if (rekeszek[melyiktol].ft < 0)
        return false;

    /* kene adni a mostani rekeszbol? mennyit? */
    int db = osszeg / rekeszek[melyiktol].ft;
    if (db > rekeszek[melyiktol].db)
        db = rekeszek[melyiktol].db;

    /* probaljunk meg ennyit adni (es utana tovabb a kovetkezo rekeszre) */
    bool sikerult;
    sikerult = kifizet(osszeg - db * rekeszek[melyiktol].ft, rekeszek, melyiktol + 1);
    while (!sikerult && db > 0) {
        /* ha nem sikerul, probaljuk meg kevesebbel. */
        db--;
        sikerult = kifizet(osszeg - db * rekeszek[melyiktol].ft, rekeszek, melyiktol + 1);
    }

    /* kijottunk a ciklusbol. vagy mert sikerult kifizetni az adott modon,
     * vagy mert nem jo, hogy ebbol a ftbol adni probalunk. */
    if (sikerult && db > 0) {
        printf("  %d db %d Ft-os kiadva\n", db, rekeszek[melyiktol].ft);
        rekeszek[melyiktol].db -= db;
    }

    return sikerult;
}

int main(void) {
    Rekesz rekeszek[] = {
        { 20000, 10 },        /* ft, db */
        { 10000, 8 },
        { 5000, 1 },
        { 2000, 5 },
        { 1000, 1 },          /* 1 db ezres */
        { -1 }                /* tomb veget jeloli */
    };
    int o;
    bool siker;

    o = 6000;
    printf("%d-t adok:\n", o);
    siker = kifizet(o, rekeszek, 0);
    printf("%s\n\n", siker ? "Sikerult!" : "Nem sikerult!");

    printf("%d-t adok:\n", o);
    siker = kifizet(o, rekeszek, 0);
    printf("%s\n\n", siker ? "Sikerult!" : "Nem sikerult!");

    printf("%d-t adok:\n", o);
    siker = kifizet(o, rekeszek, 0);
    printf("%s\n\n", siker ? "Sikerult!" : "Nem sikerult!");

    return 0;
}

Vajon tényleg a legjobb megoldást találjuk meg? Sajnos valójában nem. Az algoritmus még mindig mohó. Csak azt a hibáját javítottuk, amikor a mohóság miatt nem talál megoldást; azt nem, amikor a mohóság miatt nem a legegyszerűbbet találja meg. Tekintsük az alábbi példát (feltéve, hogy érméink is vannak):

Ebben az esetben a 6000-hez a program nem fogja megtalálni a 3×2000-es, legegyszerűbb megoldást. Ez csak 3 bankjegy lenne. Helyette 5000 + 10×100-at fog kiadni, vagyis 1 bankjegyet, és még pluszba 10 darab érmét. A megoldás „legegyszerűbb” olyan értelemben, hogy a lehető legtöbb nagy címletet használja. De olyan értelemben nem, hogy összesen a legkevesebb darabot.