„Rendszeroptimalizálás, 24. tétel” változatai közötti eltérés
Új oldal, tartalma: „{{GlobalTemplate|Infoszak|RopiTetel24}} ==!! Csatornahuzalozás a kétrétegű, megszorítás nélküli modellben. Switchbox-huzalozás, alsó becslés a rétegek sz…” |
Nincs szerkesztési összefoglaló |
||
| 12. sor: | 12. sor: | ||
Először egy speciális esetet bizonyítunk be, melyben minden netnek pontosan egy északi és egy déli terminálja van. A huzalozás során a következő sorrendben kötjük be a neteket: | Először egy speciális esetet bizonyítunk be, melyben minden netnek pontosan egy északi és egy déli terminálja van. A huzalozás során a következő sorrendben kötjük be a neteket: | ||
* ÉK-DNy típusú netek (/ alak): déli terminálok x koordinátája szerinti növekvő sorrendben, így nem metszik egymást | |||
* egyenes bekötések (| alak): sorrent érdektelen, nem metszhetik egymást | |||
* ÉNy-DK típusú netek (\ alak): északi terminálok x koordinátája szerinti növekvő sorrendben | |||
Végül az általános esetet visszavezetjük a speciálisra oly módon, hogy amennyiben valamelyik oldal (északi, déli, vagy mindkettő) nem felel meg a fenti speciális esetnek, a megfelelő terminálokat a [[RopiTetel23|23. tételben]] említett Gallai-féle algoritmussal egysoros huzalozásként kezelve összekötjük, majd netenként "kivezetünk" egy függőleges huzalt, így már alkalmazható a speciális esetre kidolgozott algoritmus. | Végül az általános esetet visszavezetjük a speciálisra oly módon, hogy amennyiben valamelyik oldal (északi, déli, vagy mindkettő) nem felel meg a fenti speciális esetnek, a megfelelő terminálokat a [[RopiTetel23|23. tételben]] említett Gallai-féle algoritmussal egysoros huzalozásként kezelve összekötjük, majd netenként "kivezetünk" egy függőleges huzalt, így már alkalmazható a speciális esetre kidolgozott algoritmus. | ||
A lap jelenlegi, 2015. május 25., 13:34-kori változata
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.
!! Csatornahuzalozás a kétrétegű, megszorítás nélküli modellben. Switchbox-huzalozás, alsó becslés a rétegek számára, felső becslés (biz. nélkül).
Csatornahuzalozás a kétrétegű, megszorítás nélküli modellben
Csatornahuzalozásnak az olyan feladatokat nevezzük, ahol a terminálok a lap két szemközti szélén helyezkednek el. Minden ilyen feladat megoldható kétrétegű áramköri lapon, megszorítás nélküli modellben alkalmas (nem feltétlenül optimális) szélességben, ilyen megoldást lineáris időben találhatunk.
Először egy speciális esetet bizonyítunk be, melyben minden netnek pontosan egy északi és egy déli terminálja van. A huzalozás során a következő sorrendben kötjük be a neteket:
- ÉK-DNy típusú netek (/ alak): déli terminálok x koordinátája szerinti növekvő sorrendben, így nem metszik egymást
- egyenes bekötések (| alak): sorrent érdektelen, nem metszhetik egymást
- ÉNy-DK típusú netek (\ alak): északi terminálok x koordinátája szerinti növekvő sorrendben
Végül az általános esetet visszavezetjük a speciálisra oly módon, hogy amennyiben valamelyik oldal (északi, déli, vagy mindkettő) nem felel meg a fenti speciális esetnek, a megfelelő terminálokat a 23. tételben említett Gallai-féle algoritmussal egysoros huzalozásként kezelve összekötjük, majd netenként "kivezetünk" egy függőleges huzalt, így már alkalmazható a speciális esetre kidolgozott algoritmus.
Switchbox-huzalozás, alsó becslés a rétegek számára, felső becslés
Switchbox-huzalozásnak az olyan feladatokat nevezzük, ahol a terminálok a lap mind a négy oldalán elhelyezkedhetnek. Erre az esetre Hambrusch tétele kimondja, hogy tetszőleges k számhoz található olyan feladat, amely nem oldható meg k rétegen még a megszorítás nélküli modellben sem.
TODO: bizonyítás
Alső és felső becslés a rétegek számára
ahol m = max(n / w, w / n), n és w pedig a lap magassága ill. szélessége
-- dnet - 2010.05.24.
