„Rendszeroptimalizálás, 13. tétel” változatai közötti eltérés
A VIK Wikiből
Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel13}} ==!! A k-matroid partíciós probléma, ennek algoritmikus megoldása. A 2-matroid-metszet feladat visszavezetése matroid par…” |
|||
| (3 közbenső módosítás, amit 2 másik szerkesztő végzett, nincs mutatva) | |||
| 1. sor: | 1. sor: | ||
==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=== | ===k-matroid partíciós probléma=== | ||
| 11. sor: | 5. sor: | ||
*Lemma*: MPP<sub>k</sub> NP-beli, mert tanú rá egy particionálás, és a tanú lineáris időben ellenőrizhető. <br> | *Lemma*: MPP<sub>k</sub> NP-beli, mert tanú rá egy particionálás, és a tanú lineáris időben ellenőrizhető. <br> | ||
*Lemma*: MPP<sub>k</sub> coNP-beli, mert tanú rá egy X⊆E halmaz, ami biztosan összefüggő az összegben, azaz ∑r<sub>i</sub>(X)<|X. | *Lemma*: MPP<sub>k</sub> coNP-beli, mert tanú rá egy X⊆E halmaz, ami biztosan összefüggő az összegben, azaz ∑r<sub>i</sub>(X)<|X|. | ||
===Algoritmus=== | ===Algoritmus=== | ||
Induljunk ki az ∀i E<sub>i</sub>=<big>∅</big> állapotból. Ekkor E<sub>i</sub>∈F<sub>i</sub>. | Induljunk ki az ∀i E<sub>i</sub>=<big>∅</big> állapotból. Ekkor E<sub>i</sub>∈F<sub>i</sub>. | ||
Az E<sub>i</sub> 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. | Az E<sub>i</sub> 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. | ||
| 26. sor: | 19. sor: | ||
# Ha van ilyen út, javítunk az út mentén, azaz végrehajtjuk a cseréket. <big>∪</big>E<sub>i</sub> 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. | # Ha van ilyen út, javítunk az út mentén, azaz végrehajtjuk a cseréket. <big>∪</big>E<sub>i</sub> 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-<big>∪</big>E<sub>i</sub>-ből irányított úton elérhető pontok halmaza. | # Különben STOP, nemleges a válasz, és a tanú a E-<big>∪</big>E<sub>i</sub>-ből irányított úton elérhető pontok halmaza. | ||
===Példa=== | |||
Az algoritmus futására itt egy részletesen bemutatott példa a jobb érthetőség kedvéért:<br> | |||
https://docs.google.com/document/d/1CbHAHJY4M3cxmBel0cgZ47GIgTOgQ4RJwn_MeOxbais | |||
===2-matroid-metszet feladat=== | ===2-matroid-metszet feladat=== | ||
Lásd [[Rendszeroptimalizálás, 12. tétel | 12.tétel]] | |||
-- [[PallosPeter|Peti]] - 2007.01.02. | -- [[PallosPeter|Peti]] - 2007.01.02. | ||
Javítás: ∑r<sub>i</sub>(X)<|E | Javítás: ∑r<sub>i</sub>(X)<|E| helyett ∑r<sub>i</sub>(X)<|X| ! | ||
-- [[RendesGaborAntal|Gabo]] - 2008.01.04. | -- [[RendesGaborAntal|Gabo]] - 2008.01.04. | ||
[[Kategória:Mérnök informatikus MSc]] | |||
[[ | |||
A lap jelenlegi, 2017. június 14., 21:58-kori változata
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.
Példa
Az algoritmus futására itt egy részletesen bemutatott példa a jobb érthetőség kedvéért:
https://docs.google.com/document/d/1CbHAHJY4M3cxmBel0cgZ47GIgTOgQ4RJwn_MeOxbais
2-matroid-metszet feladat
Lásd 12.tétel
-- Peti - 2007.01.02.
Javítás: ∑ri(X)<|E| helyett ∑ri(X)<|X| !
-- Gabo - 2008.01.04.
