Nelinearni kombinatorni optimizacioni problem
Evo jednog, nadam se, zanimljivog problema. Ja se vec godinu dana patim sa njim
(doduse, ne intenzivno) i stvarno ne znam gde jos nisam pitao.
Istina, problem mi se cini poznatim, definitivno je tipski, a i veoma podseca
na neki od zadataka sa recimo ACM takmicenja. Nevolja je sto ja bas i nemam
bogzna kako bogatu literaturu iz teorije algoritama, a na net-u nisam uspeo
nista da iskopam. Rezultat nije bio nista povoljniji ni u slucaju ES foruma
"Art of Programming" kao i nekih stranih news grupa koje se bave slicnom
tematikom. Program za koji mi je ovo trebalo verovatno i nema neku upotrebnu
vrednost, ali me zivo interesuje (sada samo teoretsko) resenje problema.
Posto se zadatak pogresno prelama (i pored `code' tagova u poruci), zakacio sam
ga uz poruku, a najnoviju "verziju" uvek mozete naci na:
http://tesla.rcub.bg.ac.yu/~dux64/algo/x-rle.txt.
Problem (zamalo) spada u kategoriju neresivih (bar njegova optimalna solucija)
jer je slozenost algoritma oko 2^N (ili veca). Ne trazim gotovo resenje,
potrebna mi je samo pomoc oko heuristike; interesuje me da li postoje bilo
kakve zakonitosti koje bi mogle znacajno (zapravo, drasticno) da smanje broj
pokusaja/proba prilikom ispitivanja, a samim tim i vreme potrebno za
pronalazenje optimalne kombinacije.
Posto je problem kombinatorne prirode, mislim da se moze naci i na jednom
ovakvom, strogo-matematickom forumu ("okoreli" matematicari neka mi ne zamere,
oni mogu posmatrati kompresiju kao `k(x)' i sl.).
Hvala unapred.
$dux
 |  |
 |
