Algoritam najbližeg komšije

Algoritam najbližeg komšije je bio jedan od prvih algoritama korišćen za određivanje rešenja problema trgovačkog putnika. U njemu putnik kreće iz nasumičnog grada i iznova posećuje najbliži grad, sve dok svi gradovi ne budu posećeni. Algoritmom se brzo dolazi do kratkog niza gradova, ali to obično nije optimalno rešenje.

Ovo su koraci algoritma:

1. Označimo jedan proizvoljan čvor kao trenutni
2. Nađemo najkraći put koji povezuje trenutni čvor sa ne posećenim čvorom V
3. Postavimo trenutni čvor kao V
4. Označimo V
5. Ako su svi čvorovi u domenu posećeni, onda završavamo
6. Idi na korak 2

Niz posećenih čvorova je izlaz algoritma.

Algoritam najbližeg komšije je lako implementirati i izvršava se brzo, ali nekad ume da promaši najkraću putanju koja se lakše primeti ljudskim shvatanjem, zbog njegove “pohlepne” priride. Kao opšte uputstvo, ako je poslednjih nekoliko faza uporedivo po dužini sa prvim fazama, onda je putanja razumna; ako su mnogo veće, onda je verovatnije da postoje mnogo bolje putanje. U najgorem slučaju, algoritam daje putanju koja je mnogo duža od optimalne.

Da budemo precizni, za svaku konstantu r postoji instanca problema trgovačkog putnika takva da je dužina putanje izračunata algoritmom “Najbližeg komšije” r puta veća od dužine optimalne putanje. Šta više, za svaki od gradova dodeljena je distanca između gradova za koju algoritam najbližeg komšije heuristički proizvodi jedinstvenu najgoru moguću putanju.

Literatura

• J. Bang-Jensen, G. Gutin and A. Yeo, When the greedy algorithm fails. Discrete Optimization 1 (2004), 121-127.
• G. Bendall and F. Margot, Greedy Type Resistance of Combinatorial Problems, Discrete Optimization 3 (2006), 288-298.