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

kood

def fact(k):
    if k < 1:
        return 1
    else:
        return k*fact(k-1)

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

  def hanoi(k, x, y, z):
    if k < 1:
        return
    else:
        hanoi(k-1, x, z, y)
        print(x, '->', z, end='; ')
        hanoi(k-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 not_peaceful(k) : kas lipp number k on mõne eelneva lipu tules (samal real või diagonaalil, samas veerus ei saa olla juba seisu kujutusviisi tõttu).


kood

SIZE = 8
board = [0]*SIZE


def not_peaceful(k):
    if k < 1:
        return False
    for i in range(k):
        if board[i] == board[k]:
            return True
        if k-i == abs(board[k]-board[i]):
            return True
    return False


def main():
    num_sol = 0
    n = 0
    while n >= 0:
        if board[n] < SIZE:
            board[n] += 1
            if not_peaceful(n):
                continue
            if n < SIZE-1:
                n += 1
                continue
            else:
                num_sol = num_sol + 1
                print(str(board))
                if board[0] == 2 and board[SIZE-1] == 1:  # and board[SIZE-2] == 3:
                    print("Special: ", board)
        else:
            board[n] = 0
            n -= 1
    print("Number of solutions: ", str(num_sol))

Näide (Java). Sudoku lahendamine

Näide (Java). Malelaua katmine ratsukäikudega

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

Kood (Java)

---

J. Pöial