Matematika | Diszkrét Matematika » Hábel Réka - Az utazóügynök feladat heurisztikái

http://www.doksihu EÖTVÖS LORÁND TUDOMÁNYEGYETEM TERMÉSZETTUDOMÁNYI KAR AZ UTAZÓÜGYNÖK FELADAT HEURISZTIKÁI Szakdolgozat Hábel Réka Matematika BSc szak Alkalmazott matematikus szakirány Témavezető: Vesztergombi Katalin, egyetemi docens Számı́tógéptudományi Tanszék Budapest, 2010 http://www.doksihu Tartalomjegyzék 1. Bevezetés 2 2. Történeti áttekintés 4 3. Az utazóügynök feladat NP-teljessége 7 3.1 A Hamilton-kör probléma . 10 3.2 Az utazóügynök probléma . 13 4. Közelı́tő algoritmusok 15 4.1 A mohó módszer . 16 4.2 A legközelebbi szomszéd heurisztikája . 17 4.3 Beszúrásos heurisztikák . 18 4.4 Az optimum keresése feszı́tőfával 19 4.5 Christofides algoritmusa 21 4.6 Lin

és Kernighan heurisztikája 22 5. Alsó korlátok 24 5.1 Alsó becslés párosı́tásokkal 24 5.2 1-fa korlát 25 5.3 Held-Karp korlát 26 5.4 Lineáris programozási alsó korlát 26 5.5 Branch and Bound 29 6. Befejezés 31 1 http://www.doksihu 1. fejezet Bevezetés Az utazóügynök feladat a kombinatorikus optimalizálás egyik legfontosabb problémája. A matematikának ezen területe bizonyos gyakorlati indı́ttatású optimalizálási feladatokkal, illetve azok matematikai modelljével foglalkozik. Ezen feladatokra egzakt, approximációs, illetve véletlen algoritmusokat keresünk, melyekhez a megfelelő matematikai modell megalkotásán és a megfelelő algoritmikus technika megválasztásán keresztül vezet az út. Az utazóügynök

probléma elnevezése onnan származik, hogy egy ügynöknek kell meglátogatni a rá bı́zott terület összes városát úgy, hogy a körút végén hazaérjen, és hogy utazási költsége a lehető legalacsonyabb legyen. Nyilvánvaló, hogy ez matematikailag ugyanaz a feladat, mint egy telefonhálózat kiépı́tésekor egy legolcsóbb telefonvonalakból álló kör megkeresése. Ugyanez a probléma merül fel például a chipgyártásban, ugyanis a chip felületén az áramkör bizonyos pontjait lézerrel kell kiégetni, ı́gy a lézernek ezeket a pontokat kell valamilyen sorrendben végiglátogatni. Egy elektronikai cég ezért az utazóügynök feladat közelı́tő megoldására készı́tett egy programot, melyet évek óta használnak. Ez a probléma számos más helyen is előfordul, például a szemétszállı́tásban, levélkézbesı́tésben, közelekedési hálózatokban,

járműirányı́tásban. Térjünk vissza az eredeti problémánkra. A városok száma legyen n és bármely kettő esetében adott, hogy mennyibe kerül a közvetlen összeköttetés. Azt a kört kell megkeresni, amelyben a teljes költség a lehető legkisebb A feladat matematikai modellje a következő Legyen a G = (V, E) teljes gráfnak n pontja, melyekkel a városokat szemléltetjük. Az éleken adott egy c : E R+ 2 http://www.doksihu költségfüggvény. A feladat egy minimális összhosszú Hamilton-kör megkeresése a gráfban A harmadik fejezetben látni fogjuk, hogy a feladat NP-teljes, azaz mindezidáig senki sem adott polinomiális algoritmust a probléma megoldására. A sejtés az, hogy ilyen algoritmus nem is létezik. Ennek ellenére ez a feladat a gyakorlatban igen fontos, ı́gy számos heurisztika és approximációs (közelı́tő) algoritmus látott napvilágot. Ezek közül megismerkedhetünk

párral a negyedik fejezetben Ahhoz, hogy meg tudjuk mondani, hogy a közelı́tő algoritmusok által szolgáltatott Hamiltonkör mennyire van közel az optimumhoz, szükségünk van alsó becslésekre. Ilyen alsó korlát számı́tási módszerekkel találkozunk az ötödik fejezetben. Most nézzük meg, hogy az évek során hogyan sikerült egyre több és több városra megoldani a problémát. 3 http://www.doksihu 2. fejezet Történeti áttekintés Az utazóügynök problémáját Sir William Rowan Hamilton ı́r és Thomas Penyngton Kirkman brit matematikusok vetették fel az 1800-as években. A feladattal komolyabban az 1930-as években kezdett foglalkozni Karl Menger, osztrák matematikus. A problémát később Hassler Whitney és Merrill Flood tanulmányozta a Princeton egyetemen. A nagy áttörés 1954-ben követekezett be, amikor is George Dantzig, Ray Fulkerson és Selmer Johnson megoldották a feladatot 49

amerikai városra (ld. 21 ábra) 2.1 ábra 1987-ben felgyorsultak az események, Padberg és Rinaldi 532 amerikai telefonközpontra talált optimális összeköttetést (ld. 22 (a) ábra), majd Groetschel és Holland a világ 666 nevezetes4 http://www.doksihu ségéhez talált optimális körutat (ld. 22 (b) ábra) Szintén ugyanebben az évben Padberg és Rinaldi megoldotta a problémát 2 392 pontra, egy elektonikai cég megbı́zásából (ld 22 (c) ábra) 2.2 ábra 1998-ban Applegate, Bixby, Chvátal és Cook megtalálták az USA 13 509 települését érintő optimális kört (ld. 23 (a) ábra) 2004-ben Applegate, Bixby, Chvátal, Cook és Helsgaun megoldották a feladatot Svédország összes, szám szerint 24.978 településére (ld 23 (b) ábra) 2.3 ábra 5 http://www.doksihu A legnagyobb eddig megoldott probléma egy 85.900 pontból álló integrált áramkör bejárása, melyet 2005/06-ban

készı́tettek (ld. 24 ábra) 2.4 ábra Megoldásra váró probléma még a Föld 1 904 711 városának optimális bejárása. Egyre jobb és jobb körutak látnak napvilágot (ld 2.5 ábra), jelenleg a 2010 május 4-i eredmény a legjobb, egy 7 515 796 609 hosszú bejárással. 2.5 ábra 6 http://www.doksihu 3. fejezet Az utazóügynök feladat NP-teljessége A probléma NP-teljességének igazolása előtt nézzük meg, miért is érdekes ez a problémaosztály. Egy algoritmus polinomiális idejű, ha n méretű bemeneten a futási ideje a legrosszabb esetben is O(nk ), valamely k konstanssal. Felvetődhet a kérdés, hogy vajon minden probléma megoldható-e polinomiális időben? A válasz természetesen nem Vannak problémák - például Turing megállási problémája - melyek egyáltalán nem oldhatóak meg számı́tógéppel. Vannak olyanok is, melyek megoldhatóak, de nem polinom időben. A

