Generikus algoritmusok, visszalépő keresés

Pointer, mint fura lokális változó

ListaElem *iter;
iter = (ListaElem*) malloc(sizeof(ListaElem)); // ?!
for (iter = lista; iter != NULL; iter = iter->kov) {
    ...;
}
free(iter);

Adatszerkezetek, azok jellegzetes műveleteinek keverése

Láncolt lista eleje pointer megindexelése...
tömbön mozgo = mozgo->kov...
és hasonlók.

Nem elvi hiba, de...

strlen, strcpy, strcmp és printf %s.

Generikus algoritmusok

Írjunk programot, amelyben menüből választhatjuk ki a teendőt!

1. Összeadás
2. Szorzás
3. Hatványozás
0. Kilépés
Melyik? _

printf("1. Összeadás\n"); // 1. sorminta
printf("2. Szorzás\n");
printf("3. Hatványozás\n");
printf("0. Kilépés\n");
scanf("%u", &valasztas);

if (valasztas < 4) {
    switch (valasztas) {
        case 1: eredm = osszead(a, b); break; // 2. sorminta
        case 2: eredm = szoroz(a, b); break;
        case 3: eredm = hatvanyoz(a, b); break;
    }
    printf("E = %d\n", eredm);
}

A függvényhívás menetéről már volt szó régebben. Ismétlésként foglaljuk ezt össze!

#include <stdio.h>
#include <math.h>

double negyzet(double a) {
    return a * a;
}

int main(void) {
    double x = negyzet(5.9);
    double y = sin(6.1);

    printf("%g", x + y);
    return 0;
}

Ha két függvénynek egyforma a fejléce, akkor egyformán kezelik a vermet, és ezért kompatibilisek egymással.

double negyzet(double a);

double sin(double alfa);

int main(void) {
  double (*fptr)(double);   // ptr létrehozása
  double x;

  fptr = negyzet;           // ptr beállítása
  x = fptr(3);  /* negyzet(3) */

  fptr = sin;
  x = fptr(5);  /* sin(5) */

  return 0;
}

double (*fptr)(double);

Hogyan definiálunk egy függvényre mutató pointert?

Függvényre mutató pointer típusú változó:

VisszaTíp (*változónév)(ParamTíp, /*...*/);

double (*fptr)(double);
fptr = sin;

Hogyan segít ebben a typedef?

A típust a typedef is megadhatja:

Emlékezzünk vissza: a typedef után írt dolog szintaxisa tökéletesen megegyezik a változódeklaráció szintaxisával. Tehát ha típusként szeretnénk definiálni egy függvényre mutató pointert, ugyanazt kell csinálnunk, mint a változóknál, csak a sor elejére még a typedef kulcsszó is odakerül. A fenti példában az EgyvaltozosFvPtr nevű típus lett definiálva függvénypointerként.

typedef VisszaTíp (*ÚjTípusNév)(ParamTíp, /*...*/);

typedef double (*EgyvaltozosFvPtr)(double);
EgyvaltozosFvPtr f;
f = sin;

typedef double EgyvaltozosFv(double);
typedef EgyvaltozosFv *EgyvaltozosFvPtr;

double f(double);

double * f(double);

typedef void (*sighandler_t)(int);
sighandler_t signal(int signum, sighandler_t handler);

void (*signal(int signum, void (*handler)(int)))(int);

A menüpontok függvényei:

int osszead(int a, int b) {
  return a + b;
}

int szoroz(int a, int b) {
  return a * b;
}

int hatvanyoz(int a, int b) {
  int eredmeny = 1;
  for (int i = 0; i < b; ++i)
    eredmeny *= a;
  
  return eredmeny;
}

Vagyis minden függvény megkap két számot és elvégez rajtuk egy műveletet, aminek az eredményét a visszatérési értékben közli.

Ezekre a függvényekre egy ilyen pointer tud mutatni:

typedef int (*MatFv)(int, int);

typedef int (*MatFv)(int,int);

