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.

Tegu on optimeerimisülesandega, kus parim olek pole teada, kuid saame mingi oleku konstrueerida ja siis proovida seda samm-sammult paremaks muuta. 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 ja iga lipp peab lõpuks olema eraldi veerus, siis fikseerime iga lipu veeru ja muudame ainult rida. Teeme N pikkusega massiivi, nii et positsioonil i väärtus j näitab, et lipu koordinaadid on (i, j).
3. Iga lipp peab olema eraldi veerus JA real. Seega me võime ka fikseerida mõlemad. Vaatame lauda kui ribasid, mis tuleb õigesse järjekorda panna. Esitus mälus oleks sama kui eelmine.

Otsingukäik on tegevus, mis annab praegusest olekust ühe naaberoleku. Käik sõltub sellest, kuidas olekut esitame.

1. Ühe lipu ringi tõstmine suvalisse kohta.
2. Liigutame ühte lippu ridu mööda üles-alla.
3. Vahetame veerge omavahel või muudame nende järjekorda.

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
print("Initial position value", pos.value())
best_pos, best_value = hill_climbing(pos)
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. Stohhastilisus: algolek ja käikude järjestus otsingus on juhuslikud. See aitab lokaalsetest miinimumidest "välja raputada", eriti kui kasutad ka järgmist ideed.
2. 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)

Some high performance results from spring semester 2021

N	time, approx	algorithm	moves	language
100000	2 minutes	FCHC	row shift	Python (PyPy)
50000	18 min	SA	col swap	Java
50000	2 hours	FCHC	col swap	Java

Algorithm details:

• SA - simulated annealing
• FCHC - first choice hill climbing, with some form of random restart
• row shift - move is moving a queen to a different row
• col swap - move is swapping two columns (queens stay at their row)