MilosSavic
Član broj: 61272 Poruke: 24 *.pat-pool.nsad.sbb.co.yu.
|
Naravno da jeste lakse i jednostavnije napisati u Prologu. Zasto?
Ako pogledas, aritmeticke izraze lingvisticki mozes zapisati u sledecoj gramatici:
expr->expr + term
| expr - term
| term
term -> term * factor
| term / factor
| factor
factor -> number
|unop number
| (expr)
unop -> +|-
Sada ovo lako mozes pretociti u proloske klauze bas isto ovako :), tj. od svake gramaticke produkcije pravis jednu prolosku klauzu. Svaka klauza ima kao argument listu, sa tim sto expr kao argument ima listu svih "zaustavljenih" brojeva, kasnije kako propadas backtrackom kroz klauze smanjujes tu listu, tako da ti klauza faktor ima kao argument najcesce jednoelementnu listu i ta klauza je zadovoljena ukoliko je nesto sto je prosledjeno njoj nije prazna lista (*tj, ako je jedan od izabranih brojeva, onda super, a ako nije onda opet pokusavas da zadovoljis expr klauzu *). Prva klauza tvog proloskog programa bi onda trebala biti jednostavna klauza koja pravi permutacije liste odabranih brojeva, a zatim pokusava da zadovolji klauzu expr :) Sve u svemu 11 linija koda :)
O performansama je izlisno govoriti jer mi uglavnom danas programiramo na racunarima cija je arhitektura naredbi prilagodjena imperativnim programskim jezicima, verovatno bi na procesoru koji ima u sebi hardverski ugradjene mehanizme supstitucije i rezolucije ovaj programcic znatno brze radio nego ekvivalent zapisan u nekom od imperativnih programskih jezika (*a secam se kada sam imao 10 godina (*a to je bilo pre 10 godina (* ugnjezdeni komentari, zivela Modula-2 *) *) takvi racunari, tj. racunari pete generacije koji imaju bas to ugradjeno su pompezno najavljivani, posle je projekat propao, mada su i kod nas objavljene neke knjige na tu temu *)
Ako pogledas tvoj program, on ima red velicine 10^2 linija, mozda je moglo i manje da nisi pokusavao da nam/asistentu pokazes da znas da programiras u C-u (*kako volim te programere koji pisu svoje programe koristeci najegzoticnije mogucnosti C-a *) Cak, ne znam zasto odzavas svoju strukturu binarnog stabla, kada si se usmerio na rekurzivno nametnuto resenje problema (*ah, sve je rekurzija *), posto u toku rekurzije na steku imas interno odradjeno to tvoje stabaoce :)
Da se vratimo opet na Prolog, resenje u prologu, iako elegantno, u sebi krije manu, jer ako vi njemu kazete
?-solve([3, 4, 5, 8, 10, 75, 345])
on vam kaze yes/no i istampa resenje, medjutim sta ako resenja nema :) E onda, nista od prologa, nego se opet moramo dovijati u imperativnim programskim jezicima :)
Vec sam pomenuo da bi bilo dobro napraviti neku heuristiku :) Jer sigurno je onaj igrac koji ucestvuje u igri ne pravi sve kombinacije zaustavljenih brojeva, jos gore prateci neki backtrack algoritam :) Uigrani igraci znaju da postoji nekoliko fora na tu temu :) Evo recimo prva heuristika: neka se treba konstruisati broj a, pri tome je broj b jedan iz skupa {50, 100, 75}, c jedan iz skupa {10, 15, 20 (*ili tako nesto *)}, a d onaj jedan od cetiri jednocifrena :) Tada je ono sto bih ja prvo probao da uradim podelio a sa b i dobio c1, zatim podelio c1 sa c i iz skupa d odabrao onaj koji je najblizi c1/c i super imam jedno resenje (jer opet napominjem, cilj igre nije samo dobiti tacno resenje, jer mozda ono i ne postoji)... Ono sto se postavlja kao pitanje koje se uvek postavlja kada se problem resava heuristicki jeste uspesnost te heuristike (* Ova verovatno i nije bas nesto uspesna *), tj, trebalo bi sada napisati monte-karlo simulaciju koja ti razigrava tvoj univerzum brojeva i resava prvo heuristikom, a onda standardno bektrekom i za razigranih recimo N univerzuma, nadji n, tj. broj slucajeva kada se resenja poklapaju :) Tada se uspesnost heuristike meri kao verovatnoca n/N sa greskom koja se skalira kao koren iz jedan sa N... Siguran sam da se nadgradnjom ove heuristike (tj, ubacite malo if-ova, pokusavate da delite sa nekim zbirom iz unije skupova c i d), mogla dobiti veoma uspesna heuristika koja radi u vremenu O(1) a sto bi nam i svima bio cilj :) Jer poenta heuristickog pristupa jeste (*da se filozofski odrazim *) ne menjati entropiju univerzuma, ako si vec u tvojim monte-karlo simulacijama heuristike izracunao p (*koje su opet slozenosti onolike kolike ti zelis da budu, jer ti odredjujes sa koliko procesorskog vremena zelis da pretrazujes tvoj kompleksni univerzum u potrazi za specijalnim slucajevima koje ruse tvoju heuristiku, monte-karlo je super jer je O(n) (*jer je najobicniji random walk kroz tvoje stablo univerzuma *) a uvek znas sa kolikom greskom si ocenio p *), samo sklopis resenje, kao da je uvek bilo tamo :)
E Andrejko, eto jurim ove moje po forumima :) Vidimo se u skorije vreme u PSC, vrlo je verovatno :) Jedino ako ne odes na tu olimpijadu, pa postanes izgubljena dusa kao i ostali koji zavrse u toj sekti :)
Drugo ne vidim da je iko razmisljao o ona dva zadacica... Verujte mi veoma su korisna :) Ako sami to izmozgate, jos posebno ako ste mladi, recimo 7. ,8. ili 1. razred onda je stvarno velika slava i veliki putevi pred Vama :) Ja sam sa ta dva primera, tj. sa prvim pokusao klincima koji su sedmi razred da objasnim zasto je dobro ponekada promeniti referentni sistem, tj. ugao na koji gledas na problem :) Reci cu samo jos ovo, ako biste pokusali da napisete program koji bi Vam konstruisao resenje (*sto je naravno moguce ako ste pratili ovaj post *), onda Vam kazem takav program ne mozete napisati u strogo tipiziranim programskim jezicima (*aka, java, modula-2*)? (*nadam se da cete posle ovoga ostati zaintrigirani *), a ako uspete da izmozgate drugi zadatak, onda ste verovatno izmislili Peanovu aksiomatiku, osetili potrebu lingvistickog pristupa u matematici (*vec pomenute gramatike *) i pronasli dve od tri fundamentalne funkcije u teoriji rekurzivnih funkcija koja je osnov matematickog zasinivanja racunarstva :) (* tj, ono sto mi mozemo i znamo da izracunamo jeste po svojoj prirodi rekurzivno (* fraktal, seko, fraktal *) *)
I toliko ne bih Vise da smaram cenjeni auditorijum :)
pozdravi Milos
|