Rendszeroptimalizálás, 23. tétel

Ez az oldal a korábbi SCH wikiről lett áthozva.

Ha úgy érzed, hogy bármilyen formázási vagy tartalmi probléma van vele, akkor, kérlek, javíts rajta egy rövid szerkesztéssel!

Ha nem tudod, hogyan indulj el, olvasd el a migrálási útmutatót.

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

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ő:

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

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

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 $vw\geq d\rightarrow w\geq \lceil d/v\rceil$

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

TODO

--Tarokkk (vita) 2014. január 20., 10:49 (UTC)

-- dnet - 2010.05.24.