Izgleda da ideš na isti fakultet kao i kolega:
http://www.elitesecurity.org/t...c-oko-simulacije-igre-Moj-broj
Citat:
Trebam napraviti simulaciju igre "Moj broj" iz TV Slagalice... Random biramo 7 brojeva. Prvi , rezultat, iz skupa 0 do 999. Naredna 4 iz skupa {1,..., 9}. 5. iz skupa {10, 15, 20} i poslednji broj iz skupa {25, 50, 75 , 100}. Dozvoljene operacije su *,/, - , + i zagrade.
Program treba naći formulu koja daje tačan ili najbliži rezultat. U prinicpu, rezultat ne mora biti tačan, testira se na 20 kombinacija brojeva, pa se najbliži uzme.
Treba implementirati genetički algoritam. IDeja je da se formula razvuče u binarno stablo pa se obilazi, ali kako dobiti random formulu i implementirati stablo u javi?
Evo kako radi postfiksna, tj.inverzna poljska notacija (RPN - Reverse Polish Notation):
http://en.wikipedia.org/wiki/Reverse_Polish_notation
Tvoje pitanje, koji algoritam da se koristi, je potpuno suvišno - MORAŠ da koristiš genetski algoritam. Malo mi je čudno da profesor/asistent zada takav zadatak, a da niko ne zna šta je to genetski algoritam. Pa još niko ne zna ni šta je to postfiksna notacija, a neki ne znaju ni kako da implementiraju stablo u Javi.
Recimo da radimo sa postfiksnom notacijom.
Izraz A+B bi se u postfiknoj notaciji pisao kao AB+. Dakle, prvo argumenti operacije, a onda operacija. Na linku koji sam ti dao ima opisan algoritam kako se od infiksne notacije dobija postfiksna notacija, kao i drugi interesantni linkovi.
U problemu koji ti treba da rešiš, treba da od 6 konstani i 4 računske operacije dobiješ što približniji rezultat nakoj sedmoj konstanti.
Imamo konstante A,B,C,D,E,F ciljni rezultat X i 4 operacije +,-,* i /
Evo je gramatika koja opisuje izraze u postfiksnoj notaciji:
KONSTANTA := A | B | C | D | E | F
OPERACIJA := + | - | * | /
IZRAZ := KONSTANTA | IZRAZ IZRAZ OPERACIJA
Dodatno ograničenje je da se jedna konstanta sme pojaviti samo jednom u kompletnom izrazu.
Primeri regularnih izraza su, na primer, A, AB+, ABC+* itd.
E, sada kako ovo "ubaciti" u genetski algoritam:
Neka je postfiksni zapis izraza GENETSKI KOD crvića koji teži broju X. Potrebno je napraviti funkciju koja kaže koliko je taj crvić blizu rešenja. Ovo je uvek najteži deo u pravljenju genetskog programa (u stvari u bilo kom programu koji koristi heuristiku - kako oceniti koliko smo blizu optimalnom rešenju, kao na primer koliko je mogući potez u šahu dobar).
Meni, recimo pada na pamet, da napravim više funkcija koje to opisuju, jedna bi bila razlika između broja X i vrednosti izraza, druga bi bila količnik broja X i vrednosti izraza. Sada, koliko je to dobro, zavisi od vrednosti konstanti i ciljnog broja. Na primer, ako je jedan crvić udaljen za 6 od ciljnog broja, a postoji neka konstanta koja je jednaka 6, onda je to jako dobro. Ili, ako je vrenost crvića 1/2 tražene vrednosti, a postoji crvić sa vrednošću 2 ili konstanta 2 i to je jako dobro...
Sledeće, generiše se prva generacija N crvića sa slučajnim genetskim kodom (a koji predstavlja jednu od mogućih i dozvoljenih postfiksnih zapisa izraza). Oceni se koliko su dobri, a zatim sledi sledeća generacija.
Sledeća generacije se dobija MUTACIJOM i UKRŠTANJEM. Mutacija je proces u kojem se na slučajnom mestu u genetskom kodu promeni neki gen.
Recimo, crvić koji ima genetski kod AB+, može mutacijom da postane AC+ (dakle, drugi gen "B" je mutirao u "C").
Ukrštanje dva crvića daje novi organizam. Recimo crvići AB+ i CD* mofu da se ukrste tako što se povežu nekom operacijom, recimo -, pa se dobije AB+CD*-.
Još jedna vrsta mutacije bi bila da se u genetski kod jednog crvića izbaci jedan gen a ubaci genetski kod drugog crvića. Opet na primeru AB+ i CD* zamenom B dobijemo crvića ACD*+.
Neki crvići koji su jako loši (jako daleko od X) umiru, a jako dobri mutiraju ili se ukrštaju sa drugim uspešnim crvićima.
Tako se formira K generacija, pa se onda kao rešenje prikaže onaj crvić koji je najbliži rešenju.
A sada, stvarno, pravac Google pa potraži genetske (evolucione) algoritme.