2009-06-23

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

No comments: