U kakvoj su vezi efikasno pakovanje putne torbe, spajanje komponenti matične ploče i problem trgovačkog putnika?
Tekst: Slađana Šimrak
Prodajom Ikozijanske igre jednom londonskom dileru 1859. godine, Vilijam Hamilton je zaradio ukupno dvadeset pet funti. Sudeći po njegovom biografu, ovo je bio jedini novac koji je Hamilton zaradio na svojim otkrićima i publikacijama. Diler je imao dobro oko: igra je, iako lagana, zaživela i bila je distribuisana u više prodavnica širom Engleske i kontinenta.
Za igranje je potrebno imati čovečuljka i dodekaedar. Svako teme dodekaedra predstavlja po jedan grad. Čovečuljak se inicijalno nalazi u nekom gradu i ima za zadatak da, putujući po ivicama tela, obiđe sve gradove tako da u svaki svrati samo po jedanput, i da se potom vrati u mesto iz kog je krenuo.
Slične zanimacije su u nekom obliku postojale i mnogo pre Hamiltona. Zabeleženo je da je još u devetom veku indijski pesnik Rudrata sastavljao strofe takve da se njihovi stihovi mogu čitati na dva načina: uobičajeno, s leva na desno, ili tako što se, polazeći od početka, do svake naredne reči stiže skakanjem po strofi poput skakača u šahu. Skakačeva putanja zanimala je mnoge pisce, pa ako ubrzamo do dvadesetog veka, naići ćemo npr. na roman Žorža Pereka, Život uputstvo za upotrebu, pisan po ovom šablonu. Ali, njime su se njime zanimali i matematičari. Prvi je bio Leonard Ojler, ali je konačno rešenje postavio nemački matematičar H.C. fon Varnsdorf.
No, Ikozijanska igra je, više nego po svojoj tadašnjoj popularnosti, ostala upamćena kao primer jednog od najpoznatijih računarskih problema današnjice, i jednog od onih koji su se najviše proučavali – problema trgovačkog putnika. Njega je formalno definisao bečki matematičar Karl Menger, tridesetih godina prošlog veka, gostujući na Harvardu, konačno podstičući interes naučne zajednice za njegovo rešavanje.
Pohlepna metoda
Problem je postavljen slično Ikozijanskoj igri, ali sa jednim dodatkom: potrebno je, među svim mogućim rešenjima, pronaći najkraću putanju takvu da se obiđu svi gradovi. Dakle, trgovac pred sobom ima određen broj gradova koji mora da obiđe i da se potom vrati u onaj iz kog je krenuo – kako da isplanira posete tako da uštedi troškove puta što je više moguće?
Zadatak ne zvuči teško. Uobičajen postupak je da se korišćenjem iscrpne pretrage prebroje sve moguće putanje, i da se potom odabere najoptimalnija. Ovo je metoda koja gotovo trivijalnim putem dovodi do rešenja ako je u igri manji broj gradova.
Druga metoda koja se često koristi je pohlepna metoda. Ideja ove metode je da se krene od proizvoljnog grada i da se za naredni bira uvek onaj koji je najbliži. Ovaj algoritam često daje dobro rešenje, ali kako ne uzima u obzir sve podatke, nije sasvim pouzdan. Takođe se koriste i genetski algoritmi, zasnovani na evolucionim mehanizmima. Njihova prednost je što u razumnom vremenu uglavnom daju rešenje koje je svega dva ili tri odsto lošije od optimalnog.
No, nijedna od njih ne predstavlja univerzalno rešenje koje će garantovati najbolji rezultat u svakom slučaju. Razlog neuspehu je vremenska složenost algoritama, koja je faktorijelna. To znači da povećanjem broja gradova ukupan broj putanja raste ogromnom brzinom i računarima bi praktično bilo potrebno beskonačno mnogo vremena da dođu do rešenja.
Tako, na primer, ukoliko trgovac na svojoj turneji mora da obiđe dvadeset jedan grad, on bi trebalo da bira najbolju od ukupno 20! putanja, što je zapravo broj 2432902008176640000. Zato se ovaj zadatak svrstava u takoreći nerešive, barem u opštem smislu, odnosno u zadatke takozvane NP klase.
Simbolom P označava se klasa problema za čije se rešavanje može pronaći algoritam koji ima polinomijalnu vremensku složenost. Ovo u najvećem broju slučajeva znači da računar za relativno kratko vreme može doći do rezultata. S druge strane, kada je reč o pripadnicima NP klase, efikasan algoritam za njihovo rešenje verovatno ne postoji. Postavlja se pitanje da li je moguće NP probleme svesti na P? Većina matematičara je saglasna da to verovatno nije slučaj, ali dokaz i dalje nije pronađen.
No, često je dovoljno zaustaviti se na dovoljno dobrim rešenjima, umesto nastavljati potragu za najoptimalnijim rešenjem. Tako razni problemi koji imaju velike praktične primene imaju u praksi zadovoljavajuća rešenja, a algoritmi koji služe nalaženju ovih zadovoljavajućih rešenja zovu se heuristike.
Nagrada od milion dolara
Međutim, zadatak P=NP, kao najpoznatiji nerešen problem u računarstvu, nalazi se među „Milenijumskim problemima“ za čije rešenje američki institut Klej nudi nagradu od milion dolara.
Nakon što je Grigorij Perelman pre petnaestak godina zatvorio poglavlje o dokazu Poenkareove hipoteze, na listi Milenijumskih matematičkih problema ostalo je njih šest koji i danas čekaju na rešenje. I svaki je vredan po milion dolara.
Zadatak P=NP ima tragove još u pedesetim godinama prošlog veka, i o njemu su tada pisali Džon Neš, Kurt Gedel i Džon fon Nojman, međutim zvanično je definisan 1971. godine, u radu Stivena Kuka.
Radi se, dakle, o dilemi: ako računar može dovoljno brzo da utvrdi da li neki problem ima rešenje, može li takođe brzo, pronaći to rešenje? Kako zbog svoje svakodnevne primene, tako izbog milenijumske nagrade, tek, putujući trgovac je tema koja redovno privlači i naučnike i mejnstrim medije.
Bumbareva napredna logika
Mali pčelinji mozgovi pobedili su računare. Tako je glasio naslov u Gardijanu, oktobra 2010. Povod za tekst bilo je istraživanje koje su nedugo pre toga sproveli biolozi sa dva londonska koledža. Oni su, naime, uočili da se bumbari u svom letu sa cveta na cvet, koriste naprednom logikom kako bi proces učinili što efikasnijim.
U početku, oko bumbara su bili postavljeni cvetovi tako da je svaki od njih sadržao istu količinu nektara. Bumbari su vrlo brzo, putem pokušaja i pogrešaka, naučili da odrede putanju kojom će utrošiti najmanje vremena i energije. Ali zatim su naučnici pred njih postavili teži zadatak: promenili su količine nektara tako da je svaki cvet imao različitu količinu. Time su naterali bumbare da odluče hoće li i dalje pratiti najkraću rutu ili će najpre posetiti cvet sa najviše nektara.
Bumbari su i ovde došli do zaključka povoljnog po sebe. Ukoliko bi procenili da će se dužina leta tek neznatno promeniti ukoliko prvo posete cvet sa najviše nektara, odlučivali bi da tako promene svoju putanju. U suprotnom, ukoliko bi se ukupna dužina značajnije povećavala, držali bi se najkraće rute koju su smislili na početku.
Sličan talenat za optimizaciju poseduju i mravi. Istraživač u oblasti veštačke inteligencije, Marko Dorigo, opisao je 1993. godine heurističku metodu „dobrih rešenja“ problema putujućeg trgovca koristeći model mravlje kolonije.
Dorigo je koristio činjenicu da je kod mrava izražen fenomen kolektivne inteligencije. Ispuštajući feromon pri kretanju, i prateći koja putanja ima najviše feromona, članovi kolonije međusobno razmenjuju informacije o okruženju.
Svaki mrav, sa određenom verovatnoćom, bira naredno mesto koje će posetiti na osnovu udaljenosti do tog mesta i količine ispuštenog feromona. Mrav koji je odabrao najkraći put ostavlja najviše feromona, jer su dužina puta i količina feromona obrnuto proporcionalne. Tako ostali mravi sve više prate ovaj trag i kako vremenom feromon isparava, putevi koje mravi ređe koriste ostaju bez njega, i time ubuduće ne privlače nikoga iz grupe.
UPS
Pored velike primene sa osnovnom postavkom zadatka, mnogi problemi se mogu svesti na problem trgovačkog putnika, kao što su problemi u rendgenskoj analizi strukture kristala, problem efikasnog pakovanja putne torbe, spajanje komponenti matične ploče računara i slično.
Princip mravlje algoritma je, recimo, jednu od glavnih našao u rešavanju problema rutiranja vozila. Ovaj problem se javio pedesetih godina kao centralni problem kompanija koje se, na primer, bave dostavom pošiljki. Ovde je potrebno odrediti minimalan broj vozila koji je potreban za izvršavanje zadataka, kao i rutu koja će obezbediti najveću uštedu.
Kompanija UPS, vodeća svetska kompanija za dostavu pošiljki, koja svakodnevno isporučuje oko četrnaest miliona paketa, od 2000. godine radi na projektu ORION (On-Road Integrated Optimization and Navigation). Njihov tim matematičara svakodnevno radi na pronalaženju najefikasnijih vozačkih ruta. Sistem je prvi put testiran 2008. godine, a kako tvrde, to im na godišnjem nivou donosi uštedu od preko 35 miliona dolara.