„Rendszeroptimalizálás, 23. tétel” változatai közötti eltérés

(Egy közbenső módosítás, amit egy másik szerkesztő végzett, nincs mutatva)

18. sor:

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 nem, új sorba tesszük

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

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>

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)

@@ 18. sor: / 18. sor: @@
 Az algoritmus menete a következő:
-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.
-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 nem, új sorba tesszük
@@ 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).
-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 &#8805; 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>
 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 &#8805; 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)