Znanost i algoritmi, drugi dio

Prije nekoliko mjeseci u postu Znanost i algoritmi pisao sam o nekim znanstvenim radovima u kojima glavnu ulogu igraju algoritmi ne toliko različiti od onih na natjecanjima. U međuvremenu sam se sjetio još dvaju dobrih primjera u kojima glavnu ulogu igraju naši algoritmaši. Za početak spomenimo članak u kojem su naši bivši uspješni natjecatelji (Goran Žužić i Filip Pavetić) objavili efikasan algoritam računanja sličnosti stringova. A o drugom primjeru treba napisati nešto više, pa krenimo.

Na 1. kolu HONI-ja 2012. postavio sam zadatak Mars. U njemu je riječ o potpunom binarnom stablu u kojemu možemo proizvoljno zamijeniti lijevo i desno podstablo bilo kojeg vrha – ili, ekvivalentno, odabrati permutaciju listova u kojoj svako podstablo i dalje pokriva uzastopan podniz – tako da zbroj “odbojnosti” susjednih listova (koja je definirana za sve parove u ulaznim podatcima) bude što manji.

Zanimljivo je da sam poslije naišao na znanstvene radove koji rješavaju isti problem. Ovaj članak rješava isti problem za PQ-stablo i primjenjuje ga na poznati problem trgovačkog putnika (Travelling Salesman Problem ili TSP). U ovom članku problem se rješava za K-arna stabla (u binarnom stablu je K = 2) i primjenjuje u bioinformatici za sortiranje gena. Algoritmi i jednog i drugog članka svode se na O(n^3) za binarno stablo, što je i složenost mog rješenja u zadatku Mars.

Ali to nije najbolja moguća složenost! Kao što pokazuje ovaj članak Urlika Brandesa, problem za binarna stabla moguće je riješiti u O(n^2 \log_2 n). Zanimljivo je da je jedan natjecatelj na samom natjecanju pronašao takvo, brže rješenje (o kojem je, dakle, netko prethodno napisao znanstveni rad) – to je bio Luka Kalinovčić na COCI natjecanju. Nakon što sam proučio njegovo rješenje, opisao sam ga (uz vlastito) u službenim rješenjima, tada još ne znajući za cijelu ovu priču. Svaka čast Luki!

Spomenimo i da navedeni Brandesov članak navodi još neke primjene ovog problema kao što je sortiranje piksela u svrhu sažimanja slika, te je predloženi algoritam zbog memorijske složenosti od O(n) bolji od algoritma iz članka koji se izvorno bavi tim praktičnim problemom.

Komentiraj

Popunite niže tražene podatke ili kliknite na neku od ikona za prijavu:

WordPress.com Logo

Ovaj komentar pišete koristeći vaš WordPress.com račun. Odjava /  Izmijeni )

Google photo

Ovaj komentar pišete koristeći vaš Google račun. Odjava /  Izmijeni )

Twitter picture

Ovaj komentar pišete koristeći vaš Twitter račun. Odjava /  Izmijeni )

Facebook slika

Ovaj komentar pišete koristeći vaš Facebook račun. Odjava /  Izmijeni )

Spajanje na %s