1. =========================================================================
problem pretrage deli se na stanja i akcije, moze se opisati grafom.
	cvorovi predstavljaju stanja
	grane predstavljaju akcije

graf moze biti usmeren ili neusmeren.
	slagalica neusmeren - iz nekog stanja A za koji postoji neka akcina kojom se moze stici do B, postoji i neka akcija iste cene koja iz B vodi u A.
	gradovi neusmeren - svakom cvoru pridruzen jedan grad
	sah usmeren - postoje potezi takvi da se iz A moze doci do B ali ne i obrnuto

pretrazivanjem, obilaskom grafa prostora stanja dobija se stablo pretrage.
	broj cvorova stabla pretrage moze biti besk i ako je prostor stanja konacan, zato sto se stanja u stablu pretrage mogu ponavljati

pathfinding: naci put u grafu od cvora A do cvora B tako da cena bude minimalna
	koristi se u google mapama, rutiranje u racunarskim mrezama, navigacija robota, dizajniranje cipova.

Da bi neki problem resavali kao problem pretrage, on treba ispuniti sledece:
	- razmatranje razlicitih stanja - za odlucivanje u datom trenutnu potrebno je znatisva raspoloziva stanja.
	- polazni stanje - stanje od koga krecemo
	- zavrsno stanje - problem je resen ako se dodje do zavrsnog stanja.
		* test cilja - provera da li je trenutno stanje, zavrsno.
	- skup akcija - niz akcija koje (grane) koje dovode do resavanja problema. Moze da bude isti u svakom stanju ili da se razlikuje od stanja do stanja, zavisi od problema koji resvamo
	- funkcija prelaska - preslikava par stanje-akcija u novo stanje. Ukoliko ona nije poznata, ne zna se u koje ce se stanje dospeti i odlucivanje je dosta otezano. Ukoliko nije poznata cesto se aproskimira na osnovu procesa koji se zasniva na analizi pokusaja i gresaka.
	- cena akcije - preslikava stanje-akcija u numericku vrednost

deca stanja, susedi stanja - stanja koja su dostupna iz nekog stanja

resenje problema - niz akcija koje vode od polaznog do zavrsnog stanja
svako resenje ima svoju cenu - suma svih ceni akcija koje dovode do resenja
optimalno resecnje - resenje sa minimalnom cenom

svojstva algoritama pretrage:
	- potpunost - svojstvno koje garantuje da ce alg naci neko resenje ako resenje uopste postoji. Nije uvek slucaj, u nekim teskom problemima u vecini slucanjeva pronalaze resenje. Bolje nego potpuni algoritmi, ali ne garantuju da ce resenje naci.
	- optimalnost - da ce resenje biti sa najmanoom cenom. Alg koji nemaju ovo svojstno nalaze blizu optimalno ali u znatno kracem vremenu.
	- vremenska slozenost - koliko ce vremena biti potrebnog. Razmatra se najgori i prosecni slucaj.
	- prostorna slozenost - koliko je prostora potrebno. Razmatra se najgori i prosecan slucaj.

informisana/neinformisana pretraga:
	dele se na osnovu dostupnosti informacija pretrage.
	na osnovu toga delimo i agloritme pretrage.


2. ==============================================================================

Neinformisana pretraga
	- nema dodatnih informacija koje mogu pomoci u pronalazenju ciljnog stanja
	- primer lavirinta - ako je graf koji odgovara algoritmu, stablo, lavirint je savrsen

BFS i DFS metode neinformisanje pretrage koje ispitnuju sve cvorome u grafu trazeci obicno neki specificni cvor
backtracking - modifikacija DFS-a

Pretraga u dubinu DFS - pretrazuje pocevsi od polaznog cvora, zatim obradjuje sve njegove potomke, pa sve potomke potomaka, sve dok se trazeni cvor ne pronadje i sve dok potomci postoje. Ukoliko vise nema potomaka vraca se unazad do cvora ciji svi potomci nisu ispitani. Obicno se cuva na steku LIFO listi. Potrebno je cuvati info o posecenim cvorovima kako ne bi upali u besk petlju. Kada se pronadje cvor, na staku se nalazi put do njega.

DFS - 	ulaz: G, polazni cvor, ciljni cvor
	izlaz: put u G od polaznog do ciljneg
	1. stek put i skup posecenih cvorova sadrze samo ulazni cvor
	2. idemo sve dok stek nije prazan
		* uzmemo cvor n sa vrha steka
		* ako je n ciljni cvor, pronasli smo put i vratomo sadrzaj steka put
		* ako n nema potomka koji nije posecen izbaciti ga sa steka
		* u suprotnom izaberi prvog takvog potomka, m, stavi ga na stek put i dodaj ga u skup posecenih
	3. obavesti da put nije pronadjen

bektrekint - modifikacija DFS tako sto se pretraga u dubinu tekuceg cvora prekida kada se ustanovi da trazeni cvor nije u potomcima datog cvora, tada se vraca na prethodni cvor i nastavlja dalje. Najcesci problem je problem 8 dama.

backtracking - dodavanje parcijalnog resenja, ako nije moguce vraca se unazad

