Poslusaj Danila, to ti je moj savet i potrazi negde na internetu vec gotov algoritam, program ili nesto slicno tome u bilo kom jeziku, pa ako ne razumes, prevescemo ti mi
A ako bas moras da se ti zezas s tim, onda uzmi neku diskretnu matematiku od vec pomenutog dr Dragosa Cvetkovica (on drzi matematiku IV na etf-u) i covek je zaljubljen u grafove i teoriju grafova. Izmedju ostalog, nacini resavanja ovog problema se i predstavljaju preko grafa.
Ukratko, problem trgovackog putnika je generalno problem slozenosti n! i moze se resiti jednostavnom primenom grube sile za neke male vrednosti n-a (recimo do n=12 cvorova) u nekom pristojnom vremenu (12! je nekih 480 miliona i neka treba 10-tak sekundi za obradu na brzom(!!!) procesoru. Odatle imamo da za n=20 nam treba oko 5e+9 puta vise vremena, a to je nekih 1600 godina
, a to je realno jos mnogo i veci broj). Zbog kompleksnosti ovaj algoritam spada u grupu losih algoritama.
Svaku tacku proglasimo cvorem grafa. Svake dve tacke spojimo granama grafa. Posto je svejedno da li idemo iz tacke A u B ili iz B u A, onda je to neorijentisan graf. Svakoj grani grafa dodelimo broj koji predstavlja rastojanje izmedju tacaka koje spaja - ovo je tezinski graf. Sada se nas problem sastoji u tome da nadjemo put koji spaja sve tacke (ili ako treba da se vratimo na pocetak onda konturu - to se zove Hamiltonova kontura) najmanje duzine. Preformulacijom problema iz "naci Hamiltonovu konturu najmanje duzine" u "da li postoji Hamiltonova kontura cija je duzina manja od nekog zadatog L" dobija se nedeterministicki polinomijalni algoritam. Onda ovo mozes resiti primenom Turingove masine ili da krenes ovako: imamo neorijentisan tezinski potpuni graf (svaka tacka je spojena sa svakom tackom); u njemu ima m=n(n-1)/2 grana; uvodimo promenljive p1,p2,...pm gde svaka moze da ima vrednosti 0 ili 1 (Bulove promenljive-pripada konturi ili ne pripada); krecemo iz tacke p1 pa pravimo binarno stablo. Pokusavamo da dobijemo odgovor za zadato L. U krajnjoj tacki stabla pi, postavljamo pitanje da li je pi1,pi2,...pin=1 (za n cvorova), ako jeste, uocavamo grane izmedju cvorova, ako obrazuju Hamiltonovu konturu, onda je to potencijalno resenje, racunamo duzinu te konture, uporedjujemo sa L i ako je odgovor na pitanje DA, onda kraj, inace ako pi1,pi2,....pin<>1 ili nije Hamiltonova kontura ili je odgovor >L, onda se ide na dalje grananje. Bulova promenljiva nam govori o ukljucenosti grane u konturu. Ako su sve grane p=0, onda je odgovor NE. Poenta je sto je slozenost polinomijalna (proizvod dva polinoma).
Mozda bolji pristup daje heuristicno resenje problema. Daje neko blisko optimalno resenje. Imamo gridding algoritam - ovo resenje je lokalno dobro ali ne valja pred kraj (a mozda i globalno). Sastoji se od toga da se krene iz jedne tacke, pa da se trazi najbliza tacka. Onda se iz te tacke trazi sledeca najbliza, itd. Problem nastaje pred kraj, tada cemo mozda morati da izaberemo bezrazlozno duge puteve, ali moze da da odredjeni rezultat.
Najbolja je 3-optimalna (ima i r-optimalna) heuristika. Kaze profa da daje nekako najbolje rezultate. Podje se od slucajno izabranog puta i izracuna se njegova duzina. Onda se izbace neke 3 grane i ubace neke nove 3 grane radi poboljsanja. Ovako se dobija novi put. I ovako ponavljamo postupak do nekog kriterijuma. Treba voditi racuna o slucajevima kada dati put ne formira Hamiltonovu konturu (npr. 2 puta kroz isti cvor prolazi put,...).
Ne znam koliko je sve ovo pomoglo, ali kao sto vidis problem nije ni malo naivan, cak sta vise o njemu postoje raznorazne rasprave i studije. Treba se dovijati na razne nacine ne bi li se dobili neki priblizno zadovoljavajuci odgovori, ali optimalno resenje traziti i pokazati da je to pravo...pa to ce bez primene grube sile sacekati neka bolja vremena. Zbog svega ovoga, ponavljam opet ono sto rece Danilo, ako ti bas toliko treba, potrazi negde vec nesto gotovo.
