Построяване на свърх голями алгоритми



страница2/3
Дата31.03.2018
Размер387.29 Kb.
#63983
1   2   3

Фиг. 23.5 Етажен план и производното оформление.a) Дял от правоъгълник претставляващ етаж. b) Оформление с действащи компоненти, съответващи на етажа.c) Хоризонтално ограничителен граф.

припокриващи се страни на оформлението правоъгълник или подправоъгълник, дължината на тези ръбове е 0. Имайте предвид че тези ограничения придвижват два правоъгълника които не се допират но са свързани чрез верига от ръбове с 0-дължина междъ лявата страна от единия и дясната страна от другия, а другия да лежи от двете страни на вертикална линия в оформлението. Това е още едно ограничение по отношение на оформлението, но важно за верноста на алгоритъма претставен подолу за калибриране на нарязване разпределения.

Сега вече имаме машина да се съочи с проблема на интереси.

Етаж оразмеряване: Подчиняват на определени C компоненти, линейна форма функция за всеки компонент, както и план за пода C, намери работа на специфични форми на компонентите, така че областа на оформлението е сведена на минимум.

Stockmayer показа че за общите разпределения на пода, проблема с етажо оразмеряването е NP-complete. Това важи дори ако компонентите са с фиксирана форма, но могат да бъдат ротирани 90. В този случай формата функция на всеки компонент е стъпка функция с най-много две стъпки s(x)= за 0 и s(x)= за x когато размерите на компонента са и с . Въпреки това, за общи планове на специална форма, наречена нарязване разпределения, Stockmaer ни дава полином-временен алгоритъм за разпределение на проблема с оразмеряване, когато продуктите са с фиксна форма но могат да ротираат. Otten общи този резултат всяка линейна форма функция. За наразяване разпределения, в който дял на оформлението правоъгълник могат да се изграждат чрез рекурсивно рязане на правоъгълната област в два под-региона или с помоща на вертикален или хоризонтален сегмент. Рекурсивен метод на разделяне на изграждането, както погоре, се произвежда нарязване на разпределение.



Фиг. 23.6 Разпределение на нарязване

Плана за нарязване етажа може да бъде претставен с бинарни дървета. Коренът на дървото претставлява целия правоъгълник и върху него се етикетират според посоката на првия рязан. Други вътрешни върхове претставляват правоъгълни подрегиони, който трябва да бъдат разделени, а на етикета върху такъв връх е по посока на намаляване. Нивата на бинарните дървета претставляват правоъгълна форма съответстваща на компонентите. Ще претставим форма функция която е стъпка функция от списока на двойки (,s()) за 0 i и =. Тълкуването за всички е x, x . Параметара е броя почивки в процеса. Претставителството на функцията е линейно на броя на прекъсвания. Дадени са стъпка функции, и , за формите на две деца на върха, формата функция, s, за върха ще бъде функция стъпка. Когато посоката на порязока е хоризонтална формата функция може лесно да се добави, която е, s(x)=(x) + (x). Всяка следваща точка пауза за или е точка пауза за s, така че +. Комбиниране на формата функция отнема време O(+).

За изчисляване на функцията формата на нарязване етаж, един просто прави прекосяван постпорядък на бинарните дървета, изчислявайки формата функция на всеки връх от формата функция на децата от връховете. Броя на почивки во формата функция за всеки връх не е повече от броя на почивки во формата функция на нивата от поддървата основани на връха. Нека b да е максималния брой на който и да е форма функция на компонент. Тогава времето за работа на този алгоритъм с n компоненти ще бъде:



T(n) T() + T() + bn

dbn

Кадето d е дълбочината на дървото. Имаме следното:

Когато се има предвид като пример за разпределението оразмеряване-проблема, който съдържа рязане етаж и стъпкови функции като форма мункция за компонентите , има O(dbn)-временен алгоритъм за решаване на формата функция от оформлението правоъгълник.

Скоро Shi, претстави модификация на тази техника, която подобрява времето за работа на небалансираното рязане дървета.



Проблеми с Маршрутизация

