Kako se kale kraljice

Još jedan problem s kojim se ljudi koji se bave umetnošću programiraju vaćaju u koštac je problem N kraljica. Na tabli N x N treba postaviti N kraljca a da jedna drugu ne jedu.

I ovaj problem se može rešiti Simuliranim kaljenjem. Funkcija cilja je u ovom slučaju broj sukoba, samo za razliku od prošlog primera sa trgovcem ovde se zna da je optimalno rešenje kad je f. cilja = 0.

Počentno rešenje se lako nalazi. Prvo ne sme se desti da više od jedne kraljce bude u bilo kom redu i bilo kojoj koloni. Dakle najprostije je da se poređaju po dijagonali. U mom rešenju se takvo rešenje tvikuje par puta i dobija se početno rešenje.

Tvikovanje se sastoji u nasumičnoj zameni 2 kolone.

Implementacija je takva da se u klasi Resenje u nizu koji se zove kraljice čuva pozicija kraljice u redu za svaku kolonu. Npr. niz [1, 0, 2] znači da se u 1. koloni kraljica nalazi u 2. redu, 2. koloni u redu 1, a u 3. koloni u redu 3 (i u Pythonu su prvi elementi niza na poziciji 0). Dakle u početnom rešenju ćemo pre tvikovanja imati ovakav niz: [0, 1, 2, 3, ...] jer kraljice postavljamo po dijagonali.

Dalje formiramo tabelu N x N i koja se puni None objektima (u pythonu je sve objekat pa i Null vrednost ) osim što se na dijagonalama postavi string K kao oznaka da je tu kraljica.

Samo simulirano kaljenje je slično kao u prošlom primeru. Jedino se manje vrši resetovanje tekućeg rešenja jer je takav zadatak da se tvikovanje može obaviti na već tvikovano rešenje bez većeg problema.

A pošto znamo koje je optimalno rešenje, kaljenje se ponavlja iznova sve dok ne dođemo do tog rešenja kad se štampa optimalni raspored na tabli.

import random, copy, math, time

class Resenje(object):
    def __init__(self, br_kraljica):
        self.br_kraljica = br_kraljica
        # resenje: pozicija kraljice u koloni 0 do len - 1
        self.kraljice = range(br_kraljica)  
        # energija: treba da je  0 
        self.__broj_sukoba = None
        
        ## postavljamo pocetno resenje
        # generisemo tabelu br_kraljica X br_kraljica popunjenu None elementima
        self.tabla = [[None for i in range(br_kraljica)] for j in range(br_kraljica)]
        
        # postavimo kraljice po dijagonali
        for i in xrange(br_kraljica):
            self.tabla[i][i] = 'K'
        
        # promesamo kolone    
        for i in xrange(br_kraljica):
            self.tvikuj_resenje()
        
    # f-ja cilja, optimalno resenje ima 0 sukoba   
    def get_broj_sukoba(self):
        # Ovo je optimizacija da se broj sukoba racuna samo ako vec nije izrazcunat
        if not self.__broj_sukoba:
            self.__broj_sukoba = self.__racunaj_broj_sukoba()
        return self.__broj_sukoba
    
    # racuna energiju resenja, prakticno funkciju cilja koja se minimizuje
    # a je ovde broj sukoba svih kraljica na tabli
    def __racunaj_broj_sukoba(self):
        # povratna vr. 
        # zato sto se sukobljava sam sa sobom i to pri proveri svake od 4 
        # dijagonala a to se ne racuna
        br_sukoba = -4 * self.br_kraljica 
        
        dx = (-1, 1, -1, 1) # pomeraj koordinate x za kretanje po dijagonalama
        dy = (-1, 1, 1, -1) # pomeraj koordinate y -//-
        
        # provera dijagonala
        for x, y in enumerate(self.kraljice): # (x,y) koord. kraljica
            for i in xrange(4): # za sva 4 kraka dijagonala
                pomx, pomy = x, y # pretraga krece od koordinata kraljice
                # dok se pomeranjem po dijagonali nalazimo na tabli ispitujemo 
                # da li smo nabasali na kraljicu. Svaki od 4 ciklusa za 4 dijagonale
                # nailazi na sopstvenu kraljicu pa je zato br_sukoba inicijalizovan 
                # na -4 * self.br_kraljica 
                while (0 <= pomx < self.br_kraljica) and (0 <= pomy < self.br_kraljica): 
                    if self.tabla[pomx][pomy] == 'K':
                        br_sukoba += 1
                    pomx += dx[i]
                    pomy += dy[i]
            
        return br_sukoba
    
    broj_sukoba = property(get_broj_sukoba)
    
    # zamenjuje 2 kolone
    def tvikuj_resenje(self):
        r1 = random.randrange(self.br_kraljica)
        r2 = random.randrange(self.br_kraljica)
        
        # kolone moraju biti razlicite
        while r2 == r1:
            r2 = random.randrange(self.br_kraljica)
            
        # zameni redove r1 i r2
        self.tabla[r1], self.tabla[r2] = self.tabla[r2], self.tabla[r1]
        
        # zameni elemente
        self.kraljice[r1], self.kraljice[r2] = self.kraljice[r2], self.kraljice[r1]
        
        # prethodno izracunata duzina puta vise ne vazi pa se setuje na None
        self.__broj_sukoba = None
    
    def __str__(self):
        rez = ''
        for red in self.tabla:
            s = ''
            for element in red:
                if element: s += element
                else: s += '.'
            rez += s 
            rez += '\n'
        return rez
        
    