8 dama - 1848 godine - 92 razlicitih resenja
	uopstenje - n dama na tabli n x n, tako da se nikoje dve ne sudaraju. U svakoj koloni mora biti po jedna dama i da se one ne napadaju

Pretraga u sirinu BFS - ispituje cvorove koji su susedi trenutnom cvoru, a kasnije njihove potomke. Kada se prodanje trazeni cvor on ce uvek biti na najmanjem rastojanu (po broju grana) od polaznog cvora. Cvorovi koji se razmatraju cuvaju se u redu FIFO listi, i takodje treba da se obeleze poseceni kako ne bi doslo do besk petlje. Informacija o posecenom se ne cuva eksplicitno vec se zna na osnovu predhodnog cvora.

BFS - 	ulaz: graf, polazni cvor, ciljni cvor
	izlaz: najkraci put od polaznog do ciljnog u G ako takav put postoji
	1. RED init sadrzi samo polazni cvor
	2. Izvrsava se dok red S nije prazan
		* uzima cvor n sa pocetka reda i brise ga iz reda
		* ako je n ciljni cvor, pronasli smo put, vratiti unazad put od ciljnog cvora
		* za svaki od potomka m cvora n za koji nije def roditelj, zapamti n kao roditelja i dodaj ga na kraj S
	3. obavesti da trazeni put ne postoji.

DFS pogodnija pretraga, vidi zbog cega
Vremenska slozenost algoritma BFS I DFS je (O(|V|+|E|)) - broj cvorova + br grana
	  a prostorna slozenost agloritma  (O(|V|)) - broj cvorova

Dejkstring algoritam - 1959 - pronalazi najkrace puteve u grafu sa ne negativnim cenama.
koristi se za pronalazenje najkraceg puta od A do B, ali i od svih cvorova do B

Dejkstrin - 	ulaz: G, ulazni i izlazni cvor
		izlaz: najkraci put ako postoji
		1. inicijalno skup Q sadrzi sve cvorove
		2. radimo sve dok skup Q nije prazan
			* iz Q se uzme cvor n sa najmanjim rastojanjem od polaznog cvora i brise se iz Q
			* ako n zavrsni cvor, kostruisemo put iduci unazad
			* za svaki cvor m iz Q koji je vezan sa n proveriti da li je pd polaznog do m rastojanje vece nego preko n, ako jeste postaviti roditelja m da bude n i zapamtiti novo rastojanje
		3. obavestiti da ne postoji, Q prazan a uspeh nije projavljen

Dijkstra invarijanta - Invarijanta petlje je da se za ˇcvorove koji
nisu u 𝑄 zna najkra´ce rastojanje od ciljnog ˇcvora

Dijkstra se najcesce implementira uz pomoc niza ili povezanih lista i tu je slozenost O(|V|^2)
za neke grafove koji imaju mnogo manje grana, moze biti efikasnije, time sto se implementira preko binarnog min-hipa i slozenost je O((|E|+|V|)log|V|)
		min-hip je stabolika struktura koja zadovoljava hip svostvo, te je najmanji element uvek koren stabla. Analogno max-hip

3. ======================================================================
Informisana pretraga - nema info samo o mogucim akcijama, vec i dodatno znanje o konkretnom problemu, te usmerava pretragu ka stanjima koja vise obecavaju. Ta informacija moze biti ocena ili moze da bude zasnovana na info o pocetnom i zavrsnom stanju. Nije 100% tacna, vec predstavlja procenu, heuristicku vrednost.

Heuristike - mere koje sluze za usmeravanje i susavanje pretrage u kojima se javlja kombinatorna ekspozija
	   - izbor izmedju nekoliko mogucih akcija, tako da se izabera najbolja koja dovodi do nekog cilja

f - funkcija evaluacije stanja - funkcija koja odredjuje kvalitet stanja
f(n) - ocenja stanja
moze se desiti da postoje ista stanja u stablu pretrage, te je bolje reci ocenja cvora a ne ocena stanja

=======
Pohlepna pretraga

pohlepni algoritam - tezi neposrednom povecanju vrednosti neke ciljne funkcije
		   - on ne procenjuje akcije koje dovode do najefikasnijeg ostvarenja cilja, vec u trenutku izbora, na osnovu trenutnog znanja on bira
		     		najbolju medju raspolozivim akcijama

Pohlepni -	ulaz: G, pocetni i ciljni cvor
		izlaz: niz koraka od polaznog do ciljneg cvora ili neuspen (neuspeh ili besk petlja moguce i ako postoji put)
		1. tekuci cvor, je polazni cvor
		2. beskonacno izvrsava sledece korake
			* ako je n ciljni, obavesti o ospehu i vrati put od polaznog do ciljneg
			* ako tekouci cvor nema direktno dostupnih cvorova, neuspeh
			* od direktno dostupnih cvorova izaberi novi n, koji ima najbolju ocenu f(n)

problem ovog alg:
	* ne nadje uvek najbolje resenje
	* mozda ne nadje resenje ako postoji
	* moze ostati u besk petlji

Menhetn rastojanje - najkrace restojanje izmedju A i B (najmanji br polja) krecuci se samo horizontalno ili vertikalno (nema dijagonalno)

