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

Tóth Ádám Aladin: /* k-matroid partíciós probléma */

2017-06-14T20:58:09Z

k-matroid partíciós probléma

← Régebbi változat		A lap 2017. június 14., 22:58-kori változata
5. 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&sube;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&sube;E halmaz, ami biztosan összefüggő az összegben, azaz ∑r<sub>i</sub>(X)<\|X\|.

	===Algoritmus===		===Algoritmus===

Schnell Henrik: Részletes példa futás kidolgozásának hozzáadása

2015-06-12T08:38:58Z

Részletes példa futás kidolgozásának hozzáadása

← Régebbi változat		A lap 2015. június 12., 10:38-kori változata
19. 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===

Szikszayl, 2014. március 13., 12:49-n

2014-03-13T12:49:28Z

← Régebbi változat		A lap 2014. március 13., 14:49-kori változata
29. sor:		29. sor:
	-- [[RendesGaborAntal\|Gabo]] - 2008.01.04.		-- [[RendesGaborAntal\|Gabo]] - 2008.01.04.

	[[~~Category~~:~~InfoMsc~~]]		[[Kategória:Mérnök informatikus MSc]]

Szikszayl, 2013. október 16., 12:41-n

2013-10-16T12:41:41Z

← Régebbi változat		A lap 2013. október 16., 14:41-kori változata
1. sor:		1. sor:
	~~{{GlobalTemplate\|Infoszak\|RopiTetel13}}~~		==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.==


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

	~~__TOC__~~

	===k-matroid partíciós probléma===		===k-matroid partíciós probléma===

14. sor:		8. sor:

	===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.
28. sor:		21. sor:

	===2-matroid-metszet feladat===		===2-matroid-metszet feladat===
			Lásd [[Rendszeroptimalizálás, 12. tétel \| 12.tétel]]
	~~Ld.~~ [[~~RopiTetel12#MMP2~~\|12. tétel~~, MMP<sub>2</sub> szakasz~~]]

	-- [[PallosPeter\|Peti]] - 2007.01.02.		-- [[PallosPeter\|Peti]] - 2007.01.02.

	Javítás: ∑r<sub>i</sub>(X)<\|E\|\| helyett ∑r<sub>i</sub>(X)<\|\|X !		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.

			[[Category:InfoMsc]]
	[[Category:~~Infoszak~~]]

Unknown user: Ú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…”

2012-10-22T09:43:35Z

Ú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…”

Új lap

{{GlobalTemplate|Infoszak|RopiTetel13}}

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

__TOC__

===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&sube;E halmaz, ami biztosan összefüggő az összegben, azaz ∑ri(X)<|X.

===Algoritmus===

Induljunk ki az ∀i Ei=<big>∅</big> á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-<big>∪</big>Ei-ből {p1, ..., pk}-ba.
# Ha van ilyen út, javítunk az út mentén, azaz végrehajtjuk a cseréket. <big>∪</big>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-<big>∪</big>Ei-ből irányított úton elérhető pontok halmaza.

===2-matroid-metszet feladat===

Ld. [[RopiTetel12#MMP2|12. tétel, MMP2 szakasz]]

-- [[PallosPeter|Peti]] - 2007.01.02.

Javítás: ∑ri(X)<|E|| helyett ∑ri(X)<||X !

-- [[RendesGaborAntal|Gabo]] - 2008.01.04.

[[Category:Infoszak]]