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

Nyíri Gábor, 2015. május 25., 12:35-n

2015-05-25T12:35:10Z

← Régebbi változat		A lap 2015. május 25., 14:35-kori változata
18. sor:		18. sor:
	Az algoritmus menete a következő:		Az algoritmus menete a következő:

	1 A neteket bal szélső termináljuk szerinti növekvő sorrendbe rendezzük.		* A neteket bal szélső termináljuk szerinti növekvő sorrendbe rendezzük.
	1 Ha az 1 ... i-1 sorszámú netek huzalozása kész		* Ha az 1 ... i-1 sorszámú netek huzalozása kész
	** ha az i. net vízszintes huzalszakasza belefér valamelyik "megkezdett" sorba, ott elhelyezzük		** ha az i. net vízszintes huzalszakasza belefér valamelyik "megkezdett" sorba, ott elhelyezzük
	** ha nem, új sorba tesszük		** ha nem, új sorba tesszük

Tarokkk: /* Csatornahuzalozás k rétegen a Manhattan modellben */

2014-01-20T10:52:26Z

Csatornahuzalozás k rétegen a Manhattan modellben

← Régebbi változat		A lap 2014. január 20., 12:52-kori változata
31. sor:		31. sor:
	Csatornahuzalozásnak az olyan feladatokat nevezzük, ahol a terminálok a lap két szemközti szélén helyezkednek el. A rétegek száma előre meghatározott, cél a feladat megoldása minél kisebb szélességben. A rétegeket - mivel Manhattan-modellben dolgozunk - függőleges és vízszintes huzalozású rétegekre bontjuk, ezek számosságát f-fel ill. v-vel jelöljük (f + v = k).		Csatornahuzalozásnak az olyan feladatokat nevezzük, ahol a terminálok a lap két szemközti szélén helyezkednek el. A rétegek száma előre meghatározott, cél a feladat megoldása minél kisebb szélességben. A rétegeket - mivel Manhattan-modellben dolgozunk - függőleges és vízszintes huzalozású rétegekre bontjuk, ezek számosságát f-fel ill. v-vel jelöljük (f + v = k).

	Az előző feladathoz képest annyit változtatunk a terhelés mérésén, hogy nem rácspontok között, hanem rácspontokon keresztül menő egyeneseken mérjük. A legnagyobb terhelés értékét d-vel jelöljük ez a feladat sűrűsége. Ekkor egy megoldás minimális szélessége <math>\lceil d / v \rceil</math>. Emellett minden ilyen feladat megoldható <math>\lceil d / (f - 1) \rceil</math> szélességben (ha f ≥ 2), és ilyen megoldás található is lineáris időben.		Az előző feladathoz képest annyit változtatunk a terhelés mérésén, hogy nem rácspontok között, hanem rácspontokon keresztül menő egyeneseken mérjük. A legnagyobb terhelés értékét d-vel jelöljük ez a feladat sűrűsége.

	==== Egy csatornahuzalozási feladat Manhattan-modellbeli megoldásának minimális szélessége legalább <math>\lceil d / v \rceil</math> ====		==== Tétel: Egy csatornahuzalozási feladat Manhattan-modellbeli megoldásának minimális szélessége legalább <math>\lceil d / v \rceil</math> ====
	Tegyük fel, hogy van w szélességű huzalozás. Mivel d terhelésű egyenest csak a vízszintes rétegek soraiban metszhetnek szakaszok és ilyen sorból vw van, azért <math>		Tegyük fel, hogy van w szélességű huzalozás. Mivel d terhelésű egyenest csak a vízszintes rétegek soraiban metszhetnek szakaszok és ilyen sorból vw van, azért <math>
	vw \geq d \rightarrow w \geq \lceil d / v \rceil</math>		vw \geq d \rightarrow w \geq \lceil d / v \rceil</math>

			==== Tétel: Minden csatornahuzalozási feladat megoldható <math>\lceil d / (f - 1) \rceil</math> szélességben (ha f ≥ 2), és ilyen megoldás található is lineáris időben. ====
			TODO

	--[[Szerkesztő:Tarokkk\|Tarokkk]] ([[Szerkesztővita:Tarokkk\|vita]]) 2014. január 20., 10:49 (UTC)		--[[Szerkesztő:Tarokkk\|Tarokkk]] ([[Szerkesztővita:Tarokkk\|vita]]) 2014. január 20., 10:49 (UTC)

Tarokkk: /* Egy csatornahuzalozási feladat Manhattan-modellbeli megoldásának minimális szélessége legalább \lceil d / v \rceil */

2014-01-20T10:49:19Z

Egy csatornahuzalozási feladat Manhattan-modellbeli megoldásának minimális szélessége legalább \lceil d / v \rceil

← Régebbi változat		A lap 2014. január 20., 12:49-kori változata
36. sor:		36. sor:
	Tegyük fel, hogy van w szélességű huzalozás. Mivel d terhelésű egyenest csak a vízszintes rétegek soraiban metszhetnek szakaszok és ilyen sorból vw van, azért <math>		Tegyük fel, hogy van w szélességű huzalozás. Mivel d terhelésű egyenest csak a vízszintes rétegek soraiban metszhetnek szakaszok és ilyen sorból vw van, azért <math>
	vw \geq d \rightarrow w \geq \lceil d / v \rceil</math>		vw \geq d \rightarrow w \geq \lceil d / v \rceil</math>


			--[[Szerkesztő:Tarokkk\|Tarokkk]] ([[Szerkesztővita:Tarokkk\|vita]]) 2014. január 20., 10:49 (UTC)

	-- [[VeresSzentkiralyiAndras\|dnet]] - 2010.05.24.		-- [[VeresSzentkiralyiAndras\|dnet]] - 2010.05.24.