Ще обсъдим само найсрещания маршрут модел – Праволинея канал маршрут модел. В този модел оформлението е праволинейно. Регионите на оформлението, който не са опхванати от компонентите са разделени в не препокриващи правоъгълници наричат се канали. Разрешените дялове са ограничени, така че всеки канал има компоненти докосващи хоризонталните му ръбове (хоризонтален канал) или вертикалните му ръбове (вертикален канал). Ръбовете ще бъдат посочени като горна и долна част на канала, без значение дали канала е вертикален или хоризонтален. Правоъгълните ръбове, познати като „левия край” и „десния край” от канала, могат само да докоснат други канали. Тези канали съставлят площта за тел-маршрутизация. Има няколко стратегии за разделяне на маршрутизираната зона в каналите т.е. „определяне” на канала, но повечето използват максимално правоъгълници когато е възможно. Пейона на оформлението става правоъгълник, който е разделен на отделни правоъгълници от два вида: компоненти и канали. (Виж Фиг.23.7.)

23.5 Routing Problems

Ние ще обсъждаме само най-често срещания модел на маршрутизация (рутиране) за общо расположение на клетка- на праволинейни канал маршрута модел. В този модел, оформлението е праволонейно. Регионите на оформлението, които не са обхванати от
компоненти са разделени на не припокриващи се правоъгълника, наречени канали. Резрешените дялове са ограничени, така че всеки канал има само компоненти докосвайки си хоризонталните ръбове (хоризонтален канал)
или вертикални ръбове (вертикален канал). Тези краищата ще бъдат наричани "връхът" и "дъното" на
канала, независимо дали каналът е хоризонтален или вертикален. Правоъгълните ръбове, наричани за нас "левия край" и "десния край" на канала, може само да се докосват до друг канал. Тези канали съставят област за жичен маршрут. Съштествуват няколко стратегии за разделяне на маршрутната област в канали, т.е. определяне на канали, но повечето използват максимално правоъгълници кадето е възможно (т.е. два канала не е възможно да се слеят за да направят един по-голям). Оформената област става правоъгълник който е разделен в под-правоъгълници от два тъпа: компоненти и канали. (виж фиг. 23.7.)

Фигура 23.7 Разделянето на оформление в маршрутни канали и компоненти.



Като се има предвид оформление с определени информационни канали, проблемат с маршрутизацията може да се раздели на два под-проблема. Глобалната маршрутизация е проблемат за избирането кой канал ще бъде използван за осигуряване на междусистемни връзки за всяка мрежа. Актуални пътища не са произведени. Правейки първо глобалната маршрутизация, един може да определи актуалните пътища за жиците във всеки канал оделно. Проблемът на подробна маршрутизация е да се определят реалните пътища и е по-често се нарича "канал маршрут." Разбира се, сегментите от жичния път във всеки канал трябва да се присъединът по краищата на канала за производство на действително взаимно свързване на терминалите. За да се разберът подходите за работа с този интерфейс, трябва да имаме подетална дефиниция за проблемът на каналната маршрутизация, който ние даваме седващ. Проблемът на каналната маршрутизация е определен така, че има първоначални позиционни ограничения само в едно измерение. Спомнете си че ние определяме канали да опират компоненти само на двеуспоредни страни "бръхът" и "дъното" Това е така, че маршрутите на канала ще бъдат ограничени от крайни(терминални) позиции на двете страни. Стандартните проблеми на каналната маршрутизация имат следния вход: правоъгълник (на канала), съдържащ точки (терминали) на определени позиции покрай горния и долния край, съвкупност от мрежи, които трябва да бъдат насочени в канала, и задачите на всеки един от терминалите на канала на една от тези мрежи. Съшто така, две (възможно празни) подгрупи на мрежите са посочени: една съдържаща мрежи чиято маршрутизация трябва да се свържи с левия край на канала и една съдържаща мрежи чиято маршрутизация трябва да се свърже с десния край на канала. Позициите, във кои жици трябва да се пресичат левия и десния край(ръб) не са определени. Размера на канала от левия край до десния край се нарича дължината на канала; размерът от горния край до долния край на канала е широчината на канала. (виж фигура 23.8). Тъй като няма терминали на левия и десня край , ширината често се приема че е променлива, целта е да се намерат пътища за маршрутизация достигайки конекции определени от мрежите и намаляване на ширината на канала. В този случай, мястото неопходимо за жиците определя ширината на канала. Дължината на канала по-често се разглежда като фиксирана, въпреки че има модели на маршрутизация в които е позволено да преминават маршрути извън левия и десния край на канала. Сега можем да обсъдим проблемът (interfacing routes) в каналните краеви. Има два главни подхода за справяне с интерфейса на канали. Един от тях е да се определят каналите, така че всички съседни канали формират „Т” -та , а не „+” –ове. Тогава ако каналния маршрут е направен за основата на „Т” първо, позициите на пътиштата напускащи основата на „Т” и влизането в напречното парче на „Т” са фиксирани от маршрута на основата и могат да бъдат третирани като крайни(терминални) позиции за напречното парче на „Т”. Използването на този подход поставя ограничения по отношение на маршрутния ред на каналите. Ние можем да проектираме тези ограничения използвайки насочен график: Има връх (теме) vC за всеки канал C и един край(ръб) от vA до vB ако канал А и канал В граничат с канал А като основа на „Т” и с канал В като напречното парче на „Т”. Краят(ръбът) от vA до vB представлява че кана А трябва да бъде маршрутизиран преди канал В. Този график трябва да е ацикличен за серия от ограничения по наредба маршрута да бъде изпълним(възможен). Ако графката не е ациклична друг метод трябва да бъде използван да се справи със некои от каналните интефейси.