polinomiális idejű algoritmussal megoldható problémákat általában jól kezelhetőnek tekintjük Ahhoz, hogy a polinom időben megoldható problémák osztályát átlássuk, először is meg kell mondanunk, mit értünk problémán. Az absztrakt problémát kétváltozós relációként definiáljuk a probléma eseteinek és megoldásainak halmazán, ám ez jóval általánosabb, mint amire szükségünk van. Az egyszerűség kedvéért az NP-teljesség elmélete csak úgynevezett döntési problémákkal foglalkozik, azaz olyanokkal, melyekre a megoldás ”igen” vagy ”nem” Az utazóügynök feladat - mely egy optimalizálási probléma - túl absztrakt, ezért, hogy az NP-teljesség elméletét erre is alkalmazni tudjuk, döntési problémává kell átalakı́tanunk. Ezt az átalakı́tást majd a probléma NP-teljességének bizonyı́tásánál látjuk részletesebben A P osztály

definiálásához szükségünk lesz még néhány fogalomra. Legyen Σ szimbólumok véges halmaza (ábécé). Szavak az ábécé elemeiből képzett véges sorozatok. A szavak halmaza legyen Σ∗ Az L nyelv pedig nem más, mint a szavak egy tetszőleges halmaza (L ⊆ Σ∗ ). Azt mondjuk, hogy az A algoritmus elfogadja az x ∈ Σ∗ szót, ha az x bemeneten A 1-et ad, azaz 7 http://www.doksihu A(x) = 1. Az A algoritmus elfogadja az L nyelvet, ha L minden szavát elfogadja Azt mondjuk, hogy az A algoritmus eldönti az L nyelvet, ha az L-beli szavakat elfogadja, a többi szót pedig elutası́tja. Az A algoritmus polinom időben elfogadja/eldönti az L nyelvet, ha bármely n hosszú x ∈ L szót O(nk ) időben elfogad/eldönt, valamely k szám mellett. Az L nyelv (polinom időben) elfogadható/eldönthető, ha létezik algoritmus, mely (polinom időben) elfogadja/eldönti. Ezek után definiálhatjuk a P bonyolultsági osztályt. P

:= {L : L polinom időben eldönthető nyelv} Most térjünk rá az NP bonyolultsági osztály definiálására. Ehhez szükségünk lesz a tanú fogalmára Azt mondjuk, hogy az L nyelvnek tanúja az L0 nyelv, ha x ∈ L akkor és csak akkor, ha van olyan y ∈ Σ∗ szó, hogy (x, y) ∈ L0 . L nyelvnek f (n) hosszúságú, g(n) idejű tanúja az L0 nyelv, ha tanúja és egyrészt L0 legfeljebb g(n) időben eldönthető, másrészt minden x ∈ L-re van olyan y ∈ Σ∗ szó, hogy |y| ≤ f (|x|) és (x, y) ∈ L0 . Ezek után definiálhatjuk NP-t: NP := {L : L-nek létezik polinomiális hosszú és idejű tanúja } Érdemes még definiálni a co-NP osztályt is, a következőképp: co-NP := {L : Σ∗ L ∈ NP } A P és NP közti kapcsolatról való tudásunk hiányos. Azt tudjuk, hogy P ⊆ (NP ∩ co-NP), ám nem tudjuk, hogy a tartalmazás valódi-e. A P , NP sejtés felvetése 1971 óta az elméleti

számı́tógéptudomány egyik legmélyebb és legnehezebb kutatási területe. A P , NP sejtés melletti legnyomósabb érv talán az NP-teljes problémák létezése. Ezen problémák rendelkeznek a következő tulajdonsággal: ha közülük akár csak egy is megoldható polinom időben, akkor valamennyi NP-beli probléma megoldható polinom időben, azaz P=NP. Az évtizedek óta folyó kutatások ellenére sem sikerült egyelőre polinomiális algoritmust találni egyetlen NP-teljes problémára sem. Az NP-teljes nyelvek definiálásához azonban szükség lesz a visszavezethetőség fogalmára. Azt mondjuk, hogy az L1 ⊆ Σ∗1 nyelv polinomiálisan visszavezethető az L2 ⊆ Σ∗2 nyelvre (jelölése L1 ≤ p L2 ) , ha létezik olyan polinomiális időben kiszámı́tható f : Σ∗1 Σ∗2 függvény, hogy minden x ∈ Σ∗1 szóra x ∈ L1 ⇐⇒ f (x) ∈ L2 . Most már készen állunk az NP-teljesség

definiálásához. 8 http://www.doksihu Egy L nyelv NP-teljes, ha NP-beli és minden L′ ∈ NP-re L′ ≤ p L Ha egy nyelv a második tulajdonságot teljesı́ti, de az elsőt nem feltétlenül, akkor NP-nehéznek nevezzük. Néhány NP-teljes probléma: • Boole-formulák kielégı́thetősége (SAT): Adott egy φ Boole-formula, ami változókból (x1 , x2 , .), Boole-függvényekből (és, vagy, nem, implikáció,ekvivalencia) és zárójelekből áll. Ez a formula kielégı́thető, ha létezik olyan 0-1 sorozat, melyet x1 , x2 , . helyére ı́rva φ értéke 1 lesz A SAT probléma: Egy adott Boole-formula kielégı́thető- e vagy sem? E problémának történelmi jelentősége, hogy róla bizonyı́tották először, hogy NP-teljes. • Klikk-probléma: Adott G = (V, E) gráfban keresünk (a csúcsok számában) maximális méretű klikket, vagyis csúcsok egy V ′ halmazát, ami teljes gráf. A

klikk-probléma: Mekkora a legnagyobb klikk egy G gráfban? Ez egy optimalizálási probléma, ı́gy át kell alakı́tani döntésivé: létezik-e a G gráfban k méretű klikk? • Lefedés- probléma: Adott G = (V, E) gráfban keresünk (a csúcsok számában) minimális méretű lefedő csúcshalmazt, vagyis egy olyan V ′ -t, melyre igaz az, hogy G minden élét legalább egy eleme fed. A lefedés-probléma: Mekkora a legkisebb lefedő csúcshalmaz egy G gráfban? Ez egy optimalizálási probléma, ı́gy át kell alakı́tani döntésivé: létezik-e a G gráfban k méretű lefedő csúcshalmaz? • Hamilton-kör probléma stb. Most nézzük meg, hogyan kell egy problémáról bebizonyı́tani, hogy NP-teljes. 3.01 Lemma Ha L olyan nyelv, melyhez létezik L′ NP-teljes nyelv, hogy L′ ≤ p L, akkor L NP-nehéz. Ha L ∈ NP is teljesül, akkor L NP-teljes Ezek alapján az utazóügynök feladat NP-teljességét

úgy látjuk be, hogy a hozzá szorosan kapcsolódó Hamilton-kör problémát polinomiálisan visszavezetjük az utazóügynök problémára. Emiatt előbb a Hamilton-kör probléma NP-teljességét bizonyı́tjuk 9 http://www.doksihu 3.1 A Hamilton-kör probléma A Hamilton-kör keresésének problémáját irányı́tatlan gráfban már több, mint száz éve tanulmányozzák. Egy irányı́tatlan G = (V, E) gráf Hamilton-körén olyan kört értünk, amely G minden pontján pontosan egyszer megy át. Az ilyen kört tartalmazó gráfokat szokás Hamilton-gráfoknak nevezni. A Hamilton-kör probléma: ”Van-e a G gráfnak Hamilton köre?” Formális nyelvként definiálva: HAM = {hGi : G Hamilton-gráf} 3.11 Tétel A Hamilton-kör probléma (HAM) NP-teljes Bizonyı́tás. Könnyű belátni, hogy HAM ∈ NP A G = (V, E) gráf esetén a tanú egy |V| csúcsból álló sorozat. Az ellenőrző algoritmus

