Ifi6057w6

6. Nädal

AIMA chapter 4.1 (katab ka mõned metaheuristikud).

Metaheuristikute loomaaed.

Metaheuristiku näide: ILS. Lühendatud slaidid PDF (T. Stützle originaalid).

Harjutustund

Tee harjutustunniks uus pythoni skript (näiteks ht6.py). Kopeeri sinna:

import search
from collections import deque

class EightPuzzle(search.Problem):
    def actions(self, state):
        space = state.index(0)
        row = space // 3
        col = space % 3

        act = []
        if row == 0:
            act.append(state[space + 3])
        elif row == 1:
            act.append(state[space + 3])
            act.append(state[space - 3])
        elif row == 2:
            act.append(state[space - 3])
        if col == 0:
            act.append(state[space + 1])
        elif col == 1:
            act.append(state[space + 1])
            act.append(state[space - 1])
        elif col == 2:
            act.append(state[space - 1])
        return act

    def result(self, state, action):
        newstate = list(state)
        klotsi_idx = newstate.index(action)
        space = newstate.index(0)
        newstate[space] = action
        newstate[klotsi_idx] = 0
        return tuple(newstate)

Ülalolev on taaskasutatud eelmiste harjutustundide 8-Puzzle lahendamise kood. Lisaks kopeeri endale see:

def step_cost(node, action, next_state):
    return 1

(See kood ei ole EightPuzzle klassi sees)