Još
Dodatno

Ukucajte željeni termin u pretragu i pritisnite ENTER

Problem trgovačkog putnika

U kakvoj su vezi efikasno pakovanje putne torbe, spajanje komponenti matične ploče i problem trgovačkog putnika?

 Izvor: Foto: Shutterstock

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.

Pročitajte i Koja matematička strategija se krije iza dečje igre „Papir kamen makaze“?

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.

Komentari 0

Vaš komentar je uspešno poslat i postaće vidljiv čim ga naši administratori odobre.

Slanje komentara nije uspelo.

Nevalidna CAPTCHA

Inicijalizacija u toku...

Najnovije

Priroda

Nauka