Matematika i zabava: Putovanje kroz 81,998 barova u Južnoj Koreji
Matematika i zabava su često spojeni na načine koje ne možemo lako zamisliti. U najnovijem eksperimentu, matematičari su dokazali ovu tvrdnju s interaktivnom kartom koja ilustrira savršenu rutu za posjetiti svih 81,998 barova u Južnoj Koreji. Ova inovacija nije samo izgovor za organiziranje pub crawl-a na trošak sveučilišta, već pravi djelo koje koristi poznati matematički problem: problem putujućeg prodavača.
Problem putujućeg prodavača: Kako ga riješiti?
William Cook, profesor kombinatorike i optimizacije na Sveučilištu Waterloo u Kanadi, jedan je od matematičara koji su radili na ovom izazovu. On napominje da bi “putovanje prošlo kroz vrlo dugačno pub crawl”, no cilj nije prodavati više pića, već prikazati složenost jednog od najpoznatijih matematičkih problema.
- Ukupno vrijeme putovanja za cijelu rutu iznosi 15,386,177 sekundi, ili 178 dana, 1 sat, 56 minuta i 17 sekundi.
- Za vrijeme putovanja trebate mnogo pauza za piće.
Što je problem putujućeg prodavača?
Ovaj problem istražuje najbrži način posjeta svim točkama na mapi, vraćajući se na početnu točku. Da bismo to ilustrirali, zamislite da živite u New Yorku. Koji bi bio najbrži put do tri susjedna grada i nazad? Naizgled lak zadatak može se ispostaviti mnogo složenijim nego što izgleda. Problem putujućeg prodavača je “NP-težak”, što znači da rješenje postaje sve kompliciranije kako se broj točaka povećava.
Označavanje rješenja kroz napredne metode
U ovom istraživanju, Cook i njegov tim koristili su dvije glavne tehnike: Lin-Kernighan heuristiku, koja je jedna od najboljih algoritama za nalazenje rješenja za problem putujućeg prodavača, i metodu “rezanja”, koja omogućava slanje dijela putnika kroz različite grane rute. Ovaj pristup rezultirao je impresivnim rješenjem više od 3,361,795,000 putnih vremena.
Zaključak: Problemi i rješenja
Unatoč gigantskoj komplikaciji ovog zadatka, Cook naglašava: “Ovaj ogroman broj mogućih rješenja je zastrašujući, ali to ne znači da ga ne možemo riješiti.” Iako bi putovanje kroz gotovo 82,000 barova moglo zvučati nezamislivo, ovo istraživanje služi kao jedan od najdramatičnijih primjera primjene matematičkih teorija za rješavanje stvarnih problema. Nažalost, nakon toliko vremena provedenog u barovima, teško je očekivati da će netko doći do potpuno jasnog razumijevanja ove složene matematičke zagonetke. Uživajte s pićem, istovremeno razmišljajući o dubokim matematičkim pitanjima!
