Rendszeroptimalizálás, 16. tétel

Ez az oldal a korábbi SCH wiki-ről lett áthozva. Az eredeti változata itt érhető el.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor kérlek javíts rajta egy rövid szerkesztéssel.

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót

!! 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.

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.

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.

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.

-- Peti - 2007.01.03.