PEDAGOŠKA FAKULTETA
Študijski program: MATEMATIKA IN RAČUNALNIŠTVO
PROBLEM TRGOVSKEGA POTNIKA
DIPLOMSKO DELO
Mentor: doc. dr. Primož Šparl Kandidatka: Kaja Zupanc
Ljubljana, avgust 2012
i
Zahvala
Zahvaljujem se mentorju doc. dr. Primoˇzu ˇSparlu za vso strokovno pomoˇc, vodenje in potrpeˇzljivost pri nastajanju diplomskega dela ter druˇzini, ki mi je ves ˇcas stala ob strani.
Hvala Evi Hafner za lektoriranje diplomskega dela. Posebna zahvala gre Ivi Antonˇciˇc in Maruˇsi Saksida za ˇstudijska leta, ko smo skupaj premagovale izzive.
Program dela
V diplomskem delu predstavite problem trgovskega potnika. Obravnavajte zahtevnost samega problema in predstavite kak eksakten in kak aproksimacijski algoritem za nje- govo reˇsevanje. Predstavite nekaj konkretnih situacij, v katerih se ta problem pojavi.
Pri obravnavi se lahko naslonite na knjigo Korte, B., Vygen, J. (2008), Combinatorial optimization: Theory and algorithms, Berlin, Springer-Verlag.
Ljubljana, januar 2012 Mentor: doc. dr. Primoˇz ˇSparl
iii
POVZETEK
Pri problemu trgovskega potnika imamo podan graf, trgovski potnik pa mora obiskati vse toˇcke grafa (ki predstavljajo mesta), vsako natanko enkrat, in se vrniti v izhodiˇsˇce. Pri tem ˇzeli, da bo skupna cena (razdalja) poti najmanjˇsa (najkrajˇsa). Hamiltonov cikel grafa je sklenjen sprehod po grafu, v katerem vsako toˇcko obiˇsˇcemo natanko enkrat. Pri problemu trgovskega potnika torej iˇsˇcemo Hamiltonov cikel z minimalno ceno. Problem je v 19. stoletju prvi matematiˇcno obravnaval irski matematik W. R. Hamilton, danes pa je eden izmed najbolj preuˇcevanih problemov kombinatoriˇcne optimizacije. Problem trgovskega potnika je NP-teˇzak problem, kar med drugim pomeni, da zanj (zaenkrat) ne poznamo algoritma reˇsljivega v polinomskem ˇcasu. V diplomskem delu obravnavamo eksaktne in aproksimacijske algoritme za reˇsevanje problema trgovskega potnika. Ogle- damo si eksaktni algoritem Concorde za reˇsevanje tako imenovane simetriˇcne razliˇcice problema in s pomoˇcjo raˇcunalniˇskega programa preverimo, kako dobra sta dva aproksi- macijska algoritma: algoritem najbliˇzjega soseda inalgoritem podvojenega drevesa. Poleg tega spoznamo tudi konkretne situacije, v katerih se problem pojavlja.
Klasifikacija MSC (2010): 05C45, 90C27, 90C35.
KLJU ˇCNE BESEDE
problem trgovskega potnika,
Hamiltonov cikel,
Concorde,
algoritem najbliˇzjega soseda,
algoritem podvojenega drevesa.
TITLE: THE TRAVELING SALESMAN PROBLEM
ABSTRACT
Inthe traveling salesman problemwe are given a graph. The task of the salesman is to find the shortest (or cheapest) possible route by visiting each vertex (that represents cities) exactly once and returning to the initial vertex (city). A Hamilton cycle is a cycle in a graph, in which each vertex is visited only once. In the traveling salesman problem we are thus searching for a Hamilton cycle with a minimum price. The problem was posed in 19th century by the Irish mathematician W. R. Hamilton. Today, this is one of the most intensively studied problems in combinatorial optimization. The traveling salesman problem belongs to the class of NP-hard problems. In particular, this means that we (so far) cannot construct a polynomial-time algorithm that would solve this problem. The bachelor’s thesis deals with exact and approximation algorithms for solving the traveling salesman problem. We present an exact Concorde algorithm for solving symmetric tra- veling salesman problems and use it to examine how good two approximation algorithms are: thenearest neighbour algorithmand thedouble-tree algorithm. We also explore appli- cability of the traveling salesman problem to various problems encountered in the fields of science and engineering.
MSC (2010) Classification : 05C45, 90C27, 90C35.
KEYWORDS
traveling salesman problem,
Hamilton cycle,
Concorde,
nearest neighbour algorithm,
double-tree algorithm.
Kazalo
0 UVOD 1
1 UVOD V TEORIJO GRAFOV 3
1.1 OSNOVNI POJMI . . . 3
1.2 PREDSTAVITEV GRAFA Z MATRIKO . . . 7
2 RAZVOJ PROBLEMA TRGOVSKEGA POTNIKA 11 2.1 ZGODOVINA . . . 11
2.2 DANES . . . 14
3 NP-POLNOST PROBLEMA TRGOVSKEGA POTNIKA 17 3.1 RAZREDA P IN NP . . . 17
3.2 NP-POLNOST PROBLEMOV . . . 20
4 REˇSEVANJE PROBLEMA TRGOVSKEGA POTNIKA 29 4.1 POSEBNI PRIMERI . . . 29
4.1.1 SIMETRI ˇCNI IN ASIMETRI ˇCNI PROBLEM TRGOVSKEGA PO- TNIKA . . . 29
4.1.2 METRI ˇCNI PROBLEM TRGOVSKEGA POTNIKA . . . 30
4.1.3 EVKLIDSKI PROBLEM TRGOVSKEGA POTNIKA . . . 30
4.2 REˇSEVANJE PTP . . . 31
4.2.1 EKSAKTNI ALGORITMI . . . 31
4.2.2 APROKSIMACIJSKI ALGORITMI . . . 38
4.2.3 LOKALNA OPTIMIZACIJA . . . 44 v
5 U ˇCINKOVITOST IMPLEMENTIRANIH ALGORITMOV ZA REˇSEVANJE
PTP 47
5.1 PREDSTAVITEV IMPLEMENTACIJ ALGORITMOV . . . 48
5.1.1 ALGORITEM NAJBLIˇZJEGA SOSEDA . . . 48
5.1.2 ALGORITEM PODVOJENEGA DREVESA . . . 48
5.1.3 CONCORDE . . . 49
5.2 PRIMERJAVA REˇSITEV ALGORITMOV . . . 50
5.2.1 “PRAVILNI” GRAFI . . . 50
5.2.2 GRAFI Z ENO ODDALJENO TO ˇCKO . . . 52
5.2.3 GRAF S TO ˇCKAMI, RAZPOREJENIMI V DVA KROGA . . . 54
5.2.4 GRAFI Z NAKLJU ˇCNO RAZPOREJENIMI TO ˇCKAMI . . . 55
5.3 CASOVNA ZAHTEVNOST ALGORITMOVˇ . . . 60
5.3.1 “PRAVILNI” GRAFI . . . 60
5.3.2 GRAFI Z ENO ODDALJENO TO ˇCKO . . . 60
5.3.3 GRAF S TO ˇCKAMI, RAZPOREJENIMI V DVA KROGA . . . 61
5.3.4 GRAFI Z NAKLJU ˇCNO RAZPOREJENIMI TO ˇCKAMI . . . 61
5.4 KOMENTAR K REˇSITVAM ALGORITMOV . . . 62
5.4.1 ALGORITEM NAJBLIˇZJEGA SOSEDA . . . 63
5.4.2 ALGORITEM PODVOJENEGA DREVESA . . . 64
6 OBLIKE PROBLEMOV TRGOVSKEGA POTNIKA 67 6.1 POTOVANJA . . . 67
6.2 GENETSKE RAZISKAVE . . . 68
6.3 TELESKOPI, RENTGENSKI ˇZARKI IN LASERJI . . . 69
6.4 USMERJANJE INDUSTRIJSKIH NAPRAV . . . 70
6.5 AUDIO IN VIDEO . . . 70
6.6 MIKROPROCESORJI . . . 71
6.7 OSTALA PODRO ˇCJA . . . 72
7 ZAKLJU ˇCEK 73
Poglavje 0 UVOD
Trgovski potnik bi na svoji poti rad obiskal veˇcje ˇstevilo trgovin v razliˇcnih mestih. Seveda je v njegovem interesu, da bo potovanje ˇcim krajˇse in cenejˇse. Skupina ljudi se odpravlja na potovanje po glavnih mestih Evrope, ˇzelijo najti najcenejˇso pot, tako da bodo obiskali vsa mesta. Varnostnik mora nadzorovati veˇc razliˇcnih lokacij, kar pomeni, da se mora voziti od ene do druge. Rad bi naˇsel najkrajˇso pot, tako da obiˇsˇce vse lokacije. Pisatelj naˇcrtuje reklamno kampanijo za svojo knjigo, pri tem pa bo obiskal razliˇcna mesta po drˇzavi. Najti ˇzeli najkrajˇso pot, tako da obiˇsˇce vsa mesta. Kako najti optimalno pot za vse zgoraj naˇstete probleme?
Vsi zgoraj naˇsteti problemi so klasiˇcni primeri problema trgovskega potnika. Predsta- vimo ga lahko s pomoˇcjo teorije grafov. Mesta predstavljajo toˇcke grafa, cene povezav med toˇckami pa ceno oz. razdaljo poti med dvema mestoma. Pri problemu trgovskega potnika imamo podan graf, trgovski potnik pa mora obiskati vse toˇcke grafa, vsako na- tanko enkrat, in se vrniti v izhodiˇsˇce, pri tem pa ˇzeli, da bo skupna cena (razdalja) poti najkrajˇsa. Problem je v 19. stoletju prvi matematiˇcno obravnaval irski matematik W. Ha- milton, danes pa je verjetno najbolj preuˇcevan problem kombinatoriˇcne optimizacije. To ne preseneˇca, saj se pojavlja v raznih oblikah na veˇc razliˇcnih podroˇcjih. Problem spada v razred tako imenovanih NP-teˇzkih problemov, kar med drugim pomeni, da zanj ˇse vedno ne poznamo algoritma, reˇsljivega v polinomskem ˇcasu. Pomeni tudi, da je vsaj tako teˇzak, kot vsi ostali v tako imenovanem razredu NP. Najveˇcji do sedaj reˇsen problem trgovskega
1
potnika, pri katerem so cene kar obiˇcajne razdalje, ima 85 900 mest.
V diplomskem delu so na zaˇcetku obrazloˇzeni nekateri glavni pojmi iz teorije grafov, ki jih potrebujemo za laˇzje razumevanje nadaljevanja. V drugem poglavju je predstavljen problem trgovskega potnika in njegova zgodovina. Sledi poglavje, kjer so predstavljeni razredi P, NP, NP-polnih in NP-teˇzkih problemov in dokaz, da je problem trgovskega potnika NP-teˇzak. V ˇcetrtem poglavju so opisani posebni primeri problema in algoritmi za reˇsevanje problema trgovskega potnika. V petem poglavju so predstavljene implementacije nekaterih algoritmov. V zadnjem poglavju pa so opisani mnogi primeri v katerih najdemo oblike problemov trgovskega potnika.
Poglavje 1
UVOD V TEORIJO GRAFOV
Najprej si poglejmo nekatere osnovne pojme v teoriji grafov, ki so potrebni za razumevanje nadaljevanja. Definicije in rezultati tega poglavja so povzeti po [2].
1.1 OSNOVNI POJMI
Definicija 1.1 Graf X je urejen par (V(X), E(X)), kjer je V(X) neprazna mnoˇzica toˇck in E(X) mnoˇzica neurejenih parov toˇck {u, v}, kjer sta u, v ∈ V(X) in u 6= v..
Elementom mnoˇzice E(X) reˇcemo povezave. Ce jeˇ e = {u, v} ∈ E(X), pravimo, da povezava e povezuje toˇcki uin v in da sta u inv krajiˇsˇci povezavee. V tem primeru tudi pravimo, da sta u inv sosednji toˇcki vX, kar oznaˇcimo z u∼v. Povezavo med toˇckama u in v bomo krajˇse zapisaliuv. Primer grafa je prikazan na sliki 1.1.
Ce v definiciji 1.1 zahtevamo, da so povezave urejeni pari toˇˇ ck, dobimo pojem usmerjenega grafa.
Definicija 1.2 Usmerjen graf alidigraf X je urejen par (V(X), E(X)), kjer sta V(X) in E(X) mnoˇzici vozliˇsˇc in povezav. Povezavaeje urejen par toˇck (u, v), kjer stau, v ∈V(X) in u6=v. Pravimo, da je povezava eusmerjena odu dov in da je uzaˇcetna, v pakonˇcna toˇcka povezavee. Primer digrafa je prikazan na sliki 1.1.
V definiciji 1.1 gre za tako imenovanienostaven graf. V sploˇsnem lahko obravnavamo tudi neenostavne grafe, to je grafe z zankami (povezava, katere zaˇcetna toˇcka je tudi konˇcna
3
Slika 1.1: Primera grafa in digrafa.
toˇcka) in vzporednimi povezavami (povezave, ki imajo skupno zaˇcetno in konˇcno toˇcko).
Primera enostavnega in neenostavnega grafa sta prikazana na sliki 1.2. V nadaljevanju bomo besedo graf uporabljali za enostavne grafe.
Slika 1.2: Primera enostavnega in neenostavnega grafa.
Definicija 1.3 Naj bo X = (V(X), E(X)) graf. Podgraf grafa X je vsak graf Y = (V(Y), E(Y)), za katerega velja V(Y)⊆V(X) in E(Y)⊆E(X).
Definicija 1.4 Stopnja ali valenca toˇcke v v grafu X, ki jo oznaˇcimo z δ(v), je ˇstevilo sosednjih toˇck toˇcke v v grafu X. Pri usmerjenih grafih ima vsaka povezava zaˇcetno in konˇcno toˇcko, zato lahko doloˇcimo vhodno stopnjo (oznaka: δ−(v)) in izhodno stopnjo (oznaka: δ+(v)) toˇcke. Vhodna stopnja nam pove, pri koliko povezavah v X je v konˇcna toˇcka, izhodna stopnja pa nam pove, pri koliko povezavah v X je v zaˇcetna toˇcka.
Definicija 1.5 Graf je k-regularen, ˇce ima vsaka toˇcka stopnjo (valenco) k. Pravimo tudi, da ima graf stopnjo k. Primeri regularnih grafov so prikazani na sliki 1.3, primer neregularnega grafa pa je prikazan na sliki 1.1.
Definicija 1.6 Polni graf na n toˇckah oznaˇcimo s Kn in nam predstavlja razred vseh grafov na n toˇckah, pri katerih sta poljubni dve toˇcki povezani. Primeri polnih grafov so prikazani na sliki 1.3.
Osnovni pojmi 5
Slika 1.3: Primeri polnih grafov K4, K5 inK6.
Definicija 1.7 Cikelje povezan graf stopnje 2. Cikel nantoˇckah oznaˇcimo sCn. Primeri ciklov so prikazani na sliki 1.4.
Slika 1.4: Primeri ciklov C4,C5 inC6.
Definicija 1.8 Sprehod v grafu X = (V(X), E(X)) je alternirajoˇce zaporedje toˇck in povezav oblike:
v0e0v1e1v2. . . vn−1en−1vn, (1.1) pri ˇcemer je ei povezava s krajiˇsˇcema vi in vi+1. Sprehod (1.1) bomo krajˇse zapisali kot v0v1v2. . . vn−1vn. Pravimo, da gre za sprehod od v0 do vn. V primeru, da so vse toˇcke sprehoda med seboj razliˇcne, sprehod imenujemo pot.
Definicija 1.9 Sklenjen sprehod aliobhod v grafuX je sprehod oblike:
v0v1v2. . . vn−1vnv0.
V tem primeru torej zahtevamo, da sta prva in zadnja toˇcka enaki. ˇCe so v obhodu vse toˇcke, z izjemo prve in zadnje, razliˇcne, potem obhod imenujemo cikel.
Opomba: Bralec naj bo pri razumevanju pojma cikel ˇse posebno previden. V definiciji 1.7 govorimo o ciklu Cn kot o grafu, v zgornji definiciji 1.9 pa gre za obhod, torej sklenjen sprehod.
Definicija 1.10 Naj bo X povezan graf brez ciklov. Tedaj je X drevo. Primeri dreves so prikazani na sliki 1.5.
Slika 1.5: Primeri dreves.
Definicija 1.11 Pot je drevo z maksimalno stopnjo 2. Pot na n toˇckah oznaˇcimo s Pn. Primer poti je prikazan na sliki 1.6.
Slika 1.6: Primer potiP5.
Opomba: Bralec naj bo tudi pri razumevanju pojma pot ˇse posebno previden. V defini- ciji 1.11 govorimo o poti Pn kot o grafu, v definiciji 1.8 pa gre za sprehod.
Definicija 1.12 Graf X je povezan, ˇce za poljubni dve toˇcki u in v grafaX obstaja pot odudov. V nasprotnem primeru je grafnepovezan. Primera povezanega in nepovezanega grafa sta prikazana na sliki 1.7.
Slika 1.7: Primer povezanega in nepovezanega grafa.
Predstavitev grafa z matriko 7 Definicija 1.13 Sklenjen sprehod, ki vsebuje vse povezave v grafu je Eulerjev sprehod.
Grafu z Eulerjevim sprehodom pravimo Eulerjev graf. Primer grafa z Eulerjevim spreho- dom je prikazan na sliki 1.8 (na sliki je prikazan vrstni red obiskanih povezav).
Izrek 1.14 [2]Naj bo X graf. X je Eulerjev natanko tedaj, ko so vse toˇcke grafa X sode stopnje.
Definicija 1.15 Naj boX graf. Hamiltonova potgrafaXje pot, ki gre skozi vsako toˇcko na grafu (natanko enkrat). ˇCe sta pri tej poti zaˇcetna in konˇcna toˇcka sosednji, pripadajoˇci obhod imenujemo Hamiltonov cikel . ˇCe graf premore Hamiltonov cikel, pravimo da je hamiltonski. Primer grafa s Hamiltonovim ciklom je prikazan na sliki 1.8 (Hamiltonov cikel sestavljajo polne povezave).
Slika 1.8: Primer grafa z Eulerjevim sprehodom in Hamiltonovim ciklom.
1.2 PREDSTAVITEV GRAFA Z MATRIKO
Ko ˇzelimo prikazati graf, nam ga ni potrebno vedno predstaviti s sliko, ampak ga lahko predstavimo tudi z matriko, s katero je graf natanko doloˇcen.
Definicija 1.16 Matrika sosednosti grafa X z mnoˇzico toˇck{v1, v2, . . . , vn}je kvadratna matrika M(X) = [mij], v kateri je
mij = 1, ˇce je vi ∼vj in mij = 0, sicer.
Slika 1.9: Primer neusmerjenega grafa.
Primer Matrika sosednosti grafa je seveda simetriˇcna. Vsota po vrsticah ali stolpcih predstavlja stopnjo toˇcke. Poglejmo si primer. Matrika sosednosti grafa, predstavljenega na sliki 1.9, je enaka
M =
v1 v2 v3 v4 v5 v1 0 1 1 1 1 v2 1 0 1 0 1 v3 1 1 0 1 1 v4 1 0 1 0 1 v5 1 1 1 1 0
Matriko sosednosti lahko definiramo tudi za digraf.
Definicija 1.17 Matrika sosednosti digrafa X z mnoˇzico toˇck {v1, v2, . . . , vn} je kvadra- tna matrika M(X) = [mij], v kateri je
mij = 1, ˇce je (vi, vj)∈E(X) in mij = 0, sicer.
Primer Matrika sosednosti digrafov je v sploˇsnem nesimetriˇcna. Vsota po vrsticah pred- stavlja izhodno stopnjo, vsota po stolpcih pa predstavlja vhodno stopnjo toˇcke. Poglejmo si primer. Matrika sosednosti grafa, predstavljenega na sliki 1.10, je enaka
Predstavitev grafa z matriko 9
M =
v1 v2 v3 v4 v5
v1 0 1 1 0 0 v2 0 0 1 0 0 v3 0 0 0 1 1 v4 1 0 0 0 1 v5 1 0 0 0 0
Slika 1.10: Primer usmerjenega grafa.
Definicija 1.18 Uteˇzeni graf X je urejena trojica (V(X), E(X), c), kjer sta V(X) in E(X) mnoˇzici toˇck in povezav, funkcija c pa je definirana kot c : E(X) → R, ki vsaki povezavi grafa X prirediceno oz. uteˇz. Uteˇzeni graf je prikazan na sliki 1.11.
Definicija 1.19 Naj boX = (V(X), E(X)) uteˇzeni graf, kjer jeV(X) = {v1, v2, . . . , vn}.
Cenovna matrika sosednosti uteˇzenega grafa X je kvadratna matrika M(X) = [mij], v kateri je
mij =c(vi, vj), ˇce je vi ∼vj, mij =∞, sicer.
PrimerPoglejmo si ˇse primer uteˇzenega grafa (slika 1.11) in pripadajoˇce cenovne matrike sosednosti.
M =
v1 v2 v3 v4 v5
v1 ∞ 3 4 7 1
v2 3 ∞ 5 ∞ 9
v3 4 5 ∞ 6 2
v4 7 ∞ 6 ∞ 5
v5 1 9 2 5 ∞
Slika 1.11: Primer uteˇzenega grafa.
Poglavje 2
RAZVOJ PROBLEMA
TRGOVSKEGA POTNIKA
Problem trgovskega potnika (angl. the traveling salesman problem) ali krajˇse PTP je v 19.
stoletju prvi matematiˇcno obravnaval irski matematik W. Hamilton, danes pa je verjetno najbolj preuˇcevan problem kombinatoriˇcne optimizacije. Pri problemu trgovskega potnika imamo podan graf, trgovski potnik pa mora obiskati vse toˇcke grafa (ki predstavljajo mesta), vsako natanko enkrat, in se vrniti v izhodiˇsˇce, pri tem pa ˇzeli, da bo skupna cena (razdalja) poti najcenejˇsa (najkrajˇsa). Toˇckam grafa pravimo tudi mesta. Povedano z drugimi besedami, iˇsˇcemo Hamiltonov cikel z minimalno ceno.
2.1 ZGODOVINA
Navedbe tega razdelka so povzete po [1, 13, 15].
Zaˇcetki PTP so nejasni. Problem je bil omenjen ˇze leta 1832 v priroˇcniku za potujoˇce trgovce s priloˇzenimi primeri obhodov po Nemˇciji in ˇSvici, vendar ta ne vsebuje nobene matematiˇcne obravnave. V 19. stoletju sta ga obravnavala irski matematik W. R. Ha- milton in britanski matematik T. P. Kirkman. Leta 1857 je Hamilton predstavil igro Potovanje okoli sveta (the Icosian game). Igra je prikazana na sliki 2.1.
Bistvo igre je poiskati Hamiltonov cikel na dodekaedru, katerega ogliˇsˇca so oznaˇcena z imeni velemest: London, Pariz, Madrid itd. Graf igre Potovanje okoli sveta je prikazan
11
Slika 2.1: Igra Potovanje okoli sveta [13].
na sliki 2.2. Sir Hamilton je pokazal, da vedno obstaja tak cikel, ne glede na izbiro prvih petih zaporednih mest. Problem je reˇsil s pomoˇcjo tako imenovanega ikozaedrskega raˇcuna.
Slika 2.2: Graf v igri Potovanje okoli sveta.
Sploˇsna oblika PTP naj bi bila prviˇc preuˇcevana v tridesetih letih 20. stoletja na Dunaju in na Harvardu, zlasti je ta problem preuˇceval K. Menger, ki ga je tudi definiral. Nato sta raziskave na Princetonu spodbujala M. Flood in H. Whitney, ki je tudi uvedel ime problema. V petdesetih in ˇsestdesetih letih 20. stoletja je problem postal zelo priljubljen v znanstvenih krogih v Evropi in ZDA. Viden prispevek k reˇsevanju problema so prispevali G. Dantzig, R. Fulkerson in S. Johnson, ki so predstavili problem kot celoˇstevilski linearni
Zgodovina 13 program in razvili tako imenovano metodo “preseˇcnih ravnin” za reˇsevanje problema.
Reˇsili so primer na 49 mestih in dokazali, da noben drug obhod ne more biti krajˇsi. Izbrali so po eno mesto za vsako izmed 48 zveznih drˇzav ZDA (Aljaska in Havaji sta postali zvezni drˇzavi ˇsele leta 1959) in dodali Washington. Cene povezav so bile definirane kot zraˇcne razdalje med mesti. Reˇsitev PTP na 49 mestih je prikazana na sliki 2.3. Omenjeni problem in problemi v nadaljevanju so posebni primeri problema trgovskega potnika, kjer so toˇcke kar toˇcke v ravnini, cene pa ustrezajo evklidski razdalji. Omejitev nekoliko poenostavi problem.
Slika 2.3: Reˇsitev PTP na 49 mestih [1].
Leta 1971 sta IBM-ova raziskovalca M. Held in R. M. Karp reˇsila primer na 64 toˇckah.
Karp je leto pozneje tudi dokazal, da je problem obstoja Hamiltonovega cikla NP-poln problem, kar implicira, da je PTP NP-teˇzak problem. M. Gr¨otschel je leta 1977 v svoji doktorski dizertaciji objavil reˇsen problem na 120-ih nemˇskih mestih. Nato je sledilo leto 1987, ko je bilo objavljenih kar nekaj reˇsitev na do 2392 mestih. Ob koncu 20. stoletja so D. Applegate, R. Bixby, V. Chv´atal in W. Cook razvili program Concorde, ki se ˇse danes uporablja za reˇsevanje PTP. Leta 2006 so Cook in ostali izraˇcunali optimalen obhod za 85 900 mest. Problem izhaja iz podroˇcja izdelovanja ˇcipov po meri. ˇCip izdelajo tako, da s pomoˇcjo laserja prereˇzejo toˇcno doloˇcene povezave. Toˇcke predstavljajo lokacije povezav, ki morajo biti prerezane s pomoˇcjo laserja. Iskali so optimalno pot premikanja laserja od toˇcke do toˇcke. Reˇsitev PTP na 85 900 mestih je prikazana na sliki 2.4. V spodnji tabeli je po letih prikazano maksimalno ˇstevilo toˇck v grafu, na katerih so naˇsli optimalno pot.
1954 1971 1975 1977 1980 1987 1987 1987
49 64 80 120 318 532 666 2392
1992 1994 1998 2001 2004 2005 2006 3038 7397 13509 15112 24978 33810 85900
Slika 2.4: Reˇsitev PTP na 85.900 mestih [1].
2.2 DANES
Leta 2001 je bil predstavljen problem, sestavljen iz vsakega mesta, naselja in vasi na svetu.
Problem sestavlja 1 904 711 mest. Do sedaj ga ni uspel reˇsiti ˇse nihˇce, trenutno najboljˇso reˇsitev pa je predstavil Danec K. Helsgaun 10. oktobra 2010. Verjetno smo od optimalne reˇsitve oddaljeni vsaj ˇse kakˇsno desetletje.
Realno bolj dostopen primer je problem Mona Lise, prikazan na sliki 2.5, s 100 000 toˇckami in razpisano nagrado $1,000 za optimalno reˇsitev. Problem je leta 2009 predstavil
Danes 15 R. Bosch in sicer je potrebno narisati portret da Vinci-jeve Mona Lise z neprekinjeno ˇcrto.
Toˇcke so vnaprej doloˇcene, seveda pa iˇsˇcemo optimalno pot. Najkrajˇsi obhod do sedaj je leta 2009 predstavil Y. Nagata. Trenutno je najkrajˇsi obhod dolˇzine 5 757 191. 16.
februarja 2012 so s pomoˇcjo Concorda dokazali, da noben obhod ne more biti krajˇsi od 5 757 080.
Slika 2.5: Problem Mona Lise na 100.000 mestih [1].
Poglavje 3
NP-POLNOST PROBLEMA TRGOVSKEGA POTNIKA
V tem poglavju bomo predstavili dva razreda odloˇcitvenih problemov, in sicer razreda P in NP. Spoznali bomo tudi razreda NP-polnih in NP-teˇzkih problemov. Nato bomo dokazali, da je problem trgovskega potnika NP-poln. Obravnava v tem poglavju je nekoliko ohlapna.
Bralcu, ki ga zanimajo natanˇcne definicije in formalni dokazi vseh navedenih dejstev, priporoˇcamo knjigi [3] in [5].
3.1 RAZREDA P IN NP
Probleme reˇsujemo s pomoˇcjo algoritmov, ki pa imajo razliˇcne zahtevnosti. Algoritem je postopek, s katerim reˇsujemo problem. Zapisan je kot seznam konˇcno mnogo natanko definiranih korakov, ki nas pripeljejo do reˇsitve problema. Algoritem vedno potrebuje vhodni podatek, nato raˇcuna korak za korakom in vrne izhodni podatek. Primer algoritma je shematiˇcno prikazan na sliki 3.1.
Kako uˇcinkoviti so algoritmi, merimo predvsem s ˇcasovno zahtevnostjo algoritmov. Casovnaˇ zahtevnost ovrednoti, koliko najveˇc korakov oz. operacij potrebuje algoritem za izvedbo, glede na “velikost” vhodnega podatka. Pri problemih na grafih je “velikost” vhodnega podatka obiˇcajno ˇstevilo vozliˇsˇc, ˇstevilo povezav ali vsota obeh ˇstevil. ˇCasovno zahtev- nost obiˇcajno merimo le do mnoˇzenja s konstanto natanˇcno, kar oznaˇcimo s simbolom
17
Slika 3.1: Primer algoritma Vrni veˇcje ˇstevilo.
O. ˇCe je na primer ˇcasovna zahtevnost algoritma pri vhodnem podatku velikosti nenaka 2n3+ 4n, pravimo, da gre za algoritem s ˇcasovno zahtevnostjoO(n3). V nadaljevanju se bomo posvetili algoritmom s polinomsko ˇcasovno zahtevnostjo. Za algoritem pravimo, da je izvedljiv v polinomskem ˇcasu, ˇce obstaja celo ˇstevilok, da je ˇcasovna zahtevnost algo- ritma O(nk). V primeru, ko velja k = 1, pravimo, da je algoritem izvedljiv v linearnem ˇ
casu. Probleme lahko reˇsujemo z razliˇcnimi algoritmi, obiˇcajno pa iˇsˇcemo najhitrejˇsega, torej tistega z najmanjˇso ˇcasovno zahtevnostjo.
Veˇcina teorije kompleksnosti se ukvarja z odloˇcitvenimi problemi. Odloˇcitveni problem P je problem pri katerem se za vsak primer tega problema spraˇsujemo ali ima neko is- kano lastnost ali ne. Na vpraˇsanje lahko vedno odgovorimo z “da” ali “ne”. Tako je na primer problem obstoja popolnega prirejanja v grafu odloˇcitveni problem. Razred vseh odloˇcitvenih problemov, za katere obstaja algoritem s polinomsko ˇcasovno zahtevnostjo, oznaˇcimo s P. Oznaka prihaja iz angleˇsˇcine (polynomial). Za nek odloˇcitveni problem pokaˇzemo, da je v razredu P, tako da zanj poiˇsˇcemo algoritem, ki je izvedljiv v polinom-
Razreda P in NP 19 skem ˇcasu. Sledi nekaj primerov problemov, ki spadajo v razred P.
POVEZANOST GRAFA Primer: Graf G.
Vpraˇsanje: Ali jeG povezan?
POT V DIGRAFU
Primer: Digraf D= (V(D), E(D)) in dve podmnoˇzici S, T ⊆V(D).
Vpraˇsanje: Ali obstaja pot od toˇcke izS do toˇcke iz T v D?
MINIMALNO VPETO DREVO
Primer: Povezan uteˇzeni graf G= (V(G), E(G), c) in celo ˇsteviloL.
Vpraˇsanje: Ali obstaja vpeto drevo vG s ceno Lali manj?
Bralcu, ki bi si ˇzelel ogledati dokaze, da ti problemi zares spadajo v razredP, priporoˇcamo [5].
Poglejmo si sedaj ˇse naslednji odloˇcitveni problem.
HAMILTONOV CIKEL Primer: Neusmerjen graf G.
Vpraˇsanje: Ali ima GHamiltonov cikel?
Za problem obstoja Hamiltonovega cikla in ˇse veliko drugih problemov (zaenkrat) ne znamo poiskati algoritma, izvedljivega v polinomskem ˇcasu. Kar nekaj teh problemov je takih, da imamo algoritme s polinomsko ˇcasovno zahtevnostjo, ki znajo preveriti, ali je dana dopustna reˇsitev, ki naj bi dokazovala, da je odgovor na vpraˇsanje “da”, zares takˇsna. Tem algoritmom pravimo preveritveni algoritmi. Takˇsni odloˇcitveni problemi spadajo v razred NP. Oznaka NP prihaja iz angleˇsˇcine (nondeterministic polynomial).
Tako problem obstoja Hamiltonovega cikla oˇcitno spada v razred NP, saj za dani niz zlahka preverimo, ˇce je Hamiltonov cikel ali ne. Torej je razlika med razredoma P in NP sledeˇca: za probleme v razredu P poznamo algoritme izvedljive v polinomskem ˇcasu, za probleme v razredu NP pa znamo v polinomskem ˇcasu s pomoˇcjo preveritvenih algoritmov
preveriti le, ˇce so kandidati za reˇsitev pravilni ali ne.
Najveˇcji odprt problem v teoriji kompleksnosti je zagotovo vpraˇsanje, ali velja enakost P=NP. ˇCeprav bomo omenili kar nekaj NP problemov, za katere ne poznamo algoritma izvedljivega v polinomskem ˇcasu, do sedaj ni ˇse nihˇce dokazal, da taki algoritmi ne obsta- jajo. Zagotovo pa velja P⊆NP, saj lahko za vse odloˇcitvene probleme v P v polinomskem ˇ
casu preverimo ali so njihove reˇsitve pravilne ali ne.
Nedeterministiˇcni algoritemje algoritem, ki na vsakem koraku algoritma sprejme odloˇcitev, kako bo nadaljeval. To pomeni, da je potek delovanja algoritma razliˇcen ob razliˇcnih pono- vitvah in da je lahko izhodni podatek razliˇcen ob razliˇcnih ponovitvah. Ravno nasproten je deterministiˇcni algoritem, ki vedno vrne enako reˇsitev. Izkaˇze se [3], da odloˇcitveni problem spada v razred NP natanko tedaj, ko ima nedeterministiˇcni algoritem reˇsljiv v polinomskem ˇcasu.
Naj bosta P1 in P2 odloˇcitvena problema. Pravimo, da se P1 polinomsko prevede v P2, ˇ
ce obstaja funkcijaf, izvedljiva v polinomskem ˇcasu, ki katerikoli primerY1 problemaP1 preslika v primer f(Y1) problemaP2 tako, da jeY1 primer P1, na katerega odgovorimo z
“da” natanko tedaj, ko je f(Y1) primer P2 na katerega odgovorimo z “da”.
3.2 NP-POLNOST PROBLEMOV
Spoznajmo ˇse en razred odloˇcitvenih problemov. Odloˇcitveni problemP ∈NP se imenuje NP-poln, ˇce so vsi ostali problemi iz NP polinomsko prevedljivi v P. Na nek naˇcin gre torej za najteˇzje NP probleme. ˇCe namreˇc nek NP-poln problem reˇsimo v polinomskem ˇ
casu, sledi P=NP. Torej ima razred NP-polnih problemov naslednji lastnosti:
Za noben NP-poln problem ne poznamo algoritma s polinomsko ˇcasovno zahtevno- stjo.
Ce obstaja algoritem reˇsljiv v polinomskem ˇˇ casu za katerikoli NP-poln problem, potem obstaja algoritem reˇsljiv v polinomskem ˇcasu za vse NP probleme.
NP-polnost problemov 21 Kot smo ˇze omenili ˇse za noben NP-poln problem ni bilo dokazano, da tak algoritem zares ne obstaja. Velja prepriˇcanje, da bo za morebiten dokaz potrebno odkriti popolnoma nove matematiˇcne tehnike. ˇCe ˇzelimo pokazati, da je problem NP-poln, moramo pokazati dve stvari:
Problem je v NP razredu.
Vse ostale probleme iz NP lahko polinomsko prevedemo v naˇs problem.
Ce kakˇsen problem zadovolji samo drugi pogoj, ne pa nujno prvega, reˇˇ cemo da je problem NP-teˇzak. Tako so vsi NP-polni problemi tudi NP-teˇzki, niso pa vsi NP-teˇzki problemi tudi NP-polni. NP-teˇzki problemi so vsaj tako teˇzki, kot najteˇzji problemi v NP. Drugi pogoj ponavadi dokaˇzemo tako, da pokaˇzemo, da lahko poznan NP-poln problem polinomsko prevedemo v naˇs problem. Relacija polinomske prevedljivosti je seveda tranzitivna (ˇce lahko Apolinomsko prevedemo v B inBpolinomsko prevedemo v C, potem lahko tudiA polinomsko prevedemo v C), zato bo to dovolj. Seveda pa je potreben ekspliciten dokaz za prvi NP-poln problem. Cook [8] je dokazal, da je problem izpolnljivosti, ki ga bomo opisali v naslednjem odstavku, NP-poln problem.
Naj bo X konˇcna mnoˇzica logiˇcnih (Boolovih) spremenljivk, to je spremenljivk, ki lahko zavzamejo le vrednosti 0 ali 1. Doloˇcitev vrednosti za X je funkcija T : X → {0,1}.
Funkcija T torej pomeni izbiro vrednosti za posamezne logiˇcne spremenljivke xi. Tedaj lahko funkcijo T naravno razˇsirimo na mnoˇzico literalov L := X ∪ {x : x ∈ X}, tako da je T(x) := 0 natanko tedaj, ko je T(x) := 1 in T(x) := 1 natanko tedaj, ko je T(x) := 0 (x torej obravnavamo kot negacijo x). Elementi mnoˇzice L so torej bodisi izjavne spremenljivke ali njihove negacije. Na vsako podmnoˇzico literalov lahko gledamo kot na disjunkcijo pripadajoˇcih literalov. Druˇzina takˇsnih podmnoˇzic nam tedaj lahko predstavlja izjavo v konjunktivni normalni obliki, torej kot konjunkcija samih disjunkcij.
Zanima nas ali za dano izjavo v konjunktivni normalni obliki obstaja izbira vrednosti T logiˇcnih spremenljivk izX, pri kateri je ta izjava resniˇcna. Reˇcemo tudi, da v tem primeru
T izpolni dano izjavo.
IZPOLNLJIVOST
Primer: Mnoˇzica logiˇcnih spremenljivk X ={x1, x2, . . . , xn} in izjava nad X v konjuk- tivni normalni oblikiZ.
Vpraˇsanje: Ali jeZ izpolnljiva?
Naslednja omejitev problema IZPOLNLJIVOST nam bo v pomoˇc pri dokazih NP-polnosti nekaterih problemov.
3-IZPOLNLJIVOST
Primer: Mnoˇzica logiˇcnih spremenljivk X ={x1, x2, . . . , xn} in izjava nad X v konjuk- tivni normalni oblikiZ, tako da vsaka disjunkcija vsebuje natanko tri literale.
Vpraˇsanje: Ali jeZ izpolnljiva?
Izkaˇze se, da je moˇc problem IZPOLNLJIVOST polinomsko prevesti na problem 3- IZPOLNLJIVOST. Dokaz lahko zainteresirani bralec najde v [3].
Izrek 3.1 [3] 3-IZPOLNLJIVOST je NP-poln problem.
Izrek 3.2 [3] HAMILTONOV CIKEL je NP-poln problem.
Dokaz
Da ta problem pripada razredu NP, smo ˇze ugotovili.
Dokaˇzimo, da se 3-IZPOLNLJIVOST polinomsko prevede v HAMILTONOV CIKEL. Naj bo Z izjava nad X = {x1, ..., xn} v konjunktivni normalni obliki, kjer vsaka disjunkcija vsebuje tri literale. Sestavimo graf G tako, da je G hamiltonski natanko tedaj, ko je Z izpolnljiva. Najprej definirajmo dva podgrafa, ki se bosta v grafu G pojavila veˇckrat, in sicer grafa A inB. Grafu na sliki 3.2 bomo rekli A.
Slika 3.2: Graf A.
NP-polnost problemov 23 Privzemimo, da je A podgraf grafa G in da nobena toˇcka grafa A, razen u, u0, v, v0, ni sosedna z nobeno drugo toˇcko grafa G. To pomeni, da gre katerikoli Hamiltonov cikel skozi A na enega od naˇcinov prikazanih na sliki 3.3.
Slika 3.3: Hamiltonov cikel skoziA.
Torej lahko A nadomestimo z dvema povezavama z omejitvijo, da mora vsak Hamiltonov cikel grafa G vsebovati natanko eno od teh dveh povezav, kar je prikazano na sliki 3.4.
Slika 3.4: Predstavitev grafa A.
Poglejmo si ˇse graf B, prikazan na sliki 3.5.
Slika 3.5: Graf B.
Tudi za graf B privzemimo, da je podgraf grafaG ter da nobena toˇcka grafa B, razen u in u0, ni sosedna z nobeno drugo toˇcko grafa G. Potem noben Hamiltonov cikel ne gre skozi vse tri povezave e1, e2, e3 (razen, ˇce je B =G). Zlahka se tudi prepriˇcamo, da graf B vsebuje Hamiltonovo pot odudou0, ki vsebuje poljuben nabor najveˇc dveh (lahko tudi niˇc) povezav izmed e1, e2 ine3. Graf B predstavimo s sliko 3.6.
Sedaj lahko sestavimo graf G. Za vsako disjunkcijo dodamo kopijo grafa B pri ˇcemer jih poveˇzemo enega za drugim. Med prvo in zadnjo kopijo grafa B dodamo po dve
Slika 3.6: Predstavitev grafa B.
toˇcki za vsako spremenljivko in jih poveˇzemo eno za drugo. Potem podvojimo povezave med vsakima dvema toˇckama, ki predstavljata posamezno spremenljivko. Ti dve povezavi predstavljataxinx. Povezavee1, e2, e3v vsaki kopiji grafaBso sedaj povezane prek kopije grafaA s povezavami, ki predstavljajo prvi, drugi in tretji literal ustrezne disjunkcije. Te konstrukcije so narejene zaporedno: ko dodamo kopijo grafa A na povezavo e = {w, z}, ki ustreza literalu, prevzame povezava, ki je na grafuA incidenˇcna z-ju, vlogoe-ja. Sedaj ta povezava ustreza literalu.
Celotna konstrukcija za primer {{x1, x2, x3},{x1, x2, x3},{x1, x2, x3}} je podrobno prika- zana na sliki 3.7.
Slika 3.7: Predstavitev grafa Gin poveˇcava ˇcrtkanega dela.
NP-polnost problemov 25 Dokaˇzimo, da je graf Ghamiltonski natanko tedaj, ko je izjava Z izpolnljiva.
Naj bo C Hamiltonov cikel grafa G. Zaradi lastnosti grafa A je oˇcitno, da so za vsako spremenljivko xivCvsebovani ali vsi segmentifj ali vsi segmentifj0 (slika 3.7). Doloˇcitev vrednosti spremenljivk torej lahko definiramo tako, da nastavimo literal na resniˇcen na- tanko tedaj, ko C vsebuje (vse) pripadajoˇce segmente. Zaradi lastnosti grafa B v C ni vsebovana vsaj ena od povezav e1, e2, e3 za vsako disjunkcijo. Zato vsaka disjunkcija vsebuje literal, ki je resniˇcen. To namreˇc sledi iz lastnosti grafov A in B. Zaradi la- stnosti grafa A sledi, da C vsebuje bodisi povezavo iz leve strani (ei) bodisi povezavo iz desne strani (xi ali xi). Ker po lastnosti grafa B vsaj ene izmed povezav e1, e2, e3 ni v C, sledi da je vsebovana ustrezna povezava iz desne strani. Po zgoraj opisani dodelitvi resniˇcnosti spremenljivk je pripadajoˇci literal resniˇcen, zato pa je resniˇcna tudi dana dis- junkcija. Opiˇsimo ta premislek ˇse na zgornjem primeru. Naj na primer C za disjunkcijo {x1, x2, x3} ne vsebuje povezavee2, ki predstavlja literalx2. To pomeni, da bo vsebovana povezava, ki predstavlja x2, na desni strani, to je, C bo vseboval segmente f1, f2 in f3. Po doloˇcitvi resniˇcnosti sledi, da je x2 = 1, torej je disjunkcija{x1, x2, x3} resniˇcna.
Nasprotno, naj bo Z izpolnljiva. Sestavimo Hamiltonov cikel na naslednjem podgrafu G0 grafa G. Graf G0 ne vsebuje grafov A. Hamiltonovo pot za vsako disjunkcijo naredimo tako, da ne vsebuje povezav, ki predstavljajo literale, ki so resniˇcni (po lastnosti grafa B to lahko storimo). Na desni C vsebuje povezave literalov, ki so resniˇcni. Sedaj v C dodamo vse povezave med disjunkcijami na levi in literali na desni ter obe povezavi, ki povezujeta levo in desno stran. Tako dobimo Hamiltonov cikel grafa G0. GrafA povezuje povezavi na levi in desni strani, ki predstavljata isti literal. Torej, ˇce je literal resniˇcen, je povezava ˇze vsebovana na desni strani, ˇce pa literal ni resniˇcen, je vsebovana na levi strani. Po lastnosti grafa A lahko C razˇsirimo tako, da vsebuje ˇse vse toˇcke vstavljenega
grafa A. Sledi, da je graf Ghamiltonski.
Razˇsirimo sedaj naˇse rezultate ˇse na optimizacijske probleme. Optimizacijska naloga je urejena trojica (D, c, m), kjer je D dopustna mnoˇzica, c:D →R∪ {−∞,∞} je cenovna funkcija inm ∈ {min, max}. Elementom x ∈ D pravimo tudi dopustne reˇsitve. Pri tem iˇsˇcemo minimum funkcije c na D, ˇce je m = min ali maksimum funkcije c na D, ˇce je
m = max. Optimalno reˇsitev zapiˇsemo kot OP T = m(D, c). Optimizacijski problem je mnoˇzica optimizacijskih nalog “istega tipa”, ki se torej razlikujejo le po dopustni mnoˇzici D in/ali cenovni funkcijic.
NP-teˇzki problemi niso nujno odloˇcitveni problemi, lahko jih definiramo tudi kot opti- mizacijske probleme. Definirajmo sedaj problem trgovskega potnika kot optimizacijski problem.
PROBLEM TRGOVSKEGA POTNIKA (PTP)
Primer: Polni graf Kn(n≥3) in cenovna funkcija c:E(Kn)→R+. Naloga: Poiˇsˇci Hamiltonov cikel C, katerega cenaP
e∈E(C)c(e) je minimalna.
Toˇcke so pri PTP pogosto imenovane mesta, cena pa se nanaˇsa na razdaljo med dvema mestoma ali na ceno potovanja med dvema mestoma.
Izrek 3.3 [3] PTP je NP-teˇzak problem.
Dokaz
Ce ˇˇ zelimo pokazati, da je PTP NP-teˇzak problem, moramo pokazati, da lahko poznan NP-poln problem polinomsko prevedemo v PTP. Pokaˇzimo, da je PTP NP-teˇzak celo v primeru, ko so vse cene 1 ali 2. Opiˇsimo polinomsko prevedbo problema HAMILTONOV CIKEL na PTP. Imejmo graf G na n ≥ 3 toˇckah in zgradimo naslednji primer PTP. Za mnoˇzico toˇck ustreznega polnega grafa vzamemo kar mnoˇzico toˇck grafaG. Cene povezav nato doloˇcimo tako, da povezavam, ki so prisotne tudi v G, doloˇcimo ceno 1, ostalim pa 2. Oˇcitno je, da je grafG hamiltonski natanko tedaj, ko ima optimalni obhod trgovskega
potnika ceno n.
Poznamo pa tudi odloˇcitveno varianto problema trgovskega potnika.
ODLO ˇCITVENI PROBLEM TRGOVSKEGA POTNIKA (OPTP)
Primer: Polni graf Kn(n≥3), cenovna funkcija c:E(Kn)→R+ ink ∈N. Vpraˇsanje: Ali ima Kn Hamiltonov cikel T, ki ima ceno P
e∈E(C)c(e)< k.
NP-polnost problemov 27 Izrek 3.4 [5] OPTP je NP-poln problem.
Dokaz
Polinomska prevedba je podobna kot v dokazu izreka 3.3. Da je OPTP∈NP je oˇcitno, saj za vsak ponujen obhod zlahka preverimo, ˇce njegova cena ne presega k.
Poglavje 4
REˇ SEVANJE PROBLEMA TRGOVSKEGA POTNIKA
V prejˇsnjem poglavju smo dokazali, da je problem trgovskega potnika NP-poln problem, kar pomeni, da je vsaj tako teˇzak kot katerikoli NP problem. V tem poglavju pa bomo spoznali naˇcine reˇsevanja problema trgovskega potnika in s tem spoznali teˇzavnost iskanja eksaktne reˇsitve.
V naˇsi definiciji problema imamo polni graf, kar pomeni, da so vse toˇcke med seboj povezane. ˇCe med dvema toˇckama povezava ne obstaja, dodamo povezavo z dovolj veliko ceno.
4.1 POSEBNI PRIMERI
V tem razdelku bomo spoznali nekatere primere problema trgovskega potnika, ki jih bomo potrebovali v nadaljevanju.
4.1.1 SIMETRI ˇ CNI IN ASIMETRI ˇ CNI PROBLEM TRGOV- SKEGA POTNIKA
Problem trgovskega potnika na grafu je simetriˇcni PTP, saj so cene potovanja med toˇckami v obe smeri enake. Asimetriˇcni PTP pa definiramo na digrafu, kar pomeni,
29
da sta lahko ceni potovanja med dvema toˇckama razliˇcni, odvisno v katero smer potu- jemo. Prometne nesreˇce (zaprtje cest ali delov cestiˇsˇca), enosmerne ulice in cene letalskih kart (razliˇcne cene potovanja med dvema mestoma, odvisno v katero smer potujemo) so samo nekateri primeri, ki pokaˇzejo, da simetriˇcni PTP ni vedno pravi model. Kljub temu se bomo v nadaljevanju omejili na simetriˇcne PTP.
4.1.2 METRI ˇ CNI PROBLEM TRGOVSKEGA POTNIKA
Definirajmo naslednji optimizacijski problem.
METRI ˇCNI PTP
Primer: Polni grafKn s cenamic: E(Kn)→R+, kjer c({x, y}) +c({y, z})≥c({x, z}) za vse x, y, z ∈V(Kn).
Naloga: Poiˇsˇci Hamiltonov cikel v Kn z minimalno ceno.
V metriˇcnem PTP cenovna funkcija zadoˇsˇca trikotniˇski neenakosti. To je najbolj naravna omejitev, saj zahteva, da je cenovna funkcija metrika. Uvedba metrike pomeni, da je direktna povezava odxdoyvedno najkrajˇsa. Tako kot obiˇcajen PTP je tudi METRI ˇCNI PTP NP-teˇzak problem.
4.1.3 EVKLIDSKI PROBLEM TRGOVSKEGA POTNIKA
Evklidski PTP je PTP, pri katerem so toˇcke grafa Kn toˇcke v ravnini R2, cene pa so kar razdalje v obiˇcajni evklidski metriki. Evklidski PTP je poseben primer metriˇcnega PTP, saj za poljubno metriko velja trikotniˇska neenakost.
Izrek 4.1 [3] Metriˇcni PTP je NP-teˇzak.
Dokaz
Prevedbo iz problema obstoja Hamiltonovega cikla napravimo kot v dokazu izreka 3.3.
Jasno je namreˇc, da cenovna funkcija v tem primeru zadoˇsˇca trikotniˇski neenakosti.
Izkaˇze se [3], da je tudi Evklidski PTP NP-teˇzak problem.
Reˇsevanje PTP 31
4.2 REˇ SEVANJE PTP
Standardna naˇcina za reˇsevanje PTP sta v grobem dva:
eksaktni algoritmi, ki so sicer zelo poˇcasni, a poiˇsˇcejo optimalno reˇsitev, ter
aproksimacijski algoritmi, ki so sicer hitrejˇsi, a obiˇcajno poiˇsˇcejo le pribliˇzek opti- malni reˇsitvi.
Velikokrat pa se pri reˇsevanju PTP uporablja tudi iskanje posebnih primerov problema in iskanje “podproblemov”, za katere obstaja eksaktni ali boljˇsi aproksimacijski algoritem.
4.2.1 EKSAKTNI ALGORITMI
V nadaljevanju bomo spoznali nekaj primerov eksaktnih algoritmov za reˇsevanje PTP.
“BRUTE-FORCE” ALGORITEM
Najbolj direkten in hkrati najbolj zamuden algoritem je ta, da preprosto izraˇcunamo ceno za vsakega izmed n! obhodov. Nato izmed vseh moˇznosti izberemo najcenejˇso. ˇCasovna zahtevnost tega algoritma je O(n!).
SESTOPANJE
Sestopanje ali vraˇcanje je sploˇsen algoritem za iskanje vseh (ali nekaterih) dopustnih reˇsitev problema. Algoritem postopoma pridobiva dopustne reˇsitve in opusti vmesne kandidate za reˇsitve takoj, ko se izkaˇze, da ne bodo tvorili optimalne reˇsitve. Sestopanje lahko ponazorimo z drevesom stanj, kjer toˇcke drevesa predstavljajo toˇcke grafa.
Slika 4.1: Sestopanje [12].
Algoritem vedno zaˇcne z najbolj levo vejo, tako da izraˇcuna prvo dopustno reˇsitev (izraˇcuna ceno obhoda). S to dopustno reˇsitvijo nato primerja ostale kandidate za reˇsitev. Algo- ritem se vraˇca nazaj po nivojih in raˇcuna vmesne reˇsitve tako, kot je prikazano na sliki 4.1. Takoj, ko je vmesna reˇsitev slabˇsa od najboljˇse dopustne reˇsitve, algoritem preneha z raˇcunanjem v smeri trenutne veje in se vrne nivo viˇsje. Optimalna reˇsitev je tako naj- boljˇsa dopustna reˇsitev. Le-te najdemo v listih drevesa na najniˇzjem nivoju. Obhod pa preberemo kot pot od korena do lista. Oglejmo si vse skupaj na konkretnem primeru.
PrimerImejmo polni grafK4, podan s cenovno matrikoM (tu imamo torej opravka celo z asimetriˇcnim PTP).
M =
v1 v2 v3 v4 v1 ∞ 20 30 10 v2 15 ∞ 16 4 v3 3 25 ∞ 2 v4 19 6 18 ∞
Kot smo omenili, algoritem najprej izraˇcuna prvo dopustno reˇsitev, ki jo predstavlja najbolj leva veja v drevesu stanj. V naˇsem primeru dobimo dopustno reˇsitev s ceno 57. Vrnemo se na zadnji nivo, kjer smo se odloˇcili za najbolj levo pot (torej na mesto, kjer smo se odloˇcili, da iz toˇcke v2 krenemo k v3), in izraˇcunamo naslednjo dopustno reˇsitev. Ta je boljˇsa od prve, in sicer ima ceno 45. Zopet se vrnemo nazaj (do vozliˇsˇca
Reˇsevanje PTP 33 v1) in raˇcunamo naslednjo dopustno reˇsitev. ˇSe preden pridemo do dopustne reˇsitve, ima kandidat za reˇsitev ˇze ceno 55, kar je slabˇse od naˇse trenutno najboljˇse dopustne reˇsitve, zato raˇcunanje v smeri te veje zakljuˇcimo. Tako nadaljujemo dokler ne izraˇcunamo tudi cene za najbolj desno vejo drevesa stanj. Optimalna reˇsitev je najboljˇsa izmed dopustnih reˇsitev, torej tista, katere cena je 35. Pripadajoˇci obhod preberemo kot pot od korena do lista. V naˇsem primeru je to obhod v1v4v2v3v1.
Sestopanje je pogosto veliko hitrejˇsi algoritem kot “brute-force” algoritem, saj lahko izloˇci kandidate za reˇsitev, ki ne bodo tvorili optimalne reˇsitve. Vendar pa ni zagotovila, da s tem algoritmom ni potrebno izraˇcunati vseh dopustnih reˇsitev, zato je v najslabˇsem primeru ˇcasovna zahtevnost ˇse vednoO(n!).
ALGORITEM RAZVEJI IN OMEJI
Tako kot pri sestopanju, tudi z algoritmom razveji in omeji iˇsˇcemo vse (ali nekatere) dopu- stne reˇsitve problema. Pri reˇsevanju razvijamo drevo stanj. Kot pri prejˇsnjem algoritmu tudi tu raˇcunamo vmesne reˇsitve, ki predstavljajo spodnje meje kandidatov za reˇsitev. Pri algoritmu razveji in omeji se uporablja ocenjevanje obetavnosti toˇck, kar pomeni, da ve- dno raˇcunamo v smeri najbolj obetavne veje ter s tem razvijamo drevo stanj. To pomeni, da vedno nadaljujemo s tistim kandidatom za reˇsitev, ki ima najcenejˇso spodnjo mejo.
Drevo stanj nam pri tem pomaga, da je vse skupaj veliko bolj pregledno. Reˇsitev dobimo, ko je dopustna reˇsitev cenejˇsa od vseh spodnjih mej. Uteˇzeni graf je podan s cenovno matriko, s pomoˇcjo katere izraˇcunamo spodnjo mejo za ceno obhoda. Trgovec mora iz vsake toˇcke oditi natanko enkrat. Cena poti od toˇcke v1 do prve naslednje toˇcke stane najmanj toliko, kot je cena najcenejˇse povezave iz v1. Ker mora trgovec izv1 v natanˇcno eno od preostalih toˇck, lahko ceno najcenejˇse povezave odˇstejemo od cen vseh ostalih v vrstici. Enako velja za ostale vrstice in podobno tudi za stolpce, saj mora trgovec v vsako mesto priti natanko enkrat, zato lahko tudi po stolpcih odˇstejemo najmanjˇse vrednosti.
Mogoˇce bralcu ni tako oˇcitno, zakaj lahko to naredimo tudi v stolpcih, saj smo odˇstevali ˇ
ze po vrsticah, vendar se velikokrat zgodi, da pri odˇstevanju najcenejˇsih povezav v vsaki vrstici ne obstaja tak obhod, ki bi toˇcko vedno zapustil skozi najcenejˇso povezavo. To
opazimo tako, da v vsakem stolpcu najcenejˇsa povezava ni niˇc. Kar pa pomeni, da ˇse nismo upoˇstevali (priˇsteli) najmanjˇse cene, ki jo moramo plaˇcati, da pridemo v vsako od toˇck. Pravimo, da smo matrikoreducirali. Najprej smo narediliredukcijo po vrsticah, nato ˇse redukcijo po stolpcih. Vsoto vseh odˇstetih vrednosti uporabimo kot oceno za spodnjo mejo. Kaj pove spodnja meja? Vsi obhodi v naˇsem grafu imajo ceno vsaj toliko, kot znaˇsa spodnja meja. Metodo bomo podrobneje razloˇzili na primeru.
Primer Imejmo zopet polni graf K4, podan z isto cenovno matriko M kot v zgornjem primeru.
M =
v1 v2 v3 v4
v1 ∞ 20 30 10 v2 15 ∞ 16 4 v3 3 25 ∞ 2 v4 19 6 18 ∞
redukcija
−−−−−→
vrstice
v1 v2 v3 v4
v1 ∞ 10 20 0 v2 11 ∞ 12 0 v3 1 23 ∞ 0 v4 13 0 12 ∞
redukcija
−−−−−→
stolpci
v1 v2 v3 v4 v1 ∞ 10 8 0 v2 10 ∞ 0 0 v3 0 23 ∞ 0 v4 12 0 0 ∞
V vsaki vrstici smo izbrali najcenejˇso povezavo in njeno ceno odˇsteli od cen vseh povezav v vrstici. S tem smo naredili redukcijo po vrsticah. Nato sledi ˇse redukcija po stolpcih.
Tudi v vsakem stolpcu odˇstejemo ceno najcenejˇse povezave od cen vseh povezav v stolpcu.
Vsota vseh odˇstetih vrednosti po vrsticah je 22 in po stolpcih 13, izraˇcun spodnje meje je torej 22 + 13 = 35. Sedaj po vrsti raˇcunamo spodnje meje za obhode, ki vsebujejo doloˇcene povezave. Izraˇcunajmo najprej spodnjo mejo za obhod, ki vsebuje povezavo
Reˇsevanje PTP 35 v1v2.
M =
v1 v2 v3 v4
v1 ∞ ∞ ∞ ∞
v2 10 ∞ ∞ 0
v3 0 ∞ ∞ 0
v4 12 ∞ 0 ∞
To pomeni, da povezavo, ki gre iz toˇcke v1 in ki pride v toˇcko v2, ˇze imamo, zato lahko izbriˇsemo to vrstico in stolpec (vse te povezave). V celotno vrstico in stolpec za cene bomo vpisali ∞, kar pomeni, da nadaljujemo z matriko, ki ima stolpcev1, v3, v4 in vrstice v2, v3, v4. Na tej matriki zopet naredimo redukcijo po vrsticah in stolpcih. Ker imajo najcenejˇse povezave v vseh vrsticah in stolpcih ceno 0, je vsota odˇstetih vrednosti enaka 0. Spodnji meji priˇstejemo ˇse ceno povezave v1v2. Spodnja meja za vse obhode, ki vsebujejo povezavo v1v2, je tako enaka 35 + 10 + 0 = 45. Naˇse trenutno drevo stanj:
Ze zgoraj smo omenili, da vedno nadaljujemo s kandidatom za reˇsitev, ki ima najobetav-ˇ nejˇso oz. najcenejˇso spodnjo mejo. V naˇsem primeru je najobetavnejˇsa spodnja meja ˇse vedno 35, zato bomo nadaljevali z raˇcunanjem spodnje meje za obhod, ki vsebuje povezavo v1v3.
M =
v1 v2 v3 v4
v1 ∞ ∞ ∞ ∞
v2 10 ∞ ∞ 0 v3 0 23 ∞ 0 v4 12 0 ∞ ∞
Redukcijo smo naredili na matriki brez vrstice v1 in stolpca v3. Najcenejˇse povezave v vseh vrsticah in stolpcih imajo ceno 0. Spodnja meja za vse obhode, ki vsebujejo povezavo
v1v3, je tako enaka 35 + 8 + 0 = 43. Ker je ˇse vedno najbolj obetavna spodnja meja 35, nadaljujmo z raˇcunanjem spodnje meje za obhod, ki vsebuje povezavo v1v4.
M =
v1 v2 v3 v4
v1 ∞ ∞ ∞ ∞
v2 10 ∞ 0 ∞ v3 0 23 ∞ ∞ v4 12 0 0 ∞
Redukcijo smo naredili na matriki brez vrstice v1 in stolpca v4. Najcenejˇse povezave v vseh vrsticah in stolpcih imajo ceno 0. Spodnja meja za vse obhode, ki vsebujejo povezavo v1v4, je tako enaka 35 + 0 + 0 = 35. Naˇse trenutno drevo stanj:
Ker ima obhod, ki vsebuje povezavo v1v4, najobetavnejˇso spodnjo mejo (35), nadaljujemo s to vejo. Izraˇcunajmo spodnjo mejo za obhod, ki vsebuje pot v1v4v2.
M =
v1 v2 v3 v4
v1 ∞ ∞ ∞ ∞
v2 10 ∞ 0 ∞
v3 0 ∞ ∞ ∞
v4 ∞ ∞ ∞ ∞
Redukcijo naredimo na matriki s stolpci v1 in v3 ter vrsticami v2 in v4. Ponovno imajo najcenejˇse povezave v vseh vrsticah in stolpcih ceno 0, zato je spodnja meja za vse obhode, ki vsebujejo pot v1v4v2, enaka 35 + 0 + 0 = 35. Naˇse trenutno drevo stanj:
Reˇsevanje PTP 37
Nadaljujemo z najobetavnejˇso spodnjo mejo. Izraˇcunamo spodnjo mejo za obhode, ki vsebujejo pot v1v4v2v3.
M =
v1 v2 v3 v4
v1 ∞ ∞ ∞ ∞
v2 ∞ ∞ ∞ ∞
v3 0 ∞ ∞ ∞
v4 ∞ ∞ ∞ ∞
V matriki nam ostaneta le ˇse vrstica v3 in stolpec v1. Spodnja meja za vse obhode, ki vsebujejo pot v1v4v2v3 je enaka 35 + 0 + 0. Ostane nam ˇse povezava nazaj do izhodiˇsˇca v1, ki ima prav tako ceno 0, kar pomeni, da je naˇsa optimalna reˇsitev obhod v1v4v2v3v1, ki ima optimalno ceno 35. Drevo stanj za naˇso reˇsitev:
Pri raˇcunanju optimalne reˇsitve s pomoˇcjo algoritma razveji in omeji obiˇcajno prihranimo kar nekaj raˇcunanja, saj raˇcunamo vedno v smeri najbolj obetavne reˇsitve in se tako izognemo nepotrebnemu raˇcunanju reˇsitev, ki niso kandidati za optimalno reˇsitev. Vendar pa ni zagotovila, da s tem algoritmom ni potrebno izraˇcunati vseh dopustnih reˇsitev, zato je v najslabˇsem primeru ˇcasovna zahtevnost ˇse vedno O(n!).
4.2.2 APROKSIMACIJSKI ALGORITMI
Definicija 4.2 Naj bo P optimizacijski problem z nenegativnimi cenami in k ≥ 1. k- faktorski aproksimacijski algoritem za P je v polinomskem ˇcasu reˇsljiv algoritem A, za katerega velja
1
kOP T(I)≤A(I)≤kOP T(I)
za vse optimizacijske naloge I iz P. OP T(I) predstavlja optimalno reˇsitev, A(I) pa aproksimacijsko reˇsitev algoritma A.
Prva neenakost se nanaˇsa na maksimizacijske probleme, druga pa na minimizacijske pro- bleme. Za primere I, za katere je OP T(I) = 0, potrebujemo eksaktno reˇsitev. 1-faktorski
Reˇsevanje PTP 39
aproksimacijski algoritmi so natanko eksaktni in v polinomskem ˇcasu reˇsljivi algoritmi.
Izrek 4.3 [3] Razen v primeru, da velja P=NP, ne obstaja k-faktorski aproksimacijski algoritem za PTP za noben k ≥1.
Dokaz
Predpostavimo, da obstaja k-faktorski aproksimacijski algoritem A za PTP. Dokaˇzimo, da tedaj obstaja v polinomskem ˇcasu reˇsljiv algoritem za problem obstoja Hamiltonovega cikla. Ker je slednji NP-poln po izreku 3.2, iz tega sledi, da je P=NP.
Imejmo grafGin konstruirajmo primer PTP zn=|V(G)|toˇckami, kjer so cene definirane kot c:E(Kn)→Z+ na naslednji naˇcin:
c({i, j}) :=
1, ˇce{i, j} ∈E(G), 2 + (k−1)n, ˇce{i, j}∈/ E(G).
Sedaj uporabimo algoritem A na tem primeru. ˇCe ima vrnjen obhod ceno n, potem je ta obhod Hamiltonov cikel v G. V nasprotnem primeru ima vrnjen obhod ceno najmanj n−1 + 2 + (k−1)n = kn+ 1. ˇCe je OPT(Kn, c) cena minimalnega obhoda, potem je kn+ 1 ≤ kOPT(Kn, c), saj je A k-faktorski aproksimacijski algoritem. Iz tega sledi, da velja OPT(Kn, c)> n, kar pomeni, da G nima Hamiltonovega cikla.
Posvetimo se sedaj nekaterim aproksimacijskim algoritmom in podrobneje spoznajmo njihovo delovanje.
ALGORITEM NAJBLIˇZJEGA SOSEDA
Algoritem najbljiˇzjega soseda je bil eden izmed prvih algoritmov za reˇsevanje problema trgovskega potnika. V njem trgovski potnik zaˇcne v poljubni toˇcki in vedno znova kot na- slednjo obiˇsˇce toˇcko, ki je izmed vseh neobiskanih toˇck najbljiˇzje (oz. je cena poti najniˇzja) trenutni toˇcki. Algoritem obiskovanje najbliˇzjih toˇck ponavlja, dokler niso obiskana vsa mesta. Algoritem deluje zelo hitro, vendar pa obiˇcajno izbran obhod ni optimalen. Za- radi svoje poˇzreˇsne narave ta algoritem velikokrat vrne precej slabe reˇsitve. Casovnaˇ zahtevnost je O(n2). Algoritem sicer ni konstantno-faktorski aproksimacijski algoritem.
Za METRI ˇCNI PTP velja, da za neskonˇcno mnogo vrednosti nobstajajo primeri (Kn, c), za katere algoritem najbliˇzjega soseda vrne obhod dolˇzine 13OPT(Kn, c)logn [3].
ALGORITEM PODVOJENEGA DREVESA
Pri algoritmu podvojenega drevesa si pomagamo s Primovim algoritmom za iskanje mi- nimalnega vpetega drevesa in Eulerjevim algoritmom za iskanje Eulerjevega sprehoda.
PRIMOV ALGORITEM
Vhodni podatek: Povezan neusmerjen grafG s cenovno funkcijoc:E(G)→R. Izhodni podatek: Minimalno vpeto drevo T.
Algoritem deluje po naslednjih korakih:
1. Izberi poljubno toˇcko v ∈V(G), T := ({v},∅).
2. Dokler V(T)6=V(G):
Izberi povezavo e∈δG+(V(T)) z minimalno ceno.
T :=T +e
Pri tem δG+(V(T)) predstavlja mnoˇzico vseh povezav e = v1v2, kjer v1 ∈ V(T) in v2 ∈/ V(T), v2 ∈V(G).
Izrek 4.4 Primov algoritem ima ˇcasovno zahtevnost (O(n2)). [3]
Dokaz
Za vsako toˇcko v ∈ V(G)\V(T) izberemo najcenejˇso povezavo e, ki povezuje toˇcko v in toˇcko iz mnoˇzice E(V(T) (ˇce obstaja). Tem povezavam bomo rekli kandidati. Inicia- lizacija kandidatov ima ˇcasovno zahtevnost O(m), saj moramo pregledati vse povezave.
Vsaka izbira najcenejˇse povezave med kandidati ima ˇcasovno zahtevnost O(n), saj mo- ramo v najslabˇsem primeru primerjati n − 1 povezav. Posodobitev kandidatov lahko naredimo s pregledom povezav, ki imajo krajiˇsˇce v toˇcki, ki je bila dodana v V(T). Tudi to nam vzame O(n) korakov, saj moramo v najslabˇsem primeru pregledati n−2 povezav.
Ker pa ima dokler-zanka v 2. koraku n−1 ponovitev je s tem ˇcasovna zahtevnost O(n2)
dokazana.
Reˇsevanje PTP 41
EULERJEV ALGORITEM
Vhodni podatek: Neusmerjen povezan Eulerjev graf G.
Izhodni podatek: Eulerjev sprehod W v G.
EulerjevObhod(G, v) [4]
zaˇcetek
inicializacija W ˇ
ce v nima sosednih povezav potem vrni prazen obhod [v]
drugaˇce
Zaˇcenˇsi v toˇcki v sestavi obhodW, ki ne porabi nobene povezave dvakrat.
Izbriˇsi povezave na W v G.
Za vsako toˇcko u naW ponovi:
S klicem EulerjevObhod(G,u) poiˇsˇci Eulerejev obhod Wu v povezani komponenti grafa, ki vsebujeu.
Odstrani povezave obhoda Wu iz grafa G.
Na mestu pojavitve una W vstavi dobljeni obhod Wu. Vrni dobljeni sestavljeni obhod.
konec
Izrek 4.5 [3] Eulerjev obhod v Eulerjevem grafu G lahko poiˇsˇcemo v linearnem ˇcasu (O(|E(G)|)).
Dokaz
Naj bo G Eulerjev graf. Z indukcijo na ˇstevilo povezav v G bomo dokazali, da Eulerjev algoritem vrne Eulerjev sprehod. ˇCe je |E(G)| = 0, tedaj ima graf eno samo toˇcko in tako je trivialni sprehod dolˇzine niˇc Eulerjev. V sploˇsnem primeru pa izberemo toˇcko v ∈ V(G). Najprej poiˇsˇcemo poljuben sklenjen sprehod zaˇcenˇsi v toˇcki v. Iskanje ni teˇzko: odpravimo se v poljubno sosedo toˇcke v. Ker ima toˇcka, v katero tako pridemo,
sodo mnogo sosedov, je incidenˇcna z vsaj eno povezavo, ki je ˇse nismo prehodili. Zato lahko nadaljujemo sprehod po neki neprehojeni povezavi. To se nadaljuje, dokler ne pridemo nazaj v zaˇcetno toˇcko v. Ker ima graf konˇcno mnogo povezav, se to prej ko slej tudi zgodi. Sedaj odstranimo povezave tako dobljenega sprehoda iz G in induktivno v vsaki od preostalih povezanih komponent poiˇsˇcemo Eulerjev sprehod. To lahko storimo, saj so v ostanku vse toˇcke sode stopnje - v vsaki toˇcki smo namreˇc odvzeli sodo mnogo povezav.
Oˇcitno je, da iz prvotno dobljenega sprehoda in Eulerjevih sprehodov v preostalem delu lahko sestavimo Eulerjev sprehod v G. Primer je prikazan na sliki 4.2.
Slika 4.2: Primer iskanja Eulerjevega obhoda.
Casovna zahtevnost je linearna, saj je vsaka povezava izbrisana takoj za tem, ko je bilaˇ
uporabljena.
Lema 4.6 [3] Imejmo primer (Kn, c) metriˇcnega PTP in povezan Eulerjev graf G, vpet na V(Kn), lahko tudi z vzporednimi povezavami. Potem lahko sestavimo obhod s ceno najveˇc c(E(G)) v linearnem ˇcasu.
Dokaz
Po izreku 4.5 lahko Eulerjev sprehod v Gnajdemo v linearnem ˇcasu. Vrstni red v katerem se toˇcke pojavljajo v tem sprehodu (zanemarimo vse razen prvega pojava toˇcke) doloˇci obhod. Iz trikotniˇske neenakosti takoj sledi, da ta obhod ni daljˇsi kot c(E(G)).
Reˇsevanje PTP 43
Sedaj lahko predstavimo algoritem podvojenega drevesa.
ALGORITEM PODVOJENEGA DREVESA
Vhodni podatek: Primer (Kn, c) metriˇcnega PTP.
Izhodni podatek: Obhod.
Algoritem deluje po naslednjih korakih:
1. Poiˇsˇci minimalno vpeto drevo T v Kn z upoˇstevanjem funkcije c.
2. Podvoji vsako povezavo v T, da dobiˇs vpet Eulerjev graf G.
3. Poiˇsˇci Eulerjev sprehod v tako dobljenem grafu.
4. Iz dobljenega sprehoda doloˇci obhod trgovskega potnika kot v dokazu leme 4.6.
Izrek 4.7 [3] Algoritem podvojenega drevesa je 2-faktorski aproksimacijski algoritem za metriˇcni PTP. ˇCasovna zahtevnost je O(n2).
Dokaz
Poglejmo najprej ˇcasovno zahtevnost. Iskanje minimalnega vpetega drevesa ima zahtev- nost O(n2), preostali trije koraki pa se dajo opraviti v linearnem ˇcasu O(n). Skupna ˇ
casovna zahtevnost je torej O(n2).
c(E(T))≤OPT(Kn, c), saj ˇce zbriˇsemo katerokoli povezavo na (optimalnem) obhodu, do- bimo vpeto drevo, drevoT pa je najcenejˇse. Tako jec(E(G)) = 2c(E(T))≤2OP T(Kn, c).
Obhod je torej najveˇc dvakrat daljˇsi od optimalnega. Po lemi 4.6 je cena obhoda, ki ga
vrne zgornji algoritem, najveˇc c(E(G)).
CHRISTOFIDESOV ALGORITEM
Christofidesov algoritem je uˇcinkovita izboljˇsava algoritma podvojenega drevesa. Imeno- van je po Nicosu Christofidesu.
CHRISTOFIDESOV ALGORITEM
Vhodni podatek: Primer (Kn, c) metriˇcnega PTP.
Izhodni podatek: Obhod.
Algoritem deluje po naslednjih korakih:
1. Poiˇsˇci minimalno vpeto drevo T v Kn z upoˇstevanjem funkcije c.
2. Naj bo W mnoˇzica toˇck lihe stopnje v T. Poiˇsˇci najcenejˇse maksimalno prirejanje M v polnem grafu s toˇckami W.
3. Drevesu T dodaj povezave grafa M, tako dobiˇs graf G.
4. V Eulerjevem grafu G (Eulerjev je, ker je povezan, vse toˇcke pa so sode stopnje) poiˇsˇci Eulerjev sprehod.
5. Iz dobljenega sprehoda doloˇci obhod trgovskega potnika kot v dokazu leme 4.6.
Dokazati se da, da je Christofidesov algoritem 32-faktorski aproksimacijski algoritem za metriˇcni PTP. ˇCasovna zahtevnost je O(n3). (Bralcu, ki bi si ˇzelel ogledati dokaz teh dejstev, priporoˇcamo ogled knjige [3], poglavje 21.)
4.2.3 LOKALNA OPTIMIZACIJA
Za reˇsevanje PTP se v praksi uporablja tudi lokalna optimizacija, ki je v sploˇsnem uspeˇsna metoda za pridobivanje dobrih reˇsitev.
Ideja je naslednja: zaˇcnemo z nekim obhodom, ki ga dobimo s pomoˇcjo poljubnega algo- ritma. Nato poskuˇsamo izboljˇsati naˇso reˇsitev z doloˇcenimi lokalnimi spremembami. Na primer, naˇs obhod lahko razbijemo na dva dela tako, da izbriˇsemo dve povezavi in nato sestavimo dela v drugaˇcen obhod.
Vnaprej je potrebno sprejeti dve odloˇcitvi:
