Az utazo u gyno k proble ma e s alkalmaza sai

¨ 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ány

Témavezet˝o: Kiss Attila Szám´ıtógéptudományi Tanszék

Budapest, 2017

K¨ osz¨ onetnyilv´ an´ıt´ as Munk´ am végére érve szeretném megk¨ oszönni témavezet˝omnek, Kiss Attilának azt a rengeteg seg´ıtséget és t´ amogat´ ast, mellyel hozz´ aj´ arult szakdolgozatom ´ırásához, ezzel el˝oseg´ıtvén annak megsz¨ uletését. K¨ osz¨ onet illeti még Recski Andr´ ast, aki felkeltette az érdekl˝odésemet a véges matematika iránt. K¨ ul¨ on k¨ osz¨ onet a csal´ adomnak és bar´ ataimnak támogatásukért és t¨ urelm¨ ukért, valamint barátn˝omnek, aki mindezek mellett a nyelvi ´ attekintésben is seg´ıtségemre volt.

”Az u ´t ¨ or¨ ok és tétlen mégis mindent végbevisz észrevétlen...” ´ és Erény könyve Lao-Ce, Tao Te King: Az Ut We¨ ores S´ andor ford´ıt´ as´ aban, Tericum Kiadó, 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éges matematika, azon bel¨ ul is a gráfelmélet iránti érdekl˝odésem volt. Ezek ut´ an j´ ol megfontolt v´ alasztásom egy egyszer˝ unek t˝ un˝o, ámde annál összetettebb gráfelméleti optimaliz´ al´ asi feladatra esett. Ez az utazó u ¨gynök problémája. A feladat igen egyszer˝ u: Adott n v´ aros, valamint az u ´tiköltség/távolság bármely két város között és keress¨ uk a legolcs´ obb/legr¨ ovidebb utat egy adott városból indulva, amely minden várost pontosan egyszer érint, majd a kiindul´ asi v´ arosba ér vissza. Ez megfeleltethet˝o egy gráfelméleti problémának, a minim´ alis s´ uly´ u Hamilton-k¨ or keresésének, egy adott él s´ ulyozott gráfban.

Frod´ oék is ezt a legr¨ ovidebb utat keresték, b´ ar ˝ ok a megszokott´ ol eltér˝ oen s´ ulyozt´ ak az utat. A probléma elsz¨ or 1832-ben egy kézikönyvben [1] t˝ unt fel, ahol 45 német város közötti legr¨ ovidebb u ´tvonalat keresték, de ennek csak kés˝obb, 1983-ban adtak jelent˝oséget. Nem sokkal kés˝obb Sir William Rowan Hamilton [2][3] és Thomas Penyngton Kirkman [4] vetette fel a problémát az 1850es években, icosian j´ aték form´ aj´ aban, ez egy olyan logikai játék, melynek célja, hogy egy ’gráfban’ 3

