„Rendszeroptimalizálás, 23. tétel” változatai közötti eltérés
Ú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…” |
|||
| 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. | ||
==== 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. | ||