pohlepni algoritmi koriste se i u resvanju problema matematicke optimizacije, a tada se najcesce nazivaju algoritmi penjanja uz brdo, posto biraju susede koji imaju najvecu vrednost fje cilja. Zahtevaju postojanje funkcije cilja i skupa dopustivih resenja, a pronalaze optimalno resenje.

Pohlepna pretraga se ponasa dobro ukoliko se optimalno resenje problema gradi od lokalno optimalnih resenja problema.

Mane penjanja uz brdo:
	1. opasnost od lokalnog maksimuma - nemaju nacina da utvrde da li su u lokalnom maksimumu. Susedi trenutnog cvora imaju manju vrednost fje cilja nego ona, ali je njegova vrednost manja od globalnog max.
	2. neefikasnost u slicaju grebena (uske staze koje opadaju i rastu duz nekog pravca) - penjanje uz brdo ne vodi u pravcu rasta vec treba napraviti dosta cik cak pokreta da bi se popeo/spustio.
	3. Platoi - oblast prostora pretrage u kojoj funkcija ima konstantnu brednost, pa se ne moze odrediti koji je potez najbolji a cesto se iz njega ne moze ni izaci.

modifikacije koje resavaju neke probleme:
	1. Stohasticko penjanje uzbrdo - ne bira uvek susedno stanje koje ima najvecu vrednost, ali verovatnoca da neko stanje bude izabrano je da ima sto vecu vrednost
	2. penjanje sa slucajnim restartovanjem - gde se nakon pronalazenja lokalnog max, pretraga ponovo pogrece iz random generisanog polaznog stanja


=====
PRESKOCIO - 3.1.1 Pohlepna pretraga u sluˇcaju diferencijabilne funkcije cilj

=====
pretraga prvo najbolji - pronalazi put od pocetnog do ciljneg cvora. Svakom cvoru se pridruzuje informacija o svom predhodniku (roditelju) slicno kao kod dijgstre. Kako bi se izbegla beskonacna petlja (ponavljanje istih cvorova) cuvaju se dve liste cvorova.
	* zatvorena lista - lista stanja za koje su ispitani svi susedi
	* otvorena lista - lista stanja koja su posecena, ali nisu ispitani svi susedi (treba lako da pristupi el sa najboljom ocenom)

ideja ukratko: otvorena lista na pocetku zadrzi samo polazni cvor a zatvorena je prazna. Ideja je da ispitujemo cvor sa najboljom ocenom iz otvorene liste i obradjuju se njegova neposredna stanja. ukoliko se naidje na ciljno stanje algoritam prekida rad.

prvo najbolji:
	ulaz - G, pocetno i krajnje stanje
	izlaz - niz koraka, od ciljnog, ako postoji
	1. inicijalno otvorena lista sadrzi pocetno stanje, zatvorena je prazna
	2. sve dok postoje elementi u otvorenoj listi
		* izaberemo cvor n koji ima najbolju ocenu iz otvorene liste
		* ako je taj cvor ciljni, uspesno, vracamo put pocevsi od tog cvora
		* za svaki cvor m koji je direktno dostupan iz n
			- ako m nije ni u jednoj listi, dodaj ga u otvorenu listu i oznaci nkao njegovog roditelja
		* izbaci n iz otvorene i dodaj u zatvorenu
		* izvestaj da put nije prodanadjen


Optimizacija:
prvo najbolji ne daje optimalno resenje, i to ne garantuje. Ali se ta sansa moze unaprediti ako, kada se ispituje trenutni cvor m, koji je diraktan sa n, ako se m vec nalazi u nekoj od listi, moze se proveriti da li je put od polaznog cvora do cvora m preko n, bolji od postojeceg puta do m. Ako je bolji promeniti roditelja cvora m na n, a ako je m uzatvorenoj listi prebaciti ga u otvorenu.

T1: ako je broj stanja i akcija konaca Prvo najbolji se zaustavlja i nalazi trazeni put uvek kada postoji.

Algoritam prvo najbolji je slican pohlepnom alg, samo sto ima mogucnost da se vrati na cvorove koji nisu ispitani. Takodje algoritam prvo najbolji ima mogucnost da nastavi pretragu ukoliko naidje na plato ili lokalni optimum (zahvaljujuci alternativama otvorenoj lisi) i eliminise mogucnost beskonacnih petlji (zahvaljujuci pamcenju obradjenih cvorova u zatvorenoj listi)

ukoliko funkcija f(n) vraca dubinu cvora n, onda se algoritam ponasa kao BFS, a ukoliko vraca zbir cena od polaznog do n, onda se ponasa kao dijkstrin

prvo najbolji je sposoban da resi lojdovu slagalicu, ali ne garantuje najmanji br poteza.