k¨ orutat kell tal´ alni. Az probléma ´ altalános alakja csak kés˝obb, 1930-ban alakult ki. A név Travelling Salesman Problem (TSP) is ez id˝o tájt alakult ki. Ez id˝oben Karl Menger [5] foglalkozott a feladattal és ért el eredményeket ezzel kapcsolatban. Megállap´ıtotta például, hogy a legközelebbi szomszéd algoritmus nem mindig ad optimális megoldást a feladatra. Ezek után Menger el˝o is adta eredményeit a Harvardon és a Princetonon, mellyel több neves matematikus figyelmét is felh´ıvta a TSP-re. Hassler Whitney fel is figyelt a problémára, a 48 amerikai állam közt kereste a legrövidebb utat a harmincas évek elején. Ekkor tájt h´ıvták fel Flood [6] figyelmét is a TSP és az iskolabuszok u ´tvonal´ anak tervezése k¨ oz¨ otti kapcsolatra. A 40-es évekre kezdett népszer˝ uvé válni a feladat és t¨ obb atfogalmaz´ ´ asa is megjelent, éppen emiatt sok más optimalizálási feladat hozzájárult a fejl˝odéshez. Az igazi népszer˝ uséget a TSP-nek azonban 1954-ben hozta el Dantzig, Fulkerson, és Johnson [7]. Az altaluk ´ırt cikkben megoldott´ ´ ak a 49 amerikai városra a feladatot (48 állam mindegyikéb˝ol 1-1 v´ aros és még Washington D.C.) és t¨ obb u ´j módszert is kidolgoztak a TSP megoldására, megmutatták a v´ ag´ os´ıkok jelent˝ oségét. Ezut´ an ¨ orvendett igazi népszer˝ uségnek a TSP és kés˝obb több nagyszab´ as´ u kutat´ as alapj´ aul szolg´ alt a fent eml´ıtett cikk. A 60-as évekt˝ol napjainkig egyre szélesebb körben terjedt el a probléma és szakdolgozatom egyik célja, hogy az utazó u ¨gynök probléma alkalmazásait bemutassa. Rengeteg példa van az alkalmazásokra, a kés˝obbiekben párat jobban is megvizsgálunk. ´ 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ötschel [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átal, and W. Cook [15] D. Applegate, R. Bixby, V. Chvátal, and W. Cook [16] D. Applegate, R. Bixby, V. Chvátal, and W. Cook [17] D. Applegate, R. Bixby, V. Chvátal, W. Cook, and K. Helsgaun [18]

Feladat m´ erete 49 város 64 város 67 város 120 város 318 város 532 város 666 város 2,392 város 7,397 város 13,509 város 15,112 város 24,978 város

A k¨ ul¨ onb¨ oz˝ o méret˝ u TSP-k megold´ asa az évek sor´ an (1954-2004) Szakdolgozatomat az alapfogalmak tisztázásával kezdem, majd a Hamilton-kör létezésére vonatkoz´ o tételeket ismertetem. Ezut´ an a 3. fejezetben a probléma nehézségével foglalkozok, bemutatva a Turing-gépet, majd ezt felhaszn´ alva az NP-nehézséget. A 4. fejezetben a TSP megold´ as´ anak alsó és fels˝o korlátait mutatom be, majd ezután az 5. fejezetben approxim´ aci´ os algoritmusokat mutatok be a TSP megoldására. A 6. fejezetben az u ´tép´ıt˝ o algoritmusok m˝ uködését mutatom be, m´ıg a 7. fejezetben a jav´ıt´ o algoritmusokét. Ezek ut´ an a 8. fejezetben térek r´ a a TSP alkalmazásaira, amelyben a klaszterezéssel, a Concorde-dal és a nyomtatott ´ aramk¨ or¨ ok ¨ osszeszerelésével foglalkozom. Végezet¨ ul a 9. fejezetben ¨ osszefoglalom szakdolgozatom mondanivalóját.

4

2. Alapfogalmak Defin´ıci´ o. A G = (E, ϕ, V ) gr´ af H = v0 e1 v1 e2 v2 ...vn−1 en vn u ´tját (ϕ(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önböz˝ok és ezeken a pontokon k´ıv¨ ul m´ as cs´ ucspontja nincs G-nek. A G = (E, ϕ, V ) gráf K körét Hamilton-k¨ ornek mondjuk, ha K G gr´ af minden pontját tartalmazza. Megjegyzés: Ha egy Hamilton-k¨ or tetsz˝oleges élét elhagyjuk, akkor egy Hamilton-utat kapunk. A s´ ulyozott Hamilton-k¨ or keresési feladatnak létezik egy igen széles körben elterjedt megfogalmaz´ asa, ¨ az Utaz´ o Ugyn¨ ok probléma. Egy u ¨gyn¨ oknek meg kell l´ atogatnia adott városokat u ´tja során, majd a kiindulási városába kell viszszatérnie u ´gy, hogy minden v´ arosban csak egyszer járt. Adott, hogy az egyik v´ arosb´ ol a m´ asikba milyen költségek mellett tud eljutni. Természetesen szeretné a k¨ or´ ut ¨ osszk¨ oltségét minimalizálni. Ezen feladat alkalmazása igen soksz´ın˝ u, de csak speci´ alis esetekben tal´ alhatunk j´ o algoritmust a megoldására. Tegy¨ uk fel, hogy van olyan v´ aros, amelyb˝ol egy másikba nem lehet közvetlen¨ ul eljutni, m´ıg a t¨ obbi v´ arosba, ahov´ a vezet k¨ ozvetlen u ´t, ugyanolyan költséggel mehet az u ¨gynök, és minden várost megl´ atogat pontosan egyszer, majd visszatér a kiindulási városba. Ekkor a feladat a Hamilton-k¨ or létezésére reduk´ al´ odik, hisz ha a v´ arosokat megfeleltetj¨ uk egy gráf cs´ ucsainak, és két cs´ ucs köz¨ ott akkor és csak akkor van él, ha a nekik megfelel˝o városok közt van közvetlen u ´t. Ebben az esetben akkor létezik Hamilton-kör, ha létezik n összköltség˝ u kör´ ut, mely minden várost érint. A létezésére vonatkoz´ oan t¨ obb elégséges feltételt is adtak, néhányat ismertet¨ unk itt. Természetesen mindenhol olyan egyszer˝ u gr´ afr´ ol beszél¨ unk ahol a cs´ ucsok száma nagyobb, mint három azaz n > 3. Megeml´ıt¨ unk egy sz¨ ukséges feltételt is, ez azonban nem elégséges, sajnos sz¨ ukséges és elégséges feltétel nincs. A Hamilton-k¨ or létezésének egy sz¨ ukséges feltétele az alábbi. ´ ıt´ All´ as. Ha a G gr´ afban k pontot t¨ or¨ olve a gráf több mint k komponensre esik, akkor a gráfban nem létezik Hamilton-k¨ or. Hasonl´ oan, ha létezik k olyan pont, amelyeket törölve a gráf több 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ör, de k pontot elhagyva a gráf k-nál több komponensre esik szét. Gondoljuk meg, hogy a Hamilton-kör tartalmazza a gráf minden pontját ´ıgy a feladat ´ at´ırhat´ ou ´gy, hogy egy k¨ orb˝ ol k pontot elhagyva a kör széteshet-e k-nál több komponensre. Erre a v´ alasz nyilv´ anval´ oan nem, hisz könnyen látszik, hogy egy pont elhagyása után még mindig egy komponens¨ unk lesz. Ez ut´ an m´ aris egyenérték˝ u lesz a feladat a Hamilton-´ utra vonatkozó feltétellel, amely ebben a megfogalmaz´ asban triviális, hiszen egy u ´tból egy cs´ ucsot elhagyva az maximum két komponensre esik szét.

5

Vannak természetesen j´ ol haszn´ alható, elégséges feltételek is Hamilton-kör létezésére, lássunk néh´ anyat. T´ etel. [Ore][19] Ha az n pont´ u G gr´ afban b´ armely két nem szomszédos x, y ∈ V (G) pontpárra, teljes¨ ul, hogy d(x) + d(y) ≥ n, akkor a gr´ afban van Hamilton-kör. Másképp, ha az n pont´ u G gráfban bármely két szomszédos x, y ∈ V (G) pontp´ arra, teljes¨ ul, hogy d(x)+d(y) < n, akkor a gráfban van Hamilton-k¨ or. Bizony´ıt´ as. Indirekt tegy¨ uk fel, hogy a gr´ af kielég´ıti a feltételt, de nincsen benne Hamilton-kör. Vegy¨ unk hozz´ aa gr´ afhoz éleket mindaddig, am´ıg m´ ar bárhogyan is vesz¨ unk hozzá u ´jabb élet, lesz a gráfban Hamilton k¨ or. Így kapunk egy G’ gr´ afot, melyre továbbra is teljes¨ ul a feltétel. Tehát biztos van két olyan pont, hogy nem szomszédosak G’-ben. Ha e pontok közé beh´ uznánk egy élt, akkor az ´ıgy kapott gráfban lenne Hamilton-k¨ or. Ez azt jelenti, hogy G’-ben van Hamilton u ´t. Legyen ez P = (v1 , v2 . . . vn ), ahol v1 és vn k¨ ozt nem fut él. Ha v1 szomszédos P valamely vk pontjával, akkor vn nem lehet szomszédos vk−1 -el hiszen akkor (v1 , . . . , vk−1 , vn , vn−1 , . . . vk , v1 ) egy Hamilton-kör 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ás, mert v1 és vn nem szomszédos cs´ ucsok. Az el˝ oz˝ o tétel k¨ ozvetlen¨ ul k¨ ovetkezik a Dirac tételb˝ol, Ore ez alapján alkotta meg ezt az éles´ıtést. T´ etel. [Dirac] [20] Ha egy n pont´ u egyszer˝ u gr´ afban minden pont fokszáma legalább Hamilton-k¨ or.

n 2

Bizony´ıt´ as. Ez k¨ ovetkezik az Ore tételb˝ ol, hiszen ha minden pont foka legalább tétel feltétele.

akkor a gráfban biztosan van

n 2,

akkor triviálisan teljes¨ ul a

Tov´ abbi elégséges feltételek is ismertek Hamilton-kör létezésére, többek között magyar eredmény is van ezzel kapcsolatban, amit P´ osa Lajos publikált [21] 1962-ben. Emellett megnézz¨ uk még Chv´ atal [22] tételét is, melynek lényege az, hogy ha elég sok éle van egy gráfnak akkor van benne Hamilton k¨ or. T´ etel. [P´ osa] Jel¨ olj¨ uk G pontjainak foksz´ amait nagyság szerint növekv˝o sorrendben d1 ≤ d2 ≤ ... ≤ dn –nel. Ha minden k < n2 -re dk ≥ k + 1, akkor G-ben van Hamilton-kör. T´ etel. [Chv´ atal] Az el˝ oz˝ o jel¨ olésekkel, 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ása A probléma megold´ asa nem egy egyszer˝ u feladat, bár kézenfekv˝o, hogy minden Hamilton-kört megkeres¨ unk és kiv´ alasztjuk az optim´ alis utat, ez azonban nagyobb gráfoknál szinte lehetetlen. Ugyanis egy n pont´ u gr´ afn´ al (n−1)! lehet˝ oséget kellene kipróbálnunk. Ha szám´ıtógép¨ unk 1000000 Hamilton2 k¨ ort tud megtal´ alni m´ asodpercenként, akkor is 15 városra már több mint egy napba telne megtal´ alni az optim´ alis eredményt, m´ıg 20 v´ arosra több mint 20 millió évbe telne megtalálni a megoldást. Így teh´ at a ’brute force’ megold´ as nem célra vezet˝o. B´ ar 1962-ben Bellman [23], Held és Karp [24] kitalált egy algoritmust, ami redukálta a ’brute force’ elj´ ar´ as id˝ oigényét, de még az is csak O(n2 2n ) id˝oigény˝ u, ez azt jelenti, hogy 50 város esetén már ez is t´ uls´ agosan id˝ oigényes, nem haszn´ alható. De vajon van-e olyan algoritmus, amely ésszer˝ u id˝oben meg tudja oldani a problém´ at? Ehhez arra lenne sz¨ ukség¨ unk, hogy az eljárás polinomiális id˝oben lecsengjen. Azonban sajnos a feladat NP nehéz.

7

3.

Bonyolults´ agelm´ elet

Hogy megérts¨ uk az NP nehéz fogalom defin´ıcióját, el˝oször meg kell érten¨ unk a Turing-gép fogalm´ at. A Turing-gépet (Turing Machine - TM) Alan Turing angol matematikus ismertette el˝oször 1936-ban megjelent cikkében [25].

3.1. A determinisztikus Turing-gép A gép egy olyan matematikai modell, amely egy (vagy akár több) mindkét irányban végtelen 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 és minden mez˝o egy véges Σ abécéb˝ ´ ol tartalmazhat jelet. Van egy speciális 0 ∗0 jel, ami az u ¨res mez˝ot jelöli és véges 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ó-olvasó fej, mely a szalag egy mez˝ojét tudja leolvasni, majd fel¨ ul´ırni azt és esetleg egyet jobbra vagy balra lépni. A gép emellett egy k¨ ozponti egységet használ, amelynek lehetséges állapotai egy véges Γ halmaz elemei. A legfontosabb ´ allapotai a Start és két leállási állapot az ELF(elfogad) és az ELUT (elutas´ıt´ as). Indul´ askor mindig a START ´ allapotból kezd¨ unk, a fej(ek), szalag(ok) kezd˝omez˝ojén (0.-ik mez˝ on) van(nak). Az egyszer˝ uség kedvéért tegy¨ uk fel, hogy egy szalag van. A fej minden lépésben leolvassa a jelet, majd ez alapj´ an a k¨ ozponti egység a következ˝oket csinálhatja: ´ • Allapotot v´ alt • A fejnek utas´ıt´ ast ad, hogy ´ırjon • A fejnek utas´ıt´ ast ad, hogy tov´ abblépjen A gép akkor ´ all le, ha a k¨ ozponti egység ELF vagy ELUT állapotba ker¨ ul. A Turing-gépet matematikailag a k¨ ovetkez˝oképpen ´ırhatjuk le: T = hk, Σ, Γ, α, β, γi, ahol k pozit´ıv egész szám a szalagok száma, Σ és Γ a fent eml´ıtett véges halmazok, ∗ ∈ Σ, ST ART, ELF, ELU T ∈ Γ és

γ:

α:

Γ × Σk → Γ

β:

Γ × Σk → Σk

Γ × Σk → {−1, 0, 1}

tetsz˝ oleges leképezések. α adja meg az u ´j állapotot, β a szalagokra ´ırt jeleket, γ a fej lépéseit. AΣ´ abécét r¨ ogz´ıtettnek vessz¨ uk és feltessz¨ uk, hogy legalább három jelb˝ol áll, tartalmazza a ’*’-ot és mondjuk 0-t és 1-et (a legt¨ obb esetben elegend˝o erre a két jelre szor´ıtkozni). Egy Turing-gép bemenetén az induláskor a szalagon lév˝o szavakat értj¨ uk. Ezek a szavak, mindig ´ a kezd˝ omez˝ ot˝ ol kezdve van a szalagra ´ırva. Erdemes föltenni, hogy a szavak a 0 ∗0 jelet nem tartalmaznak (K¨ ul¨ onben nem lehetne tudni, hogy hol van a bemenet vége). Az ábécét a 0 ∗0 nélk¨ ul Σ0 -lal jel¨ olj¨ uk. Feltessz¨ uk azt is, hogy a Turing-gép az egész bemenetét elolvassa m˝ uködése során. A gép kimenete a meg´ all´ askor a szalagokon lev˝o szavakból álló rendezett sor.

8

´ ıt´ All´ as Minden t¨ obb szalagos (k ≥ 2) S Turing-géphez létezik olyan egy szalagos T Turing-gép, amely S-et p´ otolja. Ez u ´gy néz ki, hogy minden x szóra (x *-ot nem tartalmaz), S csak abban az esetben ´ all meg véges sok lépésben x-en, ha T megáll és megálláskor S utolsó szalagjára ugyanaz lesz ´ırva, mint T szalagj´ ara. Tov´ abb´ a, ha S n lépést tesz, akkor T O(n2 ) lépést fog tenni. Defin´ıci´ o. Egy T Turing-gép eld¨ onti az L nyelvet, ha minden inputra leáll véges sok lépésben és egy x inputra pontosan akkor ´ all meg ELF ´ allapotban, ha x ∈ L. Egy nyelv akkor lesz algoritmikusan eldönthet˝o, hogyha van olyan Turing-gép, ami eldönti ˝ot.

3.2. A nemdeterminisztikus Turing-gép A determinisztikus és nemdeterminisztikus Turing-gép közt a k¨ ulönbség annyi, hogy a nemdeterminisztikus Turing-gép k¨ ozponti egységének állapota és a leolvasott jelek alapján több lehetséges lépést tehet. Form´ alisan, T = hk, Σ, Γ, α, β, γi-ben minden változatlan, kivéve α, β, γ :

γ⊆

α⊆

Γ × Σk × Γ

β⊆

Γ × Σk × Σ k

Γ × Σk × {−1, 0, 1}k

A nemdeterminisztikus Turing-gépekkel nem szeretnénk semmilyen valódi számoló- eszközt sem modellezni, ezek a gépek a feladatok kit˝ uzésének eszközei. A nemdeterminisztikus Turing-gép egy legális számolásán a lépések egy sorozatát értj¨ uk, ahol minden egyes lépésben (mint a determinisztikus Turing-gépnél) a központi egység u ´j állapotba ker¨ ul, a fej u ´j jeleket ´ır és esetleg lép egyet jobbra vagy balra. A gép egy szituációban többféle lépést tehet, ezeknek nincs ismert eloszl´ asuk, azaz a számolásnak nincs várható értéke. Most pedig a Turing-gép seg´ıtségével definiáljuk a P és NP osztályt. Defin´ıci´ o. A P azoknak a nyelveknek az oszt´ alya, amelyekhez van polinomid˝obeli determinisztikus Turing-gép, m´ıg az NP pedig azoké, amelyekhez van polinomid˝obeli nemdeterminisztikus Turing-gép. Defin´ıci´ o. NP oszt´ aly: egy L nyelv az NP osztálybeli, ha ∀x ∈ L-re ∃ olyan y, hogy az polinom hossz´ u és polinomi´ alis id˝ oben ellen˝ orizhet˝ o bizony´ıték. Azaz, ha L-hez létezik polinomi´ alis idej˝ u E ellen˝orz˝o Turing-gép és c konstans, hogy: Ha x ∈ L, akkor ∃y, hogy |y| ≤ |x|c és E az (x, y) párt 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étel. 9

Ha a tan´ ar megmondja nek¨ unk, hogy G-ben van Hamilton-kör, és meg is mutatja, melyik kör az, akkor be tudom bizony´ıtani, hogy ebben a gráfban van Hamilton-kör. Azaz a Hamilton kör létezésére a tan´ u a Hamilton-k¨ or. Ha azonban nincs a gr´ afban Hamilton-kör, akkor nem tudunk jobbat, minthogy minden egyes körr˝ ol megmutatjuk, hogy az nem Hamilton-kör. Ezt viszont egy nagyobb gráf esetén nagyon id˝oigényes. Az olyan eld¨ ontési problém´ ak oszt´ alyát, amelyeknél az igenl˝o válasz esetén a tanár biztosan tud olyan seg´ıtséget adni, amellyel polinom id˝oben be tudjuk bizony´ıtani, hogy a válasz igen, NP-nek nevezz¨ uk. Pontosabban, egy eld¨ ontési probléma akkor NP-beli, ha minden olyan I inputhoz, melyre igenl˝ oa v´ alasz, létezik egy olyan, T ”tan´ u”,mely f¨ ugg I-t˝ol és T hossza fel¨ ulr˝ol becs¨ ulhet˝o I hosszának egy polinomj´ aval, m´ asrészt I és T ismeretében polinom id˝oben ellen˝orizhet˝o, az igenl˝o válasz. Természetesen vannak olyan problémák is, amelyeknél a nemleges választ tudjuk polinom id˝oben bebizony´ıtani, ha seg´ıt a tan´ ar. Az ilyen problémák osztálya a co-NP osztály. Egy problém´ at NP-nehéznek nevez¨ unk, ha minden NP-beli probléma visszavezethet˝o rá. Ha ez a probléma eleme NP-nek, akkor NP-teljesnek h´ıvjuk. Ha egy NP-teljes problém´ at meg tudnánk oldani polinom id˝oben, akkor minden NP-beli problém´ ara lenne polinom idej˝ u megold´ as. T´ etel (Cook). [26] Létezik NP-teljes nyelv. Az NP-teljesség bizony´ıt´ ast a 70-es évek elején Stephen Cook és Leonid Levin egymástól f¨ uggetlen¨ ul, nagyj´ ab´ ol egy id˝ oben adta. A bizony´ıt´ asban szerepl˝ o nyelv bizonyos logikai formulákról szól. Kés˝obb aztán az NP-teljes nyelvek sz´ ama rohamosan n˝ ott, a 70-es évek végére már egy egész könyvet megtöltöttek vel¨ uk. Ha már van legal´ abb egy NP-teljes nyelv¨ unk, akkor a további nyelvek NP-teljességének bizony´ıtása a következ˝ o séma szerint kész´ı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án kés˝obb siker¨ ult belátni, hogy a Hamilton-k¨ or keresése NP-teljes. ´ ıt´ All´ as P ⊆ N P és N P ⊆ co-N P A sz´ am´ıt´ astudom´ any egyik legfontosabb (és legnépszer˝ ubb) nyitott kérdése, hogy P és NP megegyezike vagy sem. Ha P ⊂ NP val´ odi tartalmaz´ as, akkor ez azt jelentené, hogy vannak olyan kérdések, amikre van polinom hossz´ u bizony´ıték, de ezt nem lehet polinom id˝oben megtalálni. Vagyis egy igenl˝o válasz ellen˝ orzése algoritmikusan lehet lényegesen egyszer˝ ubb, mint egy igenl˝o válasz megtalálása. Ha egy L nyelvr˝ ol megmutatjuk, hogy NP-teljes, akkor abból következik, hogy L csak akkor lehet P-ben, ha P=NP. Mivel a TSP NP-neh´ ez ´ıgy sz¨ ukség¨ unk van valamiféle becslésre az optimális utat illet˝oen. Ehhez most két 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ényegében egy minim´ alis s´ uly´ u fesz´ıt˝ofa. Ezt az als´ o korl´ atot a k¨ ovetkez˝ oképpen áll´ıtjuk el˝o egy adott (V, d) gráfra, ahol d : V × V → R. Kiv´ alasztunk egy cs´ ucsot véletlenszer˝ uen a gráfból, legyen ez v0 ∈ V ezt a pontot ideiglenesen kiszedj¨ uk a gr´ afb´ ol, majd ebben a módos´ıtott gráfban keres¨ unk egy minimális s´ uly´ u fesz´ıt˝o fát. Legyen r a minim´ alis fesz´ıt˝ o fa (R∗ ) hossza a (V − v0 , d) gráfon. Legyen s a két legolcs´ obb él ¨ 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ó korlátot kapjunk a minimális fesz´ıt˝ofa hosszához hozzáadjuk a két legolcs´ obb él ¨ osszegét. t=r+s Megold´ asul pedig egy olyan t értéket kapunk amelyre igaz, hogy l(T ) ≥ t minden T TSP kör´ utra. ´ ıt´ All´ as Az 1-fa algoritmus val´ oban als´ o korl´ atot eredményez. Bizony´ıt´ as. Minden T TSP k¨ or´ utnak haszn´ alnia kell két élet, e-t és f -et amely illeszkedik v0 -ra. Ezt a két élet és v0 -t elt´ avol´ıtva T -b˝ ol egy minim´ alis fesz´ıt˝ofát (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ális kör´ ut hossza alatt. A most következ˝o alsó korl´ at sokkal pontosabb becslést ad ennél. 4.1.2. Held-Karp als´ o korl´ at Az al´ abbi ´ abra [28] seg´ıt megérteni a problémát. Bal oldalt az optimális kör´ ut van kiemelve, középen az el˝ oz˝ o jel¨ olések szerint az R∗ ehhez hozzávéve a v0 -hoz tartozó két minimális hossz´ uság´ u élet, amely ´ıgy null´ at ad becslés¨ ul. Ez nyilv´ an nem egy jó becslés.

Az ¨ otlet ennek megold´ as´ ara a k¨ ovetkez˝o: Adjunk hozzá az u-ból kiinduló élek s´ ulyához 10-et 11

(Jobb széls˝ o ´ abra). Minden k¨ or´ ut pontosan kett˝ot használ ezekb˝ol az élekb˝ol, azaz minden kör´ ut hossza 20-szal fog n˝ oni. Speci´ alisan, most az lOP T = 30 ez az optimális körutunk hossza a módos´ıtott gr´ afban. M´ asrészt az 1-fa als´ o korl´ at által meghatározott t most meg fog egyezni lO P T -al. Amikor egy u cs´ ucshoz hozz´ arendel¨ unk egy ku számot, ezt a számot levonjuk minden u-ból indul´ o élb˝ ol. A jobb oldali képen ku = −10, minden u-hoz csatlakozó élb˝ol kivontam ezt a számot. Majd hasonl´ oan minden egyes u ∈ V − v0 -hoz hozzárendel¨ unk egy ilyen ku -t. Ezután kész´ıt¨ unk egy minim´ alis s´ uly´ u fesz´ıt˝ of´ at, Rk − t a (V − v0 , d) gráfon. P A k¨ ovetkez˝ o pedig m´ ar egy j´ o als´ o korlát lesz a körutunkra: l(Rk ) + 2 u∈V −v0 ku Ezt nevezik Held-Karp als´ o korl´ atnak. Ehhez kell még, hogy olyan ku -kat találjunk, amivel a korlát a lehet˝o legnagyobb lesz. Nem egyszer˝ u feladat megtal´ alni minden egyes cs´ ucshoz az ideális ku -t, de ezzel szakdolgozatomban nem foglalkozom.

4.2. Fels˝ o korl´ at Az egyértelm˝ u, hogy b´ armilyen Hamilton-kört találunk, az fels˝o korlátja lesz a feladatnak. A ”legk¨ ozelebbi szomszéd” algoritmus (Rosenkrantz, Stearns és Philip M. Lewis 1977 [29]) az els˝ o olyan algoritmus, amellyel a TSP megoldását határozták meg. A kulcsa az egésznek az, hogy moh´ o m´ odon a legk¨ ozelebbi v´ arost l´ atogatjuk mindig. Gyorsan található vele egy bejárás, futási ideje O(n2 ), de ´ altal´ aban az nem optim´ alis. Az algoritmus a k¨ ovetkez˝ oképpen ép¨ ul fel: Kiv´ alasztunk egy tetsz˝ oleges v´ arost, megkeress¨ uk a legközelebbi még nem látogatott szomszédj´ at, és oda megy¨ unk. Ismételj¨ uk ezt a lépést mindaddig, am´ıg van még meg nem látogatott város majd térj¨ unk vissza a kiindul´ asi v´ arosba. El˝ ofordulhat, hogy létezik a gr´ afban Hamilton kör, de azt az algoritmusunk nem találja meg. Az algoritmus egy m´ odos´ıt´ asa még, hogy minden cs´ ucsot kipróbálunk mint kezd˝opont és ezek k¨ oz¨ ul v´ alasztjuk ki a legr¨ ovidebbet.

12

5. Approxim´ aci´ ok Miut´ an a TSP problém´ ara nem tudunk olyan pontos megoldást adni, ami polinomiális id˝oben végez, ezért k¨ ul¨ onb¨ oz˝ o algoritmusokkal pr´ obálunk optimumhoz közeli eredményt elérni. Rengeteg ilyen algoritmus létezik, szakdolgozatomban csak néhány jelent˝osebb algoritmussal ismerked¨ unk meg. A k¨ ovetkez˝ o approxim´ ació ismertetéséhez, az alábbi defin´ıciókra lesz sz¨ ukség¨ unk. Defin´ıci´ o. [Euler-k¨ or] A G = (E, ϕ, V ) gr´ af L = v0 e1 v1 e2 v2 ...vn−1 en vn bejárását (ϕ(e1 ) = (v0 , v1 ), ϕ(e2 ) = (v1 , v2 ), ..., ϕ(en ) = (vn−1 , vn )) Euler-s´ et´ anak nevezz¨ uk, ha E minden élét pontosan egyszer tartalmazza. S z´ art Euler-sét´ anak vagy Eluler-k¨ ornek mondjuk, ha v0 = vn , egyébként pedig ha v0 6= vn , akkor L-et ny´ılt Euler-sét´ anak h´ıvjuk. ´ ıt´ All´ as Ha egy gr´ af minden cs´ ucs´ anak p´ aros a fokszáma, akkor létezik benne Euler-kör. Defin´ıci´ o. [Metrikus TSP] A gr´ afunk éleinek a s´ uly´ ara teljes¨ ul a háromszög egyenl˝otlenség. c(u, v) + c(v, w) ≥ c(u, w) ∀u, v, w ∈ V Legyen G(V, E) egy teljes gr´ af és c egy s´ ulyf¨ uggvény az élekre, melyre teljes¨ ul a háromszög egyenl˝ otlenség. Azaz tényleges s´ıkbeli pontoknak feleltethet˝o meg V , és a között¨ uk lév˝o távolság lesz a c f¨ uggvény az élekre. Az approxim´ aci´ os algoritmus amivel folalkozni fogunk a minimális s´ uly´ u fesz´ıt˝ofa azon tulajdonság´ at haszn´ alja fel, hogy az egy természetes alsó korlátja a TSP-nek. Az algoritmusról belátjuk, hogy 2-approxim´ aci´ os azaz, hogy az algoritmus által kapott kör´ ut legrosszabb esetben az optimális kör´ ut hossz´ anak dupl´ aja. Az algoritmus k¨ ovetkez˝ oképpen néz ki: • Keress¨ unk G gr´ afunkban egy minimális fesz´ıt˝o fát. Legyen ez T . Tudjuk, hogy c(T ) ≤ OP TT SP • Dupl´ azzuk meg T éleit. • Az ´ıgy létrehozott G0 gr´ afban keres¨ unk Euler-kört. Biztos, hogy találni fogunk benne, hisz minden cs´ ucs foka p´ aros lesz módos´ıtásunk miatt. • Ezut´ an j´ arjuk be ezt a k¨ ort és megjegyezz¨ uk a cs´ ucsok sorrendjét, majd ebb˝ol alkotjuk meg a Hamilton-k¨ ort a k¨ ovetkez˝ oképpen: • Legyen a cs´ ucsok sorrendje a következ˝o (p1 , p2 , ...pN ). Induljunk a p1 pontból és látogassuk meg a k¨ ovetkez˝ o pontot p2 -t és ´ıgy tovább.

13

• Ezt addig ismételj¨ uk, am´ıg olyan ponthoz nem jutunk, ahonnan már csak meglátogatott cs´ ucs érhet˝ o el. Ezeket az éleket kell kisz˝ urn¨ unk, amik ilyen cs´ ucsok között mennek. Tegy¨ uk fel, hogy p1 , p2 , . . . pn k¨ ul¨ onb¨ oz˝ o cs´ ucsok, de pn -b˝ol már csak olyan cs´ ucsba tudunk menni, amit m´ ar l´ atogattunk. Ilyenkor megkeress¨ uk a sorrendben következ˝o meg nem látogatott cs´ ucsot, pn+1 -et ha van, ha nincs akkor p1 –et és a pn , pn−1 , . . . pn+1 élsorozatot lecserélj¨ uk a (pn , pn+1 ) élre. • A h´ aromsz¨ og egyenl˝ otlenség miatt a kör¨ unk hossza nem növekedett az ilyen fajta csere által. • Ezt ismételve vég¨ ul egy Hamilton-kört kapunk, amely költsége maximum kétszerese 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árásnak a legm˝ uveletigényesebb része a fesz´ıt˝ ofa megkeresése, amely Prim [30] algoritmussal végezve O(n2 ) futási id˝ovel b´ır. Itt használhat´ o ak´ ar Boruvka [31] algoritmusa is.

5.1. Christofides algoritmusa Ez egy olyan algoritmus, amellyel közel´ıt˝o megoldásokat találhatunk az utazó u ¨gynök problém´ aj´ ara, olyan esetekben, amikor a t´ avolságok metrikus teret alkotnak (szimmetrikusak és teljes¨ ul a h´ aromsz¨ og egyenl˝ otlenség). Ez az algoritmus garantálja, hogy megoldásai az optimális megold´ as hossz´ us´ ag´ anak maximum 23 szerese. Az algoritmust Nicos Christofides-r˝ol nevezték 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ább az alábbi módon: 1. Keress¨ unk egy minim´ alis fesz´ıt˝ ofát G-ben. Legyen ez itt is T . 2. Legyen V 0 egy részhalmaza V-nek mely a T páratlan fok´ u cs´ ucsait tartalmazza. Azt tudjuk, hogy p´ aros sok ilyen cs´ ucs van. 3. Ebb˝ ol az k¨ ovetkezik, hogy létezik V 0 felett minimális s´ uly´ u teljes páros´ıtás. Legyen ez M . 4. (V, T ∪ M ) egy Euler gr´ af, minden cs´ ucs fokszáma páros, azaz van benne Euler-kör. 5. Ebben a gr´ afban egy Euler-k¨ ort keresve és az el˝oz˝o eljárást alkalmazva kapunk vég¨ 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átnunk ehhez: • c(T ) ≤ OP TT SP • c(M ) ≤ 12 OP TT SP • c(H) ≤ c(T ∪ M ) Az els˝ o pont egyértelm˝ u, a minim´ alis s´ uly´ u fesz´ıt˝ofa egy alsó korlát lesz az optimumra. A harmadik pont is k¨ onnyen l´ atszik, hisz következik a háromszög-egyenl˝otlenségb˝ol. A m´ asodik pont kicsit ¨ osszetettebb már. Tekints¨ unk egy optimális Hamilton-kört. Ha a körnek csak azon cs´ ucsait vessz¨ uk, amik elemei V’-nek és az ezek közti éleket nézz¨ uk, akkor egy olyan k¨ ort kapunk, amely hossza nem nagyobb az optimálisnál. Nevezz¨ uk ezt a kört CV 0 -nek. Tov´ abb´ a, mivel |V 0 | p´ aros elemsz´ am´ u ´ıgy a kör két páros´ıtás diszjunkt uniója lesz, M1 és M2 -é. 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én c(M ) ≤

1 OP TT SP 2

Ezzel bel´ attuk, hogy Christofields algoritmusa valóban

15

3 2

közel´ıt˝o algoritmus.

´ ep´ıt˝ 6. Ut´ o algoritmusok Legyen G(V, E) egy n cs´ ucs´ u gr´ af és c egy s´ ulyf¨ uggvény az élekre.

6.1. Mohó algoritmus A Greedy (moh´ o) algoritmus egy olyan problémamegoldó algoritmus, amely helyi optimumokat haszn´ alva pr´ ob´ al glob´ alis optimumot találni. Ez itt a TSP-nél azt jelenti, hogy minden városb´ ol a hozz´ a legk¨ ozelebbi, addig még nem látogatott városba fog utazni az u ¨gynök. Az algoritmus m˝ uk¨ odése: Rendezz¨ uk az éleket s´ uly szerint majd Válasszuk ki a legrövidebb élet, ami még nem szerepelt és adjuk hozz´ a a k¨ or¨ unkh¨ oz, ha nem hoz létre n élnél kevesebb˝ol álló kört vagy nem növeli valamelyik cs´ ucs fok´ at kett˝ onél t¨ obbre. Ismételj¨ uk ezt am´ıg nem lesz egy n élb˝ol álló kör¨ unk. Így vég¨ ul egy Hamilton-k¨ ort kapunk. Ez az eljárás nem t´ ul hatékony, gyakran nagyon eltér az optimumt´ ol.

6.2. Boruvka algoritmus Az algoritmust el˝ osz¨ or Otakar Bor˚ uvka tette közzé 1926-ban [31], villamosenergia-hálózat konstru´ al´ as´ ahoz. Az algoritmus minim´ alis s´ uly´ u fesz´ıt˝ofát keres O(|E| ∗ log|V |) futási id˝ovel, a concorde TSP megold´ o program is felhaszn´ alja a dupla fesz´ıt˝ofás módszernél. Az algoritmus u ´gy kezd˝ odik, hogy minden cs´ ucsot megvizsgálunk és ez alapján hozzáadjuk a legolcs´ obb élet, ami két cs´ ucs k¨ ozt fut. Ezután ugyanezt ismételj¨ uk tekintet nélk¨ ul a már hozzáadott élekre. Ezt addig folytatjuk , am´ıg az ´ıgy létrejöv˝o él csoportok össze nem állnak egy minden cs´ ucsot lefed˝ o f´ aba. Pszeudok´ od: Input: Egy ¨ osszef¨ ugg˝ o G gr´ af, c s´ ulyf¨ uggvénnyel az élekre. Legyen T egy erd˝o, amely az elején egy cs´ ucs´ u f´ akb´ ol ´ all, azaz a gr´ af minden cs´ ucsa egy k¨ ulön 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é tartó élet és adjuk hozzá S-hez Adjuk a legolcs´ obb élet S-b˝ ol T -be Vonjuk ¨ ossze az élek ´ altal ¨ osszek¨ ot¨ ott fákat, hogy nagyobb komponenseket alkossanak Output: T egy minim´ alis s´ uly´ u fesz´ıt˝ofa.

16

6.3. Besz´ ur´ asos algoritmusok Lényeg¨ uk, hogy egy kiv´ alasztott élb˝ ol kiindulva ahhoz hozzávesz¨ unk egy pontot a módszert˝ol f¨ ugg˝ oen és az ´ıgy kapott k¨ or¨ unkbe sz´ urunk be ezután valamilyen szabály szerint pontokat, ´ıgy b˝ov´ıtve a k¨ ort. Amire figyelni kell az az, hogy minimális legyen a költségnövekedés (c(u, v) a kör¨ unk egy élének a k¨ oltsége). min{c(u, w) + c(v, w) − c(u, v)}; u, v, w ∈ V Az elj´ ar´ asnak akkor lesz vége, ha minden pontot besz´ urtunk már. Az elj´ ar´ as egyes fajt´ ai: • A legk¨ ozelebbi besz´ ur´ asa - O(n2 ) Válasszuk ki a legrövidebb élet. Keress¨ uk meg a végpontjaihoz, kés˝obb a kör pontjaihoz a legközelebbi pontot és sz´ urjuk be. Figyelj¨ unk a minim´ alis k¨ oltségnövekedésre. min{c(u, w) + c(v, w) − c(u, v)}; u, v, w ∈ V Ismételj¨ uk, am´ıg minden pontot be nem sz´ urtunk. • A legt´ avolabbi besz´ ur´ asa - O(n2 ) Az el˝oz˝ohöz hasonló, de a leghosszabb élet keress¨ uk meg, majd a legk¨ ozelebbi helyett legtávolabbi pontot sz´ urunk be mindig. ¨ enyes’ vagy véletlenszer˝ • ’Onk´ u besz´ urás - O(n2 ) A pontokat véletlenszer˝ uen sz´ urjuk be. A legk¨ ozelebbi cs´ ucs besz´ ur´ asa megfeleltethet˝o Prim minimális fesz´ıt˝ofát keres˝o algoritmusával. Egy v´ aros besz´ ur´ asa megfelel egy él hozzáadásának a minimális fesz´ıt˝ofához. Ha teljes¨ ul a háromsz¨ og egyenl˝ otlenség, akkor a minim´ alis fesz´ıt˝ofával egy fels˝o korlátot adhatunk a TSP-re mint azt láttuk. Így ez a m´ odszer az optimum dupl´ aj´ at adja legrosszabb esetben. A legt´ avolabbi besz´ ur´ asa algoritmus meglep˝o módon gyakran jobb, mint a legközelebbi besz´ ur´ asa, osszekapcsolja a messzi v´ ¨ arosokat a t´ urában, hogy létrehozzon egy vázlatot az egész t´ uráról. urának. Az algoritmus ´ altal gener´ alt k¨ orsét´ ak 32 –szorosai az optimális t´

17

7. Jav´ıt´ o algoritmusok Ha létrehoztunk m´ ar egy t´ ur´ at valamelyik heurisztikánkkal, akkor az alábbi algoritmusokkal lehet jav´ıtani a m´ ar meglév˝ o megold´ ast. Számos módja van ennek, de a legelterjedtebbek a 2-opt és 3-opt lok´ alis keresések, emellett ott van például a tabu keresés, amely módos´ıtva felhasználja a 2-opt és 3-opt lépéseit. Ezeken k´ıv¨ ul k¨ ul¨ on kiemelném 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álta ki Croes 1958-ban [33]. Mivel ez egy jav´ıtó algoritmus, ezért egy meglév˝ o utat fejleszt. Az algoritmus a k¨ ovetkez˝ on alapszik: • Vesz két élet a k¨ or´ utb´ ol. Legyen ezek s´ ulya c(v, w) és c(u, x)

A 2-opt egy lépése ¨ • Osszek¨ oti a két élhez tartoz´ o négy cs´ ucsot (nem lehet a két élnek közös cs´ ucsa) u ´gy, hogy u ´j k¨ orutat kapjunk. Ezt csak egyféleképpen tehetj¨ uk meg u ´gy, hogy továbbra is körutunk legyen. • Az u ´j élek s´ ulyai legyenek c(v,u) és c(w,x). Ha ezek kisebbek, mint c(v,w)és c(u,x) akkor az eredeti éleket lecserélj¨ uk a kisebb o¨sszs´ uly´ u élekre. Form´ alisan: c(v, w) + c(u, x) > c(v, u) + c(w, x) ⇒ cserél¨ unk éleket Az algoritmus akkor áll le, ha m´ ar nem tudunk cserét végrehajtani. Ekkor a k¨ orutunkat 2-optim´ alisnak nevezz¨ uk. Az algoritmus futási ideje: O(n2 ).

18

7.2. 3-opt Az elj´ ar´ as Lin nevéhez f˝ uz¨ odik, aki 1965-ben publikálta algoritmusát.[34] Hasonl´ oan m˝ uk¨ odik az el˝ oz˝ oh¨ oz, de itt 2 él helyett 3-at választunk ki, és itt kétféleképpen lehet osszek¨ ¨ otni ezen élekhez tartoz´ o cs´ ucsokat u ´gy, hogy u ´j körutat kapjunk. Itt lehet két élnek köz¨ os cs´ ucsa is ak´ ar. Tekinthet¨ unk u ´gy is erre, mint kett˝o vagy három 2-opt lépésre. Az algoritmusnak akkor van vége, ha m´ ar nem tudunk cserélni. Ekkor a körutunkat 3-optimálisnak nevezz¨ uk. Alkalmazhat´ o ez h´ aromn´ al nagyobb számokra is. Az érték lehet négy, öt, de akár nagyobb is. Nagyobb sz´ amokra nem mindig olyan hatékony az eljárás.

7.3. k-opt Egy k¨ or´ ut k-optim´ alis, ha nem hajtható végre k él cseréje u ´gy, hogy jobb eredményt kapjunk. Teh´ at egy n v´ arosb´ ol ´ all´ o k¨ or´ ut akkor optimális, ha n-optimális.

7.4. Lin-Kernighan algoritmus Ez egy lok´ alisan optimaliz´ al´ o algoritmus, melyet Shen Lin és Brian Kernighan talált ki 1973-ban [35]. A k-opt egy tov´ abbfejlesztése. Nem fix k van, hanem minden lépésben próbáljuk az optim´ alis k-t megtal´ alni. Ez az elj´ ar´ as felhasználja azt, hogy minden k-opt lépés reprezentálható, mint 2-opt ´ ép´ıti fel ezt a sorozatot, hogy lépésenként növeli k-t és ellen˝orzi minden lépés lépések sorozata. Ugy ut´ an, hogy a csere r¨ ovidebb k¨ or´ uthoz vezet-e. Tekintettel arra, hogy a csere k él között végrehajtható egy tesztsorozatot hajtunk végre annak eld¨ ontése érdekében, hogy k+1 él cseréje lehetséges-e. Ez addig folytatódik, am´ıg a leállási kritérium nem teljes¨ ul. Az algoritmus minden lépésben b˝ov´ıti a létrehozott halmazt, a potenciális cserékkel (k=2-vel kezd). Ezeket a cseréket u ´gy választjuk meg, hogy felhasználva ˝oket a folyamat bármely szakasz´ aban egy u ´j k¨ orutat kapunk. Vég¨ ul ha találunk egy u ´j rövidebb körutat, akkor végrehajtjuk a cserét, azaz egy k¨ orutat konvert´ al a´t egy u ´j, optimálisabb kör´ uttá, majd megáll ha már nem lehet jav´ıtani. Az algoritmus fut´ asi ideje O(n2,2 ). Nézz¨ uk most ezt kicsit részletesebben. Legyen T az aktu´ alis k¨ or´ ut. Az algoritmus minden lépésben megpróbál találni két halmazba éleket, X = {x1 . . . xk } és Y = {y1 . . . yk }, ha T -b˝ol kiszedj¨ uk az X-ben lév˝o éleket és helyette az Y -belieket haszn´ aljuk, akkor az eredmény egy jobb kör´ ut lesz. Ezt nevezz¨ uk k-opt lépésnek. X-et és Y -t elemenként ép´ıtj¨ uk fel, u ´gy hogy az elején mindkét halmaz u ¨res. Az i. lépésben az xi és yi élet adjuk hozz´ a a halmazokhoz. Annak érdekében, hogy az algoritmusunk elég hatékony legyen csak olyan éleket adunk X-hez és Y -hoz, melyek teljes´ıtik a következ˝o oldalakon le´ırt kritériumokat.

19

A szekvenci´ alis cser´ ek krit´ eriuma xi -nek és yi -nek kell k¨ oz¨ os végponttal rendelkeznie, ahogy yi -nek és xi+1 -nek is. Ha t1 jelöli az xi egyik végpontj´ at, azaz xi = (t2i−1 , t2i ), yi = (t2i , t2i+1 ) és xi+1 = (t2i+1 , t2i+2n , i ≥ 1. Innen látszik, hogy a sor (x1 , y1, x2, y2, x3, ..., xk, yk) szomszédos éleket tartalmaz. Sz¨ ukséges, de nem elégséges feltétel, hogy X éleinek lecserélése Y éleire egy t´ urában akkor lesz zárt, ha yk = (t2k , t1 ). A cserét szekvenci´ alisnak nevezz¨ uk, ha le´ırható egy olyan u ´tvonal, amely a törölt és hozzáadott élek k¨ oz¨ ott v´ altakozik. ´ Altal´ aban a t´ ura fejlesztése elérhet˝ o szekvenciális cserével, ha megfelel˝o sorban vessz¨ uk az éleket. Azonban olyan is el˝ ofordulhat, hogy nem tudunk cserét végrehajtani.

A fels˝ o´ abr´ an egy szekvenci´ alis cserét l´ athatunk, m´ıg az als´ on egy olyan esetet, ahol nem tudunk ilyen cserét végrehajtani.

Megval´ os´ıthat´ os´ agi krit´ erium Sz¨ ukséges, hogy ha xi = (t2i−1 , t2i )-t kiválasztjuk, akkor t2i csatlakozzon t1-hez és a csere után egy k¨ orutat kapunk. Ezt i ≥ 3-ra alkalmazzuk és garantálja, hogy a t´ ura zárt lesz, a folyamat bármelyik szakasz´ aban k¨ or´ utt´ a alak´ıthat´ o lesz. Ez a kritérium fontos a fut´ asi id˝ o és a kódolás egyszer˝ us´ıtésének érdekében is.

20

A pozit´ıv nyeres´ eg krit´ eriuma yi -t mindig u ´gy v´ alasztjuk meg a javasolt cserehalmazból, hogy a nyereség (Gi ), pozit´ıv legyen. Legyen gi = c(xi ) − c(yi ) az xi és yi csere nyeresége. Ekkor Gi = g1 + . . . + gi . Ez a le´ all´ asi kritérium fontos szerepet játszik az algoritmus hatékonyságában. Az, hogy minden gi pozit´ıv legyen t´ ul nagy megszor´ıt´ asnak t˝ unik, de nem ez a helyzet. Ha egy számsornak pozit´ıv az osszege, akkor létezik olyan permut´ ¨ aciója a számoknak, hogy minden részösszeg pozit´ıv legyen. Diszjunktivit´ as krit´ eriuma Vég¨ ul kell még az is, hogy X és Y diszjunktak legyenek. Hatékony leállási kritériumot ad és csökkenti a fut´ asi id˝ ot. Az algoritmus l´ ep´ esei: 1. Kezdj¨ unk egy véletlenszer˝ uen választott t´ urával. 2. Legyen i = 1. V´ alasszuk ki t1 -et. 3. V´ alasszuk meg x1 -et, x1 = (t1 , t2 ) eleme T 4. V´ alasszunk mellé egy y1 -et, y1 = (t2 , t3 ) nem eleme T , G1 > 0. Ha nem lehetséges ilyet tal´ alni menj¨ unk a 12. lépésre. 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áció 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étezik Ha yi nem létezik, menj¨ unk az 5. lépésre. 8. Ha van még kipr´ ob´ alatlan alternat´ıva y2 -re akkor legyen i = 2 és menj¨ unk a 7. lépésre. 9. Ha van még kipr´ ob´ alatlan alternat´ıva x2 -re akkor legyen i = 2 és menj¨ unk a 6. lépésre. 10. Ha van még kipr´ ob´ alatlan alternat´ıva y1 -re akkor legyen i = 1 és menj¨ unk a 4. lépésre. 11. Ha van még kipr´ ob´ alatlan alternat´ıva x1 -re akkor legyen i = 1 és menj¨ unk a 3. lépésre. 12. Ha van még kipr´ ob´ alatlan alternat´ıva t1 -re akkor menj¨ unk a 2. lépésre. ´ 13. Alljon meg az algoritmus. (Kezdj¨ uk el egy másik véletlen t´ urával az els˝o lépést˝ol.) 21

Kieg´ esz´ıt´ esek 3. l´ ep´ es x1 -et kétféleképpen v´ alaszthatjuk (a t´ ura egy cs´ ucsa t1 ). 6. l´ ep´ es xi megv´ alaszt´ asa két féleképpen lehetséges, azonban adott yi−1 esetében csak egy amely lehet˝ ové teszi a t´ ura bez´ ar´ as´ at, yi hozzáadásával. A másik választás két diszjunkt kört eredményez. Azonban egy esetben m´ as a helyzet, i = 2-re. 8-12. l´ ep´ es Ezek visszalépéshez vezetnek, de csak akkor, ha nincs javulás az els˝o vagy második szinten. 13. l´ ep´ es Akkor ´ all le, ha m´ ar minden t1 értékre kipróbáltuk az algoritmust és 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ális keresési módszerek hajlamosak lokális optimumba ragadni, ezt a hib´ at k¨ usz¨ ob¨ oli ki a tabu keresés. Ez az algoritmus 2-opt lépéseket használ és megengedi a negat´ıv nyereséget, ha nem tal´ alunk pozit´ıvat. Az alapgondolat az, hogy az algoritmus létrehoz egy tabulistát, amely a tiltott lépéseket ´ırja le. A list´ at minden iter´ aci´ oban fel¨ ul´ırjuk és az aktuális lépés visszalépésének tiltásával b˝ov´ıtj¨ uk, az elavult tilt´ asokat t¨ or¨ olj¨ uk. Az aktu´ alis iterációban nem lehet a lista által tiltott lépést megtenni, ´ ezzel biztos´ıtjuk, hogy nem lép¨ unk vissza az el˝oz˝o megoldásra. Altal´ aban a tabu keres˝o algoritmus a legjobb megold´ ast v´ alasztja a k¨ ornyezetb˝ol, ha az nem az aktuális megoldás illetve nincs tiltva a tabulista ´ altal. Amennyiben a legjobb megoldás az aktuális megoldás -azaz lokális optimumban vagyunk - vagy a legjobb megold´ ast tiltja a tabulista, akkor más kevésbé jó megoldást választ az algoritmus.

22

8. Alkalmaz´ asok Ebben a fejezetben az utaz´ ou ¨gyn¨ ok probléma sokrét˝ u alkalmazását mutatom be. A feladatnak igen szerte´ agaz´ o a felhaszn´ al´ asi k¨ ore, sok való életben el˝oforduló probléma vezethet˝o vissza a TSP-re. Csak, hogy néh´ anyat eml´ıtsek u ´tvonalak optimalizálása, teleszkópok, lézerek, röntgenek irány´ıt´ asa, mikroprocesszorok tesztelése, feladatok u ¨temezése, tapéta hulladékának minimalizálása.

8.1. Klaszterek bejárása TSP-vel El˝ osz¨ or is, vezess¨ uk be a klaszterezett utazó u ¨gynök probléma fogalmát (Clustered Traveling Salesman Problem - CTSP). Ez egy kib˝ov´ıtése a TSP-nek, ahol a városokat parcion´ aljuk klaszterekbe és az u ¨gynök egymás után meglátogatja a klasztereket. Nyilv´ anval´ o, hogy a CTSP megegyezik a a TSP-vel, ha minden klaszter egy elemb˝ol áll. A CTSP-t egy teljes gr´ afon defini´ aljuk, G = (V, E), ahol V = {v1 , ..., vn } a ponthalmaz és E = {(vi , vj ) : vi , vj ∈ V, i 6= j} élhalmaz. Van emellett egy nem negat´ıv éls´ uly cij , (vi , vj ) élre, ez alapján ker¨ ulnek a pontok k egymást kiz´ ar´ o és teljes klaszterekbe, azaz V1 , ..., Vk klaszterek és V = V1 ∪ V2 ∪ ... ∪ Vk u ´gy, hogy Vi ∩ Vj = Ø ∀i, j, i 6= j. A CTSP-t megfeleltethet˝ o egy minimális s´ uly´ u TSP kör´ ut keresésének. A k¨ ovetkez˝ o képpen transzform´ aljuk adatainkat: • V 0 ekvivalens V -vel. • Defini´ aljuk c0ij = cij 0 , ahol vi és vj ugyan abba a klaszterba tartoznak. • Ha vi és vj k¨ ul¨ onb¨ oz˝ o klaszterekbe tartoznak akkor c0ij = cij + M , ahol M egy sz¨ ukségesen nagy konstans, ez itt azt jelenti, hogy M nagyobb a legnagyobb élköltségnél.

CTSP (n=23, k=6) [37] Ez ut´ an a transzform´ aci´ o ut´ an a TSP körutunk mindig végigmegy egy klaszteren, és csak ut´ ana megy ´ at m´ asikra. Az optim´ alis k¨ or´ ut értéke a TSP kör´ ut értéke minusz kM, mivel k db klaszterek k¨ ozti él van. Emiatt az ´ atalak´ıt´ as miatt haszn´ alhatunk a CTSP megoldására TSP-t megoldó programokat. Ilyen j´ ol ismert hatékony program a Concorde. 23

8.2. Concorde A Concorde (2001) egy olyan program, amely a TSP megoldására törekszik, k¨ ulönböz˝o heurisztik´ akkal. Napjainkig az egyik legjobb TSP megoldó program. M˝ uk¨ odése: koordin´ at´ akkal megadott pontok között keresi a legrövidebb utat. A program u ´gy keresi ez optim´ alis utat, hogy b´ armelyik pontból bármelyikbe el lehet jutni. A program gyorsasága a ’branch-and-cut’ és a Chained Lin-Kernighan algoritmusok használatán alapszik. A hatékonys´ ag´ at az is mutatja, hogy mikor Reinelt létrehozta a TSPLIB-et (egy könyvtár, k¨ ulönb¨ oz˝ o forr´ as´ u és t´ıpus´ u TSP feladatok sz´ amára (és kapcsolódó problémák részére)) 1990-ben még 24 esetet tartalmazott melyek nagyj´ ab´ ol 1000 városból álltak. Ez a szám 1995-re 34-re emelkedett az u ´j, kih´ıv´ ast jelent˝ o problém´ ak hozz´ aad´ asával. Kett˝ot ezen problémák köz¨ ul megoldottak pap´ıron, a fennmarad´ o 32 probléma mindegyikét megoldotta a Concorde. Teh´ at a Concorde TSP megold´ ot TSPLIB esetek optimális megoldásainak meghatározására is haszn´ alt´ ak. A legnagyobb ilyen 85.900 v´ arosra volt. A Concorde egy C programnyelven ´ıródott David Applegate, Robert E. Bixby, Vaˇsek Chvátal, és William J. Cook ´ altal és k¨ or¨ ulbel¨ ul 130 000 sorból áll, emellett szabadon felhasználható tudományos célokra. A Concorde t¨ obb kor´ abbi kulcsfontosság´ u TSP kutatásra ép¨ ul, melyek vég¨ ul a projekt létrehoz´ as´ at eredményezték. A Concorde-ot az egyik legkorszer˝ ubb megvalós´ıtásnak nevezik, az egyik legjobb TSP-megoldó program, ami jelenleg elérhet˝ o. 2001-ben a Concorde egy m´ odos´ıtott verziója 5000 Gulden-os d´ıjat nyert a CMG informatikai cégt˝ ol, amiért megoldotta az 1996-os j´ arm˝ uforgalmi problémáját. A feladat az volt, hogy megtalálják a legjobb utakat 4 u ´js´ agos fi´ u sz´ am´ ara, hogy 120 u ¨gyfélnek kihordják az u ´jságokat. A Concorde h´ıvhat´ o k¨ onyvt´ ar t¨ obb mint 700 olyan funkciót tartalmaz, amelyek lehet˝ové teszik a felhaszn´ al´ ok sz´ am´ ara speci´ alis k´ odok létrehozását a TSP szer˝ u problémákhoz. A Concorde t´ amogatja a QSopt line´ aris programozási megoldást és a cplex-et. Hans Mittelmann létrehozott egy NEOS szervert a Concorde-nak, amely lehet˝ové 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 által kész´ıtett körutat • Boruvka: Kisz´ am´ıt egy Boruvka algoritmus által kész´ıtett körutat • Quick Boruvka: Kisz´ am´ıt egy Quick Boruvka algoritmus által kész´ıtett körutat • Nearest Neighbor: Kisz´ am´ıt egy legközelebbi szomszéd algoritmus által kész´ıtett körutat • Random: Kisz´ am´ıt egy véletlen körutat • Lin Kernighan: Kisz´ am´ıt egy Lin-Kernighan algoritmus által kész´ıtett körutat

Olaszorsz´ ag - 16,862 v´ aros és az optim´ alis u ´t [38] A TSP megold´ asa azt jelenti, hogy meg kell találnunk egy abszol´ ut legrövidebb t´ urát és biztosnak kell lenn¨ unk abban, hogy nincs ennél jobb t´ ura. Ennek ellen˝ orzésére a Concorde k¨ ul¨ onböz˝o eljárásokat használ: Geometriai alsó határt ellen˝orzési z´ on´ akkal, t´ ur´ ak elimin´ aci´ oj´ at, v´ ag´ asi s´ıkok módszerét, helyi vágásokat és ’Branch-and-cut’ módszert emellett ellen˝ orzi a sz´ am´ıt´ asok pontosságát. A programot mostan´ aban is akt´ıvan használják, ennek bemutatására szolgál a következ˝o példa.

25

Pok´ emon Go ´ es a TSP ´ minél gyorsabban? Erre egy remek TSP modellt lehet fel´ırni. Szerezd meg h´ at mind? Es A pokémon mesterek szerencséjére a Concorde rengeteg id˝ot spórol nekik, hisz megmondja, hogyan juthatnak el a legr¨ ovidebb u ´ton az o¨sszes Pokémonhoz. Ha a Pokémonok egy ter¨ uleten t¨ obb százan vagy akár több ezren vannak, akkor sz¨ ukség van matematik´ ara, hogy meglelj¨ uk a legjobb utat és lehet˝oleg a lehet˝o legrövidebb id˝o alatt. A Pokemon Go NYC csoport naprakész térképet tart a ritka Pokémonok felfedezéseir˝ol. Az ábr´ an l´ athat´ o az optim´ alis t´ ura 68 ritka pokémonhoz.

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éter. Ez egy kicsit hossz´ u séta egyszerre, de ha valaki csak Manhattan-hez ragaszkodna, akkor ott elegend˝o Pokémont talál egy délutánra. A Concordot sok m´ as ter¨ uleten is használják, csak hogy néhányat eml´ıtsek: A legkézenfekv˝obb alkalmaz´ asa a k¨ ul¨ onb¨ oz˝ o k¨ orutak és t´ ur´ ak tervezése, optimális száll´ıtmányozázi u ´tvonalak meghatároz´ asa. Ezeken k´ıv¨ ul akad még m´ as ter¨ uleteken is alkalmazása. Használják például géntérképezéshez, teleszk´ opok és lézerek ir´ anyt´ as´ ahoz, bolygók kereséséhez, mikrochipek teszteléséhez és k¨ ulönböz˝o veszteségek minimaliz´ al´ as´ ahoz is. 26

8.3. Nyomtatott ´ aramk¨ or¨ ok o ¨sszeszerel´ ese Az alkatrészek elhelyezésének sorba rendezése egy olyan összetett feladat, ami a nyomtatott áramk¨ or¨ ok ¨ osszeszerelésénél el˝ oj¨ on. Am´ıg néh´ any elhelyez˝ o gép sz´ am´ ara minden elhelyezési sor elfogadható, más esetekben néh´ any ilyen sorozat nem megengedett az elhelyez˝o fej formája miatt. Ezekben az esetekben, m´ıg a fej lefelé mozog, hogy egy elhelyezést elvégezzen eközben egy másik már korábban elhelyezett alkatrész megsér¨ ulhet. Egy ilyen minimum összeg˝ u sorrend meghatározásának problém´ aja egy PCTSP (Precedence Constrained Travelling Salesman Problem) megfogalmazásához vezet. Ebben a részben egy megold´ asi m´ odszert vizsgálunk erre a problémára, illetve kivitelezését a nyomtatott ´ aramk¨ or¨ ok (PCB) ¨ osszeszerelési környezetében. A sz´ am´ıt´ ogépek és a numerikusan szabályozott elektronikus alkatrészek elhelyezéséért felel˝os gépek sebességet és precizit´ ast és megb´ızhatóságot biztos´ıtottak a PCB összeszerelési m˝ uveletébe. Ezzel egyetemben azonban k¨ ul¨ onb¨ oz˝ o problémák is felmer¨ ultek, amelyeket hatékonyan meg kell oldani, hogy elérj¨ uk a maxim´ alis hasznos´ıt´ as´ at a gépeknek. A f˝obb problémák pl. az elhelyezési sorrend meghat´ aroz´ asa, az adagol´ o kész¨ ulék konfigurációja, a munkaterhelés kiegyens´ ulyozása és az áramkör¨ ok termelésének u ¨temezése, melyek ´ altalában egymástól f¨ uggetlenek. Ha már a gép az adagoló automat´ aval (mechanizmus ahol az alkatrészt´ıpusokat tárolják) ellátja alkatrészekkel az elhelyez˝o fejet, fontos kérdés az adagol´ o kész¨ ulék konfigurációja, ugyanis közvetlen¨ ul befolyásolja az egym´ ast k¨ ovet˝ o elhelyezések k¨ ozti id˝ ot. Ez a probléma u ´gy ´ırható fel, mint egy lineáris vagy kvadratikus hozz´ arendelési probléma. Ha egy gy´ art´ o t¨ obb gépet telep´ıt, hogy egy PCB-t összerakjon, akkor sz¨ ukségszer˝ u, hogy egyenl˝ oen ossza fel az ¨ osszeszerelési munk´ at, hogy elker¨ ulje az u ¨res járatokat. Az ¨ osszeszerelési munk´ ak kiegyens´ ulyozása mellett ugyancsak fontos meghatározni a gyártási u ¨temtervet, hogy a megfelel˝ o mennyiségben álljon rendelkezésre a termék. A problém´ ak matematikai megfogalmazása, komplexitása és megoldása nagyban f¨ ugg a haszn´ alt gép t´ıpus´ at´ ol és a termelési k¨ or¨ ulményekt˝ol. Mi ezek köz¨ ul az elhelyezési sorrend meghatározás´ aval fogunk f˝ oként foglalkozni, ez arra utal, hogy az adott gép¨ unk milyen sorrendben rakja le az alkatrészeket a PCB-re. Ez sok gép számára egy TSP lenne Csebisev távolsági mértékkel. Azonban a mi eset¨ unkben ez egy kicsit komplikáltabb. Néhány gép esetében ugyanis néhány elhelyezési sorrend k´ art okoz, az elhelyez˝ o fej k´ aros´ıt egy már korában lerakott alkatrészt. Ez nem megengedhet˝ o. Így h´ at annak érdekében, hogy megtaláljuk a megoldást figyelembe kell venni néhány korlátozást és ´ıgy vég¨ ul egy els˝ obbségi sorrend ´ altal megszor´ıtott TSP-hez (PCTSP). Az alkatrész károsodásának problém´ aja ´ altal´ aban sug´ arvezérelt gépeknél fordul el˝o vagy olyan gépeknél ahol a fej a mérete és form´ aja miatt bizonyos esetekben k´ art okozhat.

27

A gép amit t¨ uzetesebben is vizsgálni fogunk a török elektronikai iparban is használt Universal 6346 A t´ıpus´ u sug´ arvezérelt gép. Ennek a gépnek van egy online sorba rendez˝o mechanizmusa (adagol´ o automata), amely a gép m¨ og¨ ott helyezkedik el és 60 féle alkatrészt´ıpust tud tárolni. Az alkatrészeket az adagol´ o fejekkel (DH) elvágja és futószalagra rakja (minden adagoló/sorba rendez˝ o poz´ıci´ ohoz van egy megfelel˝ o DH és az összetartozók megfelel˝oen vannak számozva), ami elviszi az alkatrészeket az elhelyez˝ o fejhez az elhelyezés sorrendjében.

Az elhelyez˝ o fej egy helyben ´ all végig, ´ıgy helyette az elhelyezési pont s´ıkba áll´ıtását a hordozó lap (a fel¨ ulet ahol a PCB-t elhelyezz¨ uk) végzi az x-y s´ıkon f¨ uggetlen egyidej˝ u mozgással. Miután az elhelyezési pont a fej alatt van, a fej lehelyezi a sorban következ˝o alaktrészt.Az eljárás pontosabban: • A hordoz´ o lap a megfelel˝ o x-y koordinátára mozog • A rakod´ ogép el˝ oremegy és alkatrésszel látja el az elhelyez˝o fejet • A k¨ ovetkez˝ o alkatrész a rakod´ ogép elé megy • Az elhelyezési fej lemegy és elfordul, ha sz¨ ukséges • A v´ ag´ asért és r¨ ogz´ıtésért felel˝ os fej felemelkedik (a hordozótábla alatt helyezkedik el) • A nyom´ or´ ud lenyomja az alkatrészt a lapra • Az alkatrészt elv´ agja és r¨ ogz´ıti ez ezért felel˝os fej • Az elhelyez˝ o fej felemelkedik • A v´ ag´ asért és r¨ ogz´ıtésért felel˝ os fej leereszkedik

28

Ezeket a lépéseket hajtjuk végre egymás után, az els˝ot leszám´ıtva a többi lépés f¨ uggetlen a komponens t´ıpus´ at´ ol és az elhelyezés sorrendjét˝ol (az els˝o lépést leszám´ıtva egy ilyen lépéssorozat 0,34 m´ asodpercet vesz igénybe). Az elhelyez˝ o fej mint feljebb eml´ıtettem forog ha sz¨ ukséges és három forgási szöggel tud elhelyezni: 0◦ , +90◦ , −90◦ . A fej akkor fordul el amikor lefelé megy, ´ıgy ez nem vesz plusz id˝ot igénybe. Az alkatrészek horizont´ alisan és vertik´ alisan is elhelyezhet˝oek, emellett lehetnek elektromosan polárisak és apol´ arisak is. A hordoz´ o lap nem forog, szóval ha poláris alkatrészt szeretnénk elhelyezni 180◦ -os elforgat´ assal, akkor az alkatrész kioszt egy második helyet az adagoló automatában ami ford´ıtott polarit´ assal, 0◦ -os elforgat´ assal helyezi el, ha nincs szabad hely akkor a m˝ uveletet manuálisan kell elvégezni. Az ´ altalunk megfigyelt gépnél a probléma az optimális sorrend megtalálására korlátozódik. Azonban figyelni kell a sér¨ ulés veszélyre. Ha egy korábban lerakott elem t´ ul közel van a következ˝o lerakand´ o elemhez, akkor a fej ´ altal megsér¨ ulhet a korábban lerakott elem. Azaz nagyban f¨ ugg a rong´ al´ od´ as veszélye az alkatrészek k¨ ozelségét˝ol.

A k¨ ozelség mellett az alkatrész magassága is fontos, mivel a mi eset¨ unkben az elhelyez˝o fej hátulja egy 45◦ -os ferdes´ık ´ıgy alacsonyabb magasság´ u alkatrészeket nem káros´ıtja, m´ıg magasabbakat már igen. A fej szélességének tudat´ aban, azonban kész´ıthet¨ unk egy becslést a sér¨ ulési ter¨ ulet meghatározás´ ara.

29

Teh´ at, legyen adott egy fix szélesség, emellett a derékszög˝ u ter¨ ulet hosszát (d) meghatározhatjuk az alkatrész magass´ ag´ anak és a sz¨ og kotangensének szorzatával, amit a fej zár be az x-y s´ıkkal. A fels˝ o korl´ at pedig a D-vel kaphat´ o, amely a derékszög˝ u károsodási ter¨ ulet hossza, amir u ´gy kapunk, hogy a fej ferdes´ıkj´ anak a végét levet´ıtj¨ uk a tengelyre. Annak érdekében, hogy elker¨ ulj¨ uk a károsodást két dolgot tehet¨ unk: • elhelyezési sz¨ og v´ altoztat´ as´ aval • elhelyezési sorrend megv´ altoztatásával Így jutunk el vég¨ ul oda, hogy a matematikai modell¨ unk egy els˝obbségi sorrend által megszor´ıtott TSP lesz (PCTSP). Ennek megold´ asa azonban korán sem egyszer˝ u, nem lehet rá zárt formulát adni. A megold´ asi m´ odszer¨ unkh¨ oz ´ıgy h´ at egy kis tr¨ ukköt alkalmazunk. Formalizáljuk a feladatot u ´gy, hogy az alkatrészek sér¨ ulésének problémáját figyelmen k´ıv¨ ul hagyva az elhelyezési problémát egy TSP-vel azonos´ıthatjuk Csebisev t´ avolsági mértékkel. 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ési pontok halmaza S – nem u ¨res részhalmaza N-nek xi,j - 1 ha i el˝ obb van mint j, k¨ ul¨ onben 0 ti,j - id˝ o ami eltelik i és j teljes´ıtése közt t0 - elj´ ar´ as fix ideig tart t1i,j - a hordoz´ o lap mozg´ asi ideje x tengelyen i és j között t2i,j - a hordoz´ o lap mozg´ asi ideje y tengelyen i és j között ti,j = t0 + max(t1i,j , t2i,j ) Ezt megoldjuk, majd ezut´ an elt´ avol´ıtjuk a károsodási tényez˝oket a meglév˝o TSP körutunkból.

30

8.3.1. A probl´ ema megold´ asa A TSP megold´ as´ ara a konvex burok algoritmust és az Or-Opt algoritmust használjuk. Konvex burok (Convex Hull) algoritmus • Keress¨ uk meg a pontok konvex burkát, csináljunk ebb˝ol egy kört. • Minden k¨ or¨ on k´ıv¨ uli pontot sz´ urjunk be, a legközelebbi besz´ urás módszerével. • Ismételj¨ uk az elj´ ar´ ast, m´ıg minden pont be nem lesz sz´ urva. Majd az ´ıgy kapott megold´ ast fejlesztj¨ uk tovább az Or-Opt algoritmussal. Az Or-Opt algoritmus a konvex burok algoritmus által megadott megoldáson jav´ıt u ´gy, hogy a pontok minden lehetséges ´ athelyezesését, illetve minden egymást követ˝o pontpárt és ponthármast athelyezését kipr´ ´ ob´ alja. Egy véletlenszer˝ uen v´ alasztott pontal kezdj¨ uk az algoritmust, ehhez a ponthoz hozzávessz¨ uk a t´ ur´ ab´ ol a két r´ ak¨ ovetkez˝ o pontot és ezt a ponthármast ideiglenesen eltávol´ıtjuk. Ezután megpróbáljuk besz´ urni ezeket a pontokat, vagy rendes vagy ford´ıtott sorrendben, a t´ ura két egymást követ˝o pontja k¨ ozé. Akkor sz´ urjuk be a pontokat, ha jav´ıtunk az eredeti t´ urán a besz´ urással. Ezután a következ˝ o pontot v´ alasztom ki és az ut´ ana lév˝ o két pontot és ugyanezt megcsismétlem. Ezt addig csin´ aljuk, am´ıg az el˝ osz¨ or kiválasztott ponthoz nem ér¨ unk el u ´jra. Ha u ´jra eljutunk a kiindul´ asi ponthoz, akkor hasonlóan jár 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ézz¨ uk ugyanezeket a pontcseréket. Az ´ıgy kapott optimaliz´ alt k¨ or´ uton pedig lefuttatunk egy károsodást redukáló algoritmust (DRP´ Damage Reduc. Procedure). Ugy van tervezve, hogy minimális költség növekedést okozzon a megk¨ otés nélk¨ uli TSP-ben. El˝ osz¨ or u ´gy próbáljuk megsz¨ untetni a lehetséges károk forrását, hogy ±180◦ -al elforgatjuk (csak a ±90◦ -n´ al lehetséges és nem növeli a TSP költségét). Ha ez sikeres volt, és marad még k´ ar forr´ as amit nem tudunk már ezzel kik¨ uszöbölni, akkor megpróbáljuk a lerak´ asi sorrendet megv´ altoztatni, hogy megsz¨ untess¨ uk. Az elj´ ar´ as lépései: 1. A t´ ura ir´ any´ anak megtal´ al´ asa. Az adott t´ uránkat mindkét irányban kör¨ uljárjuk, majd azt a k¨ or¨ ulj´ ar´ ast (lerak´ asi sorrendet) választjuk, amelyikben a sér¨ ult alkatrészek száma kevesebb. 2. Az ´ıgy kiv´ alasztott k¨ or¨ ulj´ ar´ assal folytatva, a szög változtatásával próbálunk jav´ıtani apol´ aris alkatrészeknél. Ha +90◦ (−90◦ )-os elhelyezése egy apoláris alkatrésznek kárt okoz, akkor ha −90◦ (+90◦ )-os sz¨ oggel helyezz¨ uk el megsz¨ untethetj¨ uk a problémát u ´gy, hogy nem keletkezik u ´jabb k´ arosod´ as. Ha ez teljes¨ ul megváltoztatjuk a szöget, ha nem u ´gy hagyjuk ahogy volt. 3. Ezut´ an a sz¨ oget és az adagol´ o fejet (DH) cserélj¨ uk a poláris alkatrészeknél. Ha egy +90◦ (−90◦ )-os elhelyezés˝ u poláris alkatrész kárt okozna és ha az alkatrész t´ıpusa hozz´ a van rendelve (vagy hozz´ arendelhet˝o) két adagoló fejhez az adagoló automatában ford´ıtott polarit´ assal és meggondoljuk, hogy egy alternat´ıv adagoló veszi fel (ford´ıtott polaritással) és helyezi el −90◦ (+90◦ )-os sz¨ oggel. Ezut´ an ellen˝ orizz¨ uk, hogy megsz˝ unt-e a kár és hogy nem hoztunk-e létre u ´jabb károsodásokat. Ha ez teljes¨ ul akkor megv´ altoztatjuk az elhelyezési szöget és az eredeti helyre lerakó DH szám´ at

31

az alternat´ıv DH sz´ amra v´ altoztatjuk, ahol az alkatrészt´ıpus most elhelyezkedik. Ha nem teljes¨ ul mindent v´ altozatlanul hagyunk. 4. Elhelyezési sorrend v´ altoztat´ asa. Keress¨ uk meg a megmaradt alkatrészeket, amik károsodnának és azonos´ıtsuk a sorrendj¨ uket. V´ altoztassuk meg az elhelyezési sorrendj¨ uket a következ˝o szerint: jelölj¨ uk meg a sér¨ ult alkatrészek k¨ oz¨ ul azokat, amelyeket egymást követ˝oen helyez¨ unk el a körutunk szerint. Tekints¨ uk ezeket kis sorozatoknak és ezen sorozatok sorrendjét ford´ıtsuk meg és rakjuk le ˝ oket ideiglenesen, ha az els˝ o nem sér¨ ult alkatrész megjelenik a sorozatban. Ezut´ an Or-Opt-ot haszn´ alunk és próbálunk jobb helyet találni a sorozatban lév˝o pontoknak a teljes elhelyezési u ´tvonalon u ´gy, hogy besz´ urjuk ˝oket a normál sorrendj¨ ukben a kör´ ut pontjai k¨ ozé. Ha tal´ alunk jobb helyet besz´ urjuk oda, ha nem akkor az ideiglenes hely¨ uk lesz a végleges. ´ 5. Ujabb sz¨ ogv´ altoztat´ asok. A 2-es és 3-as lépést alkalmazva próbáljuk elt¨ untetni a sorrendváltozás (4-es lépés) által létrehozott u ´j k´ arosod´ asokat. 6. Ha még maradt k´ arosod´ as, akkor a 4-es és 5-ös lépést ismételj¨ uk am´ıg meg nem sz¨ unik minden k´ arosod´ as vagy el nem érj¨ uk az el˝ore megadott iterációs lépésszámot. Az 1-5-ig a lépéseket a DRP egy alkalmazásának nevezz¨ uk, a 6. lépés pedig mindig egy u ´jabb alkalmaz´ asa a DRP-nek. A 4-es lépés gyakran el˝ofordul problémára világ´ıt rá a PCB-knél ugyanis az adott tervezés miatt és magasabb kapacitás érdekében (kondenzátorok) érdemes egymás mellé rakni az alkatrészeket. El˝ ofordul, hogy u ´gyis egy ’sorozatnak’ vessz¨ uk az elemeket, hogy a sér¨ ult elem el˝ otti és ut´ ani lév˝ o elem sértetlen. A sér¨ ulést általában az egymást követ˝o lehelyez˝o eljárások okozz´ ak. Ezért is f¨ ugg ¨ ossze a sér¨ ulési feltétel az alkatrészek közelségével. Az ilyen közeli elemeket altal´ ´ aban megszak´ıt´ as nélk¨ ul egym´ as után helyezik el, a konvex burok algoritmusnak megfelel˝ oen. Emiatt a 4. lépésben a sér¨ ult alkatrészek az els˝o nem sér¨ ult mögé ker¨ ulnek, azt várva, hogy a sér¨ ulési feltétel megsz˝ unik. Ha nem ez a helyzet és egy kés˝obbi alkatrész okozza a kárt, akkor az egy kés˝obbi DRP alkalmaz´ assal megsz˝ untethet˝ o. A DRP azonban nem tud minden problémát megsz¨ untetni, pl. ha egy alkatrész t¨ obb m´ as alkatrész lehelyezése miatt is sér¨ ul, ilyenkor lehet, hogy nem lehet a DRP t¨ obbsz¨ ori alkalmaz´ as´ aval sem megoldani a problémát, és az áramkör tervezésének megváltoztat´ asa sz¨ ukséges. 8.3.2. Az elj´ ar´ as teljes´ıtm´ enye Hogy végleges´ıts¨ uk az elhelyezési sorrendet a sugárvezérelt gépekben a DRP alkalmazása seg´ıtségével egy tov´ abbi kiigaz´ıt´ as sz¨ ukséges. El˝ oször kiszámoljuk a sér¨ ulési ter¨ uleteket, vagy fels˝o becslést adunk r´ ajuk, ´ıgy kapjuk meg a potenci´ alisan sér¨ ult alkatrészek halmazát, ez alapján végleges´ıtj¨ uk a sorrendet. Tudjuk, hogy a ¨ osszeszerelési id˝ o nagyobb lesz, mivel a sér¨ ulés megel˝ozés növelheti a TSP kör´ ut k¨ oltségét. A most haszn´ alt algoritmusunkat egy régebben alkalmazottal (Legközelebbi szomszéd algoritmus) hasonl´ıtottuk ¨ ossze a k¨ ovetkez˝ ok alapján: • A teljes ¨ osszeszerelési id˝ o jav´ıt´ asa • Az elhelyezésenkénti 0,34 sec. elhanyagolva (hogy kiegyens´ ulyozottabb összehasonl´ıtást kapjunk) a teljes´ıtmény mérték ¨ osszehasonl´ıtása 32

Ennek eredményként azt kaptuk, hogy amikor a VOPT-ot használtunk és a DRP-t egyszer, az összeszerelési id˝ o ´ atlagosan 1,96%-ot javult, m´ıg a teljes´ıtmény mérték átlagosan 6,47% (az átlagok az elhelyezett alkatrészek sz´ am´ aval s´ ulyozottak). A potenciálisan sér¨ ult elemek száma 90%-al csökkentek. (A val´ o életben természetesen ha marad még potenciálisan sér¨ ult elem, akkor annak elhelyezését manu´ alisan végzik.) Ha a DRP-t t¨ obbsz¨ or alkalmazzuk, a potenciális sér¨ ult elemek száma tovább csökken, és átlagosan 4 iter´ aci´ o ut´ an az eredmény m´ ar a nullához vagy egy kis számhoz konvergál. A károknak a megsz¨ untetésére ir´ anyul´ o k¨ oltség csak 0,9% volt. A tanulm´ anyban végrehajtott k´ısérleti megvalós´ıtás nem csak a teljes´ıtmény 2% -os közvetlen n¨ ovekedését eredményezte (az NN algoritmussal szemben), hanem olyan sugárvezérelt elhelyezési sorrendek létrehoz´ as´ at is seg´ıtette, amelyek csak nagyon kisszám´ u potenciálisan sér¨ ult elemet tartalmaznak. Emellett majdnem teljesen automatizált a m˝ uvelet (az NN-nél még sz¨ ukség volt manu´ alis jav´ıt´ asokra).

A potenci´ alisan sér¨ 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észek sz´ ama Init. time - A TSP k¨ oltsége a DRP el˝ott 1. time - A TSP k¨ oltsége a DRP egyszeri alkalmazása után Last time - A TSP k¨ oltsége a DRP h´ uszszori alkalmazása után Dam(NN) – A potenci´ alisan sér¨ ultek száma NN alkalmazása után k = 1, . . . , 20 - A potenci´ alisan sér¨ ultek száma k DRP alkalmazás után

33

¨ 9. Osszefoglal´ as Ami´ ota csak létezik a probléma rengeteg matematikus figyelmét ragadta meg, számos értekezés sz¨ uletett r´ ola, de még ma is sok nyitott kédés maradt a TSP-vel kapcsolatban. A kombinatorikus optimaliz´ al´ as egyik f˝ o problém´ aja ez, mely napjainkban is aktualitását éli. Pontos és gyors megold´ ast a mai napig nem tudunk adni erre az egyszer˝ unek látszó feladatra. Val´ oj´ aban ha a TSP ´ altal´ anos alakj´ at valaki megoldaná az a P =? NP problémáját is megoldan´ a, és ´ıgy egy 1,000,000$-os d´ıjat nyerne el az Clay Mathematics Intézett˝ol. Ez azonban még nem t¨ ortént meg és bár a TSP komplexitása még mindig ismeretlen, több mint 50 évnyi tanulm´ anyoz´ as ut´ an sz´ amos heurisztika és közel´ıtés létezik a megoldásra, melyek bizonyos feltételek mellett remek¨ ul m˝ uk¨ odnek. Ezeket ellen˝ orzésére vannak korl´ atok, melyek seg´ıtségével becslést tudunk adni az optimális TSP k¨ or´ utra. Emellett természetesen ha ép´ıt¨ unk vagy találunk egy körutat azt tudjuk jav´ıtani. A szakdolgozatom egyik célja az volt, hogy ezeket bemutassam, ellett szerettem volna szem¨ uk elé t´ arni az utaz´ ou ¨gyn¨ ok probléma sokrét˝ u alkalmazásait, illetve olyan megoldási módszereket és programokat melyeket a val´ o életben használnak a probléma megoldására. Abban biztos vagyok, hogy a probléma továbbra is foglalkoztatja majd a matematikusokat, mind m´ as és m´ as megfogalmaz´ asban és ezekre egyre jobb megoldásokkal állnak majd el˝o, de, hogy a probléma problém´ at valaki megoldja-e valaha az egy u ´jabb nyitott kérdés.

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ém problému minimáln´ı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ó 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élet, Typotex 2014. Lov´ asz L´ aszl´ o - Algoritmusok Bonyolults´ aga Egyetemi Jegyzet Friedl Katalin - Turing-gépek (Kiegész´ıt˝o anyag az Algoritmuselmélet tárgyhoz) 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átal and William J. Cook: The Traveling Salesman Problem Christian Nilsson: Heuristics for the Traveling Salesman Problem, Linköping 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

Az utazo u gyno k proble ma e s alkalmaza sai

Recommend Documents