Programming techniques - recursion, exhaustive search

Programmeerimistehnikatest

Rekursioon

Rekursiivne algoritm sisaldab sellesama algoritmi poole pöördumist mingi "lihtsama juhu" jaoks.

Tavaliselt saab eristada rekursiooni baasjuhtu ja sammu - analoogia matemaatilise induktsiooniga.

Vormilt võib rekursioon olla

• otsene:   A ->  A
• kaudne:  A  ->  B  ->  ...  ->  A

Näide. Faktoriaal

0! = 1
n! = n(n-1)!     kui n>0

Rekursiivne definitsioon ei eelda rekursiivset programmi - tavaline tsükkel võib osutuda palju otstarbekamaks.

Automaatne teisendamine "tsükkel - rekursioon"  ja "rekursioon - tsükkel".

Näide. Fibonacci arvud (ebaotstarbekas realiseerida rekursiivse programmina)

f(0) = 0
f(1) = 1
f(n) = f(n-1) + f(n-2)

Rekursioon ei pruugi olla läbinähtav ülesande sõnastuses

Näide. Hanoi tornid
On n erineva läbimõõduga ketast, augud keskel, ning kolm varrat, millele kettaid saab laduda. Igal käigul tohib võtta ühe ketta ning tõsta selle mingile teisele vardale, kuid suuremat ketast ei tohi kunagi asetada väiksema peale. Eesmärgiks on laduda "torn" ainult lubatud käikude abil ühelt vardalt teisele (kolmandat varrast abiks võttes).
Osutub, et ülesanne on eksponentsiaalse ajalise keerukusega ketaste arvu suhtes.

Arutluskäik:
Baasjuht: kui ketaste arv on null, siis ei ole tarvis mitte midagi teha.
Samm: kui oskame laduda k-1 ketast vardalt a vardale b, siis k ketta ladumiseks vardalt x vardale z tuleb:

1. laduda k-1 ketast vardalt x vardale y (võimalik eelduse põhjal)
2. tõsta suurim ketas (k) vardalt x vardale z "põhjaks"
3. laduda needsamad k-1 ketast vardalt y vardale z (võimalik eelduse põhjal)

On oluline, et algseis (ja tegelikult ka mistahes järgnev seis) oleks lubatav.

kood

  public static void hanoi (int n, int x, int y, int z) {
      if (n > 0) {
         hanoi (n-1, x, z, y);
         System.out.print (String.valueOf(x) + ">" + String.valueOf(z) + " "); // t6ste
	 hanoi (n-1, y, x, z);
      }
  }

    

Rekursiooni eemaldamine

Ammendav otsing (variantide läbivaatus)

Teatud ülesannete korral on ainsaks täpseks lahendusmeetodiks "proovimise meetod", s.t. kõigi võimalike lahendusvariantide süstemaatiline läbivaatus (ammendav otsing). Kuna lõplikul n-elemendilisel hulgal on 2^n alamhulka, siis on ammendava otsingu ülesanne üldjuhtumil eksponentsiaalse keerukusega. Konkreetset keerukust saab teatud juhtudel vähendada otsinguruumi ahendamisega.

Kaht liiki ülesanded:

• esimese sobiva lahendi leidmine
• kõigi lahendite leidmine

Variandigeneraator - funktsioon lahendusvariantide süstemaatiliseks genereerimiseks.

Tagasivõtt, backtracking: uue variandi valik antud tasemel, kui kõik alamjuhtumid on ammendatud.

Näide. 8 lippu - kõigi lahendite leidmine.
Paigutada malelauale 8 lippu nii, et ükski neist ei oleks mõne teise lipu tules.






Idee: paigutada lippe järjekorras "vasakult paremale" nii, et n-nda lipu jaoks otsitakse kohta olukorras, kus eelnevad n-1 lippu on nõuetekohaselt paigutatud. Kui sobivat kohta n-ndas veerus ei leidu, siis vähendada n väärtust (backtracking) ning leida järgmine sobiv paigutus "eelmisele" lipule.

Kujutame malelaua seisu ühemõõtmelise massiivina board, mille iga element kodeerib ühe malelaua veeru järgmiselt:
board[j]=0 - veerus j ei ole lippu paigutatud
board[j]=i - veerus j paikneb lipp i-ndas reas (1 <= i <= 8)

Predikaat peaceful(n) : kas lipp number n pole mõne eelneva lipu tules (samal real või diagonaalil, samas veerus ei saa olla juba seisu kujutusviisi tõttu).


kood

   
    /** size of the board */
    private int size;

    /** current state, 0 <= board [i] <= size */
    private int [] board;

    /** Is the queen number k in a peaceful position on the global board
     * @param k number of the queen from the left
     * @return true if the state is peaceful
     */
    public boolean peaceful (int k) {
        if (k >= size)
            throw new RuntimeException ("Wrong index of the queen " + k);
        if (k < 1)
            return true;
        for (int i=0; i < k; i++ ) {
            if (board [i] == board [k])
                return false; // same row
            if (k-i == Math.abs (board [k] - board [i]))
                return false; // same diagonal
        }
        return true;
    }

    /** Solver itself. Places the queens on the global board.
     */
    public void place() {
        int numsol = 0;
        int n = 0;
        do {
            if (board [n] < size) {
                board [n]++;
                if (peaceful (n)) {
                  if (n < size-1) {
                      n++;
                  }
                  else {
                      // solution found
                      numsol++;
                      process();
                  }
                }
            } else {
                board [n] = 0;
                n--;
            }
        } while (n >= 0);
        System.out.println ("Finished with " + numsol + " solutions");
    }
}

Näide. Sudoku lahendamine

Näide. Malelaua katmine ratsukäikudega

Näide. Harud-tõkked. Seljakotiülesanne

Kood

---

J. Pöial