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
Ftdb
500098
200075
10000

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!

1. A visszalépő keresés

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.

2. A bankautomatában

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.

3. A program

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) {
    int db;

    /* 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? */
    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;
}