RAČUNALNIŠ TVO
Pomoc za trgovskega potnika
-i' -i' -i'
Aleksander Vesel
Trgovski potnik ima problem
Trgovski potniki, poštarji, vozniki dostavnih vozil, kurirji in ljudje podobnih poklicev nimajo prav lahkega dela. Pred delom dobijo seznam krajev oz. naslovov, ki jih morajo obiskati, ter se vrniti v izhodi-šce. Pomembno je, da obišcejo vse kraje s seznama in da za obisk porabijo cim manj sredstev, predvsem casa in goriva. Izkaže se, da je pravilna izbira vrstnega reda obiskanih krajev zelo pomembna, saj lahko z nerodno izbiro bistveno povečamo stroške poti.
Matematično lahko opišemo problem trgovskega potnika na naslednji način. Dana je množica mest C = [ci,C2, ■ ■■, cn}. Za vsak par mest ci, cj je znana cena povezave od mesta ci do mesta Cj, ki jo označimo z dij. Trgovski potnik mora zaceti pot v enem od mest, obiskati vsa preostala mesta s seznama ter se vrniti v izhodišce, tako da bo skupna cena poti cim manjša. Z drugimi besedami, poiskati želimo takšno zaporedje mest (cni ,cn2,cnn) iz C, da bo vrednost izraza d^^ + d^n + ■■■ + d^n-inn + dnn.m najmanjša. Zaporedju mest, ki minimizira zgornji izraz, bomo rekli tudi najcenejša rešitev.
Nalogo problema trgovskega potnika zelo naravno predstavimo z grafom, v katerem so mesta vozli-šca grafa. Vsako vozlišce grafa povežemo z vsemi drugimi vozlišci, povezavi pa priredimo število, ki je enako ceni poti med mestoma, ki predstavljata kra-jišce povezave.
Kot primer si poglejmo množico mest C = {c1, c2, c3, c4 , c5}, cene povezav med njimi pa so d1,2 = d2,i = 132, di,3 = d3i = 308, di,4 = d4:i = 68, di,5 = ds i = 233, d2,3 = d3,2 = 180, d2,4 = d4,2 = 66, d2,5 = d5,2 = 114, d3,4 = d4,3 = 240, d3,5 = d5,3 = 80 in d4,5 = d5,4 = 167. Primer je predstavljen na sliki 1.
Hitro opazimo, da je cena povezave od mesta ci do mesta cj enaka ceni povezave od mesta cj do mesta ci, velja torej dij = dj i za vsak par mest ci in cj. Omejitev je precej naravna, saj je naceloma dolžina poti med dvema mestoma enaka v obeh smereh. Ker je v praksi pogosto cena povezave sorazmerna dolžini razdalji med mestoma, je v takih primerih zato tudi cena povezave enaka v obe smeri. Problem s to
lastnostjo imenujemo simetrični problem trgovskega potnika.
Malo težje je opaziti, da v primeru s slike 1 za cene velja trikotniška neenakost. S tem povemo, daje cena povezave od mesta cj do mesta ci vedno manjša ali enaka vsoti cen povezav od mesta cj do mesta ci preko mesta ck. Z drugimi besedami, za poljubno trojico mest ci,cj,ck velja dij < di,k + dkj. Tudi ta omejitev je naravna, saj je dolžina direktne poti med dvema mestoma obicajno manjša od dolžine poti, pri kateri naredimo ovinek preko tretjega mesta.
Naivni algoritem
Spomnimo se, da želimo poiskati najcenejšo krožno pot, to je pot, ki se zacne v nekem mestu, gre skozi vsa preostala mesta in se zakljuci v izhodišcu. Hitro opazimo, da je vseeno, v katerem mestu zacnemo krožno pot. Brez izgube za splošnost bomo zato vedno zacenjali v c1.
Razlicnih krožnih poti je veliko, njihove cene pa zelo razlicne. Ce npr. mesta iz slike 1 obišcemo glede na narašcajoce indekse, dobimo krožno pot (c1,c2,c3,c4,c5) s ceno 952. Že majhna sprememba v zaporedju lahko povzroci bistveno spremembo cene. Ce v zgornjem zaporedju c2 premaknemo na
SLIKA 1.
Primer problema trgovskega potnika.