Фигура 23.8 Канал А. Мрежния интерфейсинг във левия край(ръб) и деснияа край(ръб) не са в

Определения ред.

Плановете Slicing floor(разделяне етажи) са много добри за този подход защото ако всяко парче(slice) е дефинирано да бъде канал, тогава графика за ограничение на канлния ред (channel order constraint graph) щте бъде ацикличен. Втора алтрнатива за справяне с интерфейсите на каналите е да се определи специален вид на канал, наричан switch box (превключвател), който е ограничен от крайни (терминални) локации на всички четири страни. В този вариант, някои или всички от стандартмите канали граничат (достигат) switch boxes (превключватели). Специялни алгоритми са използвани за да направат превключения маршрут(switch box routing), от, практически казано, това е по-труден от стандартния канален маршрут.



23.6 Глобална маршрутизация

Тъй като глобалните маршрути не е необходимо да произвеждат актуални пътища за жици (проводници), каналите могат да бъдат моделирани от графиката наричана “channel intersection graph” (графика на пресичане на канала). За всеки канл, проект на терминалите лежи върху горната и долната част на канала върху средната линия на канала. Всеки канал може да бъде разделен на сегменти от позициите на тези проектирани терминали. Графиката на пресичане на канала е една ненасочена графика със един връх (теме) за всеки проектиран терминал и един връх (теме) за всяко пресичне на каналите. Има един ръб (край) за всеки сегмент на канал, който свързва двойка върхове представляващи терминали и/или пресичания на канал ограничаващ (очертаващ) сегмента. Дължина и капацитет може да се дава на всеки ръб, представляващ, съответно дължината (растоянието) между краевите на каналния сегмент и ширината на канала. Различни версии на глобалната маршрутизация използват един или двата параметри на дължината и капацитета. Като се има в предвит графиката на пресичане на канала, проблемат за намиране глобални маршрути за набор от мрежи се превръща във проблем за намиране Щтайнерово дърво във графика на пресичането на канала за терминалите на всяка мрежа. По-рано в тази глава, ние дефинирахме (определихме) Щтайнерово дърво за точки в равнината. За обща графика G = (V, E) , Щтайнерово дърво за подмножество на върховете U С У е сет от ръбове на G който формира дърво във G и чиито набор от крайни точки съдържа сет U. Различни версии на проблема на глобалната маршрутизация се произвеждат от ограниченията и оптимизация на използваните критерии. Например, един едноставно може да поиска за минимална дължина Щтайнерово дърво за всяк мрежа, или един може да поиска за набор от Щтайнерови дървета които не нарушават капацитетните ограничения и има тоталната минимална дължина. За всеки ръб капацитета използван от набор Щтайнерови дърва е броя на Щтайнерови дърва съдържащи този ръб; това не трябва да бъде поголямо от капацитета на ръба. Друг избор е да не се има ограничения на капацитета на ръбовете, но да се намали максималния капацитет използван за всеки ръб. Като цяло, всяка комбинация от ограничения и расходни функции на дължина и капацитет можат да се използват. Както и да е, независимо от критерия, проблемат с глобалната маршрутизация е неизменно NP-пълен. По-подробна дискусия за вариациите на проблема и неговата сложност може да се намери в (19). Там има повече суфистицирани алгоритми за проблема със Щтайнеровото дърво. Тук ние ще обсъдим 2 техники базирани на основни графични алгоритми: широчина-първо търсене и Дийкстра единичен-источник най-краткия път алгоритам (Dijkstra's single-source shortest path algorithm.). Минималният Щтайнерово дърво проблем е самият NP-пълен. (виж стр. 208-209 във (7)). Ето защо един подход към глобалната маршрутизация е да се избегне намиране Щтайнерови дърва със разделяне на всяка мрежа на колекция от точка-до-точка конекции. Един начин да се направи това е да се намери минимум Евклидово или праволинейно spanning tree за терминалите принадлежащи на всяка мрежа (игнорирайки каналната структура), и използването на ръбовете на това дърво да се определят point-to-point (точка-до-точка) конекции. Тогава един може да ползва Дийкстровия single-source shortest path algorithm на графика на пресичане на канала за да се намери най-краткия път за всяка point-to-point (точка- до-точка) конекция. Пътища за конекции от истата мрежа които споделят ръбове могът да сляти, образувайки Щтайнерово дърво. Ако не съществуват ограничения на капацитета на краищата, качеството на това решение се ограничава само от зближаването на минимално Щтайнерово дърво от избрана колекция пътеки point-to-point (точка- до-точка). Ако има ограничения на капацитета, тогава след решаване на всеки проблем най-кратък път, един трябва да премахне от графиката на пресичане на канала ръбовете чиито използван капацитет е почти еднакъв на ръбовия капацитет. В този случай, редъ(order) вкои мрежи и терминали в рамките на мрежата са маршрутизирани е значителн. Един може подобре да приближи Щтайнерови дървета за мрежите от, на всчка интерация за конекции в рамките на една мрежа, избирайки терминал всеоште не конектиран с някои други терминали във мрежата като източник на алгоритама Dijkstra's. Тий като този алгоритъм изчислява най-краткия път до всяко друго теме(връх) във графиката от източника, най-краткия път който се конектира до всяко друго теме във графиката за каналните пресичания вече е на път конектирайки терминали от мрежата които могат да бъдат иползвани. Разбира се има и вариации на тази идея. За всеки график, широчина-първо търсене (breadth-first search) от темето v ще намери бай-кратък път от v до всяко друго теме във графиката когато дължината на всеки ръб(край) е 1. breadth-first search взима време O(|V| + |E|) в сравнение с най-добрите в най-лошия случай времето на работа познато за алгоритъма на Dijkstra's: O(|V| log |V| + |E|) време. Съшто така са много лесни за прилагане. breadth-first search може да се стартира от няколко върха едновремено, така че всички терминали на мрежата могат да бъдат стартиращи точки (starting points) от търсене едновременно. Ако тя е адекватна, за да видите всички сегменти на канала с еднаква дължина, тогава ръбовите дължини всички могат да бъдат с възложена стойност 1 и breadth-first search може да се ползва. Това може да възникне когато треминалите са равномерно разпределени и така разделят канали на приблизително равни по дължина сегменти. Като алтернатива, един може да обави нови темета във графиката на канални пресичания за понататъчно разлагане на каналните сегменти във сегменти единица-дължина (unit-length segments). Това може значително да увеличи |V| и |E| така че те да са пропорционални на размерите на подразбиращтата се мрежа опреляща единица за дължина, а не броя на канали и терминали във проблема. Както и да е това позволява , един да използва breadth-first search да изчисли най-кратки пътища докато моделира актуалните дължини на каналите. Всъщност breadth-first search е разработена от Лий [16]7 за маршрутизация на платки в точно този начин. Той разработи цялото табло от мрежовата графика, и моделира пречки към маршрутните пътища като мрежни темета кито липсват във графиката. Всеки жичен маршрут беше основан от извършване breadth-first search във мрежовата графика.

23.6 Канална маршрутизация

Каналната маршрутизация не е един единствен проблем, а по-скоро фамилия от проблеми базирашти се на допустимите пътища за жици в канала. Ще ограничим нашата дискусия на grid-based маршрутизация. Докато двете grid-free праволинейни и неправолинейни маршрутни техники съществуват , най основните техники са grid-based. Предполагаме че има grid (мрежа) в основата на канала, страните на канала лежът на мрежните (grid) ръбове(краеви) , терминалите лежът на мрежните(grid) точки , и всички маршрутни пътища трябва да следват ръбовете (краевите) във grid ( мрежата). За улеснение на обсъждането , ние ще се отнасяме към каналните дирекции като мислим че каналите са ориентирани със техната дължина хоризонтално. Вертикалните сегменти от grid (мрежата) които дейставт от върхъ до дънното на канала се наричат колони. Хоризонталните сегменти от мрежата които които действат от левия край до десния край (ръб) на канала се наричат писти (tracks). Ще вземем в предвит проблемите с каналната мрашрутизация които позволяват ширината на канала да варира. Поради това броят на колоните, определящи каналната дължина, ще бъде фиксиран, но броят на пистите ( tracks), определящи ширината на канала , ще варира. Целта е да се намали броя на траките използвани да маршрутизират канала. Следващата особеност е базирана на колко слоеви за рутиране са предположени. Ако има ℓ слоеви за рутиране, тогава има и ℓ опковани копии на мрежата (grid), една за всеки слой. Маршрутите които ползват същия ръб (край) на различен слой не си взаимодействат и се считат за несвързани. Маршрутите сменят слоя в мрежовите ( grid) точки ( points). Точните правила за това как маршрутите могат да сменат слоя варират, но най-често използван е да видите маршрута който отива от слой i във слой j (j > i) в мрежова точка като използвани слоеви i + 1,….,j – 1 както и в мрежовата точка. Едно може да раздели проблема с каналната маршрутизация на два под-проблеми: намиране на Щайнерови дърва в мрежата които постигат интерконекцията, както и намиране задача във слоя за всеки ръб във всяко Щтайнерово дърво така че резултатите на маршрутите са законни. Един модел за канална маршрутизация за който се прави това разделяне е knock-knee маршрутизацията.

По предизвикателен проблем е чрез намаляване, което претцтавлява да се намери легална задача за слоя която намалява броя на grid точките, във слоя който са се появили промени. Този проблем е също решим във полиномно време все докато нито едно от Щтайнеровите дървета съдържат four-way split ( техническо ограничаване на алгоритъма). За повече от два слоя, двете слоеви задачи и чрез намаляване са NP-изпълнени.

Избрали сме да говорим за два модела на маршрути във детайли: еднослойна маршрутизация (single-layer routing) и двуслойна Манхатън маршрутизация (two-layer Manhattan routing). Моделите на маршрутизация които позволяват повече от двеслойна маршрутизация, наречени мултислойни модели, стават все по-популярни заштото технологията е в състояние да предостави повече слоеве за жиците.

Манхатън маршрутизация

Манхатън маршрутизацията е доминантния двуслоен модел. Датира още от печатените платки. Доминира защото определя всички вертикални жични сегменти да бъдат на един слой, а всички хоризонтални жични сегменти да бъдат на друг слой. Поради това, хоризонталния маршрутен път и вертикалния маршрутен път могат да се кръстосват без взаимодействие, но всеки път който завива в мрежова точка е на двата слоя в тази точка и няма път който за несвързана мрежа да ползва тази точка. Въпреки Манхатън маршрутизацията предоставя по прост модел на легални маршрути, в резултат проблема с канална маршрутизация е NP-изпълнен. Важно на долната граница на каналната ширина е каналната плътност. Плтноста на било коя вертикална линия пресичаща канала е броя на мрежите които имат терминали и на ляво и на дясно на вертикалната линия. Интерпретацията е това че всяка мрежа трябва да има най-малко една жица пресичаща вертикалната линия, по този начин броя на траките равен на плътноста във вертикалната линия е неопходим. За колони, мрежи които съдържат терминали на колона се включват в плътноста , освен ако мрежата не съдържа точно два терминала и те са върхъ и дънното на колоната. Кналната плътност е максималната плътност на било кое вертикално сечене на канала. На практика , проблемът с каналната маршрутизация е решен с евристични алгоритми които намират маршрути давайки на канал ширина в рамките на една или две от плътностите, въпреки че такива перформанси вероятно не са постижими. Ако канален маршрут няма горен и долен терминал на една колона, тогава броя на траките еднакъв на каналната плътност и маршрута постиггащ тази плътност мож да бъде решен O(m + n log n) време, където n е броя на мрежите а m е броя на терминалите. В рамките на тези ограничения проблема на канална маршрутизация става еквивалентен с проблема на интервал графика оцветяване. Еквиваленцията се базира на наблюудението на това че ако колона не съдържа терминали на свойте връх и дънно , тогава било кой терминал може да се конектира със било коя трака със вертикален сегмент който не е в конфликт с някой друг път. (виж фигура 23.9). всяка мрежа може да ползав един хоризонтален сегмент, който обхваща всички колони съдържашти си терминали. Въпроса е да се оаковат тези хоризонтални сегменти във минимален брой на траки така че сегменти да не се пресичат. Еквивалентно целта е да се боядисат сегментите със минимален брой цветове така че да няма два сегмента които се присичат да са със съшти цвят. Следователно, ние имаме връзката до интервалните графики, които са набор от темета които представляват интервали на линия и ръбове помежду темеата на пресичащи се интервали.

Фигура 23.9 конектиране с траки без конфликти. Всяка от мрежите може да достигне било коя от траките с вертикален сегмент във колоните съдържащи ги терминалите.

Един класически ненаситен алгоритъм определя набор от I интервали до d траки , кадето d е канална плътност. Интервалите са поставени във траките наредени от тяхните леви endpoints всички траки са напълнени с интервали от ляво към дясно . набора от интервални endpoints е първо сортиран така че комбинирания ред от леви (стартиращи) endpoints и дясни (крайни ) endpoints е познат. Във всяка точка във алгоритъма, има траки съдържащи интервали които всеоще не са свършили и траки които са свободни да приемат нови интервали. Queue(опашка) F се използва да държи свободните траки. Непроцесираните endpoints са съхранени във оашка отточки ,P, сортирани от ляво на дясно. Функцията Dequeue (де опашка) е стандартна операция за премахване на Queue . алгоритъма започва със само една трака и додава траки колко е нужно , променлива t държи бройката колко траки са ползвани.

Interval-by-interval assignment (/)

1 Sort the endpoints of the intervals in / and build queue P

2 t ← 1


3 Free track 1

4 while P is not empty

5 do p ← Dequeue(P)

6 if p is the left endpoint of an interval i

7 then do if F is empty

8 then do t ← t + 1

9 Put i in track t

10 else do track ← Dequeue (F)

11 Put i in track

12 else do Free the track containing the interval whose right endpoint is p

За да се види че този алгоритъм никога не ползва повече от броя на траките еднакви на плътноста d на канала, забележи че когато t е увеличено във линия 8 това е така защото текущите траки всички съдържат интервали които всеоще не са свършили когато лявата endpoint p получена в линия 5 се взима в предвит. Затова когато t е увеличено за последен път до стойност w , всички траки номерирани по-малко от w съдържат интервали които обхващат текущия p : d ≥ w. След като няма препокрити интервали сместени в съща трака w = d. Поради това алгоритъма намира оптимална тракова задача. Преработването да се намери интервал за всяка мрежа отнема време O(m) и задача Interval-by-interval има време O ( | I | log | I |) = O (n log n ) до сортиране на крайни точки I.

След като един позволява терминали на двете на върхъ и на дънното на колоната , един запознава нови набори от огранчения наречени вертикални ограничения. Тези ограничения залавят факта че ако мрежа i на върхъ на колона c и мрежа j има терминал на на дънното от колона c , след което за да се конектират тези терминали към хоризонтални сегменти използвайки вертикални сегменти във колона c , хоризонталния сегмен за i трябва да бъде над хоризонталния сегмент за j . един може да конструира график който има теме , за всяка мрежа i и директния ръб помежду и , ако има колона която съдържа терминал във i на върхъ и терминал във j на дънното. Ако един счита само маршрути които ползват най-много по един хоризонтален сегмен за мрежа, тогава графиката на ограничение представлява ред ограничения на траките използвани от хоризонтални сегменти. Ако вертикалниата графика на ограничения е циклична , тогава маршрутът неможе да бъде завършен със един хоризонтален сегмент за мрежа. ако вертикалната графика на ограничения е ациклична тогава е NP-изпълнена за да определи дали маршрута може да бъде постигнат в даден брой траки. Понапред , дори и оптимален маршрут използвайки един хоризонтален сегмент за мрежа е установено, броя на изисканите траки е значително по-голям от това което може да се получи използвайки повече хоризонтални сегменти. Поради тази причина , практически алгоритмите за каналено маршрутизаиране позволяват маршрутите за всяка мрежа порции от неколку траки. Всеки път когато маршрута се сменя от една трака на друга използва секции от колони this is called a jog. ( виж фиг. 23.10).

Манхатънската канална маржрутизация остава NP-приключено, дори ако неограничени jogs са позволени.Ето защо, на практика алготитама на маршрута за този проблем исползва heuristics.Найраните от тях е то Deutsch.Deutsch позволяава на маршрутата за мрежата да слага само в една колона която съдържа терминал на нета; той нарича тези jogs ”doglegs”. Този подход ефективно разчупва всяка мрежа на две помрежи, и може да се определи след това вертикална крива в която всеки връх претставлява подмрежа.Алгоритама на Deutch e изменение на база интервал-от-интервал задача наречена track-by-track задача.Тя запълва от ляво на дясно,но и запълва една track до края преди да почне да запълва следващата.Основния алгоритъм на Deutsch е track-by-track задача,но не възлага интервал за подмрежа на track ако заданието би нарушило вертикалното ограничение.Со промяната на основнич алгоритъм се опитва да се подобри нейната ефективнос и намаляване на броя на doglegs.Класа на алготми базиран на сортиране на интервали е известен и като ляв-край-алгорими.

Манханатнската канална маршрутизавия е можеби най-широко исползваният маршрутен модел и са разработени много алгоритми по този модел. Алгоритамът колона-от-колона пръвоначално е бил предложен от Rivest и Fiduccia I e наречен „алчен“ рутер. Този рутер маршрутизира всички мрежи едновременно. Той започва от най-лявата колона на канала и продолжава на дясно. Тъй като започне от ляво на дясно създава, унищожава и и продолжава хоризонтални сегменти на мречите в канала. С исползване на подхода, лесно е да се въведе jog за мрежа в сяка колона. На всяка колона, алгоритъмът свързва терминалите в горната и длната част на хоризонталните сегменти на мрежите си, като се започн нови сегменти когато е неопходимо, и завършва сегменти когато то е оправдано. На всяка колона за всяка продолжителна мрежа с терминали на дясно тя може да сиздаде jog за да донесе хоризонтален сегмент на маршрута поблизу до края на канала съдържащ следващтия терминал от дясно. По този начин алгоритъмът работи като „поглед напред“ при определяне на това, коя леда да исползва за бсяка мрежа на всяка колона. Алгоритъмът е всъшност рамка с параметри, които могат да се регулират. Той може да създаде, за една мрежа, няколко хоризонтални сегменти, които преминават през една и съща колонаи може да продолжи маршрутите извън левия и десния краъ на канала. Тя е много гъвкава рамка, която позволява на много конкуриращи се критерии да бъдат разгледани и позволява взаиомдействието на мрежи по-пряко от стратегии, които маржрутизират една мрежа към момента. Много маршрутни инструменти са приели този подход.

Въпреки че еднослойния канал на маршрута играе роля при определяне на маршрута на многослойни канали,най-голямото му значение идва от факта, че дори и в най-общ вид може да бъде решен в оптимално време.Има богата теория за еднослойната подробна маршрута ,че е разработена не само за канална маршрутизация, но и за маршрутизация на по-общи региони.Първите алгоритмични резултати за еднослойна канална маршрута са от Томпа,който го разглежда проблема на речната маршрута.Проблемат на речната маршрута е проблем в който всяка мрежа съдържа точно два терминали,един в най-горния край на канала и един в долния край на канала.Мрежите имат терминали по същтия ред в горния и долния край на канала-изискване на проблема е да се навигационира в един слой. Томпа счита непринуден жичен път и даде Ο(n2) -време алгоритъм за n мрежи за да тестват способноста и да намерят начин, коъто минимизира както индивидуалната дължина на проводника така и общата дължина на проводника, когато ширината на канала е определена. Алгоритамът може да се исползва като подпрограма в двоично търсене за да разбереме каква е мнималната дължина на канала O(n2logn) -време. Томпа също така предлага как да се промени неговия алгоритъм за праволинеен случай. Долев изгражда върху теорията на Томпа и представлява за праволинеен случай O(n)-времев алгоритъм за изчисление на минималната ширина на канала и O(n2)-времев алгоритъм за действително производство на праволинейна машрутизация. Разликата в работното време идва от факта ,че маршрута може да има действително n сегменти на мрежа , и по този начин ше измине O(n2)-време да генерира. Тестването на способноста на разгром може да бъде направена чрез изследване на серия от ограничения на канала. Резултатите са обобщени в няколко терминални мрежи от Greenberg и Maley, кадето времето за изчисляване на минималната ширина е линейна с броя на терминалите.

Сега ще представиме теорията,която позволява ширината на канала на речната маршрута да се изчисляава в линейно време. Сърцето на теорията в наблюдението, че за речната маршрута нарязаните линии са различни от вертикалните линии които определят плтноста на канала, също така да допринесе за по-ниска граница на ширината на канала. Тази горна граница след това се проявява и каато 6горна граница. Индексирането от ляво на дясно ,позволява i тата от маршрутния канал, 1 ≤ I n, да се обозначава със двойката (ai,bi) където ai е хоризонталното положение на терминала си от горната час на канала и bi е хоризонталното положение на терминала си от долната част на канала. Има k+1 мрежи които трябва да пресечът границата. Измерването на пистите от 0о до 180о, ако линиите имат склонове ≥90о, тугава k+1 мрежи трябва да минат вертикалната (90о) линия на bi, и те трябва да бъдат k+1 пъта. Ако линията има склонове <90о и >45о, тогава всяка вертикалнен сегмент на мрежата, който пресича нилията може да се свърже с хоризонтален сегмент на мрежата коъто трябва да я пресича линията и коъто не може да бъде исползван от друга мрежа. Поради това, линията трябва да пресича k+1 пъта. И накрая. Ако линията има наклон ≤45о,тугава всеки хоризонтален сегмент на мрежата който преминава линията може да се свърже с вертикален сегмент на мрежата който трябва да преминава линията и коъто не може да бъде исползван от дръга мрежа. И накрая, трябва да има k+1 колони които преминават линията т.е., ai+k-bik. По същтия начин, чрез определяне на линия от bi+k до ai, заключаваме k+1 пъта са неопходими освен ако bk+i-aik. В случай когато k=0, ai трябва да е еднакво на bi без да се изискват хоризонтални пътища. Въз основа на това наблюдение, може да се докаже че минималния брой на пътиящта t се изисква истанция от речната маршрутизация е най-малкото t така че за всички 1≤in-t.

bi+t-ait (1)

и

ai+t-bit (2)



За да го намереме мимимума t за линеарно време, отбелазваме че ai+k+1≥ai+k+1 и bi+k+1≥bi+k+1.

Ето защо


Ако bi+k-aik тогава bi+k+1-ai≥bi+k+1-aik+1 (3)

И

Ако ai+k-bik тогава ai+k+1-bi≥ai+k+1-bik+1. (4)



Ето защо можеме да започнеме с t=0 и да търсеме нарушени ограничения от i=1 до n-t; всеки пит ограничение от формата (1) и (2) са нарушения, увеличаваме t за едно и продолжаваме со търсенето; t не може да бъде поголяамо от n. Нека N означава множеството от мржи в канала речната маршрутизация, |N|=n.Следващтия алгоритъм изчислява минималния брой на пътища неопходими за да се маршутизира канала.

  1. i 1

  2. t ← 0

  3. Каталог: saa
    saa -> Вероятностни алгоритми Цел: Упражняване в създаването и програмната реализация на вероятностни алгоритми Теоретична част
    saa -> Лекция №2 алгоритмично-програмни конструкции видове алгоритми
    saa -> Дървета Цел
    saa -> На снимката саксофонистът е Миньо Георгиев, акордеон Диньо Льолев, Пенка Манолова е но-ниската от двете певици. Снимката е от дъщерята на Стойчо Кузмов и е направена на Чирпанския панагир
    saa -> Евристически алгоритми
    saa -> Лекция №4 с о р т и р а н е и с м е с в а н е същност на сортирането
    saa -> Сортировка чрез вмъкване Същност на алгоритъма
    saa -> Конспект Синтез и анализ на алгоритми и програми


    Сподели с приятели:
1   2   3




©obuch.info 2024
отнасят до администрацията

    Начална страница