typedef struct {
    char const *nev;
    MatFv pfv;
} MenuPont;

MenuPont menupontok[] = {
  {"Összeadás", osszead},
  {"Szorzás", szoroz},
  {"Hatványozás", hatvanyoz},
  {NULL, NULL}   /* végjel */
};

Mivel mutatókat tárolnak, ezért utolsó elemnek betehető egy NULL érték, ami jelzi a végét – így biztonságosan kezelhető. Ez egy végjel: amikor egy ciklus fut a tömbön, a tömb tartalma alapján tudni fogja, hol van a vége. Nem kell majd külön szerepelnie a programban a tömbméret megadásának sem. Ezt a trükköt már rengetegszer használtuk.

A menüpontok kiírása:

for (i = 1; menupontok[i-1].nev != NULL; ++i)
    printf("%d. %s\n", i, menupontok[i-1].nev);
meret = i;

A for ciklus indexváltozójának utolsó értéke a NULL elem indexe, vagyis a tömbben lévő értékes elemek száma. Ezzel az értékkel tudjuk ellenőrizni, hogy a felhasználó által bevitt menüpont értéke érvényes-e.

A kiválasztott menüpont végrehajtása:

if (val >= 1 && val <= meret) {
    eredmeny = menupontok[val-1].pfv(a, b); // fv pointer
    printf("Eredmény: %d\n", eredmeny);
} else {
    printf("Nincs ilyen menüpont\n");
}

int szamlal(long *tomb, int n, bool (*pred)(long)) {
    int db = 0;
    for (int i = 0; i < n; ++i)
        if (pred(tomb[i]))     // adott tulajdonságú?
            ++db;
    return db;
}

A program forráskódja is így nagyon szemléletes. Akárhány függvényt írhatunk, amelyek tulajdonságokat vizsgálnak. Ezek a predikátumok:

bool negativ(long x) {
    return x < 0;
}

bool paros(long x) {
    return x % 2 == 0;
}

A függvényeket pedig egyszerűen paraméterként átadjuk:

long tomb[10] = { ……… };
printf("%d negativ van.\n", szamlal(tomb, 10, negativ));
printf("%d   paros van.\n", szamlal(tomb, 10, paros));

A függvény tehát paraméterként kapja a vizsgálandó számsort, továbbá egy másik függvényt, a predikátumot. Ezt a függvényt meghívja minden elemre – ez a függvény mondja meg, hogy az adott elemeket bele kell-e épp számolni, vagy nem. Hogy épp a negatív számok esetén növeljük a számlálót, vagy a páros számok esetén.

A rendezőalgoritmusokat is meg tudjuk fogalmazni generikusan. Ott ugyanez a helyzet, mint a számlálásnál vagy a keresésnél. Az algoritmus maga ugyanaz, csak az változik, hogy melyik tömbelem kisebb, melyik nagyobb – egész pontosan, hogy melyik való a tömb elejére, és melyik a végére, mert kisebbről és nagyobbról itt már nem beszélhetünk.

void rendez(double *t, int n, bool (*p)(double, double)) {
    for (int i = 0; i < n-1; ++i) {
        int leg = i;
        for (int j = i+1; j < n; ++j)
            if (p(t[j], t[leg]))  // !
                leg = j;
        if (i != leg)
            csere(&t[i], &t[leg]);
    }
}

A függvénynek adott predikátum most nem egy-, hanem kétparaméterű. Ugyanis nem egy elemről kell megmondania, hogy rendelkezik-e valamilyen tulajdonsággal, hanem két elemet kell összehasonlítania; előrébb való-e az egyik a rendezett tömbben, mint a másik. Ha a kisebb elemekre mondjuk azt, hogy előrébb való, akkor növekvő sorrendet kapunk. Ha a nagyobb elemek kerülnek előre, akkor csökkenő lesz a sorrend.

bool kisebb(double a, double b) {
    return a < b;
}

bool nagyobb(double a, double b) {
    return a > b;
}