class SimulatorKaljenja(object):
    def __init__(self, br_kraljica):
        self.br_kraljica = br_kraljica
        self.resenje = None
        
    def start(self, pocetna_temperatura=90.0, alpha=0.997, ponavljanja=None):
        najbolje_resenje = Resenje(self.br_kraljica)
        tekuca_temp = pocetna_temperatura
        if not ponavljanja: ponavljanja = self.br_kraljica / 2
        
        
        while tekuca_temp > 0.10 and najbolje_resenje.broj_sukoba > 0:
            privremeno_resenje = copy.deepcopy(najbolje_resenje)
            
            # Monte Carlo na tekucoj temperaturi
            for i in xrange(ponavljanja):
                privremeno_resenje.tvikuj_resenje()
                
                delta_e = privremeno_resenje.broj_sukoba - najbolje_resenje.broj_sukoba
                
                # ako je resenje bolje uzimamo ga a ako nije tada uz 
                # odredjenu verovatnocu odabiramo losije resenje kao tekuce
                if delta_e < 0.0 or (math.exp(-delta_e / tekuca_temp) > random.random()):
                    if  privremeno_resenje.broj_sukoba < najbolje_resenje.broj_sukoba:
                        najbolje_resenje = copy.deepcopy(privremeno_resenje)
                else:
                    privremeno_resenje = copy.deepcopy(najbolje_resenje)
                
            tekuca_temp *= alpha
        
        self.resenje = najbolje_resenje
    
def main():
    try:
        import psyco
        psyco.full()
    except ImportError:
        pass
        
    simulator = SimulatorKaljenja(32)    
    
    t0 = time.time()

    i = 1
    while True:
        print 'ciklus', i
        i += 1
        simulator.start()
        print 'najbolje resenje', simulator.resenje.broj_sukoba
        if simulator.resenje.broj_sukoba == 0:
            break
       
    print simulator.resenje
    print "Izvrsenje trajalo", time.time() - t0, "sekundi"
    

if __name__ == "__main__":
    main()

Primer rezultat ovoga koda je:

ciklus 1 
najbolje resenje 2 
ciklus 2 
najbolje resenje 0 
.K.............................. 
....................K........... 
..................K............. 
............K................... 
..K............................. 
...........................K.... 
.................K.............. 
K............................... 
..........K..................... 
.....K.......................... 
...............................K 
...................K............ 
..........................K..... 
.............K.................. 
.....................K.......... 
............................K... 
...............K................ 
.............................K.. 
......................K......... 
......K......................... 
.........................K...... 
.......K........................ 
..............K................. 
...........K.................... 
..............................K. 
....K........................... 
................K............... 
........................K....... 
.........K...................... 
.......................K........ 
...K............................ 
........K....................... 