Presek 41 (2013/2014) 5
27
RAČU N A L NIŠTVO
—^ konec, dobimo krožno pot (c\, c3, c4, c5, c2) s ceno 961, ce pa na konec zaporedja premaknemo c3, dobimo krožno pot (c1,c2,c4,c5,c3) s ceno 753. Tudi najcenejšo pot za ta primer lahko hitro najdemo. Ker bomo vedno zaceli v mestu c1, moramo pravilno razporediti preostala štiri mesta. Poiskati moramo vse ureditve zaporedja c2, c3,c4, c5 in izračunati cene pripadajočih krožnih obhodov. Z drugimi besedami, potrebno je poiskati in ovrednotiti vse permutacije zaporedja s štirimi elementi. Teh je natanko 4! = 24, zato jih lahko razmeroma enostavno preverimo tudi brez racunalnika. Najcenejši obhod s ceno 627 nam tako da zaporedje (c1, c2, c3, c5, c4) (glej levo stran slike 2).
Tudi v splošnem primeru lahko naredimo podobno kot zgoraj: potrebno je samo poiskati vse permutacije zaporedja c2,c3,... ,cn in izracunati ceno pri-padajocega krožnega obhoda. Opisani postopek zaradi preprostosti imenujemo tudi naivni algoritem in ga brez težav zapišemo v programskem jeziku. Ker so racunalniki in racunalnikom podobne naprave danes zelo vsakdanja stvar, si ni težko zamisliti, da bi takšen program namestili na racunalniško tablico ali pametni telefon. Program bi omogocil trgovskemu potniku vnos podatkov o mestih in cenah med njimi ter mu izracunal krožno pot z najmanjšo ceno.
Ali bomo s takim programom v resnici lahko pomagali trgovskemu potniku? V nekaterih primerih že, v vseh pa še zdalec ne. Spomnimo se, da je vseh permutacij zaporedja c2, c3, ...,cn natanko (n - 1)!. Težava je zato v tem, da število krožnih obhodov,
ki jih mora pregledati program, glede na n izredno hitro narašca. Že pri seznamu s štirinajstimi mesti število pregledanih zaporedij presega šest milijard, pri n = 42 pa dobimo število krožnih obhodov, ki je vecje od skupnega števila vseh atomov na Zemlji!
V realnem svetu to pomeni, da je problem lepo rešljiv za primere, ko je mest na seznamu malo. Ko gre za trgovskega potnika, ki potuje po Sloveniji, je to seveda cisto realna predpostavka. Drugace pa je, ko bi radi pomagali poštarju pri raznosu pošiljk znotraj vecjega mesta, saj lahko pricakujemo, da je na njegovem seznamu vec deset naslovov. V tem primeru še tako hiter racunalnik ne bo pomagal, saj bi bil cas racunanja programa mnogo prevelik.
Ce hiter racunalnik ne pomaga, se je seveda smiselno vprašati, ali bi mogoce pomagal manj naiven in zato hitrejši algoritem. Hitrejši algoritmi v resnici obstajajo, a niso bistveno hitrejši od naivnega algoritma. V praksi to pomeni, daje možno z zmogljivim namiznim racunalnikom v smiselnem casu rešiti problem za 16 ali 17 mest. Reševanje problema za vecje število mest pa bi se hitro zavleklo v vec mesecev, let ali celo stoletij, ce bi le bilo število mest dovolj veliko.
Problem trgovskega potnika spada med tako imenovane NP-težke probleme. Zelo poenostavljeno povedano s tem izrazom oznacimo probleme, ki jih ne znamo rešiti s hitrimi algoritmi, torej z algoritmi, ki bi omogocali izracun rešitve v sprejemljivem casu tudi za vecje število vhodnih podatkov. Seznam težkih problemov je zelo dolg, med zelo znane in pro-
--------^^(CiV-^^^
/ 1	V // 1 >«. V C2 )
/ 1 ^08	^^rA/ 1 N308
233233
/	\/ \l80/ ------ \180
168	/ \ \------ 168 /\ \
-/66 \\--/66
\ 1 "/	——■—ic)\ "T —■—.—Tc3
1 /	^^^^167\ 1 /
\ C4 / ( C4 J
SLIKA 2.
Najcenejša rešitev (levo) in rešitev pridobljena z algoritmom najbližja tocka (desno).
28
Presek 41 (2013/2014) 5	28
RACUNALNIŠ TVO
ucevane probleme s tega seznama tako npr. spada tudi problem izdelave urnika.
Aproksimacija
Glede na zgoraj povedano bi lahko pomislili, da trgovskemu potniku, ki mora obiskati vecje število mest, sploh ne moremo pomagati. Na sreco zadeva ni popolnoma brezupna, le svoje želje mora trgovski potnik nekoliko prilagoditi. Namesto da bi se trudil z iskanjem najcenejše rešitve, se bo moral zadovoljiti z obhodom, ki zelo verjetno ne bo najcenejši, bo pa izračunan dovolj hitro. Tako izračunanemu zaporedju mest bomo rekli približna rešitev.
Obstaja veliko pristopov, kako hitro izračunati približno rešitev problema trgovskega potnika ali kakega drugega težkega problema. Zelo zanimivi so postopki, pri katerih znamo oceniti, za koliko se bo v najslabšem primeru izračunana približna rešitev razlikovala od najcenejše. Algoritme s to lastnostjo imenujemo aproksimacijski algoritmi. Posebej zaže-ljeni so seveda aproksimacijski algoritmi, pri katerih se izracunana približna rešitev prevec ne razlikuje od najcenejše.
Algoritem z zgornjo lastnostjo za splošni problem trgovskega potnika žal ne obstaja, obstajo pa apro-ksimacijski algoritmi za problem trgovskega potnika, ki zadošca trikotniški neenakosti. Tukaj bomo predstavili algoritem najbližja točka.
Algoritem postopoma gradi krožno pot D, ki najprej obsega samo mesto c1. V nadaljevanju na posameznem koraku doda v krožno pot tisto mesto, iz katerega med vsemi mesti, ki še niso uvršcena v trenutno krožno pot, vodi najcenejša pot do nekega mesta, ki je že na trenutni krožni poti. Algoritem 1 opisuje postopek še formalno.
Algoritem 1: Najbližja tocka Vhod: Množica mest C = {c1, c2 ,...,cn}, cene di j za vsak par ct, cj.
Izhod: Zaporedje mest D = (cni, cU2,..., cnn). begin
D := (ci);
for i := 2 to n do
x naj bo mesto izven D, iz katerega vodi najcenejša pot do nekega mesta y v D; Dodaj x v D takoj za y; end end
Predstavimo potek algoritma za primer s slike 1. Pred vstopom v zanko se v zaporedje D vstavi mesto c1. Algoritem nato vstopi v zanko in med preostalimi mesti c2,c3,c4,c5 išce tisto, iz katerega vodi najcenejša pot do c1. Ocitno je to c4, iz katerega pridemo v c1 za ceno 68. Podobno se zgodi na naslednjem koraku. Algoritem izmed mest s seznama c2,c3, c5 išce tisto, iz katerega vodi najcenejša pot do c1 ali c4. Do c1 pridemo najceneje iz c2 za ceno 132, do c4 pa prav tako iz c2 za ceno 66. Zato v D dodamo c2 takoj za c4. Na podoben nacin ugotovimo, da najceneje v zaporedje (c1,c4, c2) dodamo c5 takoj za c2. Na zadnjem koraku ostane c3, ki ga najceneje prikljucimo v obhod za c5. Podrobneje je potek algoritma predstavljen v tabeli 1.
i		yD	mesta izven D	
				
		(c1)	c2, c3, c4, c5	
2	c4	c1 (c1,c4)	c2, c3, c5	
3	c2	c4 (c1,c4,c2)	c3,c5	
	c5	c2 (c1,c4,c2,c5)	c3	
5	c3	c5 (c1,c4,c2,c5,c3)		
TABELA 1.
Potek izračuna algoritma za primer s slike 1.
Izracunano zaporedje predstavlja krožno pot s ceno 636, ki je predstavljena na desni strani slike 2, dobljena rešitev pa je le za dober odstotek slabša od najcenejše krožne poti. V splošnem sicer ne moremo vedno pricakovati tako dobrega približka, dokazano pa je, da je vrednost izracunane rešitve tudi v najslabšem primeru najvec dvakratnik najcenejše rešitve. Za konec povejmo, da je znanih še nekaj aproksimacijskih algoritmov za rešitev problema trgovskega potnika, ki zadošca trikotniški neenakosti. Najboljši med njimi je Christofidesov algoritem, s katerim lahko izracunamo približno rešitev, ki se za najvec 50 odstotkov razlikuje od najcenejše.
Literatura
[1] T. H. Cormen, C. E. Leiserson in R. L. Rivest, Introduction to algorithms, The MIT Press, 2001.
_XXX
Presek 41 (2013/2014) 5
29