Az előző pont egyparaméterű predikátumait unáris predikátumnak nevezzük (unary predicate). Az összehasonlító, kétparaméterű predikátumokat pedig binárisnak (binary predicate).

A tevékenység egy függvény:

typedef struct AllapotPont {
    Allapot kovetkezo;
    void (*tevekenyseg)(void);
} AllapotPont;

Az állapotgépet kezelő program:

Esemeny esemeny;
Allapot allapot;

while ((esemeny = uj_esemenyre_var()) != -1) {
    tabla[allapot][esemeny].tevekenyseg();
    allapot = tabla[allapot][esemeny].kovetkezo;
}

Vagyis két dolgot csinálunk egy esemény hatására: elvégezzük az állapottól és az eseménytől függő tevékenységet, majd ugrunk az állapottól és tevékenységtől függő, következő állapotba. Ennyi, és ez minden állapotgépnél így van. Hogy konkrétan mi történik, az az állapot- és tevékenységtáblától függ, már nem az itteni kódtól.

Hogy ne legyen túl sok állapotunk, általában véve a tevékenységeket érdemes paraméterezni. Például a tevékenységnek paramétere lehet az aktuálisan beolvasott karakter, vagy egy kiírandó szöveg is. Így egyszerűsödhet az állapotgép.

Generikus algoritmusok tömbökön

A rendezés megvalósítására a C szabványos könyvtára tartalmaz egy qsort() nevű generikus algoritmust. Ennek az összehasonlítás kritériuma, azaz a rendezési reláció megadható. Ha sztringeket szeretnénk rendezni, könnyű a dolgunk: a szintén szabványos strcmp() függvény lehet a paraméter:

alma barack korte szilva

char szavak[4][20] = {
    "barack",
    "alma",
    "szilva",
    "korte",
};

qsort(szavak, 4, 20, strcmp);   // db = 4, meret = 20
for (int i = 0; i < 4; ++i)
    printf("%s ", szavak[i]);

Vegyük észre, hogy itt a függvénynek két paramétert is kell adni a tömbhöz. Egyrészt tudnia kell, hány eleme van (hány sztringet kell sorbaraknia). Ez itt db = 4. Másrészt pedig azt is látnia kell, hogy egy elem mekkora, vagyis hogy hány karakterből álló sztringeket kell cserélgetni. Ez meg meret = 20. (A fenti kód a qsort-nak átadott strcmp-re warningot ad, de jól működik.)

Tehát „mindkét irányban” változhat a méret, az elemszám és a sztringek hossza is tetszőleges. A qsort() paramétere ezért nem két dimenziós tömbre mutató pointer (amelybe bele kellene írni a tömb méretét is, pl. int (*p)[20]), hanem inkább egy void *. A void *-ként átadott mutatót lehetne (void*) szavak formában írni, kiemelve azt, hogy ott egy mutató konvertálásról van szó, de ezt nem szokás megtenni. A pointerek konverziója void *-ra, típus nélküli pointerre a C nyelvben automatikus, éppen ezek miatt az algoritmusok miatt.

A qsort() negyedik paramétere az összehasonlító függvény, amelyet meg fogja hívni minden elempárra, amit a rendezés közben össze kell hasonlítania.

A void * technika olyan hasznos, hogy a C könyvtár is alkalmazza:

/* dinamikus memóriakezelés */
void *malloc(size_t meret);
free(void *ptr);

/* fájlkezelés */
fwrite(void const *ptr, size_t meret, size_t db, FILE *fp);
fread(void *ptr, size_t meret, size_t db, FILE *fp);

/* gyorsrendezés, bináris keresés */
void qsort(void *tomb, size_t db, size_t meret,
           int (*hasonlit)(void const *, void const *));
void *bsearch(void const *kulcs, void const *tomb,
              size_t db, size_t meret,
              int (*hasonlit)(void const *, void const *));

int hason_sztring(void const *a, void const *b){
    return strcmp( (char const *)a, (char const *)b);
}

