Iti0210lab42

Sissejuhatus

Lahendame õpiku mänguülesande, kus tuleb malelauale paigutada lipud nii, et ükski teist ei saaks "ära lüüa" - see tähendab, et üheski reas, veerus ega diagonaalil ei tohi olla üle ühe lipu. Seda ülesannet on võimalik lahendada ka mängulaual, mis on tavalisest malelauast erineva suurusega - alates 4x4 ruudust, kuhu tuleks paigutada 4 lippu. Tähistame seda küljepikkust N. Alati on ka lippude arv sama N.

Kasutame mäeronimisotsingut, mille kirjelduse leiad näiteks loenguslaididelt. Lahendamiseks tuleks paigutada lipud kuidagimoodi mängulauale ja lasta siis mäeronimisotsingul neid ümber tõsta (leida naaberolekuid), kuni loodetavasti optimaalne olek on leitud. Seda otsingut saame õiges suunas juhtida väärtusfunktsiooniga - mitu lippu on veel "valesti" paigutatud.

Oleku kodeerimine

Et otsingut saaks teha, tuleks välja mõelda, kuidas olekuid arvutis esitada. Tuleb näidata, kus iga lipp mängulaual asub.

Mõned ideed:

1. Laua suurune, NxN tabel, kus igas ruudus kirjas, mis seal paikneb (lipp või mitte midagi). Kuna see on ruumilise keerukusega O(n²), siis sobib see ainult väikestele ülesannetele.
2. Kuna meil on N lippu, siis võime lihtsalt teha tabeli, kus igale lipule on antud tema koordinaadid
3. Edasiarendus eelmisest: kuna iga lipp peab niikuinii lõpuks olema eraldi veerus, siis teeme N pikkusega massiivi, nii et positsioonil i väärtus j näitab, et lipu koordinaadid on (i, j).

Otsingukäiguks, ehk tegevuseks, mis annab praegusest olekust ühe naaberoleku, võiks olla ühe lipu ringi tõstmine. Ka siin hoiab aega kokku, kui fikseerime iga lipu kindlasse veergu ja liigutame seda alati ainult ridu mööda. See piirab otsingu hargnemistegurit.

Oleku väärtuseks on õpikus pakutud selliste lippude paaride arv, mis asuvad samas reas, veerus või diagonaalis. Lahendatud oleku väärtus on 0 ja seega alati väiksem, kui ükskõik millise muu oleku oma. Seega peame seda väärtusfunktsiooni minimeerima.

Mäeronimisotsing

Minimeeriv hill climbing otsing:

def hill_climbing(pos):
    curr_value = pos.value()
    while True:
        move, new_value = pos.best_move()
        if new_value >= curr_value:
            # no improvement, give up
            return pos, curr_value
        else:
            # position improves, keep searching
            curr_value = new_value
            pos.make_move(move)

Siin on seis realiseeritud klassina, et ülalolev otsingualgoritm lihtsamalt loetav oleks. Enda lahenduses ei pea tingimata objektorienteeritud programmeerimist (OOP) rakendama.

class NQPosition:
    def __init__(self, N):
        # choose some internal representation of the NxN board
        # put queens on it
    
    def value(self):
        # calculate number of conflicts (queens that can capture each other)
        return value

    def make_move(self, move):
        # actually execute a move (change the board)
        
    def best_move(self):
        # find the best move and the value function after making that move
        return move, value

Ning lõpuks, kuidas etteantud toorikuid saaks kasutada. Kuna kõik olulised meetodid - konfliktide arvu leidmine, käikude genereerimine ja käigu tegemine - on realiseerimata, siis see esialgu veel ei tööta. Et mäeronimisotsing tööle saada, pead need valmis tegema.

pos = NQPosition(4) # test with the tiny 4x4 board first
best_pos, best_value = hill_climbing(pos)
print("Initial position value", pos.value())
print("Final value", best_value)
# if best_value is 0, we solved the problem

Kontrollimiseks võid lahendusi ka välja printida. Veendu, et iga lipp on ikka eraldi reas, veerus ja diagonaalis.

Kuidas lahendada suuremaid ülesandeid

Kui su programm lahendab 4-8 lipuga ülesande, oled teinud piisavalt, et ülesanne arvesse läheks.

Aga kui kaugele on võimalik minna? Õpiku peatükist 4.1.1 leiame ideid, mida edasi teha:

1. Oletame, et otsinguruumis esineb piirkondi, kus väärtusfunktsioon on platoo. Tavaline mäeronimine annab selles kohas alla, kui lubame ka võrdset naaberolekut järglaseks võtta, saame edasi liikuda. Otsingu iteratsioonide arv tuleb piirata, muidu võib lõputu tsükkel tekkida.
2. Stohhastilisus: algolek ja käikude järjestus otsingus on juhuslikud. See aitab lokaalsetest miinimumidest "välja raputada", eriti kui kasutad ka järgmist ideed.
3. Random restart. Tee otsingut korduvalt, alustades iga kord juhuslikust algolekust. Kui lahendust ei leita, katkesta otsing üsna ruttu. Jäta meelde, milline nähtud olekutest oli parim.

Kui N suureneb, võib probleeme tekkida ka parima järglase leidmisega. Mida efektiivsem on käikude genereerimine ja parima käigu väärtuse välja arvutamine, seda suuremaid ülesandeid on võimalik lahendada. Natuke on ka võimalik "sohki teha": kui genereerime käike juhuslikus järjestuses ja leiame esimese naabri, mis on praegusest seisust parem, võime käikude genereerimise katkestada ja selle naabri valida (õpikus first choice hill climbing)