Tarokkk: /* Csatornahuzalozás k rétegen a Manhattan modellben */

2014-01-20T10:48:28Z

Csatornahuzalozás k rétegen a Manhattan modellben

← Régebbi változat		A lap 2014. január 20., 12:48-kori változata
33. sor:		33. sor:
	Az előző feladathoz képest annyit változtatunk a terhelés mérésén, hogy nem rácspontok között, hanem rácspontokon keresztül menő egyeneseken mérjük. A legnagyobb terhelés értékét d-vel jelöljük ez a feladat sűrűsége. Ekkor egy megoldás minimális szélessége <math>\lceil d / v \rceil</math>. Emellett minden ilyen feladat megoldható <math>\lceil d / (f - 1) \rceil</math> szélességben (ha f ≥ 2), és ilyen megoldás található is lineáris időben.		Az előző feladathoz képest annyit változtatunk a terhelés mérésén, hogy nem rácspontok között, hanem rácspontokon keresztül menő egyeneseken mérjük. A legnagyobb terhelés értékét d-vel jelöljük ez a feladat sűrűsége. Ekkor egy megoldás minimális szélessége <math>\lceil d / v \rceil</math>. Emellett minden ilyen feladat megoldható <math>\lceil d / (f - 1) \rceil</math> szélességben (ha f ≥ 2), és ilyen megoldás található is lineáris időben.

	~~TODO: bizonyítás~~		==== Egy csatornahuzalozási feladat Manhattan-modellbeli megoldásának minimális szélessége legalább <math>\lceil d / v \rceil</math> ====
			Tegyük fel, hogy van w szélességű huzalozás. Mivel d terhelésű egyenest csak a vízszintes rétegek soraiban metszhetnek szakaszok és ilyen sorból vw van, azért <math>
			vw \geq d \rightarrow w \geq \lceil d / v \rceil</math>

	-- [[VeresSzentkiralyiAndras\|dnet]] - 2010.05.24.		-- [[VeresSzentkiralyiAndras\|dnet]] - 2010.05.24.

Unknown user: Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel23}} ==!! A (részletes) huzalozási feladat, alapfogalmak (terminál, net, Manhattan modell, megszorítás nélküli modell). Gall…”

2012-10-22T09:44:04Z

Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel23}} ==!! A (részletes) huzalozási feladat, alapfogalmak (terminál, net, Manhattan modell, megszorítás nélküli modell). Gall…”

Új lap

{{GlobalTemplate|Infoszak|RopiTetel23}}

==!! A (részletes) huzalozási feladat, alapfogalmak (terminál, net, Manhattan modell, megszorítás nélküli modell). Gallai algoritmusa. Csatornahuzalozás k rétegen a Manhattan modellben.==

__TOC__

===A huzalozási feladat, alapfogalmak===

Adott egy téglalap alakú áramköri lap, melynek szélein kivezetések helyezkednek el, ezeket '''termináloknak''' nevezzük. A '''netek''' meghatározzák, hogy mely terminálokat kell egymással elektromos szempontból összekötni, csoportonként külön-külön. A huzalok természetesen egy rétegen belül nem metszhetik egymást, valamint minimális távolságot is kell tartani egy-egy huzal között. Utóbbi probléma négyzetrács alkalmazásával oldható meg, úgy, hogy huzal csak a rács élei mentén haladhat.

Egy huzalozás '''Manhattan-modellbeli''', ha szomszédos rétegeken csak különböző irányú huzalszakaszok futnak, azaz felváltva tartalmaznak függőleges és vízszintes huzalszakaszokat. Ellenkező esetben a huzalozás '''megszorítás nélküli modellben''' van.

===Gallai algoritmusa===

Gallai algoritmusa lineáris időben ad optimális (minimális huzalozás-szélességet felhasználó) megoldást Manhattan-modellben az egysoros huzalozási problémára, melynél a terminálok az áramköri lapnak csak az egyik oldalán (egy sorban) helyezkednek el.

Az algoritmus menete a következő:

1 A neteket bal szélső termináljuk szerinti növekvő sorrendbe rendezzük.
1 Ha az 1 ... i-1 sorszámú netek huzalozása kész
** ha az i. net vízszintes huzalszakasza belefér valamelyik "megkezdett" sorba, ott elhelyezzük
** ha nem, új sorba tesszük

Ha terminálsor vonalára merőleges tetszőleges egyenes mentén mért terhelést az egyenest metsző netek számaként definiáljuk, az algoritmus lineáris időben elvégzi a huzalozást úgy, hogy annak szélessége megegyezik a legnagyobb terhelésű egyenes terhelésével.

TODO: bizonyítás

===Csatornahuzalozás k rétegen a Manhattan modellben===

Csatornahuzalozásnak az olyan feladatokat nevezzük, ahol a terminálok a lap két szemközti szélén helyezkednek el. A rétegek száma előre meghatározott, cél a feladat megoldása minél kisebb szélességben. A rétegeket - mivel Manhattan-modellben dolgozunk - függőleges és vízszintes huzalozású rétegekre bontjuk, ezek számosságát f-fel ill. v-vel jelöljük (f + v = k).

Az előző feladathoz képest annyit változtatunk a terhelés mérésén, hogy nem rácspontok között, hanem rácspontokon keresztül menő egyeneseken mérjük. A legnagyobb terhelés értékét d-vel jelöljük ez a feladat sűrűsége. Ekkor egy megoldás minimális szélessége <math>\lceil d / v \rceil</math>. Emellett minden ilyen feladat megoldható <math>\lceil d / (f - 1) \rceil</math> szélességben (ha f ≥ 2), és ilyen megoldás található is lineáris időben.

TODO: bizonyítás

-- [[VeresSzentkiralyiAndras|dnet]] - 2010.05.24.

[[Category:Infoszak]]