Rendszeroptimalizálás, 13. tétel
A VIK Wikiből
Ez az oldal a korábbi SCH wikiről lett áthozva.
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.
!! A k-matroid partíciós probléma, ennek algoritmikus megoldása. A 2-matroid-metszet feladat visszavezetése matroid partíciós problémára.
k-matroid partíciós probléma
- MPPk*: adott k matroid (Mi=(E,Fi), i=1...k). Kérdés: a matroidok összege a szabadmatroidot adja-e, vagyis E előáll-e E1∪...∪Ek alakban úgy, hogy Ei∈Fi ∀i-re. Feltehető, hogy az Ei halmazok diszjunktak, ezért hívják a feladatot matroid partíciós problémának.
- Lemma*: MPPk NP-beli, mert tanú rá egy particionálás, és a tanú lineáris időben ellenőrizhető.
- Lemma*: MPPk coNP-beli, mert tanú rá egy X⊆E halmaz, ami biztosan összefüggő az összegben, azaz ∑ri(X)<|X.
Algoritmus
Induljunk ki az ∀i Ei=∅ állapotból. Ekkor Ei∈Fi. Az Ei halmazokat addig bővítjük, amíg az uniójuk E nem lesz, vagy ha nem bővíthető, mutatunk egy X tanút.
A bővítéshez bevezetünk egy n+k pontú irányított segédgráfot, amelynek
- Csúcsai E elemei ∪ {p1, ..., pk}. pi az Ei partíció segédpontja.
- (x→pi) ∈ E(G), ha x∉Ei és Ei∪{x}∈Fi.
Az ilyen típusú élek azt jelképezi, hogy az Ei partícióba felvehető x a függetlenség megsértése nélkül. - (x→y) ∈ E(G), ha ∃i x∉Ei, y∈Ei, Ei∪{x}∉Fi, de Ei∪{x}-{y}∈Fi.
Az ilyen típusú élek azt jelentik, hogy az Ei partícióban az y elem kicserélhető x-re a függetlenség megsértése nélkül.
- Megkeressük a legrövidebb irányított utat E-∪Ei-ből {p1, ..., pk}-ba.
- Ha van ilyen út, javítunk az út mentén, azaz végrehajtjuk a cseréket. ∪Ei mérete 1-gyel nő. Azért kell a legrövidebb úton végigmenni, mert különben nem garantált, hogy a cserék során nem sérül a partíciók függetlensége.
- Különben STOP, nemleges a válasz, és a tanú a E-∪Ei-ből irányított úton elérhető pontok halmaza.
2-matroid-metszet feladat
-- Peti - 2007.01.02.
Javítás: ∑ri(X)<|E|| helyett ∑ri(X)<||X !
-- Gabo - 2008.01.04.