qsort(szavak, 4, 20, hason_sztring);   // már nincs warning

Látjuk, hogy ez az ötlet végigvonul mindenhol. Az fread() és fwrite() megkapják a tömbök elemszámát, és az egyes elemek méretét. A gyorsrendezést és bináris keresést végző függvény szintén. Sőt még a malloc()–free() páros is ilyen volt. A malloc() megkapja a foglalandó terület méretét bájtban, és void*-ot ad vissza; a free() is void*-ot vár. Egyik függvénynek sem kell tudnia, hogy tulajdonképp milyen típusú adattal dolgoznak.

A qsort() valójában nem foglalkozik vele, nem is tudja, hogy milyen típusú elemeket rendez. Az egyes elemeket meg tudja cserélni enélkül is (nyers adatot másol, mindig annyi bájtot, amennyi egy elem mérete). Az összehasonlítást pedig a paraméterként átvett függvényre bízza. Ennek a függvénynek a visszatérési értéke pont olyan kell legyen, mint ahogy azt a szabványos strcmp() is használja:

hasonlit(a, b) =
    negatív: ha a < b
      nulla: ha a == b
    pozitív: ha a > b

Vegyük észre, hogy ez egy kicsit más, mint a fentebb bemutatott bináris predikátum. Az igazzal tért vissza, ha a < b. Ez viszont egy int-et ad, aminek három leheséges értéke van, és azok a kisebb, egyenlő, nagyobb eseteket reprezentálják.

Például egy hasonlító függvény double típusú elemekre az alábbiak szerint implementálható. Figyelni kell arra, hogy mivel nem tudja a qsort(), hogy milyen adatokkal dolgozik, ezért a hasonlító függvénynek is void * típusú pointereket ad a két összehasonlítandó elemre. Egész pontosan void const *-ot, hiszen az összehasonlító függvénynek értelemszerűen nem dolga, hogy módosítsa az adatot.

Ezt a void * típusú pointert át kell konvertálnunk a saját típusunkra. De mivel tudjuk, hogy ezt a függvényt double elemeket tartalmazó tömb esetén adjuk majd a qsort()-nak, a konverzió jogos és helyes:

int hasonlit(void const *vp1, void const *vp2) {
    double const *sz1 = (double const *) vp1;
    double const *sz2 = (double const *) vp2;
    if (*sz1 > *sz2) return +1;
    if (*sz1 < *sz2) return -1;
    return 0;
}

double szamok[4] = {9.7, 3.4, 8.5, 1.2};
qsort(szamok, 4, sizeof(double), hasonlit);
for (int i = 0; i < 4; ++i)
    printf("%g ", szamok[i]);

Így tulajdonképpen a függvény bármilyen elemekből álló tömböt rendezni tud. Az egyes elemek méretét most a sizeof(double) adja meg. Vagy egyszerűen oda sizeof(szamok[0])-t is írhatnánk. (Egyébként az előző példában is a 20 * sizeof(char) lett volna teljesen korrekt.)

int t[] = {23, 119, 47, -2, 54, 86};

/* bináris keresés csak rendezett tömbökön */
qsort(t, 6, sizeof(int), hasonlit_int);

int minta = 47;
int *talalt;
talalt = (int *) bsearch(&minta, t, 6, sizeof(int), hasonlit_int);

if (talalt != NULL)
    printf("Megtaláltam, itt van: %p\n", talalt);
else
    printf("Nincs a tömbben.\n");

Vajon lehet olyan függvényt írni, ami bármilyen tömbön működik?

double szamok[4] = {9.7, 3.4, 8.5, 1.2};
void *ptomb = (void *) szamok;       // így kapja a függvény :(

Egy char* típusú mutatót használva bájtonként lépkedhetünk:

char *pbyte = (char *) ptomb;        // sizeof(char) = 1 miatt
for (int i = 0; i < 4; ++i) {          
    double *elem = (double *) pbyte; // újra double
    printf("%g ", *elem);              
    pbyte += sizeof(double);         // hány bájtot ugrunk?
}

