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