megvizsgálja, hogy a sorozat V egy permutációja-e, és hogy a szomszédos csúcsok össze vannak-e kötve. Ez polinom időben elvégezhető A probléma NP-nehézségének bebizonyı́tásához a LEFEDÉS problémát vezetjük vissza polinomiálisan HAM-ra. Egy adott G = (V, E) gráfhoz és k ≤ |V| természetes számhoz konstruálunk egy olyan G′ = (V ′ , E ′ ) gráfot, melynek pontosan akkor van Hamilton-köre, ha G-nek létezik k csúcsból álló fedése. 3.11 ábra 10 http://www.doksihu G′ felépı́tésénél speciális segédgráfokat használunk (ld. 311 (a) ábra) A G gráf minden e = ′ ′ (u, v) ∈ E éléhez G′ tartalmazni fogja a segédgráf egy példányát, melyet jelöljön G′uv = (Vuv , Euv ). G′uv 12 csúcsát [u, v, i]-vel és [v, u, i]-vel jelöljük, ahol i = 1, 2, ., 6 ′ Vuv = {[u, v, i], [v, u, i] : i = 1, 2, ., 6} ′ Euv = {([u, v, i], [u, v, i + 1]), ([v, u, i], [v, u, i +

1]) : i = 1, 2, ., 5} ∪{([u, v, 1], [v, u, 3]), ([u, v, 3], [v, u, 1])} ∪{([u, v, 4], [v, u, 6]), ([u, v, 6], [v, u, 4])} Az egyes segédgráfok csúcsai közül csak az [u, v, 1] , [u, v, 6] , [v, u, 1] , [v, u, 6] csúcsok legyenek összekötve G′ többi csúcsával. Ennek következtében G′ bármely Hamilton-köre csak az 311 (b)-(d) ábrákon látható módon haladhat keresztül G′uv csúcsain. Ha a kör az [u, v, 1] csúcsban lép be a segédgráfba, akkor az [u, v, 6] csúcsban kell kilépnie és keresztülmennie a segédgráf mind a 12 csúcsán (ld. 311 (b) ábra) vagy az [u, v, 1, ], [u, v, 2], , [u, v, 6] csúcsokon (ld 3.11 (c) ábra) Ez utóbbi esetben a körnek vissza kell térnie a segédgráfba, hogy átmehessen a [v, u, 1], [v, u, 2], ., [v, u, 6] csúcsokon Hasonlóan, ha a kör a [v, u, 1] csúcsban lép be a gráfba akkor a [v, u, 6] csúcson kell kimennie és kersztülmennie mind a 12 csúcson (ld. 311

(d) ábra) vagy a [v, u, 1], [v, u, 2], ., [v, u, 6] csúcsokon (ld 311 (c) ábra) Ezeken kı́vül nem létezik más út, amely átmenne a segédgráf minden csúcsán. G′ -höz hozzáveszünk még további úgynevezett ”szelektor” csúcsokat: s1 , s2 , ., sk , melyeket arra használunk, hogy kiválasszunk k csúcsot a G gráfból, melyek lefedik G éleit. G′ további élei kétfélék lehetnek. Az első tı́pusú élekkel a G gráf minden u ∈ V csúcsához, az u-hoz csatlakozó éleknek megfelelő segédgráfokat egy útra fel tudjuk fűzni. Ehhez tekintsük az u-ból induló élek egy tetszőleges sorrendjét. Legyenek az ı́gy kapott csúcsok u1 , u2 , , ud(u) az u-val szomszédos csúcsok. Létrehozunk egy utat G′ -ben az u-val szomszédos éleknek megfelelő segédgráfokon keresztül oly módon, hogy hozzávesszük E ′ -höz a következő éleket: Eu′ = {([u, ui , 6], [u, ui+1 , 1]), i = 1, .,

d(u) − 1} Ezek az élek arra szolgálnak, hogy ha az u csúcs szerepel G egy fedő csúcshalmazában, akkor meg tudunk adni egy utat G′ [u, u1 , 1] csúcsából [u, ud(u) , 6] csúcsába, mely végigmegy az u-hoz csatlakozó éleknek megfelelő segédgráfokon. Ha ui nincs benne a fedő csúcshalmazban, akkor az út tartalmazza a G′uui segédgráf mind a 12 csúcsát. Ha ui benne van a fedő csúcshalmazban, 11 http://www.doksihu akkor az út az [u, ui , 1], [u, ui , 2], ., [u, ui , 6] csúcsokat érinti A másik tı́pusú élek az [u, u1 , 1] és az [u, ud(u) , 6] csúcsokat kötik össze az összes választó csúccsal. Tehát hozzávesszük E ′ -höz a következő éleket: E ′′ = {(s j , [u, u1 , 1]), (s j , [u, ud(u) , 6]) : j = 1, 2, ., k, u ∈ V} Tehát G′ = (V ′ , E ′ ) gráf a következőképp néz ki: S ′ V ′ = {s j : j = 1, 2, .k} ∪ ( e=uv∈E Vuv ) S S ′ E ′ = ( e=uv∈E Euv ) ∪ ( u∈V

Eu′ ) ∪ E ′′ Megmutatjuk, hogy G′ mérete polinomiális G méretében. Ebből már következik, hogy G′ -t polinom időben meg tudjuk konstruálni G-ből, hiszen az egyes elemek konstrukciója végrehajtható polinom időben. G′ csúcsainak száma: |V ′ | = 12|E| + k ≤ 12|E| + |V|, ami polinomiális G méretében. G′ éleinek száma: |E ′ | = 14|E| + P u∈V (d(u) − 1) + 2k|V| = 14|E| + 2|E| − |V| + 2k|V| ≤ 16|E| + (2|V| − 1)|V|, ami szintén polinomiális G méretében. Most belátjuk,hogy G-ben pontosan akkor létezik k csúcsú fedés, ha G′ -ben létezik Hamiltonkör. Először tegyük fel, hogy a G = (V, E) gráfnak van egy V ∗ ⊆ V k méretű fedő csúcshalmaza. Jelölje V ∗ elemeit u1 , u2 , .uk G′ egy Hamilton-körét a következő élek alkotják Minden u j -re ( j = 1, 2, ., k) az Eu′ j -beli összes él, vagyis az u j -hez csatlakozó éleknek megfelelő segédgráfokat

