[ antraks @ 02.04.2015. 10:43 ] @
Da li moze neko da mi pomogne oko zadatka sto sam dobio da uradim? U pitanju je igra moj broj iz slagalice.

Igra „Mala matematika“ se igra na sljedeći način:
Na raspolaganju je 7 brojeva – 4 jednocifrena, jedan iz skupa {10, 15, 20} i jedan iz skupa {25,50, 75, 100}, te jedan iz opsega [1, 999] koji se naziva rezultat. Korištenjem prvih 6 opisanih brojeva (svaki broj najviše jednom) i proizvoljnog broja zagrada, te matematičkih operacija +, -,* i / potrebno je dobiti 7. broj – rezultat.
Implementirati genetički algoritam koji za datih 6 brojeva daje formulu kojom se dobija traženi rezultat (ili rezultat što bliži traženom). Algoritam testirati na 20 kombinacija brojeva koje mogu dati tačan rezultat.

Jedna ideja koju je asistent predlozio je da se napravi binarno stablo od brojeva i znakova operacija. I onda obici stablo pa dobiti izraz koji bi dao neku slucajnu vrijednost. I nesto sa postfiksnim oblikom i slicno. Nisam najbolje razumio.
Kojim algoritmom bi ovo bilo najbolje raditi? Prvi put se susrecem sa genetickim algoritmima pa mi bas i nisu najjasniji. Svaka pomoc je dobrodosla.
[ djoka_l @ 03.04.2015. 13:08 ] @
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.
[ antraks @ 03.04.2015. 16:42 ] @
Aj sto idemo na isti fakultet nego imamo isti zadatak. A nema rada u paru :D

Odmah da se zahvalim na ovako izdasnom odgovoru. Dosta si mi (nam) pomogao. Hvala puno.
Sada se treba uhvatiti posla i pokusati to uraditi.
Ovo objasnjenje oko "ubacivanja" u genetski algoritam mi je trebao. Nisam znao kako to sve da povezem da ima nekog smisla.


Odoh sada da proucim algoritme da vidim kako bi to sve islo. Jos jednom hvala.

[ MilanMilan @ 02.09.2015. 10:50 ] @
Vako nesto: https://play.google.com/store/apps/details?id=com.lanmil.mynumber ?