=====
A* - zasnovan na koriscenju heuristinka a potpun je i optimalan
   - pronalazi put izmedju 2 cvora u grafu
   - najbitniji alg vi
   - prva verzija Hart, Nilson, Rafael 1968 godine, kasnije uvedeno nekoliko modifikacija
   - predstavlja varijantu algoritma "Prvo najbolji" sa modifikovanom f
   	- koristi formulu f(n) = g(n) + h(n)
	- g(n) predstavlja cenu puta od polaznog cvora do cvora n
	- h(n) je procenjena(heuristicka) cena najjeftinijeg puta od n do ciljnog cvora
	- tokom primene algoritma, uvek se zna tekuca cena od pocetnog do n - g(n), a h(n) se moze samo procenjivati
	- najvaznija stvar je izbor kvalitetne heuristike


  - posto otkriva najbolji put do ciljnog cvora, i zato svaki cvor koji naidje proverava da li je ranije vec pronadjen neki losiji put do tog covra i ako jeste menja ga sa novim. To je opcija u prvo najbolji, a u a* je obavezno.

  - slican dijkstrinom, cesto ispituje manje cvorova, zbog toga sto je informisan sa g(m)
  - vrednost g(m) - jednaka je zbiru vrednosti funkcije g za roditelja cvora m i ceni puta od roditelja do m
  - ako se pronajde m koji je vec u otvorenoj ili zatvorenoj listi to znaci da je pronadjen novi put za m, i proverava se da li je preko n bolji od postojeceg. Ako je taj m u zatvorenoj prebaciti ga u otvorenu i ponovo ispitati, kako bi se uvek nasao najkraci put.

svojstva algoritma A*:
	moze se dokazati da je A* potpun i da je pod odredjenim uslovima optimalan

Potpun - ako su broj cvorova i broj akcija konacni, i ako postoji put izmedju 2 dvora A* ce naci neki put.
Optimalnost - od svih puteva izmedju 2 cvora, A* ce naci najkraci, ako je funkcija h dopustiva (ako nikad ne precenjuje stvarno rastojanje izmedju tekuceg cvora i ciljnog cvora. Tj ako za svaki cvor vazi 0<=h(n)<=h*(n) gde je h*(n) cena optimalnog puta od cvora n do cilja)

fja h je konzistenta ako ciljni cvor ima vrednost 0 i za bilo koja 2 susedna cvora m i n vazi
	c(n,m) + h(m) >= h(n)
gde je c(n,m) cena grane n,m

svaka konzistentna je dopustiva al obrnuto ne vazi
ako je h konzistentna, ona je i dopustiva. Obrnuto ne vazi. Moze da bude dopustiva a ne konzostentna.

l1: ako je h konzistentna heuristika, onda tokom primene algoritma, vrednosti f(n) nisu opadajuce
dokaz: ako je u nekom trenutku primene algoritma cvor m trenutni a njegov roditelj je cvor n tada vazi
	f(m) = g(m) + h(m) = g(n) + c(n,m) + h(m) >= g(n) + h(n) = f(n)

l2: ako je h konzistentna heuristika, za niz cvorova redom proglasenih za tekuce, niz vrednosti f(n) u stablu pretrage cini neopadajuci niz
dokaz: u svakoj iteraciji algoritam za tekuci cvor bira cvor sa najmanjim f(n) iz otvorene liste, te su svi preostali cvorovi veci ili jednaki po f(n).
Te svi buduci cvorovi (potomci ovih) imaju ili vece ili iste vrednosti, pa je niz tekucih cvorova ne opadajuci.

l3: sako je h konzistentna heuristika, kada neki covr stabla pretrage postanje tekuci, do njegovog stanja je vec pronadjen optimalni put. Tj. svaki cvor koji postaje tekuci bice cvor sa najmanjom cenom za to stanje.
dokaz: kada algoritam proglasi neki cvor tekucim, on ima vrednost g(n) = g0 i f(n) = g0. Ako predpostvatimo da g(n) nije optimalan puut, i da je do istog moguce doci u nekoj kasnijoj iteraciji koja ima vrednosti g1 i f1. g1 je cena optimalnog puta do n, vazi g0>g1, pa i g0+h(n) > g1+h(n) -> f0>f1, a prethodna lema kaze f0 <= f1 sto je kontradikcija.

t: ako je h konzistentna heuristika, ako je pronadjen put do ciljneg cvora on je sigurno najbolji
dokaz: vraca najdeni put cim ciljni cvor postane tekuci, a ako je h konzistentna heuristika, kada ciljni postane tekuci, on je vec optimalan na osnovu predhodne leme.

slozenost:
* slozenost zavisi od odabira heuristike. U najgorem slucaju, broj obradjenih cvorova je eksponencijalan u odnosu na duzinu najkraceg puta.
	Te je i prostorna i vremenska A* ista kao i za BFS.
* broj obradjenih cvorova je polinomijalan ako je heuristika kvalitetna, ako zadovoljava sledeci uslov:
	|h(x)-h*(x)| <= O(log h*(x))   - h* optimalna heuristika (vraca tacnu cenu puta od x do cilja)

sumasumarum:
	- A* ima najbolje performanse kada je fja heuristike bliska idealnoj funkciji heuristike.
	- Optimalnost je garantovana samo ako fja heuristike ne precenjuje stvarnu cenu puta.
	- te funkcija heuristike mora da se konstruise tako da bude bliska idealnoj ali da je nikad ne premasuje.

kada heuristika nije konzistentna treba proveravati i zatvorene cvorove !!!!!!!!!!

Specijalni slucajevi:
	obilazak grafa u dubinu sa A* ako je g(n) = 0 i pogodnom heoriskitkom h. H nije nuzno dopustiva.
	obilazak grafa u sirinu sa A* gde je h(n) = 0 u za svaki n. H je konzistentna i garantuje optimalni put.