összekötő élek, emellett az ezen segédgráfokban szereplő élek a 3.11 (b)-(d) ábrán látható módok valamelyike szerint, attól függően, hogy {u, v}∩V ∗ egyenlő {u}-val, {u, v}vel, vagy {v}-vel. Végül az {(s j , [u j , u1j , 1]) : j = 1, 2, ., k} d(u j ) {(s j+1 , [u j , u j , 6]) : j = 1, 2, ., k − 1} és k) , 6])} {(s1 , [uk , ud(u k 12 élhalmazok. http://www.doksihu Nem nehéz ellenőrizni, hogy ezek az élek valóban kört alkotnak. A kör s1 -ben kezdődik, végigmegy az u1 -hez csatlakozó élekhez tartozó segédgráfokon, majd elmegy s2 -be, végigmegy az u2 -höz csatlakozó élekhez tartozó segédgráfokon, és ı́gy tovább, amı́g vissza nem ér s1 -be. A kör minden segédgráfot egyszer vagy kétszer látogat meg, annak megfelelően, hogy a hozzá tartozó élnek hány végpontja van V ∗ -ban. Mivel V ∗ lefedő csúcshalamaza G-nek, a kör az összes segédgráf összes

csúcsán végigmegy. Minthogy a kör a szelektor csúcsok mindegyikét is érinti, ı́gy a kör valóban Hamilton-köre G′ -nek. Fordı́tva, tegyük most fel, hogy a G′ = (V ′ , E ′ ) gráfnak vagy egy C ⊆ E ′ Hamilton-köre. Azt állı́tjuk, hogy a k elemű V ∗ = {u ∈ V : ∃ j, hogy (s j , [u, u1 , 1]) ∈ C} csúcshalmaz fedi G éleit. Ennek bebizonyı́tásához osszuk fel C-t olyan maximális utakra, amelyek valamely si csúcsban kezdődnek, átmennek az (si , [u, u1 , 1]) élen, majd egy s j csúcsban érnek véget anélkül, hogy bármely más választó csúcson átmennének. Ezeket az utakat nevezzük fedőutaknak G′ konstrukciójából adódik, hogy egy ilyen fedőútnak át kell mennie az u csúcshoz G-ben csatlakozó összes élnek megfelelő segédgráfon. Jelöljük ezt a fedőutat pu -val Evidens, hogy u ∈ V ∗ Tekintsünk egy pu által érintett segédgráfot Ez vagy G′uv vagy G′vu

lesz valamely v ∈ V-re Az ennek megfelelő e = (u, v) ∈ E élt a V ∗ -beli u és v csúcs is fedi. Mivel minden segédgráfot meglátogat egy vagy két fedőút, ı́gy a V ∗ valóban fedő csúcshalmaz.  3.2 Az utazóügynök probléma Az utazóügynök problémában (traveling salesman problem - T S P) - mely szoros kapcsolatban áll a Hamilton-kör problémával - szereplő ügynöknek n várost kell meglátogatnia tetszőleges sorrendben, de minél kisebb utazási költség mellett. Precı́zebben: adott egy G = (V, E) n csúcsú teljes gráf, melynek éleihez egész számokat rendelünk. A feladat olyan Hamilton-kör megtalálása, melynek összköltsége minimális A megfelelő optimalizálási problémából nyert döntési problémához tartozó formális nyelv: T S P = {hG, c, ki : G teljes-gráf, c : V × V Z, k ∈ Z és G-nek létezik legfeljebb k költségű Hamilton-köre } 13

http://www.doksihu 3.21 Tétel Az utazóügynök probléma (T S P) NP-teljes Bizonyı́tás. Először belátjuk, hogy T S P ∈ NP A tanú egy megfelelő költségű Hamilton-kör Az ellenőrző algoritmus megvizsgálja. hogy az adott csúcssorozat Hamilton-kör-e, majd összeadja az élek költségeit és összahasonlı́tja k-val. Ez végrehajtható polinom időben A T S P NP-nehézségének bizonyı́tásához megmutatjuk, hogy a HAM polinomiálisan visszavezethető T S P-re. Adott G = (V, E) gráfhoz tekintsük a G′ = (V, E ′ ) teljes gráfot, ahol E ′ = {(i, j) : i, j ∈ V}. Az élek költségei legyenek:     0 ha (i, j) ∈ E c(i, j) =    1 ha (i, j) < E Könnyen látható, hogy G-ben pontosan akkor van Hamilton-kör, ha G′ -nek létezik legfeljebb 0 költségű Hamilton-köre.  Ezzel bebizonyı́tottuk, hogy az utazóügynök feladat NP-teljes, vagyis mindezidáig senki sem adott

polinomiális algoritmust a feladat megoldására. Ezért a továbbiakban a gyakorlatban használt közelı́tő algoritmusokat vizsgáljuk 14 http://www.doksihu 4. fejezet Közelı́tő algoritmusok Az utazóügynök feladata a G = (V, E) n pontú (teljes) gráfban a c : E R+ élhosszak esetén a legrövidebb olyan körnek a megkeresése, amely a gráf minden pontján áthalad. A c súlyfüggvényről feltesszük, hogy kielégı́ti a háromszögegyenlőtlenséget, azaz tetszőleges u, v, z pontokra teljesül: c(uv) + c(vz) ≥ c(uz). Az előző fejezetben beláttuk, hogy a feladat NP-teljes, ám elméleti és gyakorlati jelentősége miatt számos heurisztika és approximációs algoritmus látott napvilágot, ezekkel foglalkozik ez a fejezet. Heurisztika alatt általában egy matematikailag jól meghatározott algoritmust értünk, melynek teljesı́tményére vonatkozólag nem ismertek erős tételek. NP-nehéz

feladatok esetén a heurisztikáknak komoly létjogosultságuk lehet, mivel gyakran ezek teljesı́tenek legjobban a gyakorlatban Arra törekszünk, hogy algoritmusunkról egy 1-hez közeli approximációs szorzót bizonyı́tsunk. Egy konkrét input esetén az approximációs szorzó az optimum értékének és az output értékének a hányadosa. Minimalizálási feladat esetén egy algoritmus approximációs szorzójának azt a számot nevezzük, ami az összes lehetséges inputra képzett approximációs szorzók maximuma. Ha egy heurisztikáról nem tudunk kicsi approximációs szorzót biztosı́tani, akkor tesztelünk. A TSP-re ismert egy TSPLIB példagyűjtemény, melyben kb. 100 példagráf található, melyek egy része a való életből jön, más példák viszont elméleti jellegűek. Ezen a könyvtáron átlagolva az approximációs szorzót kapjuk a TSPLIB mérőszámát az algoritmusnak. Ez a

mérőszám mutatja 15 http://www.doksihu legjobban, hogy egy konkrét feladatra várhatóan milyen jól működik egy heurisztika. A továbbiakban vizsgáljunk meg néhány konkrét algoritmust (heurisztikát). 4.1 A mohó módszer Képzeljünk el egy országot, amelyben n város van. Az ország a városok között számı́tógépes hálózatot kı́ván létesı́teni. Természetesen nem akarják valamennyi várost összekötni az összes többivel, de a hálózaton belül mindegyik városnak elérhetőnek kell lennie. A gráfelmélet terminológiáját használva azt mondhatnánk, hogy a G = (V, E) teljes gráfban egy minimális összefüggő gráfot, azaz egy fát keresnek. Bármelyik fát választják, n − 1 vonalat kell lefektetni, de nem mindegy, hogy hol A vonalak között - például épı́tési költség tekintetében - komoly különbségek lehetnek. A cél tehát olyan fa

megtalálása, amelyben a teljes költség minimális Ezt a fát jelöljük F-fel. A továbbiakban a költségeket adottnak tekintjük, ezeket ugyanis ki lehet számolni Nézzük, hogyan működik esetünkben a mohó algoritmus. 1.lépés Rendezzük az éleket költség szerinti növekvő sorrendbe: e1 ≤ e2 ≤ . ≤ e(n2) 2.lépés Bevesszük e1 -et, e2 -t az F fába i := 3 3.lépés Az ei élt bevesszük az épülő F fába, ha nem alkot kört az előzőekkel i := i + 1 4.lépés Ha még van olyan csúcs, amely nem szerepel az F fában, visszaugrunk a 3 lépésre Ha az F fa minden csúcsot fed, akkor az algoritmus véget ér. Az ı́gy kapott hálózat egy n pontú összefüggő gráf, melyben nincs kör. Bebizonyı́tható, hogy az ı́gy kapott fa a lehető legolcsóbb. Ha viszont a feladatot kissé módosı́tjuk, akkor ugyanez a hozzáállás katasztrófális eredményhez vezethet. Tegyük fel, hogy -

mondjuk - biztonsági okokból megköveteljük, hogy bármelyik két várost két vonal kössön össze, méghozzá olyanok, amelyeknek nincs közös éle. Elegendő, ha a városokat egyetlen körre fűzzük fel. A feladat tehát egy minimális költségű, az n város mindegyikén átmenő kör megtalálása. Jelöljük ezt a kört H-val Lássuk, ez esetben hogyan járna el a kormány, ha a mohó stratégiát alkalmazná. 16 http://www.doksihu 1.lépés Rendezzük az éleket költség szerinti növekvő sorrendbe: e1 ≤ e2 ≤ . ≤ e(n2) 2.lépés Bevesszük e1 -et, e2 -t H-ba i := 3 3.lépés Az ei élt bevesszük az épülő H körbe, ha ı́gy a végpontok fokszáma nem lesz több 2-nél és ha az esetlegesen létrejövő kör az összes városon áthalad. i := i + 1 4.lépés Ha még van olyan csúcs, amely nem szerepel H-ban, vagy H még nem kör, visszaugrunk a 3. lépésre Ha a H kör minden

csúcsot fed, akkor az algoritmus véget ér Így elkészül egy kör, ám ez nem feltétlenül a legjobb! A 4.11 ábrán láthatjuk, hogy a mohó módszerrel olyan körhöz jutunk, amely sokkal többe kerül, mint az optimális. 4.11 ábra Tehát a mohó algoritmus az utazóügynök feladat esetében nem találja az optimumot, sőt elég messze eshet tőle. 4.2 A legközelebbi szomszéd heurisztikája A módszer a következő. Keressünk meg egy legrövidebb élet Az él egyik végpontjából kiindulva lépjünk tovább mindig egy legközelebbi pontba, ahol még nem jártunk. Ha az út már minden 17 http://www.doksihu csúcsot érint, kényszerűségből lépjünk vissza a kiindulópontba, hogy kört kapjunk. Az algoritmus futási ideje Θ(n2 ), ugyanis minden lépésben legfeljebb n élt vizsgálunk meg és legfeljebb n lépés van. Tehát az algoritmusunk elég gyors, azonban az általa adott megoldás

nagyon messze eshet az optimumtól. Ennek ellenére a TSPLIB mérőszáma 126, ami nem is rossz. 4.3 Beszúrásos heurisztikák Az alábbi heurisztikák mind úgy működnek, hogy kiválasztanak valamilyen szabály szerint egy kiindulási élet, aztán hozzávesznek egy pontot, három pontból álló kört kapva ı́gy. A továbbiakban, ha van már egy kisebb kör, akkor valamilyen szabály szerint kiválasztják a következő beszúrandó pontot, és azon két pont közé illesztik a körbe, amellyel a kör hossza a lehető legkevesebbel nő, azaz megkeresi azon két, a meglévő körben egymás után következő u, v pontot, amelyre a beszúrandó s ponttal a következő érték minimális: c(us) + c(vs) − c(uv) • Legközelebbi pont beszúrása. Egy legrövidebb élből indulunk ki, és a körhöz legközelebbi pontot szúrjuk be. • Legtávolabbi pont beszúrása. Egy leghosszabb élből indulunk ki

és mindig a körtől legtávolabbi pontot szúrjuk be. • Legolcsóbb beszúrás. Egy legrövidebb élből indulunk és megnézzük, hogy a körben nem szereplő pontok beszúrása mekkora hossznövekedést eredményez. Azt a pontot szúrjuk be, melyre ez minimális. • Véletlen pont beszúrás. Véletlenül választjuk a soron következő beszúrandó pontot Meglepő, de a gyakorlatban előforduló problémákra a legtávolabbi pont beszúrása működik a legjobban. 4.31 Állı́tás (Rosenkrantz, Stearns, Lewis, 1977) Tetszőleges beszúrási módszer által az utazóügynök feladatra adott megoldás hossza az optimális megoldás legfeljebb (logn + 1)-szerese 18 http://www.doksihu Bizonyı́tás. Az eljárás végén kapott Hamilton kört jelölje H ∗ Legyen v1 , v2 , , vn a pontok beszúrási sorrendje. A vi pont beszúrásakor a hossznövekedést jelölje b(vi ) b(v1 ) := 0, b(v2 ) := 2c(v1 v2 ). A

b(vi )-kre fennáll a következő: Pn i=1 b(vi ) = c(H ∗ ) Azt állı́tjuk, hogy tetszőleges vi és v j csúcsokra: min{b(vi ), b(v j )} ≤ 2c(vi v j ) Ugyanis ha például vi előbb szerepelt a körben, mint v j , akkor ha v j -t vi és vl közé szúrnánk be, a növekmény c(vi v j ) + c(vl v j ) − c(vi vl ) lenne, ahol vl a részkörben szereplő szomszédja vi -nek. A növekmény pedig a háromszögegyenlőtlenség miatt legfeljebb 2c(vi v j ). Ennél pedig b(v j ) nem lehet nagyobb. Jelölje H az optimális Hamilton-kört. Tekintsük ennek minden második élét Minden ilyen vi v j él egyik végpontjához rendeljük hozzá a b(vi ) és b(v j ) közül a kisebbet. Az előbbi egyenlőtlenségből következik, hogy a hozzárendelt pontok beszúrásakor a kör össznövekménye legfeljebb c(H). Tekintsük H azon pontjait, amelyekhez még nem rendeltünk értéket Ezeken a pontokon a H-ban lévő

körüljárás szerint haladva olyan kört kapunk, melynek a hossza a háromszögegyenlőtlenség miatt legfeljebb c(H). Erre a körre alkalmazzuk az előző gondolatot és folytassuk tovább az eljárást. Akkor ér véget, mikor már csak egy pont marad hozzárendelés nélkül Ám ezen pont beszúrása sem növelhette a kör hosszát jobban, mint c(H). Ezek alapján a következő egyenlőtlenség ı́rható fel: c(H ∗ ) = 4.4 Pn i=1 b(vi ) ≤ (logn + 1) ∗ c(H)  Az optimum keresése feszı́tőfával Az algoritmus a következő: 1.lépés Tekintsünk a gráfban egy (a hosszfüggvényre nézve) minimális összhosszú feszı́tőfát, melynek élhalmaza legyen F (ld. 441 (a) ábra) 2.lépés Duplázzuk meg a fa éleit, ezen élek halmaza legyen F ∗ 19 http://www.doksihu 3.lépés Tekintsük az ı́gy keletkezett G∗ = (V, F ∗ ) gráf egy Euler-bejárását (ld 441 (b) ábra) Ilyen bejárás

létezik, ugyanis G∗ összefüggő és minden pont foka páros. A bejárásban kapott pontok sorrendje legyen v1 , v2 , ., v2n 4.lépés Legyen u1 , u2 , , un a pontok azon sorrrendje, melyet úgy kapunk, hogy minden pontnak csak az első előfordulását tartjuk meg. Ez a H ∗ := (u1 , u2 , ., un ) egy Hamilton kör (ld 441 (c) ábra) 4.41 ábra 4.41 Állı́tás A kapott H ∗ Hamilton kör nem hosszabb, mint az optimum kétszerese Bizonyı́tás. Legyen H egy minimális összhosszú Hamilton-kör élhalmaza Ennek egy h elemére H − h feszı́tőfa, tehát igaz a következő: l(F) ≤ l(H − h) ≤ l(H) := OPT Másrészt a háromszögegyenlőtlenség miatt: l(H ∗ ) ≤ l(F ∗ ) = 2l(F) ≤ 2 ∗ OPT Ezzel beláttuk, hogy az emlı́tett algoritmus 2-approximációs.  20 http://www.doksihu 4.5 Christofides algoritmusa Ezen algoritmus az előbbi finomı́tása, a feszı́tőfából másként csinálunk Hamilton-kört.

1.lépés Tekintsünk egy minimális összhosszú feszı́tőfát, melynek élhalmaza legyen F (ld 451 (a) ábra). Jelölje T azon pontok halmazát, melyekre páratlan sok F-beli él illeszkedik |T | páros. 2.lépés Tekintsük a KT teljes gráfot és ebben egy minimális költségű M teljes párosı́tást, melyet Edmonds algoritmusával hatékonyan meg lehet találni (ld. 451 (b) ábra) 3.lépés Ekkor F ∪ M egy összefüggő gráf, melyben minden pont foka páros, ı́gy létezik egy v1 , v2 , ., v2n Euler-bejárása 4.lépés Legyen u1 , u2 , , un a pontok azon sorrrendje, melyet úgy kapunk, hogy minden pontnak csak az első előfordulását tartjuk meg. Ez a H ∗ := (u1 , u2 , ., un ) egy Hamilton kör (ld 451 (c) ábra) 4.51 ábra 4.51 Állı́tás A kapott H ∗ Hamilton kör nem hosszabb, mint az optimum másfélszerese Bizonyı́tás. Legyen H egy minimális összhosszú Hamilton-kör élhalmaza Ennek egy h

elemére H − h feszı́tőfa, tehát igaz a következő: 21 http://www.doksihu l(F) ≤ l(H − h) ≤ l(H) := OPT A háromszögegyenlőtlenség miatt KT -ben a minimális Hamilton-kör hossza nem több az optimumnál, melyet a H körből is megkaphattunk volna a V − T -beli pontok kiiktatásával. Jelöle HT a T -beli pontokra kapott Hamilton-kört. HT előáll két T -beli teljes párosı́tás uniójaként, ı́gy az olcsóbbik nem lehet drágább HT költségének felénél, vagyis l(M) ≤ 1 2 ∗ OPT Végül a háromszögegyenlőtlenség miatt: l(H ∗ ) ≤ l(F) + l(M) ≤ 3 2 ∗ OPT Ezzel beláttuk, hogy az emlı́tett algoritmus 32 -approximációs.  Az algoritmus TSPLIB mérőszáma 1.14, ami jobb, mint az elméleti 15-ös korlát 4.6 Lin és Kernighan heurisztikája Ez az elgondolás az általában legjobban működő utazóügynök bejárást adó heurisztikák alapsémája. 4.61

Definı́ció A v1 , e1 , v2 , e2 , , vn , en , vn+1 n pontú, n élű gráfot δ-útnak nevezzük, ha vn+1 = vi valamely 1 ≤ i ≤ n-re, és minden más pont különböző. Ha P egy δ-út, akkor legyen H(P) a P-ből az en = vn vn+1 él törlése és az e′n = vn v1 él hozzávételével kapott kör. A Lin-Kernighan algoritmus δ-utak sorozata segı́tségével keres egyre rövidebb bejárásokat A Lin-Kernighan-alapalgoritmus: Adott egy H kör G pontjain. 1.lépés (Élkeresés) A G gráf minden v csúcsára és a rá illeszkedő H-beli e = (u, v) élre hajtsuk végre a 2-5. lépést 2.lépés (Élkeresés inicializálása) u0 := u P0 legyen az a δ-út, mely H-ból az u0 v él törlésével és egy olyan u0 w0 él hozzáadásával kapunk, melyre: c(u0 w0 ) ≤ c(u0 v) 22 http://www.doksihu Ha ilyen w0 pont nincs, akkor az élkeresésnek vége. i := 0 3.lépés (Túrateszt) Ha c(H(Pi )) kisebb, mint az eddig

talált legjobb kör hossza, akkor H(Pi )-t megjegyezzük. 4.lépés (Következő δ-út) Legyen ui+1 a wi másik szomszédja a δ-út körén Ha wi ui+1 H-nak nem éle, akkor ugorjuk az 5. lépésre Különben keressünk olyan wi+1 pontot, melyre ui+1 wi+1 nem éle H-nak és teljesül a következő: c(Pi − wi ui+1 + ui+1 wi+1 ) ≤ c(H) Ha nincs ilyen pont, akkor ugorjunk az 5. lépésre Különben legyen: Pi+1 := Pi − wi ui+1 + ui+1 wi+1 i := i + 1 és ugorjunk a 3. lépésre 5.lépés Ha találtunk jobb kört, akkor legyen az az új H és ugorjunk az 1 lépésre, különben folytassuk az élkeresést. Az algoritmus TSPLIB mérőszáma 1.02 23 http://www.doksihu 5. fejezet Alsó korlátok Az előző fejezetben megismerkedtünk néhány közelı́tő algoritmussal, melyek minimális Hamiltonkört keresnek, ám többségében nem az optimális megoldást adják. Ahhoz, hogy meg tudjuk vizsgálni, hogy a kapott

heurisztikus megoldásunk mennyire jó, mennyire van közel az optimális megoldáshoz, szükségünk van az optimum alsó becslésére. Ebben a fejezetben láthatunk néhány alsó korlát számı́tási módszert. Minél jobb alsó korlátot tudunk adni, annál pontosabban értékelhetjük a már meglévő megoldásainkat. 5.1 Alsó becslés párosı́tásokkal Legyen adva egy páros sok csúcsból álló G = (V, E) gráf és ebben egy Hamilton-kör (páros hosszú). Ez a Hamilton-kör felbomlik két éldiszjunkt teljes párosı́tásra, M1 -re és M2 -re Kiindulunk a kör egy csúcsából, majd minden második élét vegyük bele M1 -be, a többi kerül M2 -be, ld 5.11 ábra Ezek alapján a minimális összhosszú Hamilton-kör költségére egy alsó becslést kapunk a legolcsóbb teljes párosı́tás költségének kétszeresével. Tehát ha a legolcsóbb teljes párosı́tást Mmel

jelöljük: 2 ∗ c(M) ≤ c(H) 24 http://www.doksihu 5.11 ábra 5.2 1-fa korlát Az előző fejezetben már használtuk a feszı́tőfát Hamilton-kör keresésére. A legolcsóbb feszı́tőfa költsége egy alsó becslés a legolcsóbb Hamilton-körre. Most ezt a becslést szeretnénk javı́tani Legyen v1 ∈ V egy rögzı́tett pont. Legyen Fv1 a G−v1 gráf egy minimális költségű feszı́tőfája Ekkor az 1-fa korlát a következő: min{c(e) + c( f ) : e = v1 s, f = v1 t, s , t} + c(Fv1 ) Tehát a v1 -re illeszkedő két legolcsóbb él költségének és F − v1 költségének az összege. Ezzel a korláttal nem lehetünk elégedettek, a korlát olykor nagyon messze esik az optimumtól, ld. 521 ábra. 5.21 ábra 25 http://www.doksihu 5.3 Held-Karp korlát Az 1-fa korlát hibája abban rejlik, hogy a korlátot adó élhalmaz alakja nagyon távol eshet az optimális Hamilton-körtől, például

nagyon nagy fokú csúcsok lehetnek a feszı́tőfában és ennek következtében sok elsőfokú csúcs. Javı́tsunk az 1-fa korláton. Válasszunk egy, a fában nagy fokú v csúcsot Minden rá illeszkedő G-beli él súlyát növeljük meg M-mel. Jól választott M esetén v kisebb fokú lesz a fában, az 1-fa korlát pedig nő, akár 2M-nél is többel. Az optimális Hamilton kör viszont pontosan 2M-mel nő, ı́gy jobb alsó korláthoz juthatunk. Alkalmazzuk ezt az elgondolást egyszerre az összes pontra. Legyen d : V − v1 R egy csúcsokon értelmezett súlyfüggvény. Legyen D a következő új élsúlyozással kapott 1-fa korlát: minden e = uv élre legyen c′ (e) := c(e) − d(u) − d(v). Ekkor a Held-Karp korlát a következő: D+2 P v∈V−v1 d(v) Ez valóban az eredeti probléma egy alsó korlátja, ugyanis minden Hamilton-kör hossza 2 P v∈V d(v) értékkel csökkent. 5.4 Lineáris

programozási alsó korlát A lineáris programozás alapfeladata egy lineáris egyenlőtlenségrendszer megoldásai közül kiválasztani azt, amelyre egy szintén lineáris célfüggvény értéke maximális. Persze azt is el kell tudni dönteni, hogy az egyenlőtlenségrendszer egyáltalán megoldható-e. Egy lineáris programozási feladatban adott egy A m × n-es mátrix és egy m dimenziós b vektor. A feladat a max{cx : Ax ≤ b} érték meghatározása és a maximumhely megkeresése. 5.41 Tétel (Farkas lemma, általános alak) A Px0 + Ax1 = b0 , Qx0 + Bx1 ≤ b1 , x1 ≥ 0 primál rendszernek akkor és csak akkor nincs megoldása, ha az 26 http://www.doksihu y0 P + y1 Q = 0, y0 A + y1 B ≥ 0, y1 ≥ 0, yb := y0 b0 + y1 b1 = −1 duális rendszernek van. 5.42 Tétel (Dualitás tétel) A primál probléma: max{(c0 x0 + c1 x1 ) : Px0 + Ax1 = b0 , Qx0 + Bx1 ≤ b1 , x1 ≥ 0} A duál probléma: min{(c0 y0 + c1 y1 ) : y0 P +

y1 Q = c0 , y0 A + y1 B ≥ c1 , y1 ≥ 0} Tegyük fel, hogy a primál rendszer megoldható, továbbá, hogy {cx : x a primál rendszer megoldása } felülről korlátos. Ekkor a primál optimalizálási feladatban szereplő maximum egyenlő a duál feladatban szereplő minimummal. Írjuk fel az utazóügynök problémát lineáris programozási feladatként. 5.41 Definı́ció Legyen H egy éleivel megadott Hamilton kör Egy x ∈ RE vektor a H Hamilton kör karakterisztikus vektora, ha teljesül:     1 ha e ∈ H xe =    0 ha e < H Olyan egyenletrendszereket kell felı́rni, melynek megoldásai Hamilton körök karakterisztikus vektorai. 0 ≤ xe ≤ 1 ∀e ∈ E (5.1) Jelölje δ(v) a v csúcsra illeszkedő élek halmazát, x(δ(v)) pedig a v-re illeszkedő éleken az x értékek összegét. ∀v ∈ V x(δ(v)) = 2 (5.2) (5.1) - (52)-nek megoldása minden Hamilton-kör karakterisztikus vektora, továbbá

megoldások még a gráfot fedő diszjunkt körök karakterisztikus vektorai is. Vegyük hozzá még a következő egyenletet: x(δ(U)) ≥ 2 ∀U ⊂ V, U , ∅ (5.3) Az (5.1) - (53) egyenlőtlenségek egész megoldásai pontosan a Hamilton-körök karakterisztikus vektorai. Sajnos a megoldások nem feltétlen egészek, az 541 ábrán látható példában az éleken jelölt xe értékek kielégı́tik az egyenlőtlenségrendszereket, de nem egészértékűek. 27 http://www.doksihu 5.41 ábra Az utazóügynök feladat lineáris programozási relaxáltja: X min (ce xe : e ∈ E) ∀v ∈ V (5.5) ∀U ⊂ V, U , ∅ (5.6) x(δ(v)) = 2 x(δ(U)) ≥ 2 (5.4) 0 ≤ xe ≤ 1 ∀e ∈ E (5.7) Mivel nem feltétlenül létezik ezen lineáris programnak egész megoldása, az optimum meghatározása csak egy alsó korlátot ad az optimális bejárás hosszára. 5.43 Tétel Annak eldöntése, hogy az Ax ≤ b feladatnak

van-e egész x megoldása, melyre cx ≥ t, NP-teljes. Jeölje γ(S ) az S halmazon belül feszı́tett élek halmazát. Ekkor az alábbi feltétel ekvivalens az (5.6)-os feltétellel: x(γ(U)) ≤ |U| − 1 ∀U ⊂ V, U , ∅ (5.8) Ugyanis: x(δ(U)) + 2 ∗ x(γ(U)) = X x(δ(v)) (5.9) v∈U Nézzük milyen problémákkal szembesülünk, ha meg szeretnénk oldani a lineáris programozási relaxáltat. Az első jelentős akadály, hogy a feladatban rengeteg, szám szerint 2|E| + |V| + 2|V| darab 28 http://www.doksihu egyenlőtlenség szerepel. Ahhoz, hogy megengedett megoldásokat keressünk, nincs szükségünk ennyi egyenlőtlenségre. Oldjuk meg először a kevés feltételt tartalmazó (5.4), (55), (57) feladatot, például egy szimplex módszert használó solverrel Ha véletlenül a kapott megoldás egy Hamilton-kör karakterisztikus vektora, akkor kész is vagyunk a feladattal Ha nem, a megoldásunk a (56)-os feltételt

nem elégı́ti ki. Keressünk sértő U halmazokat, és csak az ezekre vonatkozó egyenlőtlenségeket vegyük a feltételekhez. Oldjuk meg a kapott kibővı́tett lineáris programot, és ismételgessük az eljárást. Másik probléma nagy gráfok esetén, hogy kezelhetetlenül sok változónk van. Amit tehetünk, hogy nem kezdünk el rögtön az összes változóval dolgozni, hanem csak egy részükkel, majd fokozatosan vegyük hozzá a többit, amire szükségünk van. 5.5 Branch and Bound A Branch and Bound, azaz Korlátozás és Szétválasztás, egy általános algoritmikus keret, melynek két fontos részlete, hogy hogyan választjuk szét az eseteket és hogy milyen alsó becsléseket alkalmazunk. Az előző részekben szereplő becslésekkel jó alsó korlátokhoz juthatunk, melyek segı́tségével meggyőződhetünk arról, hogy a talált bejárásunk valóban megközelı́ti az optimumot. De mit

tegyünk, ha az optimumhoz még közelebbi megoldást keresünk? Ekkor alkalmazhatjuk a Korlátozás és Szétválasztás módszerét. Jelölje H a G gráf összes Hamilton-körének halmazát. Legyen H0 ∪ H1 H egy partı́ciója Legyenek K0 és K1 alsó korlátok, melyekre c(H) ≥ K0 ∀H ∈ H0 és c(H) ≥ K1 ∀H ∈ H1 . Ekkor a min{K0 , K1 } alsó korlátja az összes H-beli körnek. Így jó eséllyel nagyobb korlátot kapunk A továbbiakban tovább bontjuk a halamazainkat, alkalmazzuk rájuk az alsó korlát számı́tási eljárásunkat, majd az összes közül a legkisebbet választva remélhetjük, hogy javı́tunk az eddigin. Nézzük egy konkrét megvalósı́tását a fenti eljárásnak, ha a lineáris programozási alsó korláttal számolunk. Jelölje P a kiindulási problémánkat, mely a H halmazban keresi a legrövidebb kört. Vágjuk ketté H-t úgy, hogy egy e élt választva legyen H0 az e

élet nem tartalmazó körök, H1 pedig az e élet tartalmazó körök halmaza. Legyenek P0 és P1 a megfelelő problémák Ekkor a P-re vonatkozó 29 http://www.doksihu alsó korlátot számoló lineáris programot egészı́tsük ki az xe = 0 feltétellel az első esetben, mı́g a másodikban az xe = 1 feltétellel, melyek megoldása valóban H0 -ra, illetve H1 -re vonatkozó alsó korlátok. Ezután válasszunk ki egy még nem vizsgált problémát (kezdetben P0 -t), aztán egy f él szerint bontsuk tovább a hozzá tartozó halmazt (H0 -t), újabb (P00 és P01 ) problémákat kapva ı́gy. A problémák ı́ly módon ábrázolhatóak bináris fával. Melyik levélben szereplő problémát válasszuk kettévágásra? Egyik hozzáállás az, hogy mindig a legkisebb alsó korlátot adó problémát válasszuk ki. Hogyan vágjuk szét a feladatokat, mi alapján válasszuk ki az e élet? Megfelelő

választásnak tűnhet a kiválasztott probléma alsó korlátját adó lineáris program megoldásában a 1/2-hez legközelebbi értékű változóhoz tartozó él. Így a fentiek végrehajtása során egyre jobb és jobb alsó korlátokhoz juthatunk, esetleg előfordulhat, hogy valamely probléma lineáris programozási relaxáltjának megoldása egy Hamiltonkör karakterisztikus vektora, aminek a hossza talán jobb, mint az eljárás kezdetekor kezünkben lévő köré. 30 http://www.doksihu 6. fejezet Befejezés Az előző fejezetekben beláttuk, hogy az utazóügynök feladat NP-teljes, ám ennek ellenére léteznek közelı́tő algortimusok a megoldására és különböző alsó korlátokkal ellenőrizhetjük, hogy a kapott bejárásunk mennyire közel van az optimumhoz. Természetesen a problémakör ennél sokkal tágabb, számos más heurisztika létezik még az itt bemutatottakon kı́vül.

Célom az volt, hogy megmutassam, hogy a probléma megoldhatatlanságának ellenére számos, a gyakorlatban igen jól használható heurisztika létezik, melyeknek ilyen esetekben nagyon nagy jelentőségük van. Végezetül nézzünk néhány érdekes és hasznos alkalmazást. Mona Lisa TSP. 2009 februárjában Robert Bosch készı́tett egy 100.000 pontból álló példát, melynek bejárásával megkapjuk Leonardo Da Vinci Mona Lisa cı́mű festményét egy folytonos vonallal megrajzolva (ld. 61 (a) ábra) Robert Bosch a kép elkészı́tése során egy Lin-Karnighan heurisztikáján alapuló algoritmust használt a pontok összekötéséhez. Ha a legközelebbi szomszéd heurisztikáját használva akarnánk megrajzolni, másabb ábrát kapnánk, több lenne benne a hosszú él, kevésbé jó rajzot kapnánk. Google maps. Lehetőségünk van útvonaltervezésre Google maps-en Megadjuk az érinteni

kı́vánt pontokat és kapunk egy optimális bejárást. Például Lincoln elnök rendszeresen utazott Illinois államban, állomásait a 6.1 (b) ábrán láthatjuk 31 http://www.doksihu 6.1 ábra TSP Game. Kipróbálhatjuk magunkat is, jobban teljesı́tünk-e, mint az algoritmusok A játék véletlenszerűen generál pontokat a sı́kon, feladatunk minél rövidebb Hamilton-kör keresése. A játéknak van két személyes változata is, ahol egymás ellen kell játszani (ld. 62 ábra) 6.2 ábra 32 http://www.doksihu Köszönetnyilvánı́tás Köszönöm témavezetőmnek, Vesztergombi Katalinnak, hogy lehetőséget biztosı́tott szakdolgozatom megı́rásához. A szakmai segı́tség mellett ötleteivel és tanácsaival is hozzájárult, hogy dolgozatom minél tökéletesebb legyen Hálás vagyok páromnak, aki informatikai tudásával nagy segı́tségemre volt a LATEX okozta bonyodalmak leküzdésében.

Köszönettel tartozom családomnak és barátaimnak, akik végig mellettem álltak és dolgozatomat olvasgatva jó tanácsokkal láttak el. 33 http://www.doksihu Irodalomjegyzék [1] Lovász László - Pelikán József - Vesztergombi Katalin: Diszkrét matematika, Typotex Kiadó, Budapest, 2006 [2] Thomas H. Cormen - Charles E Leiserson - Ronald L Rivest: Algoritmusok, Műszaki Könyvkiadó, Budapest, 1997 [3] Katona Gyula Y. - Recski András - Szabó Csaba: A számı́tástudomány alapjai, ötödik kiadás, Typotex Kiadó, Budapest, 2006 [4] Jordán Tibor - Recski András - Szeszlér Dávid: Rendszeroptimalizálás, Typotex Kiadó, Budapest, 2004 [5] M. R Garey - D S Johnson: Computers and Intractability: A Guide to the Theory of NPCompleteness, WH Freeman and Company, USA, 1979 [6] Frank András: Operációkutatás, elektonikus jegyzet, 2006 [7] Pap Gyula: Kombinatorikus Optimalizálás előadás vázlata, elektronikus jegyzet,

2008 [8] Király Tamás - Szegő László: Kiegészı́tés az Egészértékű Programozás I. és II tárgyhoz, elektronikus jegyzet, 2008 [9] Lovász László: Algoritmusok Bonyolultsága, elektronikus jegyzet, Király Zoltán javı́tott változata, 2009 [10] http://compalg.infeltehu/ tony/Oktatas/Osztott-algoritmusok/P-NP-NPCpdf [11] http://www.mathprincetonedu/tsp A fent emlı́tett irodalmakból olykor szó szerint is idéztem, amit nem jeleztem idézőjelekkel. 34