Izvrsenje trajalo 35.1647040844 sekundi

Kako se kalio čelik

Nešto mi je ovijeh dana dosadno bilo, a dokon um đavolje dvorište. Te se dovatim jedne knjige o AI algoritmima. U pa tu ima svakakve 'euristike, ovi iz Operacionih bi zinuli

E ovde ću kako budem stizao da postavljam neke algoritme. Knjiga ima neke C kodove, sad malo ko parla C, a i ti kodovi su tako odvratni i u knizi dati iz delova i nepotpuno. Pa sam ih ja sredio u mom omiljenom prog. jeziku

Prvi algoritam je Simulirano kaljenje. Ima nešto o tome u knjizi iz Operacionih, ali to su pisali matematičari (čitaj: dosadni tipovi). Ideja je da se podražava proces kaljenja. To smo valjda učili iz Teknologije, eto neke koristi i od toga Pa kako se kali? Podigne se temperatura pa se čuka metalni predmet i izvaja u neki oblik, pa se polako 'ladi a i dalje čuka.

U ovom algoritmu se prvo nađe neko najobičnije rešenje, zatim se to rešenje tvikuje (malo se promeni) i gleda kakvo je u odnosu na prethodno. Ako je bolje super, usvajamo ga, ako nije onda po nekoj verovatnoći usvaja. Jer lošije rešenje može u nekoj sledećoj iteraciji voditi u bolje. Usvajanjem ponekog lošijeg rešenja se izbegava nalaženje nekog lokalnog minimuma koji je daleko od globalnog.

E sad da se ne bi mlogo lutalo ta vervatnoća da se usvoji lošije rešenje se iz ciklusa u ciklus smanjuje. To podražava smanjenje se temperatura metala pri kaljenju, što je metal ladniji teže ga je oblikovati. A verovatnoća usvajanja lošijeg rešenja zavisi i od toga koliko je to rešenje lošije. Ako je mlogo loše onda je mala verovatnoća da ga usvojimo.

Znam da vam ništa nije jasno Evo primer primene algoritma. Setite se problema trgovačkog putnika. Postoje algoritmi ali su oni NP-kompletni (u prevodu, teški u p.m za više od 30 čvorova). E sad Simuliranim kaljenjem se dobija rešenje blisko optimalnom ako ne i optimalno (ako vas baš ukenja).

I kako to radi? Pa uzme se neka putanja. Može nasumična može sistemo najbližih čvorova (ovo je bolje početno rešenje). Pa se onda u tom rešenju zamene mesta nekih čvorova i izračuna nova dužina i poredi sa prethodnom. Ako je bolja usvaja se rešenje, ako nije ide po onoj verovatnoći. I tako se iz ciklusa u ciklus smanjuje temperatura sve dok ne padne na neku zaustavnu a pamti se najbolje rešenje. Prosto ko pasulj

Nemojte da vas uplaši kod, to je prost jezik, a naveći deo koda odlazi na štampanje, što vam nije potrebno da razumete jer je to pythonizovan matlab.

Prvo pravimo klasu Grad koja će predstavljati jedan čvor u grafu (__init__ metoda je konstruktor u Pythonu):

Potom prvimo klasu za rešenje koje se sastoji od redosleda gradova koje treba obići.  Ima metodu za dužinu rešenja (vrednost funkcije cija što bi rekli ćelavi matematičari), metodu za tvikovanja i jednu pomoćnu za grafike:

I konačno klasa u kojoj se simulirano kaljenje obavlja. U konstruktoru se prihvata početno rešenje a u metodi start() se dešava ćudo, sa namenim ć :) :

Ovoj se klasi dodaje i metoda za prikaz rešenja u grafičkom obliku preko matplot biblioteke (i svet to besplatno i slobodno):

I na kraju puštamo u pogon ovu skalameriju koja uz to i radi :)

I jedan od rezultata može se prikazati graficima (rezultet metode stampaj_resenje):

Zna li ko kako da se postuje kod na ovom glupom blogu, otelih se slikajući i uploudovajući slike i razmeštajući ih na pravo mesto...