pronalazenje puta u mrezi covorova - mapi:
	euklidsko i menhetn rasotjanje.

Implementacija:
	otvorena lisata - bnarni mini hip - efikasno dolazi do elementa sa najmanjom vrednostcu
		dodavanje i brisanje elementa iz otvorene liste O(logV) - v je broj cvorova grafa
	zatvorena lista - hes tabela
		dodavanje cvora i provara da li je u zatvorenoj listi O(1)


	prostorna slozenost - staticko alociranje, izbegavaju se skupe op dinamicke alokacije

	treba koristiti samo celobrojnu aritmetiku.

	najgore je kada put od A do B ne postoji pa se implementira jednostavna provera.

	pronalazenje puta u uniformnoj mrezi, daje korake u 8 smerova te su putevi neprirodni. Te puteve zamenjujemo slicnim, prirodnijim - omeksavanje

=====
Genetski algoritmi
	metaheuristike 	- metode koje opisuju opste strategije pretrage za resavanje optimizacionihh problema
		       	- nisu specificne za odredjeni problem, vec imaju siroku upotrebu
		       	- razmatraju samo mali uzorak iz skupa resenja i ne garantuju pronalazenje najboljeg moguceg resenja
			- ali cesto daju dovoljno dobra resenja kada nije raspoloziva ni jedna druga egzaktna metoda za resavanje tog problema
			- genetski algoritmi koriste metaheuristicke algoritme

	bioloski pojmovi:
			- svaka celija sadrzi hromozome
			- svai hromozo sadrzi blokove DNK
			- svaki gen odredjuje neku osobinu organizma
			- GENOTIP - familija gena
			- FENOTIP - familija osobina
			- reprodukcija ukljucuje kombinovanje gena roditelja i mali nivo mutacije
			- organizmi prilagodjeni okolini opstaju, dok ne prilagodjeni nestaju kroz generacije

	Evolucioni procesi u prirodi su optimizacioni procesi!!!
		- procesi u kojima se kroz generacije optimizuje genetski materijal tako da bude sto prilagodjeniji okolini

	Moderne genetske algoritme uveo je Dzon Holadn 70tih godina, a postali su popularni krajem 80tih.

	Genetski algoritmi se primenjuju na skiroki skup problema, cesno na NP-kompetne ili teske probleme, za koje ne postoje efikasna resenja.
		primeri problema: najkraci put u grafi, problem trgovackog putnika, igranje strateskih igara

	Genetski algoritmi iako cesto nalaze globalne ekstremume, nemaju informaciju da li je ekstremum globalni ili lokalni i sa kolikom greskom
			je to odredjeno.



