Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel16}} ==!! Közelítő algoritmus a Steiner-fa problémára, illetve a metrikus utazóügynök problémára (Christofides algoritmus…”

2012-10-22T09:43:43Z

Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel16}} ==!! Közelítő algoritmus a Steiner-fa problémára, illetve a metrikus utazóügynök problémára (Christofides algoritmus…”

Új lap

{{GlobalTemplate|Infoszak|RopiTetel16}}

==!! Közelítő algoritmus a Steiner-fa problémára, illetve a metrikus utazóügynök problémára (Christofides algoritmusa). Az általános utazóügynök probléma közelíthetősége.==

__TOC__

===Steiner-fa probléma===

*Feladat*: adott G(S∪T,E) összefüggő gráf, c:E→R+ élsúlyozás. Keressük meg a minimális összköltségű, T pontjait tartalmazó fát. 
*Speciális esetek*:
* T=V: minimális feszítőfa keresés.
* |T=2: legrövidebb út.
* G teljes gráf és az élsúlyokra teljesül a háromszög-egyenlőtlenség: metrikus Steiner-fa probléma.

*Lemma*: ha a metrikus Steiner-fa problémára létezik k-approximációs algoritmus, akkor az általános problémára is létezik. 
*Biz.*: az általános problémát visszavezetjük a metrikus esetre. Legyen G'-ben minden pontpárra c'(a→b) = a és b csúcs távolsága G-ben. OPT(G')≤OPT(G), mert G'-ben kisebbek az élköltségek. Tekintsük G'-ben az algoritmus által talált fát, ennek költsége ≤k·OPT(G')≤k·OPT(G). A fa G-beli megfelelője a legrövidebb utak uniója lesz, ami egy összefüggő részgráfot alkot. Ha ebből veszünk egy feszítőfát, az összköltség nem nő.

*Lemma*: a minimális feszítőfa költsége a T halmazon legfeljebb az optimális metrikus Steiner-fa kétszerese. 
*Biz.*: vegyünk egy optimális Steiner-fát. Duplázzuk meg az éleit, és keressünk egy Euler-kört. Vegyük sorba az Euler-kör csúcsait, és dobjuk el azokat, amelyeket nem először érintettünk. A csúcsokat összekötve kaptunk egy Hamilton-utat. 
c(minimális feszítőfa T-n) ≤ c(Hamilton-út) < c(Euler-kör) = 2*OPT

*Lemma*: a minimális feszítőfa nem k-optimális k<2-re. 
*Biz.*: legyen |S=1, az S és T közötti élek 1 súlyúak, a T-beli élek pedig 2 súlyúak. Az optimum n-1, de az algoritmus 2(n-2) költségű fát talál, mivel n-1 T-beli pont van, a feszítőfához tehát n-2 élre van szükség, és minden él súlya 2.

===Metrikus utazóügynök probléma===

*Feladat*: adott G teljes gráf, és egy c:E→R+ élsúlyozás, amire teljesül a háromszög-egyenlőtlenség. Keressük a minimális összsúlyú Hamilton-kört. 

*2-approximációs algoritmus*: vesszük a minimális feszítőfát, megduplázzuk az éleit, keresünk egy Euler-kört és leszűkítjük Hamilton-körré. 
c(talált Hamilton-kör) ≤ c(Euler-kör) = 2*c(minimális feszítőfa) ≤ 2*c(minimális Hamilton-út) < 2*c(minimális Hamilton-kör) = 2*OPT

*Christofides algoritmus*: vesszük a minimális feszítőfát és egy minimális összsúlyú teljes párosítást a fa páratlan fokú csúcsai által kifeszített G' részgráfban. A fa és a párosítás élei által meghatározott részgráfban keresünk egy Euler-kört, amit leszűkítünk Hamilton-körré. 
*Tétel*: a Christofides algoritmus 3/2-approximációs. 
*Biz.*: a minimális feszítőfa összsúlya < OPT, elég azt belátni, hogy a párosítás éleinek összsúlya ≤ OPT/2. Jelöljük a minimális Hamilton-kört G gráfban H-val, G' segédgráfban H'-vel. c(H')≤OPT, mert H-t levágásokkal át tudjuk alakítani úgy, hogy csak G'-beli csúcsokat tartalmazzon, miközben nem nő az összköltsége, és az így kapott G'-beli Hamilton-körnél H' nyilván nem nagyobb súlyú. A minimális összsúlyú teljes párosítás pedig legfeljebb c(H')/2 költségű, mert H' páros élei és páratlan élei is teljes párosítást alkotnak, a kettő költségének összege c(H'), tehát van legfeljebb c(H')/2 összköltségű párosítás, aminél nem nagyobb a minimális összsúlyú teljes párosítás.

===Általános utazóügynök probléma közelíthetősége===

*Tétel*: az általános utazóügynök probléma nem k-közelíthető. 
*Biz.*: tegyük fel, hogy van rá k-közelítés. Vegyünk egy tetszőleges G(V,E) gráfot és képezzünk belőle egy G'(V,V×V) gráfot úgy, hogy G' éleire c(e)=1, ha e∈G és c(e)=k|V||, ha e∉G. Ha G-ben volt Hamilton-kör, G'-ben ||V|| lesz az optimum, különben legalább k||V||+1, tehát ha egy k-approximációs algoritmus talál egy legfeljebb k||V súlyú Hamilton-kört G'-ben, akkor G-ben volt Hamilton-kör, különben nem.

-- [[PallosPeter|Peti]] - 2007.01.03.

[[Category:Infoszak]]

Rendszeroptimalizálás, 16. tétel - Laptörténet

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel16}} ==!! Közelítő algoritmus a Steiner-fa problémára, illetve a metrikus utazóügynök problémára (Christofides algoritmus…”