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. Program za koji mi je ovo trebalo verovatno i nema neku
upotrebnu vrednost, ali me zivo interesuje 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.

Hvala unapred.

$dux

Niko ?!

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.

$dux

Uz svu opasnost da lupim, posto nisam detaljnije proanalizirao problem (sorry), zar nije zamena dzokera u okviru sekcije (ako zanemaris opseg [E,F]) ekvivalentna Huffman-ovom algoritmu?
Mozda bi uz malu modifikaciju (provera da li je suma tezina u opsegu pre spajanja) mogao da se iskoristi za ovo?

Tesko.

Problem je sto ovde ulazni niz ima specijalnu osobinu - sadrzi "oznacene"
bajtove (recimo, nekim pomocnim nizom indeksa ili specijalnom vrednoscu) kojima
treba dodeliti proizvoljnu vrednost ([A,B]), ali tako da se niz dobijen jednom
takvom vrstom preprocesovanja maksimalno kompresuje algoritmom koriscenim za
kompresiju. Ovaj algoritam diktira pravila odabira vrednosti X-objekata, tj.
direktno utice na pripremu (prilagodjavanje) niza za kompresiju.

Tako se, na primer, ulazni X-objekat tezine 10 (`xxxxxxxxxx') moze zameniti
izlaznim nizom `3122248779' (7 objekata), samo sto ovakva interpretacija nema
mnogo smisla u slucaju zadate RLE kompresije gde treba teziti sto duzim
sekvencama istih objekata (tu bi X-ove trebalo "dodeljivati" iskljucivo
susedima). Interval [E,F] je neizbezan i posledica je koriscenja bajtova kao
brojaca uzastopnih pojavljivanja istih objekata.

S druge strane, pomenuto Huffman-ovo kodiranje maksimalno pojednostavljuje
resenje problema: prvo se pronadje "normalni" objekat sa najvecom frekvencijom
pojavljivanja da bi se zatim njegov tip jednostavno dodelio _svim_ X-objektima.
Steta samo sto iz nekih drugih razloga ovaj vid kompresije (ukljucujuci
varijacije i slozenije algoritme) nije opcija.

Zadatak je kombinatorne prirode, a neki kazu da podseca na klasicni bin-packing
problem (problem optimalnog izbora), samo sto ovde objekti (ulazni niz) nisu
"fiksni".

Par korisnih linkova (medju prvima na Google-u):

Run Length Encoding (RLE)
http://www.rasip.fer.hr/research/compress/algorithms/fund/rl/

Huffman Encoding
http://www.itee.uq.edu.au/~inf...ial%20Exercises/tutorial9.html

The Bin Packing Problem
http://eng.murdoch.edu.au/EngM...mo/Section01/Section0102c.html


/dux