Opsti genetski algoritam

	- Reprezentacija jedinke naziva se hromozom iligenotip.
	- Cilj je pronaci vrednozt za koju funkcija cilja postize svoj ekstremum ili vrednost koja je dovoljno blizu ekstremuma
		vrednost moze biti: fja, num, put...
	- Jedinke se obricno reprezentuju binarno (niz 0 i 1) ali je moguce i druga reprezentacija kada binarna nije pogodna.
	- Postupak se odvija kroz generacije, gde je prva gen obicno random generisane jedinke,mogu biti i jedinke koje su rez neke druge optimizacije
	- U svakoj generaciji postoji isti broj jedinki i za svaku od njih se racuna kvalitet (prilagodjenost okolini)
		Prilagodjenost se racuna funkcijom prilagodjenosti ili funkcijom kvaliteta.
		Veoma je bitna i moze al ne mora da bude jednaka funkciji cilja.

	slicnost/razlicitost dve generacije:
	- SELEKCIJA: Iz jedne gen se na osnovu vrednost fje prilagodjenosti, biraju jedinke koje se koriste za stvaranje novih jedinki.
	- UKRSTANJE: primenjuje se na izabrane jedinke, i tako se dobijaju nove. Ta nova jeinka ima gen material od roditelja.
	- MUTACIJA: modifikuje se deo jedinke (oponasa mutacije koje se u prirodi desavaju usred spoljasnih faktora)


	Politika zamene generacija:
		-odredjuje kako se od postojecih jedinki i njihovog potomstva bira nova generacija.
		-neke jedinke u novo su losije od starih, a neke bolje, ali se ocekuje da se prosek popravlja

	Aloritam:
		- algoritam se najcesce zaustavlja, kada je dostignut zadati broj generacija, kada je dostignut zaljeni nivo kvaliteta populacije
			ili neki drugi uslov.
		- funkcija cilja moze biti definisana tek kada su dostupne sve neophodne informacije koje precizno zadaju problem.

		 Ulaz: opis problema na osnovu koga se definise fja cilja, ali i podesavanje algiritma za konkretan problem.
		 Izlaz: najkvalitetnija jedinka u trenutnoj populaciji
		1. Generise pocetnu populaciju
		2. Izracunaj prilagodjenost svake jedinke
		3. izvrsavanj petlju sve dok nije zadovoljen uslov zaustavljanja
			* izaberi skup jedinki za reporodukciju - SELEKCIJA
			* kreiraj nove jedinke i racunaj prolagodjenost - MUTACIJA i UKRSTANJE
			* kreiraj novu generaciju
		4. vrati najkvalitetniju jedinku u poslednjoj populaciji


	Komponente genetskog algoritma - moraju biti poznate pre pocetka alg:
		1. reprezentacija jedniki:
			-izbor genetskih operatora znatno utice na efikasnos genetskih algoritama.
			-moze se reprezentovati u vidu niza binarnih cifara, matricama, stablima...
			-najcesce se koristi niz binarnih cifara. Gde svaka cifra predstavlja jedan gen, a cio niz hromozom.
			-pogledaj za interval jos jednom

		2. funkcija prilagodjenosti
			-daje ocenu kvaliteta jedinke,
			-dosta utice na efikasnost algoritma
			-treba da zadovoljava:
				-prikazuje kvalitet jedinke
				-definisana za sve moguce jedinke
				-da se brzo izracunava
			-posto odredjuje ocenu jedinke, sto je veca to je veca verovanoca da ce jedinka koristiti za kreiranje naredne generacije
				pa se kroz generacije ocekuje da ukupna prilagodjenost bude sve bolja i bolja

			-za fju prilagodjenosti moze se koristiti i fja nad kojoj se trazi fja prilagodjenosti.
			-fja cilja i fja prilagodjenosti ne moraju da se podudaraju.

		3. inicijalizacija - proces generisanja pocetne populacije
			-najcesce se generise slucajno (ako binarno najcesce od 0 do 2^n-1 gde je n duzina hromozoma)
			-mogu se dodati neke specificne jedinke, ili se citava populacija moze generisati koriscenjem nekog drugog metoa
			-ponekad postoji ogranicenje nad nekim jedinkama pa i to ogranicenje treba uzeti u obzir prilikom kreiranja slucajnih jedinki
			-i u kasnijim fazama treba voditi racuna o neispravnim jedinkama, koje su se pojavile ali ne ispunjavaju uslov za cilj.
				Takve jedinke se koriguju nekim postupcima

		4. selekcija - obezbedjuje cuvanje i prenosejie dobrih osobina na sledecu generaciju.
			-u svakoj gen deo jedinki se izbdvoji za reprodukciju i generisanje nove generacije.
				Koje jedinke ce biti izdvojene govori funkcija prilagodjenosti - sto veca prilagodjenost veca sansa za potomstvo
				ali ponekad se i biraju random, sa verovatnocama izvedene iz prilagodjenosti, to dovodi do odrzanja raznolikosti
			Strategije za selekciju:
				1. Ruletska - selekcija u kojoj vece sanse imaju prilagodjenije jedinke
					f(i) - prilagodjenost za jedinku i
					N - broj jedinki
					verovatnoca da ce biti izabrana je: pi = f(i)/SUMA(j,N)f(j)
					samo ako fja prilagodjenosti ima pozitivne vrednosti
					moguce je da se jedna jedinka vise puta izabere i ucestvuje u sledecoj gen i reproduk.
						preveliki broj ponavljanja istih jedinki lose utice na performanse algoritma.
				2. Turnirska - jedinke igraju turnire i vece sanse za pobedu imaju one prilagodjenije
					Parametri: p - verovatnoca, k - velicina turnira
					bira se random k jedinki, koje se sortiraju po prilagodjenosti
					i-ta jedinka se bira sa verovatnocom p(1-p)^(i-1)
					ako je velicina turnira velika - nekvalitetne imaju manje sanse da budu izabrane
					ako je k = 1 => slucajna selekcija
					ako je p = 1 => deterministicka turnirska selekcija - bira se najbolja jedinka u svakom turniru
					ako je jednom izabrana, moze se zabraniti ucesce u narednim turnirima

		ukrstanje i mutacija su genetski operatori
		5. reprodukcija - ukrstaju se dve jedinke (roditelji) koje su izabrane u procesu selekcije
				rezultat su jedna ili dve nove jedinke (deca), nasledjuju osobine roditelja, prilagodjenost (nekad imaju i bolju)

				nacini ukrstanja kada se koristi binarna reprezentacija:
					1. visepoziciono ukrstanje - izaberemo tacke prekida i po tome ukrsamo... broj tacaka moze da bude proizvoljan.
					2. uniformno ukrstanje - svaki bit prvog roditelja sa verovatnocom p se prenosi na dete i sa verovatnocom 1-p 							na drugo dete. Verovatnoca je 0.5 uglavnom, ali moze biti i drugacija.

		6. mutacija - primenjuje se nakon ukrstanja. Ona sa nekom malo verovatnocom menja deo jedinke.
			Obicno je taj deo dosta mali, i dobija se kao parametar algoritma. Uglavnom se menja 1 bit.
			Od jedne jedinke nastaje druga.
			Sprecava da jedinke u populaciji postanu isuvise slicne, i obnavljaju izgubljen genetski materijal
			Cesto omogucava izbegavanje lokalnih ekstremuma. Vec se razmatraju novi prostori u nadi da ce se naci globalni ekstremum.
				dovoljno je da se jedna jedinka priblizi glob ekstremumu, pa ce uskoro kroz generacije sve jedinke biti tu.
			Ukoliko je verovatnoca mutacije velika - ona lici na slucajnu pretragu
			ukoliko je verovatnoca mmutacije mala - skoro da nema mutacije, i ona ce dostici neki lokalni ekstremum

		7. politika zamene generacije - opisuje kako se od tekuce generacije dobija nova
			podela:
				1. generacijski genetski algoritmi - selekcijom se biraju jedinke iz tekuce generacije tako da se moze napraviti
						cela nova generacija, ukrstaju se mutiraju i tako nova generacija zamenjuje staru.
				2. genetski algoritmi stablinog stanja - cim se izabere par roditelja vrsi se ukrstanje i mutacija
						i umetanje potomaka u populaciju nekom politokom zamene.
						neke od politika zamene su:
							1. zamena najgorih - novi menjaju najmanje prilagodjene
							2. nasumicna zamena - nasumicno zamenjuju
							3. tacmicenje roditelja i potomaka - potomci zamenjuju roditelje ukoliko su bolji
							4. turnirska zamena - bira se kao kod turnirske gore samo sto se biraju najgore prilagodjeni
				Elitizam - nekoliko najboljih jedinki se stite od eliminisanja ili bilo kakvih izmena i takve se prenose u sledecu 							generaciju. Spreceva da se pokvari vec dobra jedinka. Moze se koristiti i u 1 i u 2.
		8. zaustavljanje - izvrsava se algoritam dok se ne dodje do nekog od uslova zaustavljanja
			* pronadjeno je resenje koje zadovoljava unapred zadati kriterijum
			* dostignut je zadati broj generacija
			* funkcija prilagodjavanja je izracunata zadati br puta
			* brednost prilagodjenosti najbolje jedinke tokom odredjenog bra generacija nije popravljen
			* kombinacija nekoliko uslova