Ahhoz, hogy a mutató aritmetika működjön, a mutatót típussal kell ellátni, hiszen ilyenkor az adott típus méretével szorozzuk a lépések számát. Ha char * típusúvá alakítjuk a pointert, akkor bájtonként tudunk lépni, mivel definíció szerint sizeof(char) = 1. Mivel ilyenkor a lépések bájtonként értendők, az elem címének kiszámításakor nem azt kell megadnunk, hogy hányadik valós számra, hanem hogy hányadik bájtra ugrunk. Ezért a ciklusban a mutatónkat nem egyesével, hanem sizeof(double) lépésekkel léptetjük: annyi bájtot kell mindig előremenni, ahány bájtból egy double áll. Az így kapott pointert pedig bátran visszakonvertálhatjuk double *-gá.

Egyes fordítók megengedik azt, hogy void * mutatókon használjunk pointer aritmetikát, de ez nem szabványos, úgyhogy inkább kerüljük az ilyesmit!

A probléma tehát megoldható, mégpedig úgy, ha egy generikus tömböt feldolgozó algoritmusnak nem csak a tömb kezdőcímét (most void * formában!) és a tömb méretét adjuk át, hanem megmondjuk neki az egyes tömbelemek méretét is! Erre nincsen trükkös megoldás, egyszerűen közölni kell ezt a számot is az algoritmussal.

Egy függvény így lépdelhet végig egy void * tömbön:

void for_each_tomb(void *t, int db, size_t meret,
                   void (*muvelet)(void *))
{
    char *pbyte = (char *) t;  // sizeof(char) = 1 miatt
    for (int i = 0; i < db; ++i)
        muvelet((void *) (pbyte + i * meret));
}

Tehát ebben a char * csak azért szerepel, mert tudjuk, hogy sizeof(char) = 1, és a pointer aritmetika esetén bájtokkal dolgozunk.

A for_each_tomb() használata egy tömb minden elemének a kiírására:

void kiir_int(void *vp) {
    printf("%d ", *(int *) vp);
}

int tomb[] = { 68, 12, 125, 97, 56 };
for_each_tomb(tomb, 5, sizeof(int), kiir_int);

Visszalépő keresés (backtrack)

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

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

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?

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)!

100 000 próbálkozás / másodperc → 44 261 másodperc → fél nap.

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. Ezért másképp kell okoskodni, 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).

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ő). Tehát 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.

Észrevehetjük, hogy minden sorban pontosan egy királynő lesz:

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

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 8ⁿ 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ó.

V = 88 = 16 777 216

Vagyis 16,7 millió esetről van szó – az előzőek 260-adrészéről. 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:

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

Ha a tömbben 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 kizárhatjuk. Vagyis valójában nem egy ismétléses variációt keresünk, hanem a fenti, 1-8 számokat tartalmazó tömb permutációit. 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! Ha ez még nem lenne elég, az így kialakított tömbben az ütési helyzetek vizsgálata 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ékei), így már csak az átlós ütéseket kell vizsgálnunk majd, a függőlegeseket és a vízszinteseket nem.

Ütésben vannak, ha

Tehát csak az átlós ütésekkel kell foglalkozni. Á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.

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);
}

Valójában most is rengeteg feleslegesen kipróbált megoldás van:

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

A permutációs módszerrel rengeteg állást megvizsgáltunk hiábavalóan. Például 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 kihagyhattuk volna. És nem ez az egyetlen ilyen eset; a fenti tömbkezdemények mind olyan elhelyezéseket mutatnak, ahol a kérdőjelek helyére bármi is kerül, biztosan rossz a megoldás.

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 feladványok, 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, a) ez még lehet jó, próbáljuk meg kitölteni az alját, b) 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.

start következő folyamatos

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.

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;
    }
}

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]);
    }
}

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 néz ki. 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.

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.

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)

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);

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