Iti0210lab42

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. Esimene samm lahenduses ongi esialgu mäeronimisotsing käima saada.

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