svojstva genetski algoritama:
	1. ciljna funkicja - moze biti proizvolja, i ne mora da zadovoljava nikakve uslove (ni diferencijabilna, nista)
		ali cesto u razlicitim problemima zadaje se implicitno (nije eksplicitna) kroz veci broj kriterijuma.
	2. reprezentacija jedinki, fja prilagodjenosti i operatori
		izbor gore navedenih stvari je kljucan za efikasnost algoritma (kvalitet i brzina). Ipak za mnoge probleme je unapred
		tesko odrediti funkciju prilagodjenosti, jer se ne moze oceniti sta je resenje a sta ne. Na pocetku, reprezentacija jedinki
		fja prilagodjenosti i operatori se prilagodjavaju problemu a onda se vrsi prilagodjavanje parametara algoritmu.
	3. paramerti algoritma - velicina populacije, verovatnoca ukrstanja, verovatnoca mutacije su dosta bitni za performanse.
		Cesto se izaeru parametri koji daju lose performanse, a optimizacija se vrsi probnim resavanjem i dosta je kompleksna.
		Parametri ne moraju biti fiksni, vec se mogu menjati tokom rada.
	4. domen genetskih algoritama - dosta su primenjeni, ali za uspesno resavanje potrebno je napraviti puno dobrih izbora
	5. kvalitet resena - ne daje garanciju da je pronadjeno resenje globalni optimum, cesto idu ka lokalnom optimumu, jer je dolazak do globalnog			tezak. Cesto pronadjeno resenje je dovoljno dobro, i moze se ponuditi skup najboljih pronadjenih jedinki.
	6. zahtevani resursi - jednostavno se implementiraju, ali je potrebno prilagoditi konkretnom problemu. Cesto je izvrsavanje veoma zahtevno
		te se mogu pogodno i efikasno paralelizovati.




4. strateske igre
==================

	Tores Kevedo - 1910 konstruisao elektor-mehanicki uredjaj "sahista" koji je kao beli igrao kralj i top protiv kralja i iz svake poz pobedjivao				iako ne u najmanjem broju poteza.
	Fon Nojman - 1928 opsti problem igranja igara.
	Klod Senon - 1950 u claku "programiranje digitalnog racunara za igranje saha" opuisao je sve stratekije izbora poteza A i B
		A - minimax (lookahead) - bira se potez sa najboljom ocenom
		B - (lookup table pristup) - potez ze bira na osnovu stanja u igri i na osnovu unapred pripremljene tabele.
					   - u tabeli sa dve kolone u jednoj se nalazi trenutno stanje a u drugoj optimalan potez za to stanje
	Kenet Tompson - 1977 koriscenjem lookup pristupa kreirao "kralj i kraljica protiv kralja i topa"
	Lomonsov tabele - 2012 - tabele optimalnih poteza za sve zavrsniice (za najvise 7 figura)

	razlikujemo legalne ppozicije i legalne poteze.
		legalne pozicije: pocetne, krajnje...
		legalan potez: dalje...
	one se predstavljaju preko usmerenog grafa - pozicije cvorovi, potezi grane

	stablo igre - stablo naizmenicno 2 igraca
	kompletno stablo igre - koren je pocetna pozicija, a svi listovi su zavrsne pozicije.

otvaranje:
	biblioteka otvaranja - sadrzi informacije po poznatim i kvalitetnim potezima na otvaranu.
	moze biti staticka ali moze se i prosirivati tokom izvrsavanja.

	biranje verovatnoce poteza na nekoj poziciji: pi = mi/suma(j=1,n)mj - bolji potezi ce se birati cesce ali ne uvek.

sredisnjica:
	Da bi se odredio dobar potez trenutnog igraca, cvorovima se pridruzuju vrednosti (funkcija evaluacije) te potezi mogu da se porede po kvalitetu
	Ona se dodeljuje poziciji, pazeci na specificnosti igre, i ne ispituje prednone niti naredne poteze.
	od fje evaluacija navise zavisi kavalitet igre programa.
	Potrebno je da ima sto vise relevantnijih informacija, ali sa druge strane kako se mnogo puta izracunava, potrebno je da bude sto prostija.
	Obicno preslikava skup svih mogucih pozicija u skup celih ili brojeva u pokrentom zarezu:
			F:P -> [-M,M] - vrednosti M gde je pobednik prvi igrac, -M gde je pobednik drugi igrac
	Najjednostavnija je trovrednosna funkcija koja se primenjuje na zavrsne cvorove, ali posto treba doci do zavrsnih cesto se ide dosta duboko
			pa je gotovo ne upotrebljiva. Ima vrednosti 1 - prvi pobedio, -1 - drugi pobedio, 0 - nereseno
	ocene zavrsnoh pozicija ne moraju biti staticke - mogu se menjati dubina, kako bi se nasao najmanji broj koraka

	Minimaks: odredjuje najbolji moguci potez u datoj situaciji (najbolji - za zadati cvor, za zadatu dubinu, i za fju evaluacije)
			funkcija evaluacija za igraca koj je na potezu - biramo vecu vrednost (njemu odgovaraju pozitivni)
			a za protivnika biramo manju vrednost
		  ocene se dodeljuju samo najdubljim cvorovima (oni ne moraju biti zarsni)
		  algoritam vrsi izbor poteza na osnovu cvorova na max dubini i ne gleda dalje - a te info mogu biti veoma korisne
		  efekat horizonta - ne vide se ni cvorovi pre ni posle, samo svorovi na nekoj fiksnoj dubini

	Alfa-Beta: sredinom dvadesetog veka - algoritam zasnovan osdecanju stabla igre, heuristikama ubrzan minimax
		Semjuel, Ricards, Hart, Levin, Edvards - ranu verziju algoritma pocetkom 50tih, nezavisno Semjuel
		Makarti - 1956 - slicne ideje
		Brudno - 1963 - nezavisno otkrio i objavio A-B
	ideja kako se radi
	nalazi nabolji moguci potez
	ima najbolji efekat kada se potezi ispituju pocevsi od najboljeg, a isti kao minimaks kada se ispituje od najlosijeg ka najboljem (tekucem cv)
		tako se moze poboljsati alfa beta algoritam

	Heuristika killer: zasniva se na cinjenicama i ne korisi specificna znaja o igri
		killer potez - najbolji potez na nekoj dubinid
			u svakom sledecem cvoru na dubini d ispitivanja pocinjemo sa killer potezom za tu dubinu
			ukoliko se nadje bolji potez za taj cvor, taj potez postaje killer
		upotreba killer heuristike u alfa beta naziva se alfabeta/killer algoritam.
		ne menja rezultat alfa bete
		ideja: ako je na dubini d najbolji potez W ima izgleda da je najbolji i u drugim stablima na istoj dubini
		legalni potezi treba da budu organizovani u ciklicni niz i da svaki potez jednoznacno odredjuje drugi (legalan)

	iterativni algoritam ABkiller: 	za razliku od rekurzivnog postoji i killer potez za popocetni cvor u pretrazivanu.
					kada dodje do prekida, ima smislen rezultat tj najbolje pronadjen potez za neku iteraciju
			mana: visestruko pretrazivanje nekih cvorova.
			plus: ovo gore, zavrsna iteracija ispituje manji br cvorova od rekurzivnog
			modifikacija: da se vrse samo prva i poslednja iteracija

ALFA-BETA, MINIMAKS, Killer, killer iterativni - najbolji potez za datu fju evaluacije i dubinu

	stabilno pretrazivanje: vrsi se pretrazivanje do neke fiksne dubine, ali se pretrazivanje nastavlja ukoliko je cvor nestabilan
				po nekim kriterijumima a taj kriterijum zavisi od igre do igre (moze i u isto igri razlicit da bude)
	prekid: najbolji iterativni ab killer jer u svakoj iteraciji ima resenje koje je dovoljno dobro

zavrsnica:
	taktika je korektna ako u trenutnoj poziciji vodi do pobede, ili u remi poziciji vodi do remija
	taktika je optimalna ako do pobede vodi u najmanjem br koraka ili gubitak maksimalno odlaze.
		optimalna taktika je korektna ali ne vazi obrnuto

	bramerov opsti algoritam - algoritam za zavrsnicu 1975
		skupovi pozicija kao klasa ekvivalencije
			1.generise skup svih legalno poteza
			2.izabere najbolji potez iz skupa poteza
			3.odigra najbolji potez

implementacija: legalni potezi - ciklicni
		fja evaluacoje - celobrojna