¨ tvo ¨ s Lora ´ nd Tudoma ´ nyegyetem Eo ´szettudoma ´ nyi kar Terme
Az utaz´ ou ¨ gyn¨ ok probl´ ema ´ es alkalmaz´ asai Szakdolgozat Kulcs´ ar Zolt´ an Matematika BSc Matematikai elemz˝o szakir´any
T´emavezet˝o: Kiss Attila Sz´am´ıt´og´eptudom´anyi Tansz´ek
Budapest, 2017
K¨ osz¨ onetnyilv´ an´ıt´ as Munk´ am v´eg´ere ´erve szeretn´em megk¨ osz¨onni t´emavezet˝omnek, Kiss Attil´anak azt a rengeteg seg´ıts´eget ´es t´ amogat´ ast, mellyel hozz´ aj´ arult szakdolgozatom ´ır´as´ahoz, ezzel el˝oseg´ıtv´en annak megsz¨ ulet´es´et. K¨ osz¨ onet illeti m´eg Recski Andr´ ast, aki felkeltette az ´erdekl˝od´esemet a v´eges matematika ir´ant. K¨ ul¨ on k¨ osz¨ onet a csal´ adomnak ´es bar´ ataimnak t´amogat´asuk´ert ´es t¨ urelm¨ uk´ert, valamint bar´atn˝omnek, aki mindezek mellett a nyelvi ´ attekint´esben is seg´ıts´egemre volt.
”Az u ´t ¨ or¨ ok ´es t´etlen m´egis mindent v´egbevisz ´eszrev´etlen...” ´ ´es Er´eny k¨onyve Lao-Ce, Tao Te King: Az Ut We¨ ores S´ andor ford´ıt´ as´ aban, Tericum Kiad´o, 1994. (37. vers)
1
Tartalomjegyz´ ek 1. Bevezet´ es
3
2. Alapfogalmak 2.1. A TSP megold´ asa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
5 7
3. Bonyolults´ agelm´ elet 3.1. A determinisztikus Turing-g´ ep . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3.2. A nemdeterminisztikus Turing-g´ ep . . . . . . . . . . . . . . . . . . . . . . . . .
8 8 9
4. Korl´ atok 4.1. Als´ o korl´ atok . . . . . 4.1.1. 1-fa als´ o korl´ at 4.1.2. Held-Karp als´ o 4.2. Fels˝ o korl´ at . . . . . .
. . . .
11 11 11 11 12
5. Approxim´ aci´ ok 5.1. Christofides algoritmusa . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
13 14
´ ep´ıt˝ 6. Ut´ o algoritmusok 6.1. Moh´ o algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.2. Boruvka algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6.3. Besz´ ur´ asos algoritmusok . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
16 16 16 17
7. Jav´ıt´ o algoritmusok 7.1. 2-opt . . . . . . . . . . . . . 7.2. 3-opt . . . . . . . . . . . . . 7.3. k-opt . . . . . . . . . . . . . 7.4. Lin-Kernighan algoritmus 7.5. Tabu keres´ es . . . . . . . .
. . . . . . . . . . korl´ at . . . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
18 18 19 19 19 22
8. Alkalmaz´ asok 8.1. Klaszterek bej´ ar´ asa TSP-vel . . . . . . 8.2. Concorde . . . . . . . . . . . . . . . . . . 8.3. Nyomtatott ´ aramk¨ or¨ ok ¨ osszeszerel´ ese 8.3.1. A probl´ ema megold´ asa . . . . . . 8.3.2. Az elj´ ar´ as teljes´ıtm´ enye . . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
23 23 24 27 31 32
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
. . . . .
¨ 9. Osszefoglal´ as
. . . . .
34
2
1. Bevezet´ es Szakdolgozatom f˝ o motiv´ aci´ oja a v´eges matematika, azon bel¨ ul is a gr´afelm´elet ir´anti ´erdekl˝od´esem volt. Ezek ut´ an j´ ol megfontolt v´ alaszt´asom egy egyszer˝ unek t˝ un˝o, ´amde ann´al ¨osszetettebb gr´afelm´eleti optimaliz´ al´ asi feladatra esett. Ez az utaz´o u ¨gyn¨ok probl´em´aja. A feladat igen egyszer˝ u: Adott n v´ aros, valamint az u ´tik¨olts´eg/t´avols´ag b´armely k´et v´aros k¨oz¨ott ´es keress¨ uk a legolcs´ obb/legr¨ ovidebb utat egy adott v´arosb´ol indulva, amely minden v´arost pontosan egyszer ´erint, majd a kiindul´ asi v´ arosba ´er vissza. Ez megfeleltethet˝o egy gr´afelm´eleti probl´em´anak, a minim´ alis s´ uly´ u Hamilton-k¨ or keres´es´enek, egy adott ´el s´ ulyozott gr´afban.
Frod´ o´ek is ezt a legr¨ ovidebb utat kerest´ek, b´ ar ˝ ok a megszokott´ ol elt´er˝ oen s´ ulyozt´ ak az utat. A probl´ema elsz¨ or 1832-ben egy k´ezik¨onyvben [1] t˝ unt fel, ahol 45 n´emet v´aros k¨oz¨otti legr¨ ovidebb u ´tvonalat kerest´ek, de ennek csak k´es˝obb, 1983-ban adtak jelent˝os´eget. Nem sokkal k´es˝obb Sir William Rowan Hamilton [2][3] ´es Thomas Penyngton Kirkman [4] vetette fel a probl´em´at az 1850es ´evekben, icosian j´ at´ek form´ aj´ aban, ez egy olyan logikai j´at´ek, melynek c´elja, hogy egy ’gr´afban’ 3
k¨ orutat kell tal´ alni. Az probl´ema ´ altal´anos alakja csak k´es˝obb, 1930-ban alakult ki. A n´ev Travelling Salesman Problem (TSP) is ez id˝o t´ajt alakult ki. Ez id˝oben Karl Menger [5] foglalkozott a feladattal ´es ´ert el eredm´enyeket ezzel kapcsolatban. Meg´allap´ıtotta p´eld´aul, hogy a legk¨ozelebbi szomsz´ed algoritmus nem mindig ad optim´alis megold´ast a feladatra. Ezek ut´an Menger el˝o is adta eredm´enyeit a Harvardon ´es a Princetonon, mellyel t¨obb neves matematikus figyelm´et is felh´ıvta a TSP-re. Hassler Whitney fel is figyelt a probl´em´ara, a 48 amerikai ´allam k¨ozt kereste a legr¨ovidebb utat a harmincas ´evek elej´en. Ekkor t´ajt h´ıvt´ak fel Flood [6] figyelm´et is a TSP ´es az iskolabuszok u ´tvonal´ anak tervez´ese k¨ oz¨ otti kapcsolatra. A 40-es ´evekre kezdett n´epszer˝ uv´e v´alni a feladat ´es t¨ obb atfogalmaz´ ´ asa is megjelent, ´eppen emiatt sok m´as optimaliz´al´asi feladat hozz´aj´arult a fejl˝od´eshez. Az igazi n´epszer˝ us´eget a TSP-nek azonban 1954-ben hozta el Dantzig, Fulkerson, ´es Johnson [7]. Az altaluk ´ırt cikkben megoldott´ ´ ak a 49 amerikai v´arosra a feladatot (48 ´allam mindegyik´eb˝ol 1-1 v´ aros ´es m´eg Washington D.C.) ´es t¨ obb u ´j m´odszert is kidolgoztak a TSP megold´as´ara, megmutatt´ak a v´ ag´ os´ıkok jelent˝ os´eg´et. Ezut´ an ¨ orvendett igazi n´epszer˝ us´egnek a TSP ´es k´es˝obb t¨obb nagyszab´ as´ u kutat´ as alapj´ aul szolg´ alt a fent eml´ıtett cikk. A 60-as ´evekt˝ol napjainkig egyre sz´elesebb k¨orben terjedt el a probl´ema ´es szakdolgozatom egyik c´elja, hogy az utaz´o u ¨gyn¨ok probl´ema alkalmaz´asait bemutassa. Rengeteg p´elda van az alkalmaz´asokra, a k´es˝obbiekben p´arat jobban is megvizsg´alunk. ´ Ev 1954 1971 1975 1977 1980 1987 1987 1987 1994 1998 2001 2004
Kutat´ o csapat G. Dantzig, R. Fulkerson, and S. Johnson [7] M. Held and R.M. Karp [8] P.M. Camerini, L. Fratta, and F. Maffioli [9] M. Gr¨otschel [10] H. Crowder and M.W. Padberg [11] M. Padberg and G. Rinaldi [12] M. Gr¨ otschel and O. Holland [13] M. Padberg and G. Rinaldi [14] D. Applegate, R. Bixby, V. Chv´atal, and W. Cook [15] D. Applegate, R. Bixby, V. Chv´atal, and W. Cook [16] D. Applegate, R. Bixby, V. Chv´atal, and W. Cook [17] D. Applegate, R. Bixby, V. Chv´atal, W. Cook, and K. Helsgaun [18]
Feladat m´ erete 49 v´aros 64 v´aros 67 v´aros 120 v´aros 318 v´aros 532 v´aros 666 v´aros 2,392 v´aros 7,397 v´aros 13,509 v´aros 15,112 v´aros 24,978 v´aros
A k¨ ul¨ onb¨ oz˝ o m´eret˝ u TSP-k megold´ asa az ´evek sor´ an (1954-2004) Szakdolgozatomat az alapfogalmak tiszt´az´as´aval kezdem, majd a Hamilton-k¨or l´etez´es´ere vonatkoz´ o t´eteleket ismertetem. Ezut´ an a 3. fejezetben a probl´ema neh´ezs´eg´evel foglalkozok, bemutatva a Turing-g´epet, majd ezt felhaszn´ alva az NP-neh´ezs´eget. A 4. fejezetben a TSP megold´ as´ anak als´o ´es fels˝o korl´atait mutatom be, majd ezut´an az 5. fejezetben approxim´ aci´ os algoritmusokat mutatok be a TSP megold´as´ara. A 6. fejezetben az u ´t´ep´ıt˝ o algoritmusok m˝ uk¨od´es´et mutatom be, m´ıg a 7. fejezetben a jav´ıt´ o algoritmusok´et. Ezek ut´ an a 8. fejezetben t´erek r´ a a TSP alkalmaz´asaira, amelyben a klaszterez´essel, a Concorde-dal ´es a nyomtatott ´ aramk¨ or¨ ok ¨ osszeszerel´es´evel foglalkozom. V´egezet¨ ul a 9. fejezetben ¨ osszefoglalom szakdolgozatom mondanival´oj´at.
4
2. Alapfogalmak Defin´ıci´ o. A G = (E, ϕ, V ) gr´ af H = v0 e1 v1 e2 v2 ...vn−1 en vn u ´tj´at (ϕ(e1 ) = (v0 , v1 ), ϕ(e2 ) = (v1 , v2 ), ..., ϕ(en ) = (vn−1 , vn )) Hamilton-´ utnak mondjuk, ha a *v0 , v1 , v2 , ..., vn−1 , vn cs´ ucsok mind k¨ ul¨onb¨oz˝ok ´es ezeken a pontokon k´ıv¨ ul m´ as cs´ ucspontja nincs G-nek. A G = (E, ϕ, V ) gr´af K k¨or´et Hamilton-k¨ ornek mondjuk, ha K G gr´ af minden pontj´at tartalmazza. Megjegyz´es: Ha egy Hamilton-k¨ or tetsz˝oleges ´el´et elhagyjuk, akkor egy Hamilton-utat kapunk. A s´ ulyozott Hamilton-k¨ or keres´esi feladatnak l´etezik egy igen sz´eles k¨orben elterjedt megfogalmaz´ asa, ¨ az Utaz´ o Ugyn¨ ok probl´ema. Egy u ¨gyn¨ oknek meg kell l´ atogatnia adott v´arosokat u ´tja sor´an, majd a kiindul´asi v´aros´aba kell viszszat´ernie u ´gy, hogy minden v´ arosban csak egyszer j´art. Adott, hogy az egyik v´ arosb´ ol a m´ asikba milyen k¨olts´egek mellett tud eljutni. Term´eszetesen szeretn´e a k¨ or´ ut ¨ osszk¨ olts´eg´et minimaliz´alni. Ezen feladat alkalmaz´asa igen soksz´ın˝ u, de csak speci´ alis esetekben tal´ alhatunk j´ o algoritmust a megold´as´ara. Tegy¨ uk fel, hogy van olyan v´ aros, amelyb˝ol egy m´asikba nem lehet k¨ozvetlen¨ ul eljutni, m´ıg a t¨ obbi v´ arosba, ahov´ a vezet k¨ ozvetlen u ´t, ugyanolyan k¨olts´eggel mehet az u ¨gyn¨ok, ´es minden v´arost megl´ atogat pontosan egyszer, majd visszat´er a kiindul´asi v´arosba. Ekkor a feladat a Hamilton-k¨ or l´etez´es´ere reduk´ al´ odik, hisz ha a v´ arosokat megfeleltetj¨ uk egy gr´af cs´ ucsainak, ´es k´et cs´ ucs k¨oz¨ ott akkor ´es csak akkor van ´el, ha a nekik megfelel˝o v´arosok k¨ozt van k¨ozvetlen u ´t. Ebben az esetben akkor l´etezik Hamilton-k¨or, ha l´etezik n ¨osszk¨olts´eg˝ u k¨or´ ut, mely minden v´arost ´erint. A l´etez´es´ere vonatkoz´ oan t¨ obb el´egs´eges felt´etelt is adtak, n´eh´anyat ismertet¨ unk itt. Term´eszetesen mindenhol olyan egyszer˝ u gr´ afr´ ol besz´el¨ unk ahol a cs´ ucsok sz´ama nagyobb, mint h´arom azaz n > 3. Megeml´ıt¨ unk egy sz¨ uks´eges felt´etelt is, ez azonban nem el´egs´eges, sajnos sz¨ uks´eges ´es el´egs´eges felt´etel nincs. A Hamilton-k¨ or l´etez´es´enek egy sz¨ uks´eges felt´etele az al´abbi. ´ ıt´ All´ as. Ha a G gr´ afban k pontot t¨ or¨ olve a gr´af t¨obb mint k komponensre esik, akkor a gr´afban nem l´etezik Hamilton-k¨ or. Hasonl´ oan, ha l´etezik k olyan pont, amelyeket t¨or¨olve a gr´af t¨obb mint k+ 1 komponensre esik, akkor a gr´ afban nincs Hamilton-´ ut. Bizony´ıt´ as. Indirekt tegy¨ uk fel, hogy van a gr´ afban Hamilton-k¨or, de k pontot elhagyva a gr´af k-n´al t¨obb komponensre esik sz´et. Gondoljuk meg, hogy a Hamilton-k¨or tartalmazza a gr´af minden pontj´at ´ıgy a feladat ´ at´ırhat´ ou ´gy, hogy egy k¨ orb˝ ol k pontot elhagyva a k¨or sz´eteshet-e k-n´al t¨obb komponensre. Erre a v´ alasz nyilv´ anval´ oan nem, hisz k¨onnyen l´atszik, hogy egy pont elhagy´asa ut´an m´eg mindig egy komponens¨ unk lesz. Ez ut´ an m´ aris egyen´ert´ek˝ u lesz a feladat a Hamilton-´ utra vonatkoz´o felt´etellel, amely ebben a megfogalmaz´ asban trivi´alis, hiszen egy u ´tb´ol egy cs´ ucsot elhagyva az maximum k´et komponensre esik sz´et.
5
Vannak term´eszetesen j´ ol haszn´ alhat´o, el´egs´eges felt´etelek is Hamilton-k¨or l´etez´es´ere, l´assunk n´eh´ anyat. T´ etel. [Ore][19] Ha az n pont´ u G gr´ afban b´ armely k´et nem szomsz´edos x, y ∈ V (G) pontp´arra, teljes¨ ul, hogy d(x) + d(y) ≥ n, akkor a gr´ afban van Hamilton-k¨or. M´ask´epp, ha az n pont´ u G gr´afban b´armely k´et szomsz´edos x, y ∈ V (G) pontp´ arra, teljes¨ ul, hogy d(x)+d(y) < n, akkor a gr´afban van Hamilton-k¨ or. Bizony´ıt´ as. Indirekt tegy¨ uk fel, hogy a gr´ af kiel´eg´ıti a felt´etelt, de nincsen benne Hamilton-k¨or. Vegy¨ unk hozz´ aa gr´ afhoz ´eleket mindaddig, am´ıg m´ ar b´arhogyan is vesz¨ unk hozz´a u ´jabb ´elet, lesz a gr´afban Hamilton k¨ or. ´Igy kapunk egy G’ gr´ afot, melyre tov´abbra is teljes¨ ul a felt´etel. Teh´at biztos van k´et olyan pont, hogy nem szomsz´edosak G’-ben. Ha e pontok k¨oz´e beh´ uzn´ank egy ´elt, akkor az ´ıgy kapott gr´afban lenne Hamilton-k¨ or. Ez azt jelenti, hogy G’-ben van Hamilton u ´t. Legyen ez P = (v1 , v2 . . . vn ), ahol v1 ´es vn k¨ ozt nem fut ´el. Ha v1 szomsz´edos P valamely vk pontj´aval, akkor vn nem lehet szomsz´edos vk−1 -el hiszen akkor (v1 , . . . , vk−1 , vn , vn−1 , . . . vk , v1 ) egy Hamilton-k¨or lenne, azaz vn nincs ¨ osszek¨ otve legal´ abbd(v1 ) darab ponttal. Ebb˝ ol k¨ ovetkezik, hogy: d(vn ) ≤ n − 1 − d(v1 ) Ami viszont ellentmond´as, mert v1 ´es vn nem szomsz´edos cs´ ucsok. Az el˝ oz˝ o t´etel k¨ ozvetlen¨ ul k¨ ovetkezik a Dirac t´etelb˝ol, Ore ez alapj´an alkotta meg ezt az ´eles´ıt´est. T´ etel. [Dirac] [20] Ha egy n pont´ u egyszer˝ u gr´ afban minden pont foksz´ama legal´abb Hamilton-k¨ or.
n 2
Bizony´ıt´ as. Ez k¨ ovetkezik az Ore t´etelb˝ ol, hiszen ha minden pont foka legal´abb t´etel felt´etele.
akkor a gr´afban biztosan van
n 2,
akkor trivi´alisan teljes¨ ul a
Tov´ abbi el´egs´eges felt´etelek is ismertek Hamilton-k¨or l´etez´es´ere, t¨obbek k¨oz¨ott magyar eredm´eny is van ezzel kapcsolatban, amit P´ osa Lajos publik´alt [21] 1962-ben. Emellett megn´ezz¨ uk m´eg Chv´ atal [22] t´etel´et is, melynek l´enyege az, hogy ha el´eg sok ´ele van egy gr´afnak akkor van benne Hamilton k¨ or. T´ etel. [P´ osa] Jel¨ olj¨ uk G pontjainak foksz´ amait nagys´ag szerint n¨ovekv˝o sorrendben d1 ≤ d2 ≤ ... ≤ dn –nel. Ha minden k < n2 -re dk ≥ k + 1, akkor G-ben van Hamilton-k¨or. T´ etel. [Chv´ atal] Az el˝ oz˝ o jel¨ ol´esekkel, ha minden k-ra, amelyre dk < k < n/2 teljes¨ ul az, hogy dnk > n − k, akkor a gr´ afban van Hamilton-k¨ or.
6
2.1. A TSP megold´asa A probl´ema megold´ asa nem egy egyszer˝ u feladat, b´ar k´ezenfekv˝o, hogy minden Hamilton-k¨ort megkeres¨ unk ´es kiv´ alasztjuk az optim´ alis utat, ez azonban nagyobb gr´afokn´al szinte lehetetlen. Ugyanis egy n pont´ u gr´ afn´ al (n−1)! lehet˝ os´eget kellene kipr´ob´alnunk. Ha sz´am´ıt´og´ep¨ unk 1000000 Hamilton2 k¨ ort tud megtal´ alni m´ asodpercenk´ent, akkor is 15 v´arosra m´ar t¨obb mint egy napba telne megtal´ alni az optim´ alis eredm´enyt, m´ıg 20 v´ arosra t¨obb mint 20 milli´o ´evbe telne megtal´alni a megold´ast. ´Igy teh´ at a ’brute force’ megold´ as nem c´elra vezet˝o. B´ ar 1962-ben Bellman [23], Held ´es Karp [24] kital´alt egy algoritmust, ami reduk´alta a ’brute force’ elj´ ar´ as id˝ oig´eny´et, de m´eg az is csak O(n2 2n ) id˝oig´eny˝ u, ez azt jelenti, hogy 50 v´aros eset´en m´ar ez is t´ uls´ agosan id˝ oig´enyes, nem haszn´ alhat´o. De vajon van-e olyan algoritmus, amely ´esszer˝ u id˝oben meg tudja oldani a probl´em´ at? Ehhez arra lenne sz¨ uks´eg¨ unk, hogy az elj´ar´as polinomi´alis id˝oben lecsengjen. Azonban sajnos a feladat NP neh´ez.
7
3.
Bonyolults´ agelm´ elet
Hogy meg´erts¨ uk az NP neh´ez fogalom defin´ıci´oj´at, el˝osz¨or meg kell ´erten¨ unk a Turing-g´ep fogalm´ at. A Turing-g´epet (Turing Machine - TM) Alan Turing angol matematikus ismertette el˝osz¨or 1936-ban megjelent cikk´eben [25].
3.1. A determinisztikus Turing-g´ep A g´ep egy olyan matematikai modell, amely egy (vagy ak´ar t¨obb) mindk´et ir´anyban v´egtelen hossz´ us´ ag´ u szalagb´ ol ´ all. Ez(ek) a szalag(ok) mez˝okre van(nak) osztva, amelyek az inputot tartalmazz´ ak. Minden szalag egy kit¨ untetett nulladik mez˝ovel kezd˝odik ´es minden mez˝o egy v´eges Σ ab´ec´eb˝ ´ ol tartalmazhat jelet. Van egy speci´alis 0 ∗0 jel, ami az u ¨res mez˝ot jel¨oli ´es v´eges sok olyan mez˝ o van, amelybe 0 ∗0 jelt˝ ol k¨ ul¨ onb¨ oz˝o karaktert ´ırunk. Tov´ abb´ a a szalagokhoz tartozik egy ´ır´o-olvas´o fej, mely a szalag egy mez˝oj´et tudja leolvasni, majd fel¨ ul´ırni azt ´es esetleg egyet jobbra vagy balra l´epni. A g´ep emellett egy k¨ ozponti egys´eget haszn´al, amelynek lehets´eges ´allapotai egy v´eges Γ halmaz elemei. A legfontosabb ´ allapotai a Start ´es k´et le´all´asi ´allapot az ELF(elfogad) ´es az ELUT (elutas´ıt´ as). Indul´ askor mindig a START ´ allapotb´ol kezd¨ unk, a fej(ek), szalag(ok) kezd˝omez˝oj´en (0.-ik mez˝ on) van(nak). Az egyszer˝ us´eg kedv´e´ert tegy¨ uk fel, hogy egy szalag van. A fej minden l´ep´esben leolvassa a jelet, majd ez alapj´ an a k¨ ozponti egys´eg a k¨ovetkez˝oket csin´alhatja: ´ • Allapotot v´ alt • A fejnek utas´ıt´ ast ad, hogy ´ırjon • A fejnek utas´ıt´ ast ad, hogy tov´ abbl´epjen A g´ep akkor ´ all le, ha a k¨ ozponti egys´eg ELF vagy ELUT ´allapotba ker¨ ul. A Turing-g´epet matematikailag a k¨ ovetkez˝ok´eppen ´ırhatjuk le: T = hk, Σ, Γ, α, β, γi, ahol k pozit´ıv eg´esz sz´am a szalagok sz´ama, Σ ´es Γ a fent eml´ıtett v´eges halmazok, ∗ ∈ Σ, ST ART, ELF, ELU T ∈ Γ ´es
γ:
α:
Γ × Σk → Γ
β:
Γ × Σk → Σk
Γ × Σk → {−1, 0, 1}
tetsz˝ oleges lek´epez´esek. α adja meg az u ´j ´allapotot, β a szalagokra ´ırt jeleket, γ a fej l´ep´eseit. AΣ´ ab´ec´et r¨ ogz´ıtettnek vessz¨ uk ´es feltessz¨ uk, hogy legal´abb h´arom jelb˝ol ´all, tartalmazza a ’*’-ot ´es mondjuk 0-t ´es 1-et (a legt¨ obb esetben elegend˝o erre a k´et jelre szor´ıtkozni). Egy Turing-g´ep bemenet´en az indul´askor a szalagon l´ev˝o szavakat ´ertj¨ uk. Ezek a szavak, mindig ´ a kezd˝ omez˝ ot˝ ol kezdve van a szalagra ´ırva. Erdemes f¨oltenni, hogy a szavak a 0 ∗0 jelet nem tartalmaznak (K¨ ul¨ onben nem lehetne tudni, hogy hol van a bemenet v´ege). Az ´ab´ec´et a 0 ∗0 n´elk¨ ul Σ0 -lal jel¨ olj¨ uk. Feltessz¨ uk azt is, hogy a Turing-g´ep az eg´esz bemenet´et elolvassa m˝ uk¨od´ese sor´an. A g´ep kimenete a meg´ all´ askor a szalagokon lev˝o szavakb´ol ´all´o rendezett sor.
8
´ ıt´ All´ as Minden t¨ obb szalagos (k ≥ 2) S Turing-g´ephez l´etezik olyan egy szalagos T Turing-g´ep, amely S-et p´ otolja. Ez u ´gy n´ez ki, hogy minden x sz´ora (x *-ot nem tartalmaz), S csak abban az esetben ´ all meg v´eges sok l´ep´esben x-en, ha T meg´all ´es meg´all´askor S utols´o szalagj´ara ugyanaz lesz ´ırva, mint T szalagj´ ara. Tov´ abb´ a, ha S n l´ep´est tesz, akkor T O(n2 ) l´ep´est fog tenni. Defin´ıci´ o. Egy T Turing-g´ep eld¨ onti az L nyelvet, ha minden inputra le´all v´eges sok l´ep´esben ´es egy x inputra pontosan akkor ´ all meg ELF ´ allapotban, ha x ∈ L. Egy nyelv akkor lesz algoritmikusan eld¨onthet˝o, hogyha van olyan Turing-g´ep, ami eld¨onti ˝ot.
3.2. A nemdeterminisztikus Turing-g´ep A determinisztikus ´es nemdeterminisztikus Turing-g´ep k¨ozt a k¨ ul¨onbs´eg annyi, hogy a nemdeterminisztikus Turing-g´ep k¨ ozponti egys´eg´enek ´allapota ´es a leolvasott jelek alapj´an t¨obb lehets´eges l´ep´est tehet. Form´ alisan, T = hk, Σ, Γ, α, β, γi-ben minden v´altozatlan, kiv´eve α, β, γ :
γ⊆
α⊆
Γ × Σk × Γ
β⊆
Γ × Σk × Σ k
Γ × Σk × {−1, 0, 1}k
A nemdeterminisztikus Turing-g´epekkel nem szeretn´enk semmilyen val´odi sz´amol´o- eszk¨ozt sem modellezni, ezek a g´epek a feladatok kit˝ uz´es´enek eszk¨ozei. A nemdeterminisztikus Turing-g´ep egy leg´alis sz´amol´as´an a l´ep´esek egy sorozat´at ´ertj¨ uk, ahol minden egyes l´ep´esben (mint a determinisztikus Turing-g´epn´el) a k¨ozponti egys´eg u ´j ´allapotba ker¨ ul, a fej u ´j jeleket ´ır ´es esetleg l´ep egyet jobbra vagy balra. A g´ep egy szitu´aci´oban t¨obbf´ele l´ep´est tehet, ezeknek nincs ismert eloszl´ asuk, azaz a sz´amol´asnak nincs v´arhat´o ´ert´eke. Most pedig a Turing-g´ep seg´ıts´eg´evel defini´aljuk a P ´es NP oszt´alyt. Defin´ıci´ o. A P azoknak a nyelveknek az oszt´ alya, amelyekhez van polinomid˝obeli determinisztikus Turing-g´ep, m´ıg az NP pedig azok´e, amelyekhez van polinomid˝obeli nemdeterminisztikus Turing-g´ep. Defin´ıci´ o. NP oszt´ aly: egy L nyelv az NP oszt´alybeli, ha ∀x ∈ L-re ∃ olyan y, hogy az polinom hossz´ u ´es polinomi´ alis id˝ oben ellen˝ orizhet˝ o bizony´ıt´ek. Azaz, ha L-hez l´etezik polinomi´ alis idej˝ u E ellen˝orz˝o Turing-g´ep ´es c konstans, hogy: Ha x ∈ L, akkor ∃y, hogy |y| ≤ |x|c ´es E az (x, y) p´art ELFogadja. Ha x ∈ / L, akkor ∀y-ra E az (x, y) p´ art ELUTas´ıtja. Ez a form´ alisan le´ırt defin´ıci´ ou ´gy terjedt el, mint a tan´ u t´etel. 9
Ha a tan´ ar megmondja nek¨ unk, hogy G-ben van Hamilton-k¨or, ´es meg is mutatja, melyik k¨or az, akkor be tudom bizony´ıtani, hogy ebben a gr´afban van Hamilton-k¨or. Azaz a Hamilton k¨or l´etez´es´ere a tan´ u a Hamilton-k¨ or. Ha azonban nincs a gr´ afban Hamilton-k¨or, akkor nem tudunk jobbat, minthogy minden egyes k¨orr˝ ol megmutatjuk, hogy az nem Hamilton-k¨or. Ezt viszont egy nagyobb gr´af eset´en nagyon id˝oig´enyes. Az olyan eld¨ ont´esi probl´em´ ak oszt´ aly´at, amelyekn´el az igenl˝o v´alasz eset´en a tan´ar biztosan tud olyan seg´ıts´eget adni, amellyel polinom id˝oben be tudjuk bizony´ıtani, hogy a v´alasz igen, NP-nek nevezz¨ uk. Pontosabban, egy eld¨ ont´esi probl´ema akkor NP-beli, ha minden olyan I inputhoz, melyre igenl˝ oa v´ alasz, l´etezik egy olyan, T ”tan´ u”,mely f¨ ugg I-t˝ol ´es T hossza fel¨ ulr˝ol becs¨ ulhet˝o I hossz´anak egy polinomj´ aval, m´ asr´eszt I ´es T ismeret´eben polinom id˝oben ellen˝orizhet˝o, az igenl˝o v´alasz. Term´eszetesen vannak olyan probl´em´ak is, amelyekn´el a nemleges v´alaszt tudjuk polinom id˝oben bebizony´ıtani, ha seg´ıt a tan´ ar. Az ilyen probl´em´ak oszt´alya a co-NP oszt´aly. Egy probl´em´ at NP-neh´eznek nevez¨ unk, ha minden NP-beli probl´ema visszavezethet˝o r´a. Ha ez a probl´ema eleme NP-nek, akkor NP-teljesnek h´ıvjuk. Ha egy NP-teljes probl´em´ at meg tudn´ank oldani polinom id˝oben, akkor minden NP-beli probl´em´ ara lenne polinom idej˝ u megold´ as. T´ etel (Cook). [26] L´etezik NP-teljes nyelv. Az NP-teljess´eg bizony´ıt´ ast a 70-es ´evek elej´en Stephen Cook ´es Leonid Levin egym´ast´ol f¨ uggetlen¨ ul, nagyj´ ab´ ol egy id˝ oben adta. A bizony´ıt´ asban szerepl˝ o nyelv bizonyos logikai formul´akr´ol sz´ol. K´es˝obb azt´an az NP-teljes nyelvek sz´ ama rohamosan n˝ ott, a 70-es ´evek v´eg´ere m´ar egy eg´esz k¨onyvet megt¨olt¨ottek vel¨ uk. Ha m´ar van legal´ abb egy NP-teljes nyelv¨ unk, akkor a tov´abbi nyelvek NP-teljess´eg´enek bizony´ıt´asa a k¨ovetkez˝ o s´ema szerint k´esz´ıthet˝ o: 1. Bel´ atjuk, hogy L ∈ NP 2. Egy tetsz˝oleges NP-teljes L0 nyelvre megmutatjuk, hogy L0 visszavezethet˝ o L-re. Ezek alapj´an k´es˝obb siker¨ ult bel´atni, hogy a Hamilton-k¨ or keres´ese NP-teljes. ´ ıt´ All´ as P ⊆ N P ´es N P ⊆ co-N P A sz´ am´ıt´ astudom´ any egyik legfontosabb (´es legn´epszer˝ ubb) nyitott k´erd´ese, hogy P ´es NP megegyezike vagy sem. Ha P ⊂ NP val´ odi tartalmaz´ as, akkor ez azt jelenten´e, hogy vannak olyan k´erd´esek, amikre van polinom hossz´ u bizony´ıt´ek, de ezt nem lehet polinom id˝oben megtal´alni. Vagyis egy igenl˝o v´alasz ellen˝ orz´ese algoritmikusan lehet l´enyegesen egyszer˝ ubb, mint egy igenl˝o v´alasz megtal´al´asa. Ha egy L nyelvr˝ ol megmutatjuk, hogy NP-teljes, akkor abb´ol k¨ovetkezik, hogy L csak akkor lehet P-ben, ha P=NP. Mivel a TSP NP-neh´ ez ´ıgy sz¨ uks´eg¨ unk van valamif´ele becsl´esre az optim´alis utat illet˝oen. Ehhez most k´et als´ o korl´ atot mutatok be.
10
4. Korl´ atok 4.1. Als´ o korl´ atok 4.1.1. 1-fa als´ o korl´ at Ez l´enyeg´eben egy minim´ alis s´ uly´ u fesz´ıt˝ofa. Ezt az als´ o korl´ atot a k¨ ovetkez˝ ok´eppen ´all´ıtjuk el˝o egy adott (V, d) gr´afra, ahol d : V × V → R. Kiv´ alasztunk egy cs´ ucsot v´eletlenszer˝ uen a gr´afb´ol, legyen ez v0 ∈ V ezt a pontot ideiglenesen kiszedj¨ uk a gr´ afb´ ol, majd ebben a m´odos´ıtott gr´afban keres¨ unk egy minim´alis s´ uly´ u fesz´ıt˝o f´at. Legyen r a minim´ alis fesz´ıt˝ o fa (R∗ ) hossza a (V − v0 , d) gr´afon. Legyen s a k´et legolcs´ obb ´el ¨ osszege, ami v0 -ra illeszkedik. s = min{ d(v0 , x) + d(v0 , y), x, y ∈ V − v0 , x 6= y} Majd eztut´ an, hogy egy elfogadhat´ o als´o korl´atot kapjunk a minim´alis fesz´ıt˝ofa hossz´ahoz hozz´aadjuk a k´et legolcs´ obb ´el ¨ osszeg´et. t=r+s Megold´ asul pedig egy olyan t ´ert´eket kapunk amelyre igaz, hogy l(T ) ≥ t minden T TSP k¨or´ utra. ´ ıt´ All´ as Az 1-fa algoritmus val´ oban als´ o korl´ atot eredm´enyez. Bizony´ıt´ as. Minden T TSP k¨ or´ utnak haszn´ alnia kell k´et ´elet, e-t ´es f -et amely illeszkedik v0 -ra. Ezt a k´et ´elet ´es v0 -t elt´ avol´ıtva T -b˝ ol egy minim´ alis fesz´ıt˝of´at (R) kapunk V − v0 -on. l(T ) = d(e) + d(f ) + l(R) ≥ s + l(R∗ ) = s + r = t. Ez az als´ o korl´ at ´ altal´ aban 10%-al van az optim´alis k¨or´ ut hossza alatt. A most k¨ovetkez˝o als´o korl´ at sokkal pontosabb becsl´est ad enn´el. 4.1.2. Held-Karp als´ o korl´ at Az al´ abbi ´ abra [28] seg´ıt meg´erteni a probl´em´at. Bal oldalt az optim´alis k¨or´ ut van kiemelve, k¨oz´epen az el˝ oz˝ o jel¨ ol´esek szerint az R∗ ehhez hozz´av´eve a v0 -hoz tartoz´o k´et minim´alis hossz´ us´ag´ u ´elet, amely ´ıgy null´ at ad becsl´es¨ ul. Ez nyilv´ an nem egy j´o becsl´es.
Az ¨ otlet ennek megold´ as´ ara a k¨ ovetkez˝o: Adjunk hozz´a az u-b´ol kiindul´o ´elek s´ uly´ahoz 10-et 11
(Jobb sz´els˝ o ´ abra). Minden k¨ or´ ut pontosan kett˝ot haszn´al ezekb˝ol az ´elekb˝ol, azaz minden k¨or´ ut hossza 20-szal fog n˝ oni. Speci´ alisan, most az lOP T = 30 ez az optim´alis k¨orutunk hossza a m´odos´ıtott gr´ afban. M´ asr´eszt az 1-fa als´ o korl´ at ´altal meghat´arozott t most meg fog egyezni lO P T -al. Amikor egy u cs´ ucshoz hozz´ arendel¨ unk egy ku sz´amot, ezt a sz´amot levonjuk minden u-b´ol indul´ o ´elb˝ ol. A jobb oldali k´epen ku = −10, minden u-hoz csatlakoz´o ´elb˝ol kivontam ezt a sz´amot. Majd hasonl´ oan minden egyes u ∈ V − v0 -hoz hozz´arendel¨ unk egy ilyen ku -t. Ezut´an k´esz´ıt¨ unk egy minim´ alis s´ uly´ u fesz´ıt˝ of´ at, Rk − t a (V − v0 , d) gr´afon. P A k¨ ovetkez˝ o pedig m´ ar egy j´ o als´ o korl´at lesz a k¨orutunkra: l(Rk ) + 2 u∈V −v0 ku Ezt nevezik Held-Karp als´ o korl´ atnak. Ehhez kell m´eg, hogy olyan ku -kat tal´aljunk, amivel a korl´at a lehet˝o legnagyobb lesz. Nem egyszer˝ u feladat megtal´ alni minden egyes cs´ ucshoz az ide´alis ku -t, de ezzel szakdolgozatomban nem foglalkozom.
4.2. Fels˝ o korl´ at Az egy´ertelm˝ u, hogy b´ armilyen Hamilton-k¨ort tal´alunk, az fels˝o korl´atja lesz a feladatnak. A ”legk¨ ozelebbi szomsz´ed” algoritmus (Rosenkrantz, Stearns ´es Philip M. Lewis 1977 [29]) az els˝ o olyan algoritmus, amellyel a TSP megold´as´at hat´arozt´ak meg. A kulcsa az eg´esznek az, hogy moh´ o m´ odon a legk¨ ozelebbi v´ arost l´ atogatjuk mindig. Gyorsan tal´alhat´o vele egy bej´ar´as, fut´asi ideje O(n2 ), de ´ altal´ aban az nem optim´ alis. Az algoritmus a k¨ ovetkez˝ ok´eppen ´ep¨ ul fel: Kiv´ alasztunk egy tetsz˝ oleges v´ arost, megkeress¨ uk a legk¨ozelebbi m´eg nem l´atogatott szomsz´edj´ at, ´es oda megy¨ unk. Ism´etelj¨ uk ezt a l´ep´est mindaddig, am´ıg van m´eg meg nem l´atogatott v´aros majd t´erj¨ unk vissza a kiindul´ asi v´ arosba. El˝ ofordulhat, hogy l´etezik a gr´ afban Hamilton k¨or, de azt az algoritmusunk nem tal´alja meg. Az algoritmus egy m´ odos´ıt´ asa m´eg, hogy minden cs´ ucsot kipr´ob´alunk mint kezd˝opont ´es ezek k¨ oz¨ ul v´ alasztjuk ki a legr¨ ovidebbet.
12
5. Approxim´ aci´ ok Miut´ an a TSP probl´em´ ara nem tudunk olyan pontos megold´ast adni, ami polinomi´alis id˝oben v´egez, ez´ert k¨ ul¨ onb¨ oz˝ o algoritmusokkal pr´ ob´alunk optimumhoz k¨ozeli eredm´enyt el´erni. Rengeteg ilyen algoritmus l´etezik, szakdolgozatomban csak n´eh´any jelent˝osebb algoritmussal ismerked¨ unk meg. A k¨ ovetkez˝ o approxim´ aci´o ismertet´es´ehez, az al´abbi defin´ıci´okra lesz sz¨ uks´eg¨ unk. Defin´ıci´ o. [Euler-k¨ or] A G = (E, ϕ, V ) gr´ af L = v0 e1 v1 e2 v2 ...vn−1 en vn bej´ar´as´at (ϕ(e1 ) = (v0 , v1 ), ϕ(e2 ) = (v1 , v2 ), ..., ϕ(en ) = (vn−1 , vn )) Euler-s´ et´ anak nevezz¨ uk, ha E minden ´el´et pontosan egyszer tartalmazza. S z´ art Euler-s´et´ anak vagy Eluler-k¨ ornek mondjuk, ha v0 = vn , egy´ebk´ent pedig ha v0 6= vn , akkor L-et ny´ılt Euler-s´et´ anak h´ıvjuk. ´ ıt´ All´ as Ha egy gr´ af minden cs´ ucs´ anak p´ aros a foksz´ama, akkor l´etezik benne Euler-k¨or. Defin´ıci´ o. [Metrikus TSP] A gr´ afunk ´eleinek a s´ uly´ ara teljes¨ ul a h´aromsz¨og egyenl˝otlens´eg. c(u, v) + c(v, w) ≥ c(u, w) ∀u, v, w ∈ V Legyen G(V, E) egy teljes gr´ af ´es c egy s´ ulyf¨ uggv´eny az ´elekre, melyre teljes¨ ul a h´aromsz¨og egyenl˝ otlens´eg. Azaz t´enyleges s´ıkbeli pontoknak feleltethet˝o meg V , ´es a k¨oz¨ott¨ uk l´ev˝o t´avols´ag lesz a c f¨ uggv´eny az ´elekre. Az approxim´ aci´ os algoritmus amivel folalkozni fogunk a minim´alis s´ uly´ u fesz´ıt˝ofa azon tulajdons´ag´ at haszn´ alja fel, hogy az egy term´eszetes als´o korl´atja a TSP-nek. Az algoritmusr´ol bel´atjuk, hogy 2-approxim´ aci´ os azaz, hogy az algoritmus ´altal kapott k¨or´ ut legrosszabb esetben az optim´alis k¨or´ ut hossz´ anak dupl´ aja. Az algoritmus k¨ ovetkez˝ ok´eppen n´ez ki: • Keress¨ unk G gr´ afunkban egy minim´alis fesz´ıt˝o f´at. Legyen ez T . Tudjuk, hogy c(T ) ≤ OP TT SP • Dupl´ azzuk meg T ´eleit. • Az ´ıgy l´etrehozott G0 gr´ afban keres¨ unk Euler-k¨ort. Biztos, hogy tal´alni fogunk benne, hisz minden cs´ ucs foka p´ aros lesz m´odos´ıt´asunk miatt. • Ezut´ an j´ arjuk be ezt a k¨ ort ´es megjegyezz¨ uk a cs´ ucsok sorrendj´et, majd ebb˝ol alkotjuk meg a Hamilton-k¨ ort a k¨ ovetkez˝ ok´eppen: • Legyen a cs´ ucsok sorrendje a k¨ovetkez˝o (p1 , p2 , ...pN ). Induljunk a p1 pontb´ol ´es l´atogassuk meg a k¨ ovetkez˝ o pontot p2 -t ´es ´ıgy tov´abb.
13
• Ezt addig ism´etelj¨ uk, am´ıg olyan ponthoz nem jutunk, ahonnan m´ar csak megl´atogatott cs´ ucs ´erhet˝ o el. Ezeket az ´eleket kell kisz˝ urn¨ unk, amik ilyen cs´ ucsok k¨oz¨ott mennek. Tegy¨ uk fel, hogy p1 , p2 , . . . pn k¨ ul¨ onb¨ oz˝ o cs´ ucsok, de pn -b˝ol m´ar csak olyan cs´ ucsba tudunk menni, amit m´ ar l´ atogattunk. Ilyenkor megkeress¨ uk a sorrendben k¨ovetkez˝o meg nem l´atogatott cs´ ucsot, pn+1 -et ha van, ha nincs akkor p1 –et ´es a pn , pn−1 , . . . pn+1 ´elsorozatot lecser´elj¨ uk a (pn , pn+1 ) ´elre. • A h´ aromsz¨ og egyenl˝ otlens´eg miatt a k¨or¨ unk hossza nem n¨ovekedett az ilyen fajta csere ´altal. • Ezt ism´etelve v´eg¨ ul egy Hamilton-k¨ort kapunk, amely k¨olts´ege maximum k´etszerese az optim´ alisnak. c(T ) ≤ OP TT SP ≤ c(Hamilton − k.) ≤ c(Euler − k.) = 2c(T ) ≤ OP TT SP ⇒ c(Hamilton − k.) ≤ 2OP TT SP Ez teh´ at egy 2-approxim´ aci´ os algoritmus. Ennek az elj´ar´asnak a legm˝ uveletig´enyesebb r´esze a fesz´ıt˝ ofa megkeres´ese, amely Prim [30] algoritmussal v´egezve O(n2 ) fut´asi id˝ovel b´ır. Itt haszn´alhat´ o ak´ ar Boruvka [31] algoritmusa is.
5.1. Christofides algoritmusa Ez egy olyan algoritmus, amellyel k¨ozel´ıt˝o megold´asokat tal´alhatunk az utaz´o u ¨gyn¨ok probl´em´ aj´ ara, olyan esetekben, amikor a t´ avols´agok metrikus teret alkotnak (szimmetrikusak ´es teljes¨ ul a h´ aromsz¨ og egyenl˝ otlens´eg). Ez az algoritmus garant´alja, hogy megold´asai az optim´alis megold´ as hossz´ us´ ag´ anak maximum 23 szerese. Az algoritmust Nicos Christofides-r˝ol nevezt´ek el, aki 1976-ban ismertette algoritmus´ at [32]. Ez az egyik legjobb k¨ ozel´ıt˝ o algoritmus amit ismer¨ unk. Christofides az el˝ oz˝ o 2-approxim´ aci´ os algoritmust fejlesztette tov´abb az al´abbi m´odon: 1. Keress¨ unk egy minim´ alis fesz´ıt˝ of´at G-ben. Legyen ez itt is T . 2. Legyen V 0 egy r´eszhalmaza V-nek mely a T p´aratlan fok´ u cs´ ucsait tartalmazza. Azt tudjuk, hogy p´ aros sok ilyen cs´ ucs van. 3. Ebb˝ ol az k¨ ovetkezik, hogy l´etezik V 0 felett minim´alis s´ uly´ u teljes p´aros´ıt´as. Legyen ez M . 4. (V, T ∪ M ) egy Euler gr´ af, minden cs´ ucs foksz´ama p´aros, azaz van benne Euler-k¨or. 5. Ebben a gr´ afban egy Euler-k¨ ort keresve ´es az el˝oz˝o elj´ar´ast alkalmazva kapunk v´eg¨ ul egy H Hamilton-k¨ ort.
14
´ ıt´ All´ as. c(H) ≤ 23 OP TT SP Bizony´ıt´ as. A k¨ ovetkez˝ o h´ arom pontot kell bel´atnunk ehhez: • c(T ) ≤ OP TT SP • c(M ) ≤ 12 OP TT SP • c(H) ≤ c(T ∪ M ) Az els˝ o pont egy´ertelm˝ u, a minim´ alis s´ uly´ u fesz´ıt˝ofa egy als´o korl´at lesz az optimumra. A harmadik pont is k¨ onnyen l´ atszik, hisz k¨ovetkezik a h´aromsz¨og-egyenl˝otlens´egb˝ol. A m´ asodik pont kicsit ¨ osszetettebb m´ar. Tekints¨ unk egy optim´alis Hamilton-k¨ort. Ha a k¨ornek csak azon cs´ ucsait vessz¨ uk, amik elemei V’-nek ´es az ezek k¨ozti ´eleket n´ezz¨ uk, akkor egy olyan k¨ ort kapunk, amely hossza nem nagyobb az optim´alisn´al. Nevezz¨ uk ezt a k¨ort CV 0 -nek. Tov´ abb´ a, mivel |V 0 | p´ aros elemsz´ am´ u ´ıgy a k¨or k´et p´aros´ıt´as diszjunkt uni´oja lesz, M1 ´es M2 -´e. c(CV 0 ) = c(M1 ) + c(M2 ) Ebb˝ ol az k¨ ovetkezik, hogy: min{c(M1 ), c(M2 )} ≤
1 1 c(CV 0 )) ≤ OP TT SP 2 2
Teh´ at M minim´ alis teljes p´ aros´ıt´ as eset´en c(M ) ≤
1 OP TT SP 2
Ezzel bel´ attuk, hogy Christofields algoritmusa val´oban
15
3 2
k¨ozel´ıt˝o algoritmus.
´ ep´ıt˝ 6. Ut´ o algoritmusok Legyen G(V, E) egy n cs´ ucs´ u gr´ af ´es c egy s´ ulyf¨ uggv´eny az ´elekre.
6.1. Moh´o algoritmus A Greedy (moh´ o) algoritmus egy olyan probl´emamegold´o algoritmus, amely helyi optimumokat haszn´ alva pr´ ob´ al glob´ alis optimumot tal´alni. Ez itt a TSP-n´el azt jelenti, hogy minden v´arosb´ ol a hozz´ a legk¨ ozelebbi, addig m´eg nem l´atogatott v´arosba fog utazni az u ¨gyn¨ok. Az algoritmus m˝ uk¨ od´ese: Rendezz¨ uk az ´eleket s´ uly szerint majd V´alasszuk ki a legr¨ovidebb ´elet, ami m´eg nem szerepelt ´es adjuk hozz´ a a k¨ or¨ unkh¨ oz, ha nem hoz l´etre n ´eln´el kevesebb˝ol ´all´o k¨ort vagy nem n¨oveli valamelyik cs´ ucs fok´ at kett˝ on´el t¨ obbre. Ism´etelj¨ uk ezt am´ıg nem lesz egy n ´elb˝ol ´all´o k¨or¨ unk. ´Igy v´eg¨ ul egy Hamilton-k¨ ort kapunk. Ez az elj´ar´as nem t´ ul hat´ekony, gyakran nagyon elt´er az optimumt´ ol.
6.2. Boruvka algoritmus Az algoritmust el˝ osz¨ or Otakar Bor˚ uvka tette k¨ozz´e 1926-ban [31], villamosenergia-h´al´ozat konstru´ al´ as´ ahoz. Az algoritmus minim´ alis s´ uly´ u fesz´ıt˝of´at keres O(|E| ∗ log|V |) fut´asi id˝ovel, a concorde TSP megold´ o program is felhaszn´ alja a dupla fesz´ıt˝of´as m´odszern´el. Az algoritmus u ´gy kezd˝ odik, hogy minden cs´ ucsot megvizsg´alunk ´es ez alapj´an hozz´aadjuk a legolcs´ obb ´elet, ami k´et cs´ ucs k¨ ozt fut. Ezut´an ugyanezt ism´etelj¨ uk tekintet n´elk¨ ul a m´ar hozz´aadott ´elekre. Ezt addig folytatjuk , am´ıg az ´ıgy l´etrej¨ov˝o ´el csoportok ¨ossze nem ´allnak egy minden cs´ ucsot lefed˝ o f´ aba. Pszeudok´ od: Input: Egy ¨ osszef¨ ugg˝ o G gr´ af, c s´ ulyf¨ uggv´ennyel az ´elekre. Legyen T egy erd˝o, amely az elej´en egy cs´ ucs´ u f´ akb´ ol ´ all, azaz a gr´ af minden cs´ ucsa egy k¨ ul¨on fa lesz. Am´ıg T nem 1 komponensb˝ ol ´ all: ∀T -beli C komponensre: Legyen S egy u ¨res sor ∀ cs´ ucsra C-ben Keress¨ uk meg a legolcs´ obb C-b˝ ol kifel´e tart´o ´elet ´es adjuk hozz´a S-hez Adjuk a legolcs´ obb ´elet S-b˝ ol T -be Vonjuk ¨ ossze az ´elek ´ altal ¨ osszek¨ ot¨ ott f´akat, hogy nagyobb komponenseket alkossanak Output: T egy minim´ alis s´ uly´ u fesz´ıt˝ofa.
16
6.3. Besz´ ur´ asos algoritmusok L´enyeg¨ uk, hogy egy kiv´ alasztott ´elb˝ ol kiindulva ahhoz hozz´avesz¨ unk egy pontot a m´odszert˝ol f¨ ugg˝ oen ´es az ´ıgy kapott k¨ or¨ unkbe sz´ urunk be ezut´an valamilyen szab´aly szerint pontokat, ´ıgy b˝ov´ıtve a k¨ ort. Amire figyelni kell az az, hogy minim´alis legyen a k¨olts´egn¨oveked´es (c(u, v) a k¨or¨ unk egy ´el´enek a k¨ olts´ege). min{c(u, w) + c(v, w) − c(u, v)}; u, v, w ∈ V Az elj´ ar´ asnak akkor lesz v´ege, ha minden pontot besz´ urtunk m´ar. Az elj´ ar´ as egyes fajt´ ai: • A legk¨ ozelebbi besz´ ur´ asa - O(n2 ) V´alasszuk ki a legr¨ovidebb ´elet. Keress¨ uk meg a v´egpontjaihoz, k´es˝obb a k¨or pontjaihoz a legk¨ozelebbi pontot ´es sz´ urjuk be. Figyelj¨ unk a minim´ alis k¨ olts´egn¨oveked´esre. min{c(u, w) + c(v, w) − c(u, v)}; u, v, w ∈ V Ism´etelj¨ uk, am´ıg minden pontot be nem sz´ urtunk. • A legt´ avolabbi besz´ ur´ asa - O(n2 ) Az el˝oz˝oh¨oz hasonl´o, de a leghosszabb ´elet keress¨ uk meg, majd a legk¨ ozelebbi helyett legt´avolabbi pontot sz´ urunk be mindig. ¨ enyes’ vagy v´eletlenszer˝ • ’Onk´ u besz´ ur´as - O(n2 ) A pontokat v´eletlenszer˝ uen sz´ urjuk be. A legk¨ ozelebbi cs´ ucs besz´ ur´ asa megfeleltethet˝o Prim minim´alis fesz´ıt˝of´at keres˝o algoritmus´aval. Egy v´ aros besz´ ur´ asa megfelel egy ´el hozz´aad´as´anak a minim´alis fesz´ıt˝of´ahoz. Ha teljes¨ ul a h´aromsz¨ og egyenl˝ otlens´eg, akkor a minim´ alis fesz´ıt˝of´aval egy fels˝o korl´atot adhatunk a TSP-re mint azt l´attuk. ´Igy ez a m´ odszer az optimum dupl´ aj´ at adja legrosszabb esetben. A legt´ avolabbi besz´ ur´ asa algoritmus meglep˝o m´odon gyakran jobb, mint a legk¨ozelebbi besz´ ur´ asa, osszekapcsolja a messzi v´ ¨ arosokat a t´ ur´aban, hogy l´etrehozzon egy v´azlatot az eg´esz t´ ur´ar´ol. ur´anak. Az algoritmus ´ altal gener´ alt k¨ ors´et´ ak 32 –szorosai az optim´alis t´
17
7. Jav´ıt´ o algoritmusok Ha l´etrehoztunk m´ ar egy t´ ur´ at valamelyik heurisztik´ankkal, akkor az al´abbi algoritmusokkal lehet jav´ıtani a m´ ar megl´ev˝ o megold´ ast. Sz´amos m´odja van ennek, de a legelterjedtebbek a 2-opt ´es 3-opt lok´ alis keres´esek, emellett ott van p´eld´aul a tabu keres´es, amely m´odos´ıtva felhaszn´alja a 2-opt ´es 3-opt l´ep´eseit. Ezeken k´ıv¨ ul k¨ ul¨ on kiemeln´em a Lin-Kernighan algoritmust, amelyet az egyik legjobb TSP-heurisztik´ anak tartanak.
7.1. 2-opt Ezt az algoritmust a TSP megold´ as´ ara tal´alta ki Croes 1958-ban [33]. Mivel ez egy jav´ıt´o algoritmus, ez´ert egy megl´ev˝ o utat fejleszt. Az algoritmus a k¨ ovetkez˝ on alapszik: • Vesz k´et ´elet a k¨ or´ utb´ ol. Legyen ezek s´ ulya c(v, w) ´es c(u, x)
A 2-opt egy l´ep´ese ¨ • Osszek¨ oti a k´et ´elhez tartoz´ o n´egy cs´ ucsot (nem lehet a k´et ´elnek k¨oz¨os cs´ ucsa) u ´gy, hogy u ´j k¨ orutat kapjunk. Ezt csak egyf´elek´eppen tehetj¨ uk meg u ´gy, hogy tov´abbra is k¨orutunk legyen. • Az u ´j ´elek s´ ulyai legyenek c(v,u) ´es c(w,x). Ha ezek kisebbek, mint c(v,w)´es c(u,x) akkor az eredeti ´eleket lecser´elj¨ uk a kisebb o¨sszs´ uly´ u ´elekre. Form´ alisan: c(v, w) + c(u, x) > c(v, u) + c(w, x) ⇒ cser´el¨ unk ´eleket Az algoritmus akkor ´all le, ha m´ ar nem tudunk cser´et v´egrehajtani. Ekkor a k¨ orutunkat 2-optim´ alisnak nevezz¨ uk. Az algoritmus fut´asi ideje: O(n2 ).
18
7.2. 3-opt Az elj´ ar´ as Lin nev´ehez f˝ uz¨ odik, aki 1965-ben publik´alta algoritmus´at.[34] Hasonl´ oan m˝ uk¨ odik az el˝ oz˝ oh¨ oz, de itt 2 ´el helyett 3-at v´alasztunk ki, ´es itt k´etf´elek´eppen lehet osszek¨ ¨ otni ezen ´elekhez tartoz´ o cs´ ucsokat u ´gy, hogy u ´j k¨orutat kapjunk. Itt lehet k´et ´elnek k¨oz¨ os cs´ ucsa is ak´ ar. Tekinthet¨ unk u ´gy is erre, mint kett˝o vagy h´arom 2-opt l´ep´esre. Az algoritmusnak akkor van v´ege, ha m´ ar nem tudunk cser´elni. Ekkor a k¨orutunkat 3-optim´alisnak nevezz¨ uk. Alkalmazhat´ o ez h´ aromn´ al nagyobb sz´amokra is. Az ´ert´ek lehet n´egy, ¨ot, de ak´ar nagyobb is. Nagyobb sz´ amokra nem mindig olyan hat´ekony az elj´ar´as.
7.3. k-opt Egy k¨ or´ ut k-optim´ alis, ha nem hajthat´o v´egre k ´el cser´eje u ´gy, hogy jobb eredm´enyt kapjunk. Teh´ at egy n v´ arosb´ ol ´ all´ o k¨ or´ ut akkor optim´alis, ha n-optim´alis.
7.4. Lin-Kernighan algoritmus Ez egy lok´ alisan optimaliz´ al´ o algoritmus, melyet Shen Lin ´es Brian Kernighan tal´alt ki 1973-ban [35]. A k-opt egy tov´ abbfejleszt´ese. Nem fix k van, hanem minden l´ep´esben pr´ob´aljuk az optim´ alis k-t megtal´ alni. Ez az elj´ ar´ as felhaszn´alja azt, hogy minden k-opt l´ep´es reprezent´alhat´o, mint 2-opt ´ ´ep´ıti fel ezt a sorozatot, hogy l´ep´esenk´ent n¨oveli k-t ´es ellen˝orzi minden l´ep´es l´ep´esek sorozata. Ugy ut´ an, hogy a csere r¨ ovidebb k¨ or´ uthoz vezet-e. Tekintettel arra, hogy a csere k ´el k¨oz¨ott v´egrehajthat´o egy tesztsorozatot hajtunk v´egre annak eld¨ ont´ese ´erdek´eben, hogy k+1 ´el cser´eje lehets´eges-e. Ez addig folytat´odik, am´ıg a le´all´asi krit´erium nem teljes¨ ul. Az algoritmus minden l´ep´esben b˝ov´ıti a l´etrehozott halmazt, a potenci´alis cser´ekkel (k=2-vel kezd). Ezeket a cser´eket u ´gy v´alasztjuk meg, hogy felhaszn´alva ˝oket a folyamat b´armely szakasz´ aban egy u ´j k¨ orutat kapunk. V´eg¨ ul ha tal´alunk egy u ´j r¨ovidebb k¨orutat, akkor v´egrehajtjuk a cser´et, azaz egy k¨ orutat konvert´ al a´t egy u ´j, optim´alisabb k¨or´ utt´a, majd meg´all ha m´ar nem lehet jav´ıtani. Az algoritmus fut´ asi ideje O(n2,2 ). N´ezz¨ uk most ezt kicsit r´eszletesebben. Legyen T az aktu´ alis k¨ or´ ut. Az algoritmus minden l´ep´esben megpr´ob´al tal´alni k´et halmazba ´eleket, X = {x1 . . . xk } ´es Y = {y1 . . . yk }, ha T -b˝ol kiszedj¨ uk az X-ben l´ev˝o ´eleket ´es helyette az Y -belieket haszn´ aljuk, akkor az eredm´eny egy jobb k¨or´ ut lesz. Ezt nevezz¨ uk k-opt l´ep´esnek. X-et ´es Y -t elemenk´ent ´ep´ıtj¨ uk fel, u ´gy hogy az elej´en mindk´et halmaz u ¨res. Az i. l´ep´esben az xi ´es yi ´elet adjuk hozz´ a a halmazokhoz. Annak ´erdek´eben, hogy az algoritmusunk el´eg hat´ekony legyen csak olyan ´eleket adunk X-hez ´es Y -hoz, melyek teljes´ıtik a k¨ovetkez˝o oldalakon le´ırt krit´eriumokat.
19
A szekvenci´ alis cser´ ek krit´ eriuma xi -nek ´es yi -nek kell k¨ oz¨ os v´egponttal rendelkeznie, ahogy yi -nek ´es xi+1 -nek is. Ha t1 jel¨oli az xi egyik v´egpontj´ at, azaz xi = (t2i−1 , t2i ), yi = (t2i , t2i+1 ) ´es xi+1 = (t2i+1 , t2i+2n , i ≥ 1. Innen l´atszik, hogy a sor (x1 , y1, x2, y2, x3, ..., xk, yk) szomsz´edos ´eleket tartalmaz. Sz¨ uks´eges, de nem el´egs´eges felt´etel, hogy X ´eleinek lecser´el´ese Y ´eleire egy t´ ur´aban akkor lesz z´art, ha yk = (t2k , t1 ). A cser´et szekvenci´ alisnak nevezz¨ uk, ha le´ırhat´o egy olyan u ´tvonal, amely a t¨or¨olt ´es hozz´aadott ´elek k¨ oz¨ ott v´ altakozik. ´ Altal´ aban a t´ ura fejleszt´ese el´erhet˝ o szekvenci´alis cser´evel, ha megfelel˝o sorban vessz¨ uk az ´eleket. Azonban olyan is el˝ ofordulhat, hogy nem tudunk cser´et v´egrehajtani.
A fels˝ o´ abr´ an egy szekvenci´ alis cser´et l´ athatunk, m´ıg az als´ on egy olyan esetet, ahol nem tudunk ilyen cser´et v´egrehajtani.
Megval´ os´ıthat´ os´ agi krit´ erium Sz¨ uks´eges, hogy ha xi = (t2i−1 , t2i )-t kiv´alasztjuk, akkor t2i csatlakozzon t1-hez ´es a csere ut´an egy k¨ orutat kapunk. Ezt i ≥ 3-ra alkalmazzuk ´es garant´alja, hogy a t´ ura z´art lesz, a folyamat b´armelyik szakasz´ aban k¨ or´ utt´ a alak´ıthat´ o lesz. Ez a krit´erium fontos a fut´ asi id˝ o ´es a k´odol´as egyszer˝ us´ıt´es´enek ´erdek´eben is.
20
A pozit´ıv nyeres´ eg krit´ eriuma yi -t mindig u ´gy v´ alasztjuk meg a javasolt cserehalmazb´ol, hogy a nyeres´eg (Gi ), pozit´ıv legyen. Legyen gi = c(xi ) − c(yi ) az xi ´es yi csere nyeres´ege. Ekkor Gi = g1 + . . . + gi . Ez a le´ all´ asi krit´erium fontos szerepet j´atszik az algoritmus hat´ekonys´ag´aban. Az, hogy minden gi pozit´ıv legyen t´ ul nagy megszor´ıt´ asnak t˝ unik, de nem ez a helyzet. Ha egy sz´amsornak pozit´ıv az osszege, akkor l´etezik olyan permut´ ¨ aci´oja a sz´amoknak, hogy minden r´esz¨osszeg pozit´ıv legyen. Diszjunktivit´ as krit´ eriuma V´eg¨ ul kell m´eg az is, hogy X ´es Y diszjunktak legyenek. Hat´ekony le´all´asi krit´eriumot ad ´es cs¨okkenti a fut´ asi id˝ ot. Az algoritmus l´ ep´ esei: 1. Kezdj¨ unk egy v´eletlenszer˝ uen v´alasztott t´ ur´aval. 2. Legyen i = 1. V´ alasszuk ki t1 -et. 3. V´ alasszuk meg x1 -et, x1 = (t1 , t2 ) eleme T 4. V´ alasszunk mell´e egy y1 -et, y1 = (t2 , t3 ) nem eleme T , G1 > 0. Ha nem lehets´eges ilyet tal´ alni menj¨ unk a 12. l´ep´esre. 5. Legyen i=i+1 6. V´ alasszuk meg xi -t, xi = (t2i−1 , t2i ) eleme T , hogy • ha t2i csatlakozik t1 -hez, akkor a kapott konfigur´aci´o egy t´ ura lesz. • xi 6= ys minden s < i-re. 7. V´ alasszuk meg yi − t, yi = (t2i , t2i+1 ) nem eleme T u ´gy, hogy • Gi > 0 • yi 6= xs minden s ≤ i • xi+1 l´etezik Ha yi nem l´etezik, menj¨ unk az 5. l´ep´esre. 8. Ha van m´eg kipr´ ob´ alatlan alternat´ıva y2 -re akkor legyen i = 2 ´es menj¨ unk a 7. l´ep´esre. 9. Ha van m´eg kipr´ ob´ alatlan alternat´ıva x2 -re akkor legyen i = 2 ´es menj¨ unk a 6. l´ep´esre. 10. Ha van m´eg kipr´ ob´ alatlan alternat´ıva y1 -re akkor legyen i = 1 ´es menj¨ unk a 4. l´ep´esre. 11. Ha van m´eg kipr´ ob´ alatlan alternat´ıva x1 -re akkor legyen i = 1 ´es menj¨ unk a 3. l´ep´esre. 12. Ha van m´eg kipr´ ob´ alatlan alternat´ıva t1 -re akkor menj¨ unk a 2. l´ep´esre. ´ 13. Alljon meg az algoritmus. (Kezdj¨ uk el egy m´asik v´eletlen t´ ur´aval az els˝o l´ep´est˝ol.) 21
Kieg´ esz´ıt´ esek 3. l´ ep´ es x1 -et k´etf´elek´eppen v´ alaszthatjuk (a t´ ura egy cs´ ucsa t1 ). 6. l´ ep´ es xi megv´ alaszt´ asa k´et f´elek´eppen lehets´eges, azonban adott yi−1 eset´eben csak egy amely lehet˝ ov´e teszi a t´ ura bez´ ar´ as´ at, yi hozz´aad´as´aval. A m´asik v´alaszt´as k´et diszjunkt k¨ort eredm´enyez. Azonban egy esetben m´ as a helyzet, i = 2-re. 8-12. l´ ep´ es Ezek visszal´ep´eshez vezetnek, de csak akkor, ha nincs javul´as az els˝o vagy m´asodik szinten. 13. l´ ep´ es Akkor ´ all le, ha m´ ar minden t1 ´ert´ekre kipr´ob´altuk az algoritmust ´es nem volt jav´ıt´ as. Ekkor mint eml´ıtettem, u ´j t´ ur´ ab´ ol indulhatunk ki.
7.5. Tabu keres´ es Fred Glover tal´ alta ki 1970-ben [36]. A lok´alis keres´esi m´odszerek hajlamosak lok´alis optimumba ragadni, ezt a hib´ at k¨ usz¨ ob¨ oli ki a tabu keres´es. Ez az algoritmus 2-opt l´ep´eseket haszn´al ´es megengedi a negat´ıv nyeres´eget, ha nem tal´ alunk pozit´ıvat. Az alapgondolat az, hogy az algoritmus l´etrehoz egy tabulist´at, amely a tiltott l´ep´eseket ´ırja le. A list´ at minden iter´ aci´ oban fel¨ ul´ırjuk ´es az aktu´alis l´ep´es visszal´ep´es´enek tilt´as´aval b˝ov´ıtj¨ uk, az elavult tilt´ asokat t¨ or¨ olj¨ uk. Az aktu´ alis iter´aci´oban nem lehet a lista ´altal tiltott l´ep´est megtenni, ´ ezzel biztos´ıtjuk, hogy nem l´ep¨ unk vissza az el˝oz˝o megold´asra. Altal´ aban a tabu keres˝o algoritmus a legjobb megold´ ast v´ alasztja a k¨ ornyezetb˝ol, ha az nem az aktu´alis megold´as illetve nincs tiltva a tabulista ´ altal. Amennyiben a legjobb megold´as az aktu´alis megold´as -azaz lok´alis optimumban vagyunk - vagy a legjobb megold´ ast tiltja a tabulista, akkor m´as kev´esb´e j´o megold´ast v´alaszt az algoritmus.
22
8. Alkalmaz´ asok Ebben a fejezetben az utaz´ ou ¨gyn¨ ok probl´ema sokr´et˝ u alkalmaz´as´at mutatom be. A feladatnak igen szerte´ agaz´ o a felhaszn´ al´ asi k¨ ore, sok val´o ´eletben el˝ofordul´o probl´ema vezethet˝o vissza a TSP-re. Csak, hogy n´eh´ anyat eml´ıtsek u ´tvonalak optimaliz´al´asa, teleszk´opok, l´ezerek, r¨ontgenek ir´any´ıt´ asa, mikroprocesszorok tesztel´ese, feladatok u ¨temez´ese, tap´eta hullad´ek´anak minimaliz´al´asa.
8.1. Klaszterek bej´ar´asa TSP-vel El˝ osz¨ or is, vezess¨ uk be a klaszterezett utaz´o u ¨gyn¨ok probl´ema fogalm´at (Clustered Traveling Salesman Problem - CTSP). Ez egy kib˝ov´ıt´ese a TSP-nek, ahol a v´arosokat parcion´ aljuk klaszterekbe ´es az u ¨gyn¨ok egym´as ut´an megl´atogatja a klasztereket. Nyilv´ anval´ o, hogy a CTSP megegyezik a a TSP-vel, ha minden klaszter egy elemb˝ol ´all. A CTSP-t egy teljes gr´ afon defini´ aljuk, G = (V, E), ahol V = {v1 , ..., vn } a ponthalmaz ´es E = {(vi , vj ) : vi , vj ∈ V, i 6= j} ´elhalmaz. Van emellett egy nem negat´ıv ´els´ uly cij , (vi , vj ) ´elre, ez alapj´an ker¨ ulnek a pontok k egym´ast kiz´ ar´ o ´es teljes klaszterekbe, azaz V1 , ..., Vk klaszterek ´es V = V1 ∪ V2 ∪ ... ∪ Vk u ´gy, hogy Vi ∩ Vj = Ø ∀i, j, i 6= j. A CTSP-t megfeleltethet˝ o egy minim´alis s´ uly´ u TSP k¨or´ ut keres´es´enek. A k¨ ovetkez˝ o k´eppen transzform´ aljuk adatainkat: • V 0 ekvivalens V -vel. • Defini´ aljuk c0ij = cij 0 , ahol vi ´es vj ugyan abba a klaszterba tartoznak. • Ha vi ´es vj k¨ ul¨ onb¨ oz˝ o klaszterekbe tartoznak akkor c0ij = cij + M , ahol M egy sz¨ uks´egesen nagy konstans, ez itt azt jelenti, hogy M nagyobb a legnagyobb ´elk¨olts´egn´el.
CTSP (n=23, k=6) [37] Ez ut´ an a transzform´ aci´ o ut´ an a TSP k¨orutunk mindig v´egigmegy egy klaszteren, ´es csak ut´ ana megy ´ at m´ asikra. Az optim´ alis k¨ or´ ut ´ert´eke a TSP k¨or´ ut ´ert´eke minusz kM, mivel k db klaszterek k¨ ozti ´el van. Emiatt az ´ atalak´ıt´ as miatt haszn´ alhatunk a CTSP megold´as´ara TSP-t megold´o programokat. Ilyen j´ ol ismert hat´ekony program a Concorde. 23
8.2. Concorde A Concorde (2001) egy olyan program, amely a TSP megold´as´ara t¨orekszik, k¨ ul¨onb¨oz˝o heurisztik´ akkal. Napjainkig az egyik legjobb TSP megold´o program. M˝ uk¨ od´ese: koordin´ at´ akkal megadott pontok k¨oz¨ott keresi a legr¨ovidebb utat. A program u ´gy keresi ez optim´ alis utat, hogy b´ armelyik pontb´ol b´armelyikbe el lehet jutni. A program gyorsas´aga a ’branch-and-cut’ ´es a Chained Lin-Kernighan algoritmusok haszn´alat´an alapszik. A hat´ekonys´ ag´ at az is mutatja, hogy mikor Reinelt l´etrehozta a TSPLIB-et (egy k¨onyvt´ar, k¨ ul¨onb¨ oz˝ o forr´ as´ u ´es t´ıpus´ u TSP feladatok sz´ am´ara (´es kapcsol´od´o probl´em´ak r´esz´ere)) 1990-ben m´eg 24 esetet tartalmazott melyek nagyj´ ab´ ol 1000 v´arosb´ol ´alltak. Ez a sz´am 1995-re 34-re emelkedett az u ´j, kih´ıv´ ast jelent˝ o probl´em´ ak hozz´ aad´ as´aval. Kett˝ot ezen probl´em´ak k¨oz¨ ul megoldottak pap´ıron, a fennmarad´ o 32 probl´ema mindegyik´et megoldotta a Concorde. Teh´ at a Concorde TSP megold´ ot TSPLIB esetek optim´alis megold´asainak meghat´aroz´as´ara is haszn´ alt´ ak. A legnagyobb ilyen 85.900 v´ arosra volt. A Concorde egy C programnyelven ´ır´odott David Applegate, Robert E. Bixby, Vaˇsek Chv´atal, ´es William J. Cook ´ altal ´es k¨ or¨ ulbel¨ ul 130 000 sorb´ol ´all, emellett szabadon felhaszn´alhat´o tudom´anyos c´elokra. A Concorde t¨ obb kor´ abbi kulcsfontoss´ag´ u TSP kutat´asra ´ep¨ ul, melyek v´eg¨ ul a projekt l´etrehoz´ as´ at eredm´enyezt´ek. A Concorde-ot az egyik legkorszer˝ ubb megval´os´ıt´asnak nevezik, az egyik legjobb TSP-megold´o program, ami jelenleg el´erhet˝ o. 2001-ben a Concorde egy m´ odos´ıtott verzi´oja 5000 Gulden-os d´ıjat nyert a CMG informatikai c´egt˝ ol, ami´ert megoldotta az 1996-os j´ arm˝ uforgalmi probl´em´aj´at. A feladat az volt, hogy megtal´alj´ak a legjobb utakat 4 u ´js´ agos fi´ u sz´ am´ ara, hogy 120 u ¨gyf´elnek kihordj´ak az u ´js´agokat. A Concorde h´ıvhat´ o k¨ onyvt´ ar t¨ obb mint 700 olyan funkci´ot tartalmaz, amelyek lehet˝ov´e teszik a felhaszn´ al´ ok sz´ am´ ara speci´ alis k´ odok l´etrehoz´as´at a TSP szer˝ u probl´em´akhoz. A Concorde t´ amogatja a QSopt line´ aris programoz´asi megold´ast ´es a cplex-et. Hans Mittelmann l´etrehozott egy NEOS szervert a Concorde-nak, amely lehet˝ov´e teszi a felhaszn´ al´ ok sz´ am´ ara, hogy a TSP-feladatokat online lehessen megoldani.
24
A Concorde ´ altal haszn´ alt heurisztik´ ak: • Greedy: Kisz´ am´ıt egy moh´ o algoritmus ´altal k´esz´ıtett k¨orutat • Boruvka: Kisz´ am´ıt egy Boruvka algoritmus ´altal k´esz´ıtett k¨orutat • Quick Boruvka: Kisz´ am´ıt egy Quick Boruvka algoritmus ´altal k´esz´ıtett k¨orutat • Nearest Neighbor: Kisz´ am´ıt egy legk¨ozelebbi szomsz´ed algoritmus ´altal k´esz´ıtett k¨orutat • Random: Kisz´ am´ıt egy v´eletlen k¨orutat • Lin Kernighan: Kisz´ am´ıt egy Lin-Kernighan algoritmus ´altal k´esz´ıtett k¨orutat
Olaszorsz´ ag - 16,862 v´ aros ´es az optim´ alis u ´t [38] A TSP megold´ asa azt jelenti, hogy meg kell tal´alnunk egy abszol´ ut legr¨ovidebb t´ ur´at ´es biztosnak kell lenn¨ unk abban, hogy nincs enn´el jobb t´ ura. Ennek ellen˝ orz´es´ere a Concorde k¨ ul¨ onb¨oz˝o elj´ar´asokat haszn´al: Geometriai als´o hat´art ellen˝orz´esi z´ on´ akkal, t´ ur´ ak elimin´ aci´ oj´ at, v´ ag´ asi s´ıkok m´odszer´et, helyi v´ag´asokat ´es ’Branch-and-cut’ m´odszert emellett ellen˝ orzi a sz´ am´ıt´ asok pontoss´ag´at. A programot mostan´ aban is akt´ıvan haszn´alj´ak, ennek bemutat´as´ara szolg´al a k¨ovetkez˝o p´elda.
25
Pok´ emon Go ´ es a TSP ´ min´el gyorsabban? Erre egy remek TSP modellt lehet fel´ırni. Szerezd meg h´ at mind? Es A pok´emon mesterek szerencs´ej´ere a Concorde rengeteg id˝ot sp´orol nekik, hisz megmondja, hogyan juthatnak el a legr¨ ovidebb u ´ton az o¨sszes Pok´emonhoz. Ha a Pok´emonok egy ter¨ uleten t¨ obb sz´azan vagy ak´ar t¨obb ezren vannak, akkor sz¨ uks´eg van matematik´ ara, hogy meglelj¨ uk a legjobb utat ´es lehet˝oleg a lehet˝o legr¨ovidebb id˝o alatt. A Pokemon Go NYC csoport naprak´esz t´erk´epet tart a ritka Pok´emonok felfedez´eseir˝ol. Az ´abr´ an l´ athat´ o az optim´ alis t´ ura 68 ritka pok´emonhoz.
Erre a 68 pontra a Concorde 0,1 sec. alatt tal´ alta meg az optim´ alis utat.[39] A t´ ura teljes hossza 215 kilom´eter. Ez egy kicsit hossz´ u s´eta egyszerre, de ha valaki csak Manhattan-hez ragaszkodna, akkor ott elegend˝o Pok´emont tal´al egy d´elut´anra. A Concordot sok m´ as ter¨ uleten is haszn´alj´ak, csak hogy n´eh´anyat eml´ıtsek: A legk´ezenfekv˝obb alkalmaz´ asa a k¨ ul¨ onb¨ oz˝ o k¨ orutak ´es t´ ur´ ak tervez´ese, optim´alis sz´all´ıtm´anyoz´azi u ´tvonalak meghat´aroz´ asa. Ezeken k´ıv¨ ul akad m´eg m´ as ter¨ uleteken is alkalmaz´asa. Haszn´alj´ak p´eld´aul g´ent´erk´epez´eshez, teleszk´ opok ´es l´ezerek ir´ anyt´ as´ ahoz, bolyg´ok keres´es´ehez, mikrochipek tesztel´es´ehez ´es k¨ ul¨onb¨oz˝o vesztes´egek minimaliz´ al´ as´ ahoz is. 26
8.3. Nyomtatott ´ aramk¨ or¨ ok o ¨sszeszerel´ ese Az alkatr´eszek elhelyez´es´enek sorba rendez´ese egy olyan ¨osszetett feladat, ami a nyomtatott ´aramk¨ or¨ ok ¨ osszeszerel´es´en´el el˝ oj¨ on. Am´ıg n´eh´ any elhelyez˝ o g´ep sz´ am´ ara minden elhelyez´esi sor elfogadhat´o, m´as esetekben n´eh´ any ilyen sorozat nem megengedett az elhelyez˝o fej form´aja miatt. Ezekben az esetekben, m´ıg a fej lefel´e mozog, hogy egy elhelyez´est elv´egezzen ek¨ozben egy m´asik m´ar kor´abban elhelyezett alkatr´esz megs´er¨ ulhet. Egy ilyen minimum ¨osszeg˝ u sorrend meghat´aroz´as´anak probl´em´ aja egy PCTSP (Precedence Constrained Travelling Salesman Problem) megfogalmaz´as´ahoz vezet. Ebben a r´eszben egy megold´ asi m´ odszert vizsg´alunk erre a probl´em´ara, illetve kivitelez´es´et a nyomtatott ´ aramk¨ or¨ ok (PCB) ¨ osszeszerel´esi k¨ornyezet´eben. A sz´ am´ıt´ og´epek ´es a numerikusan szab´alyozott elektronikus alkatr´eszek elhelyez´es´e´ert felel˝os g´epek sebess´eget ´es precizit´ ast ´es megb´ızhat´os´agot biztos´ıtottak a PCB ¨osszeszerel´esi m˝ uvelet´ebe. Ezzel egyetemben azonban k¨ ul¨ onb¨ oz˝ o probl´em´ak is felmer¨ ultek, amelyeket hat´ekonyan meg kell oldani, hogy el´erj¨ uk a maxim´ alis hasznos´ıt´ as´ at a g´epeknek. A f˝obb probl´em´ak pl. az elhelyez´esi sorrend meghat´ aroz´ asa, az adagol´ o k´esz¨ ul´ek konfigur´aci´oja, a munkaterhel´es kiegyens´ ulyoz´asa ´es az ´aramk¨or¨ ok termel´es´enek u ¨temez´ese, melyek ´ altal´aban egym´ast´ol f¨ uggetlenek. Ha m´ar a g´ep az adagol´o automat´ aval (mechanizmus ahol az alkatr´eszt´ıpusokat t´arolj´ak) ell´atja alkatr´eszekkel az elhelyez˝o fejet, fontos k´erd´es az adagol´ o k´esz¨ ul´ek konfigur´aci´oja, ugyanis k¨ozvetlen¨ ul befoly´asolja az egym´ ast k¨ ovet˝ o elhelyez´esek k¨ ozti id˝ ot. Ez a probl´ema u ´gy ´ırhat´o fel, mint egy line´aris vagy kvadratikus hozz´ arendel´esi probl´ema. Ha egy gy´ art´ o t¨ obb g´epet telep´ıt, hogy egy PCB-t ¨osszerakjon, akkor sz¨ uks´egszer˝ u, hogy egyenl˝ oen ossza fel az ¨ osszeszerel´esi munk´ at, hogy elker¨ ulje az u ¨res j´aratokat. Az ¨ osszeszerel´esi munk´ ak kiegyens´ ulyoz´asa mellett ugyancsak fontos meghat´arozni a gy´art´asi u ¨temtervet, hogy a megfelel˝ o mennyis´egben ´alljon rendelkez´esre a term´ek. A probl´em´ ak matematikai megfogalmaz´asa, komplexit´asa ´es megold´asa nagyban f¨ ugg a haszn´ alt g´ep t´ıpus´ at´ ol ´es a termel´esi k¨ or¨ ulm´enyekt˝ol. Mi ezek k¨oz¨ ul az elhelyez´esi sorrend meghat´aroz´as´ aval fogunk f˝ ok´ent foglalkozni, ez arra utal, hogy az adott g´ep¨ unk milyen sorrendben rakja le az alkatr´eszeket a PCB-re. Ez sok g´ep sz´am´ara egy TSP lenne Csebisev t´avols´agi m´ert´ekkel. Azonban a mi eset¨ unkben ez egy kicsit komplik´altabb. N´eh´any g´ep eset´eben ugyanis n´eh´any elhelyez´esi sorrend k´ art okoz, az elhelyez˝ o fej k´ aros´ıt egy m´ar kor´aban lerakott alkatr´eszt. Ez nem megengedhet˝ o. ´Igy h´ at annak ´erdek´eben, hogy megtal´aljuk a megold´ast figyelembe kell venni n´eh´any korl´atoz´ast ´es ´ıgy v´eg¨ ul egy els˝ obbs´egi sorrend ´ altal megszor´ıtott TSP-hez (PCTSP). Az alkatr´esz k´arosod´as´anak probl´em´ aja ´ altal´ aban sug´ arvez´erelt g´epekn´el fordul el˝o vagy olyan g´epekn´el ahol a fej a m´erete ´es form´ aja miatt bizonyos esetekben k´ art okozhat.
27
A g´ep amit t¨ uzetesebben is vizsg´alni fogunk a t¨or¨ok elektronikai iparban is haszn´alt Universal 6346 A t´ıpus´ u sug´ arvez´erelt g´ep. Ennek a g´epnek van egy online sorba rendez˝o mechanizmusa (adagol´ o automata), amely a g´ep m¨ og¨ ott helyezkedik el ´es 60 f´ele alkatr´eszt´ıpust tud t´arolni. Az alkatr´eszeket az adagol´ o fejekkel (DH) elv´agja ´es fut´oszalagra rakja (minden adagol´o/sorba rendez˝ o poz´ıci´ ohoz van egy megfelel˝ o DH ´es az ¨osszetartoz´ok megfelel˝oen vannak sz´amozva), ami elviszi az alkatr´eszeket az elhelyez˝ o fejhez az elhelyez´es sorrendj´eben.
Az elhelyez˝ o fej egy helyben ´ all v´egig, ´ıgy helyette az elhelyez´esi pont s´ıkba ´all´ıt´as´at a hordoz´o lap (a fel¨ ulet ahol a PCB-t elhelyezz¨ uk) v´egzi az x-y s´ıkon f¨ uggetlen egyidej˝ u mozg´assal. Miut´an az elhelyez´esi pont a fej alatt van, a fej lehelyezi a sorban k¨ovetkez˝o alaktr´eszt.Az elj´ar´as pontosabban: • A hordoz´ o lap a megfelel˝ o x-y koordin´at´ara mozog • A rakod´ og´ep el˝ oremegy ´es alkatr´esszel l´atja el az elhelyez˝o fejet • A k¨ ovetkez˝ o alkatr´esz a rakod´ og´ep el´e megy • Az elhelyez´esi fej lemegy ´es elfordul, ha sz¨ uks´eges • A v´ ag´ as´ert ´es r¨ ogz´ıt´es´ert felel˝ os fej felemelkedik (a hordoz´ot´abla alatt helyezkedik el) • A nyom´ or´ ud lenyomja az alkatr´eszt a lapra • Az alkatr´eszt elv´ agja ´es r¨ ogz´ıti ez ez´ert felel˝os fej • Az elhelyez˝ o fej felemelkedik • A v´ ag´ as´ert ´es r¨ ogz´ıt´es´ert felel˝ os fej leereszkedik
28
Ezeket a l´ep´eseket hajtjuk v´egre egym´as ut´an, az els˝ot lesz´am´ıtva a t¨obbi l´ep´es f¨ uggetlen a komponens t´ıpus´ at´ ol ´es az elhelyez´es sorrendj´et˝ol (az els˝o l´ep´est lesz´am´ıtva egy ilyen l´ep´essorozat 0,34 m´ asodpercet vesz ig´enybe). Az elhelyez˝ o fej mint feljebb eml´ıtettem forog ha sz¨ uks´eges ´es h´arom forg´asi sz¨oggel tud elhelyezni: 0◦ , +90◦ , −90◦ . A fej akkor fordul el amikor lefel´e megy, ´ıgy ez nem vesz plusz id˝ot ig´enybe. Az alkatr´eszek horizont´ alisan ´es vertik´ alisan is elhelyezhet˝oek, emellett lehetnek elektromosan pol´arisak ´es apol´ arisak is. A hordoz´ o lap nem forog, sz´oval ha pol´aris alkatr´eszt szeretn´enk elhelyezni 180◦ -os elforgat´ assal, akkor az alkatr´esz kioszt egy m´asodik helyet az adagol´o automat´aban ami ford´ıtott polarit´ assal, 0◦ -os elforgat´ assal helyezi el, ha nincs szabad hely akkor a m˝ uveletet manu´alisan kell elv´egezni. Az ´ altalunk megfigyelt g´epn´el a probl´ema az optim´alis sorrend megtal´al´as´ara korl´atoz´odik. Azonban figyelni kell a s´er¨ ul´es vesz´elyre. Ha egy kor´abban lerakott elem t´ ul k¨ozel van a k¨ovetkez˝o lerakand´ o elemhez, akkor a fej ´ altal megs´er¨ ulhet a kor´abban lerakott elem. Azaz nagyban f¨ ugg a rong´ al´ od´ as vesz´elye az alkatr´eszek k¨ ozels´eg´et˝ol.
A k¨ ozels´eg mellett az alkatr´esz magass´aga is fontos, mivel a mi eset¨ unkben az elhelyez˝o fej h´atulja egy 45◦ -os ferdes´ık ´ıgy alacsonyabb magass´ag´ u alkatr´eszeket nem k´aros´ıtja, m´ıg magasabbakat m´ar igen. A fej sz´eless´eg´enek tudat´ aban, azonban k´esz´ıthet¨ unk egy becsl´est a s´er¨ ul´esi ter¨ ulet meghat´aroz´as´ ara.
29
Teh´ at, legyen adott egy fix sz´eless´eg, emellett a der´eksz¨og˝ u ter¨ ulet hossz´at (d) meghat´arozhatjuk az alkatr´esz magass´ ag´ anak ´es a sz¨ og kotangens´enek szorzat´aval, amit a fej z´ar be az x-y s´ıkkal. A fels˝ o korl´ at pedig a D-vel kaphat´ o, amely a der´eksz¨og˝ u k´arosod´asi ter¨ ulet hossza, amir u ´gy kapunk, hogy a fej ferdes´ıkj´ anak a v´eg´et levet´ıtj¨ uk a tengelyre. Annak ´erdek´eben, hogy elker¨ ulj¨ uk a k´arosod´ast k´et dolgot tehet¨ unk: • elhelyez´esi sz¨ og v´ altoztat´ as´ aval • elhelyez´esi sorrend megv´ altoztat´as´aval ´Igy jutunk el v´eg¨ ul oda, hogy a matematikai modell¨ unk egy els˝obbs´egi sorrend ´altal megszor´ıtott TSP lesz (PCTSP). Ennek megold´ asa azonban kor´an sem egyszer˝ u, nem lehet r´a z´art formul´at adni. A megold´ asi m´ odszer¨ unkh¨ oz ´ıgy h´ at egy kis tr¨ ukk¨ot alkalmazunk. Formaliz´aljuk a feladatot u ´gy, hogy az alkatr´eszek s´er¨ ul´es´enek probl´em´aj´at figyelmen k´ıv¨ ul hagyva az elhelyez´esi probl´em´at egy TSP-vel azonos´ıthatjuk Csebisev t´ avols´agi m´ert´ekkel. min
N X N X
tij xij
i=1 j=1 j6=i
PN
j=1
j6=i PN
P
i∈S
i=1 i6P =j
xij
=
1
j∈N
xij
=
1
i∈N
j∈S j6=i
xij
xij = 0 vagy
≤ 1
|S| − 1
∀ S⊂N
i, j = 1, ..., N
i 6= j
Ahol, N – az elhelyez´esi pontok halmaza S – nem u ¨res r´eszhalmaza N-nek xi,j - 1 ha i el˝ obb van mint j, k¨ ul¨ onben 0 ti,j - id˝ o ami eltelik i ´es j teljes´ıt´ese k¨ozt t0 - elj´ ar´ as fix ideig tart t1i,j - a hordoz´ o lap mozg´ asi ideje x tengelyen i ´es j k¨oz¨ott t2i,j - a hordoz´ o lap mozg´ asi ideje y tengelyen i ´es j k¨oz¨ott ti,j = t0 + max(t1i,j , t2i,j ) Ezt megoldjuk, majd ezut´ an elt´ avol´ıtjuk a k´arosod´asi t´enyez˝oket a megl´ev˝o TSP k¨orutunkb´ol.
30
8.3.1. A probl´ ema megold´ asa A TSP megold´ as´ ara a konvex burok algoritmust ´es az Or-Opt algoritmust haszn´aljuk. Konvex burok (Convex Hull) algoritmus • Keress¨ uk meg a pontok konvex burk´at, csin´aljunk ebb˝ol egy k¨ort. • Minden k¨ or¨ on k´ıv¨ uli pontot sz´ urjunk be, a legk¨ozelebbi besz´ ur´as m´odszer´evel. • Ism´etelj¨ uk az elj´ ar´ ast, m´ıg minden pont be nem lesz sz´ urva. Majd az ´ıgy kapott megold´ ast fejlesztj¨ uk tov´abb az Or-Opt algoritmussal. Az Or-Opt algoritmus a konvex burok algoritmus ´altal megadott megold´ason jav´ıt u ´gy, hogy a pontok minden lehets´eges ´ athelyezes´es´et, illetve minden egym´ast k¨ovet˝o pontp´art ´es ponth´armast athelyez´es´et kipr´ ´ ob´ alja. Egy v´eletlenszer˝ uen v´ alasztott pontal kezdj¨ uk az algoritmust, ehhez a ponthoz hozz´avessz¨ uk a t´ ur´ ab´ ol a k´et r´ ak¨ ovetkez˝ o pontot ´es ezt a ponth´armast ideiglenesen elt´avol´ıtjuk. Ezut´an megpr´ob´aljuk besz´ urni ezeket a pontokat, vagy rendes vagy ford´ıtott sorrendben, a t´ ura k´et egym´ast k¨ovet˝o pontja k¨ oz´e. Akkor sz´ urjuk be a pontokat, ha jav´ıtunk az eredeti t´ ur´an a besz´ ur´assal. Ezut´an a k¨ovetkez˝ o pontot v´ alasztom ki ´es az ut´ ana l´ev˝ o k´et pontot ´es ugyanezt megcsism´etlem. Ezt addig csin´ aljuk, am´ıg az el˝ osz¨ or kiv´alasztott ponthoz nem ´er¨ unk el u ´jra. Ha u ´jra eljutunk a kiindul´ asi ponthoz, akkor hasonl´oan j´ar el az algoritmus mint az el˝obb, de mostm´ ar csak pontp´ arokat pr´ ob´ alunk besz´ urni. Ha ezt is leellen˝orizt¨ uk akkor minden egyes pontra megn´ezz¨ uk ugyanezeket a pontcser´eket. Az ´ıgy kapott optimaliz´ alt k¨ or´ uton pedig lefuttatunk egy k´arosod´ast reduk´al´o algoritmust (DRP´ Damage Reduc. Procedure). Ugy van tervezve, hogy minim´alis k¨olts´eg n¨oveked´est okozzon a megk¨ ot´es n´elk¨ uli TSP-ben. El˝ osz¨ or u ´gy pr´ob´aljuk megsz¨ untetni a lehets´eges k´arok forr´as´at, hogy ±180◦ -al elforgatjuk (csak a ±90◦ -n´ al lehets´eges ´es nem n¨oveli a TSP k¨olts´eg´et). Ha ez sikeres volt, ´es marad m´eg k´ ar forr´ as amit nem tudunk m´ar ezzel kik¨ usz¨ob¨olni, akkor megpr´ob´aljuk a lerak´ asi sorrendet megv´ altoztatni, hogy megsz¨ untess¨ uk. Az elj´ ar´ as l´ep´esei: 1. A t´ ura ir´ any´ anak megtal´ al´ asa. Az adott t´ ur´ankat mindk´et ir´anyban k¨or¨ ulj´arjuk, majd azt a k¨ or¨ ulj´ ar´ ast (lerak´ asi sorrendet) v´alasztjuk, amelyikben a s´er¨ ult alkatr´eszek sz´ama kevesebb. 2. Az ´ıgy kiv´ alasztott k¨ or¨ ulj´ ar´ assal folytatva, a sz¨og v´altoztat´as´aval pr´ob´alunk jav´ıtani apol´ aris alkatr´eszekn´el. Ha +90◦ (−90◦ )-os elhelyez´ese egy apol´aris alkatr´esznek k´art okoz, akkor ha −90◦ (+90◦ )-os sz¨ oggel helyezz¨ uk el megsz¨ untethetj¨ uk a probl´em´at u ´gy, hogy nem keletkezik u ´jabb k´ arosod´ as. Ha ez teljes¨ ul megv´altoztatjuk a sz¨oget, ha nem u ´gy hagyjuk ahogy volt. 3. Ezut´ an a sz¨ oget ´es az adagol´ o fejet (DH) cser´elj¨ uk a pol´aris alkatr´eszekn´el. Ha egy +90◦ (−90◦ )-os elhelyez´es˝ u pol´aris alkatr´esz k´art okozna ´es ha az alkatr´esz t´ıpusa hozz´ a van rendelve (vagy hozz´ arendelhet˝o) k´et adagol´o fejhez az adagol´o automat´aban ford´ıtott polarit´ assal ´es meggondoljuk, hogy egy alternat´ıv adagol´o veszi fel (ford´ıtott polarit´assal) ´es helyezi el −90◦ (+90◦ )-os sz¨ oggel. Ezut´ an ellen˝ orizz¨ uk, hogy megsz˝ unt-e a k´ar ´es hogy nem hoztunk-e l´etre u ´jabb k´arosod´asokat. Ha ez teljes¨ ul akkor megv´ altoztatjuk az elhelyez´esi sz¨oget ´es az eredeti helyre lerak´o DH sz´am´ at
31
az alternat´ıv DH sz´ amra v´ altoztatjuk, ahol az alkatr´eszt´ıpus most elhelyezkedik. Ha nem teljes¨ ul mindent v´ altozatlanul hagyunk. 4. Elhelyez´esi sorrend v´ altoztat´ asa. Keress¨ uk meg a megmaradt alkatr´eszeket, amik k´arosodn´anak ´es azonos´ıtsuk a sorrendj¨ uket. V´ altoztassuk meg az elhelyez´esi sorrendj¨ uket a k¨ovetkez˝o szerint: jel¨olj¨ uk meg a s´er¨ ult alkatr´eszek k¨ oz¨ ul azokat, amelyeket egym´ast k¨ovet˝oen helyez¨ unk el a k¨orutunk szerint. Tekints¨ uk ezeket kis sorozatoknak ´es ezen sorozatok sorrendj´et ford´ıtsuk meg ´es rakjuk le ˝ oket ideiglenesen, ha az els˝ o nem s´er¨ ult alkatr´esz megjelenik a sorozatban. Ezut´ an Or-Opt-ot haszn´ alunk ´es pr´ob´alunk jobb helyet tal´alni a sorozatban l´ev˝o pontoknak a teljes elhelyez´esi u ´tvonalon u ´gy, hogy besz´ urjuk ˝oket a norm´al sorrendj¨ ukben a k¨or´ ut pontjai k¨ oz´e. Ha tal´ alunk jobb helyet besz´ urjuk oda, ha nem akkor az ideiglenes hely¨ uk lesz a v´egleges. ´ 5. Ujabb sz¨ ogv´ altoztat´ asok. A 2-es ´es 3-as l´ep´est alkalmazva pr´ob´aljuk elt¨ untetni a sorrendv´altoz´as (4-es l´ep´es) ´altal l´etrehozott u ´j k´ arosod´ asokat. 6. Ha m´eg maradt k´ arosod´ as, akkor a 4-es ´es 5-¨os l´ep´est ism´etelj¨ uk am´ıg meg nem sz¨ unik minden k´ arosod´ as vagy el nem ´erj¨ uk az el˝ore megadott iter´aci´os l´ep´essz´amot. Az 1-5-ig a l´ep´eseket a DRP egy alkalmaz´as´anak nevezz¨ uk, a 6. l´ep´es pedig mindig egy u ´jabb alkalmaz´ asa a DRP-nek. A 4-es l´ep´es gyakran el˝ofordul probl´em´ara vil´ag´ıt r´a a PCB-kn´el ugyanis az adott tervez´es miatt ´es magasabb kapacit´as ´erdek´eben (kondenz´atorok) ´erdemes egym´as mell´e rakni az alkatr´eszeket. El˝ ofordul, hogy u ´gyis egy ’sorozatnak’ vessz¨ uk az elemeket, hogy a s´er¨ ult elem el˝ otti ´es ut´ ani l´ev˝ o elem s´ertetlen. A s´er¨ ul´est ´altal´aban az egym´ast k¨ovet˝o lehelyez˝o elj´ar´asok okozz´ ak. Ez´ert is f¨ ugg ¨ ossze a s´er¨ ul´esi felt´etel az alkatr´eszek k¨ozels´eg´evel. Az ilyen k¨ozeli elemeket altal´ ´ aban megszak´ıt´ as n´elk¨ ul egym´ as ut´an helyezik el, a konvex burok algoritmusnak megfelel˝ oen. Emiatt a 4. l´ep´esben a s´er¨ ult alkatr´eszek az els˝o nem s´er¨ ult m¨og´e ker¨ ulnek, azt v´arva, hogy a s´er¨ ul´esi felt´etel megsz˝ unik. Ha nem ez a helyzet ´es egy k´es˝obbi alkatr´esz okozza a k´art, akkor az egy k´es˝obbi DRP alkalmaz´ assal megsz˝ untethet˝ o. A DRP azonban nem tud minden probl´em´at megsz¨ untetni, pl. ha egy alkatr´esz t¨ obb m´ as alkatr´esz lehelyez´ese miatt is s´er¨ ul, ilyenkor lehet, hogy nem lehet a DRP t¨ obbsz¨ ori alkalmaz´ as´ aval sem megoldani a probl´em´at, ´es az ´aramk¨or tervez´es´enek megv´altoztat´ asa sz¨ uks´eges. 8.3.2. Az elj´ ar´ as teljes´ıtm´ enye Hogy v´egleges´ıts¨ uk az elhelyez´esi sorrendet a sug´arvez´erelt g´epekben a DRP alkalmaz´asa seg´ıts´eg´evel egy tov´ abbi kiigaz´ıt´ as sz¨ uks´eges. El˝ osz¨or kisz´amoljuk a s´er¨ ul´esi ter¨ uleteket, vagy fels˝o becsl´est adunk r´ ajuk, ´ıgy kapjuk meg a potenci´ alisan s´er¨ ult alkatr´eszek halmaz´at, ez alapj´an v´egleges´ıtj¨ uk a sorrendet. Tudjuk, hogy a ¨ osszeszerel´esi id˝ o nagyobb lesz, mivel a s´er¨ ul´es megel˝oz´es n¨ovelheti a TSP k¨or´ ut k¨ olts´eg´et. A most haszn´ alt algoritmusunkat egy r´egebben alkalmazottal (Legk¨ozelebbi szomsz´ed algoritmus) hasonl´ıtottuk ¨ ossze a k¨ ovetkez˝ ok alapj´an: • A teljes ¨ osszeszerel´esi id˝ o jav´ıt´ asa • Az elhelyez´esenk´enti 0,34 sec. elhanyagolva (hogy kiegyens´ ulyozottabb ¨osszehasonl´ıt´ast kapjunk) a teljes´ıtm´eny m´ert´ek ¨ osszehasonl´ıt´asa 32
Ennek eredm´enyk´ent azt kaptuk, hogy amikor a VOPT-ot haszn´altunk ´es a DRP-t egyszer, az ¨osszeszerel´esi id˝ o ´ atlagosan 1,96%-ot javult, m´ıg a teljes´ıtm´eny m´ert´ek ´atlagosan 6,47% (az ´atlagok az elhelyezett alkatr´eszek sz´ am´ aval s´ ulyozottak). A potenci´alisan s´er¨ ult elemek sz´ama 90%-al cs¨okkentek. (A val´ o ´eletben term´eszetesen ha marad m´eg potenci´alisan s´er¨ ult elem, akkor annak elhelyez´es´et manu´ alisan v´egzik.) Ha a DRP-t t¨ obbsz¨ or alkalmazzuk, a potenci´alis s´er¨ ult elemek sz´ama tov´abb cs¨okken, ´es ´atlagosan 4 iter´ aci´ o ut´ an az eredm´eny m´ ar a null´ahoz vagy egy kis sz´amhoz konverg´al. A k´aroknak a megsz¨ untet´es´ere ir´ anyul´ o k¨ olts´eg csak 0,9% volt. A tanulm´ anyban v´egrehajtott k´ıs´erleti megval´os´ıt´as nem csak a teljes´ıtm´eny 2% -os k¨ozvetlen n¨ oveked´es´et eredm´enyezte (az NN algoritmussal szemben), hanem olyan sug´arvez´erelt elhelyez´esi sorrendek l´etrehoz´ as´ at is seg´ıtette, amelyek csak nagyon kissz´am´ u potenci´alisan s´er¨ ult elemet tartalmaznak. Emellett majdnem teljesen automatiz´alt a m˝ uvelet (az NN-n´el m´eg sz¨ uks´eg volt manu´ alis jav´ıt´ asokra).
A potenci´ alisan s´er¨ ult elemek sz´ ama a DRP t¨ obbsz¨ ori alkalmaz´ asa ut´ an A t´ abl´ azat oszlopainak magyar´ azata: BOARD – a t´ abla neve n – az elhelyezett alkatr´eszek sz´ ama Init. time - A TSP k¨ olts´ege a DRP el˝ott 1. time - A TSP k¨ olts´ege a DRP egyszeri alkalmaz´asa ut´an Last time - A TSP k¨ olts´ege a DRP h´ uszszori alkalmaz´asa ut´an Dam(NN) – A potenci´ alisan s´er¨ ultek sz´ama NN alkalmaz´asa ut´an k = 1, . . . , 20 - A potenci´ alisan s´er¨ ultek sz´ama k DRP alkalmaz´as ut´an
33
¨ 9. Osszefoglal´ as Ami´ ota csak l´etezik a probl´ema rengeteg matematikus figyelm´et ragadta meg, sz´amos ´ertekez´es sz¨ uletett r´ ola, de m´eg ma is sok nyitott k´ed´es maradt a TSP-vel kapcsolatban. A kombinatorikus optimaliz´ al´ as egyik f˝ o probl´em´ aja ez, mely napjainkban is aktualit´as´at ´eli. Pontos ´es gyors megold´ ast a mai napig nem tudunk adni erre az egyszer˝ unek l´atsz´o feladatra. Val´ oj´ aban ha a TSP ´ altal´ anos alakj´ at valaki megoldan´a az a P =? NP probl´em´aj´at is megoldan´ a, ´es ´ıgy egy 1,000,000$-os d´ıjat nyerne el az Clay Mathematics Int´ezett˝ol. Ez azonban m´eg nem t¨ ort´ent meg ´es b´ar a TSP komplexit´asa m´eg mindig ismeretlen, t¨obb mint 50 ´evnyi tanulm´ anyoz´ as ut´ an sz´ amos heurisztika ´es k¨ozel´ıt´es l´etezik a megold´asra, melyek bizonyos felt´etelek mellett remek¨ ul m˝ uk¨ odnek. Ezeket ellen˝ orz´es´ere vannak korl´ atok, melyek seg´ıts´eg´evel becsl´est tudunk adni az optim´alis TSP k¨ or´ utra. Emellett term´eszetesen ha ´ep´ıt¨ unk vagy tal´alunk egy k¨orutat azt tudjuk jav´ıtani. A szakdolgozatom egyik c´elja az volt, hogy ezeket bemutassam, ellett szerettem volna szem¨ uk el´e t´ arni az utaz´ ou ¨gyn¨ ok probl´ema sokr´et˝ u alkalmaz´asait, illetve olyan megold´asi m´odszereket ´es programokat melyeket a val´ o ´eletben haszn´alnak a probl´ema megold´as´ara. Abban biztos vagyok, hogy a probl´ema tov´abbra is foglalkoztatja majd a matematikusokat, mind m´ as ´es m´ as megfogalmaz´ asban ´es ezekre egyre jobb megold´asokkal ´allnak majd el˝o, de, hogy a probl´ema probl´em´ at valaki megoldja-e valaha az egy u ´jabb nyitott k´erd´es.
34
Hivatkoz´ asok [1] [‘ein alter Commis-Voyageur’], Der Handlungsreisende - wie er sein soll und was er zu thunhat, ¨ um Auftr¨ age zu erhalten und eines glUcklichen Erfolgs in seinen Gesch¨ aften gewiß zu sein - Von einem alten Commis-Voyageur, B.Fr. Voigt, Ilmenau, 1832 [reprinted: Verlag Bernd Schramm, Kiel, 1981]. [2] W.R. Hamilton, Memorandum respecting a new system of roots of unity (the Icosian calculus), Philosophical Magazine 12 (1856) 446 Proceedings of the Royal Irish Academy 6 (1858) 415-416 [reprinted in: The Mathematical Papers of Sir William Rowan Hamilton - Vol. III Algebra (H. Halberstam, R.E. Ingram, eds.), Cambridge University Press, Cambridge, 1967, p. 610]. [3] W.R. Hamilton, On a new system of roots of unity, Proceedings of the Royal Irish Academy 6 (1858) 415-416 [reprinted in: The Mathematical Papers of Sir William Rowan Hamilton - Vol. III Algebra (H. Halberstam, R.E. Ingram, eds.), Cambridge University Press, Cambridge, 1967, p. 609]. [4] T.P. Kirkman, On the representation of polyhedra, Philosophical Transactions of the Royal Society of London Series A 146 (1856) 413-418. [5] K. Menger, Some applications of point-set methods, Annals of Mathematics (2) 32 (1931) 739760. [6] M.M. Flood, The traveling-salesman problem, Operations Research 4 (1956) 61-75 [also in: Operations Research for Management - Volume IICase Histories, Methods, Information Handling (J.F. McCloskey, J.M. Coppinger, eds.), Johns Hopkins Press, Baltimore, Maryland, 1956, pp. 340-357]. [7] G. Dantzig, R. Fulkerson, S. Johnson, Solution of a Large Scale Traveling Salesman Problem, Paper P-510, The RAND Corporation, Santa Monica, California, [12 April] 1954 [published in Journal of the Operations Research Society of America 2 (1954) 393-410]. [8] Held, Michael, and Richard M. Karp. ”The traveling-salesman problem and minimum spanning trees: Part II.” Mathematical programming 1.1 (1971): 6-25. [9] Camerini, Paolo M., Luigi Fratta, and Francesco Maffioli. ”On improving relaxation methods by modified gradient techniques.” Nondifferentiable optimization. Springer Berlin Heidelberg, 1975. 26-34. [10] Gr¨ otschel, Martin. ”Polyedrische Charakterisierungen kombinatorischer Optimierungsprobleme.” (1977). [11] Crowder, Harlan, and Manfred W. Padberg. ”Solving large-scale symmetric travelling salesman problems to optimality.” Management Science 26.5 (1980): 495-509. [12] Padberg, Manfred, and G. Rinaldi. ”Optimization of a 532-city symmetric traveling salesman problem by branch and cut.” Operations Research Letters 6.1 (1987): 1-7. [13] Gr¨ otschel, Martin, and Olaf Holland. ”A cutting plane algorithm for minimum perfect 2matchings.” Computing 39.4 (1987): 327-344. 35
[14] Padberg, Manfred, and Giovanni Rinaldi. ”Optimization of a 532-city symmetric traveling salesman problem by branch and cut.” Operations Research Letters 6.1 (1987): 1-7. [15] Applegate, D., et al. ”Finding cuts in the TSP” a preliminary report distributed at The Mathematical Programming Symposium.” Ann Arbor, Michigan 16 (1994). [16] Applegate, D., et al. ”On the solution of travelling salesman problems.” (1998). [17] Applegate, D., et al. ”TSP cuts which do not conform to the template paradigm.” Computational combinatorial optimization (2001): 261-303. [18] Applegate, D., et al. ” , , , and K. Helsgaun,“Optimal Tour of Sweden,”.” World Wide Web: http://www.gatech.edu/sweden (2004). [19] Ore, Ø., ”Note on Hamilton circuits”, American Mathematical Monthly, (1960) 67 (1): 55 [20] G.A. Dirac Some Theorems on Abstract Graphs Proc. London Math. Soc., 2 (1952), pp. 69-81 [21] L Posa - Magyar Tud. Akad. Mat. Kutat´ o Int.K¨ ozl, 1962 [22] Chv´ atal, V. ”On Hamilton’s Ideals.” J. Combin. Th. 12, 163-168, 1972. [23] Richard Bellman - ‘Dynamic programming treatment of the travelling salesman problem’, Journal of Assoc. Computing Mach. 9. 1962. [24] ’A dynamic programming approach to sequencing problems’, Michael Held and Richard M. Karp, Journal for the Society for Industrial and Applied Mathematics 1:10. 1962 [25] AM Turing - On Computable Numbers, with an Application to the Entscheidungsproblem, Proceedings of the London Mathematical Society, Series 2, Volume 42, 1936; reprinted in M. David (ed.), The Undecidable, Hewlett, NY: Raven Press, 1965; online: *Boolos, G. and Jeffrey, R., Computability and Logic, 2nd ed., Cambridge: Cambridge University Press, 1980. [26] Cook, Stephen. ”The complexity of theorem proving procedures”. Proceedings of the Third Annual ACM Symposium on Theory of Computing. pp. 151–158 (1971). [27] M Held, RM Karp - Mathematical programming, 1971 - Springer [28] L. Goddyn: TSP Lower Bounds [29] DJ Rosenkrantz, RE Stearns, PM Lewis, II - An analysis of several heuristics for the traveling salesman problem SIAM journal on computing, 1977 - SIAM [30] R. C. Prim: Shortest connection networks and some generalizations, Bell System Technical Journal, 36 (1957), pp. 1389–1401. [31] Bor˚ uvka, O. ”O jist´em probl´emu minim´aln´ım” [About a certain minimal problem]. Pr´ ace mor. pˇr´ırodovˇed. spol. v Brnˇe III (in Czech and German). 3: 37–58. (1926) [32] N. Christofides, Worst-case analysis of a new heuristic for the travelling salesman problem, Report 388, Graduate School of Industrial Administration, CMU, 1976.
36
[33] G. A. CROES. A method for solving traveling salesman problems. Operations Res. 6 (1958) , pp., 791-812. [34] S. LIN. Computer solutions of the traveling salesman problem. Bell Syst. Tech. J. 44, 2245-2269. (1965) [35] Lin, Shen; Kernighan, B. W.. ”An Effective Heuristic Algorithm for the Traveling-Salesman Problem”. Operations Research. 21 (2): 498–516. (1973) [36] F. Glover. ”Future Paths for Integer Programming and Links to Artificial Intelligence”. Computers and Operations Research. 13 (5): 533–549. (1986) [37] Helsgaun, Keld. ”Solving the Bottleneck Traveling Salesman Problem Using the Lin-KernighanHelsgaun Algorithm.” Computer Science Research Report 143 (2011): 1-45. [38] http://www.math.uwaterloo.ca/tsp/world/countries.html [39] http://www.math.uwaterloo.ca/tsp/poke/index.html
37
A fejezetekhez haszn´ alt szakirodalmak 1 Bevezet˝ o Schrijver, Alexander. ”On the history of combinatorial optimization (till 1960).” Handbooks in operations research and management science 12 (2005): 1-68. 2 Defin´ıci´ ok Katona Gyula Y., Recski Andr´ as, Szab´o Csaba: A sz´ am´ıt´ astudom´ any alapjai. Typotex Kiad´ o, Budapest 2007. https://www.math.ku.edu/ jmartin/courses/math105-F11/Lectures/chapter6-part3.pdf https://gyires.inf.unideb.hu/mobiDiak/Turjanyi-Sandor/Bev.-a-komb.-es-a-grafelmeletbe/3.pdf 3 Bonyolults´ ag elm´ elet Kir´ aly Zolt´ an: Algoritmuselm´elet, Typotex 2014. Lov´ asz L´ aszl´ o - Algoritmusok Bonyolults´ aga Egyetemi Jegyzet Friedl Katalin - Turing-g´epek (Kieg´esz´ıt˝o anyag az Algoritmuselm´elet t´argyhoz) 4 Korl´ atok Luis Goddyn: TSP Lower Bounds http://mat.gsia.cmu.edu/classes/mstc/relax/node5.html 5 Approxim´ aci´ ok David L. Applegate, Robert E. Bixby, Vasek Chv´atal and William J. Cook: The Traveling Salesman Problem Christian Nilsson: Heuristics for the Traveling Salesman Problem, Link¨oping University https://en.wikipedia.org/wiki/Christofides algorithm Kis Tam´ as - Approxim´ aci´ os algoritmusok el˝oadas jegyzet William J. Cook: In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation
´ ep´ıt˝ 6 Ut´ o algoritmusok Hahsler, Michael, and Kurt Hornik. ”TSP-Infrastructure for the traveling salesperson problem.” Journal of Statistical Software 23.2 (2007): 1-21.
38
7 Jav´ıt´ o algoritmusok Keld Helsgaun An Effective Implementation of the Lin-Kernighan Traveling Salesman Heuristic, Department of Computer Science Roskilde University DK-4000 Roskilde, Denmark Markus Reuther - Implementing the Lin-Kernighan heuristic for the TSP Keld Helsgaun : Solving the Clustered Traveling Salesman Problem Using the Lin-Kernighan-Helsgaun Algorithm, ROSKILDE UNIVERSITY 2014. http://www.inf.u-szeged.hu/ cimreh/heurutem.pdf 8 Alkalmaz´ asok http://www.math.uwaterloo.ca/tsp/index.html E Duman, I Or - Taylor and Francis Precedence constrained TSP arising in printed circuit board assembly International Journal of Production Research, 2004.
39