Studopediya

КАТЕГОРИЯ:


Астрономия- (809) Биология- (7483) Биотехнологии- (1457) Военное дело- (14632) Высокие технологии- (1363) География- (913) Геология- (1438) Государство- (451) Демография- (1065) Дом- (47672) Журналистика и СМИ- (912) Изобретательство- (14524) Иностранные языки- (4268) Информатика- (17799) Искусство- (1338) История- (13644) Компьютеры- (11121) Косметика- (55) Кулинария- (373) Культура- (8427) Лингвистика- (374) Литература- (1642) Маркетинг- (23702) Математика- (16968) Машиностроение- (1700) Медицина- (12668) Менеджмент- (24684) Механика- (15423) Науковедение- (506) Образование- (11852) Охрана труда- (3308) Педагогика- (5571) Полиграфия- (1312) Политика- (7869) Право- (5454) Приборостроение- (1369) Программирование- (2801) Производство- (97182) Промышленность- (8706) Психология- (18388) Религия- (3217) Связь- (10668) Сельское хозяйство- (299) Социология- (6455) Спорт- (42831) Строительство- (4793) Торговля- (5050) Транспорт- (2929) Туризм- (1568) Физика- (3942) Философия- (17015) Финансы- (26596) Химия- (22929) Экология- (12095) Экономика- (9961) Электроника- (8441) Электротехника- (4623) Энергетика- (12629) Юриспруденция- (1492) Ядерная техника- (1748) Arhitektura- (3434) Astronomiya- (809) Biologiya- (7483) Biotehnologii- (1457) Военни бизнесмен (14632) Висока technologies- (1363) Geografiya- (913) Geologiya- (1438) на държавата (451) Demografiya- ( 1065) Къща- (47672) журналистика и смирен (912) Izobretatelstvo- (14524) външен >(4268) Informatika- (17799) Iskusstvo- (1338) историята е (13644) Компютри- (11,121) Kosmetika- (55) Kulinariya- (373) културата е (8427) Lingvistika- (374) Literatura- (1642) маркетинг-(23702) математиците на (16968) Механична инженерно (1700) медицина-(12668) Management- (24684) Mehanika- (15423) Naukovedenie- (506) образователна (11852) truda- сигурност (3308) Pedagogika- (5571) Poligrafiya- (1312) Politika- (7869) Лево- (5454) Priborostroenie- (1369) Programmirovanie- (2801) производствено (97 182 ) индустрия- (8706) Psihologiya- (18388) Religiya- (3217) Svyaz (10668) Agriculture- (299) Sotsiologiya- (6455) на (42831) спортист строително (4793) Torgovlya- (5050) транспорт ( 2929) Turizm- (1568) физик (3942) Filosofiya- (17015) Finansy- (26596) химия (22929) Ekologiya- (12095) Ekonomika- (9961) Electronics- (8441) Elektrotehnika- (4623) Мощност инженерно ( 12629) Yurisprudentsiya- (1492) ядрена technics- (1748)

Модул 2

лекции

"Усъвършенстваните модели и алгоритми за физическа синтез"

дисциплина
"Базови модели и алгоритми в VLSI CAD"

за обучение на майстори на PLO Ниу
"Физическата дизайн на микро и нанометър VLSI CAD"

Профил на "Компютърно проектиране"

Лекция 5 насочено графика. Двустранен графика. Циклично. Hypergraphs. Претеглени графики. Граф Кьониг. Ойлер графика. Hamiltonian графика. Планарна графика. Planarization и предизвикателства на planarization графики.

Съдържание:

1. Въведение.

2. Определения. Path цикъл.

3. Основно и велоалея.

4. Режисьор графики.

5. двустранен графика.

6. Hypergraphs.

7. претеглени графики.

8. Euler път и броя на цикъл.

9. Хамилтонов път и броя на цикъл.

10. Равнинни графики.

Освен обичайните графики в проблеми на физическата синтез често използва специални видове графики. Тези графики позволяват по-пълна картина на модела IP, или по-точно връзката между елементите на дисплея на схемата. Специалните видове графики са насочени графики - графики, чиито краища са насочени от един връх в друг двустранни графики или графики Кьониг, чиито върхове са разделени на две подгрупи. Циклично, Hamiltonian и Ойлер графики, които съдържат цикли и начинът на специален вид. В допълнение, за да отчита не само свойствата на върховете, т.е. обекти и връзки между тези обекти, за претегляне на ребрата, причинявайки претеглените графиките, както и за изолиране на семействата на върхове са често използвани hypergraphs. След това ще разгледаме тези групи в детайли.

Но първо, ще се въведе основните понятия.

С (или верига) в графика е ограничен последователност на върха, в която всеки връх (с изключение на последния) е свързан към следващата в последователността на върха на ръба. Например, помислете за последователността на върховете (V 1, V 2, V 3), принадлежащ към граф G. Ако множеството от ребрата на графиката - Е, включва ребра (V 1, V 2) и (V 2, V 3), оригиналната последователност е верига или от графика. Съответно, изграждането на начините, по които може да се движите, как да изберем подмножество на множеството от върховете, и подмножество на множеството от ребрата. В първия вариант, например алгоритми, базирани графики заобикалят в ширина и дълбочина, на втория - изграждането на обхващаща алгоритъм дърво.

Фигура 1 път в графиката

Един цикъл е път, в която първите и последните върховете са еднакви. Т.е. ако последователността на предишния пример да се добави като първи пик - (V 1, V 2, V 3, V 1), и по този начин графиката G включва ребро (V 3, V 1), като последователност ще бъде цикъл. Когато тази дължина на пътя (или цикъл) е броят на краищата това, представляващо (в този случай - 3). Имайте предвид, че ако върховете ф и V са краищата на ръба, според тази дефиниция, последователността (U, V, U) е един цикъл. За да се избегнат такива "изродени" случаи, да се въведе следните понятия.



Фигура 2. елементарен цикъл

Пътят (или цикъл) се нарича просто, ако ръбовете не се повтарят в него, т.е. подмножество на краищата не включва повече от едно копие на всеки ръб в E. Този цикъл изглежда като смачкан въже пръстен - начин да се пресече, но никога не отиде заедно с всяка друга. Броят на ръбовете, принадлежащи към този път в и от един връх може да бъде всеки. Пътеката се нарича елементарно, ако тя е проста и пикове в него не се повтарят. Този цикъл е подобен на вече изправи въже пръстен. От всеки връх има само един или два ръбове, принадлежащи към тази пътека. Ако този цикъл, от всяка точка на пътя минава точно две ръбове. Лесно е да се види, че:

Всеки път, свързващ два върха съдържа елементарен път, свързващ две еднакви върхове. Всъщност, спомням аналогията с смачкан въже. Ако ние го нарежете на всички места, където се докосне един с друг, и след това се сдружават на минималния брой сегменти, получаваме пряко въже, свързващ две от своя край.

Всеки прост път съдържа не-елементарно елементарен цикъл, след посещение на същия връх два пъти, ние трябваше да се върна и да се опише цикъл, и както вече знаем, всеки цикъл съдържа елементарен цикъл.

Всеки прост линия, минаваща през върха (или ръб) съдържа елементарната (под) линия, която преминава през същия връх (или ръб). В действителност, ако ни елементарен цикъл, проблемът вече е решен, в противен случай тя винаги е възможно да се определи един елементарен подрамка.

Ние наричаме контур елементарен цикъл.

Фигура 3. диграфът

Режисьор действие, насочено графика (диграфът накратко) графика, краищата на която беше дадена посока. Целеви ръбове са посочени като дъга, и някои източници и прости ръбове. Дъг е ръб (V I, V й), че всички пътища, които съдържат V I и V й, тези върхове са в този ред.

Фигура 4. Всички пътища водят от и към к

Често такъв представяне е удобен за случаите, когато върховете в графиката не са равни, например, един от тях има голям потенциал. Броят на пътеки в такива графики, са склонни да бъдат по-малки, защото ненасочена графика съответства всеки път още в посока на реда колона на върховете в който са строго фиксирани. Въпреки това, за удобство, след подаването на насочено графика в намирането на начини за ползване върви срещу посоката на ребрата. Такава техника е да бъде полезно, например, в Схема йерархична представяне. Например, върховете на графиката са компонентите на веригата на различни нива на йерархията. Ако подадете насочено край на графиката като отношението на "безплатно", то отговорът на въпроса дали основните компоненти на една малка, трябва да се направи много работа, защото всеки основен компонент съдържа много малък, което съдържа повече и повече. От друга страна, всяка, съдържаща само малка част от по-голям един. Ето защо, за да разберете дали тя съдържа в него, след като е достатъчно, за да се проследи йерархия.

Фигура схема 5. наслояване

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

Фигура 6. двустранен графиката

Просто двустранно графично е графика Кьониг.

Такава графика обикновено е електрическата схема. В такава схема ясно се разграничават два вида компоненти - верига и елементите на веригата. Ясно е, че веригата не може да комуникират един с друг (в противен случай това би било една единствена верига), същите компоненти не могат да бъдат "просто свързан", между тях би трябвало да работи най-малко една верига. По този начин, компонентите и веригата - идеални кандидати за група от върховете на двустранно графично. Тази графика ръбове ще представляват връзката "е свързана с" една верига или компонент. Също така в Kernighan-Lin раздел алгоритъм на разходите се изчислява като броят на ръбовете на двустранно графично, чиито върхове са подмножество на разлагането.

Hypergraph - общ вид на графика, в която всеки край може да бъде свързан не само два върха, но всяка подгрупа на върховете. Такава графика е удобно да представляват подмножества на множеството от върховете, например, различни части напрежение верига, или свързаните с тях области, различни тактова честота сигнали. В действителност, hypergraph е лесно да двустранна графика - една подгрупа от върха - върха на hypergraph, а вторият - ребрата. Защото на този уникален за кореспонденция hypergraphs често не са изолирани в отделен клас.

Фигура 7. двустранен графиката и съответния hypergraph

можете да поставите всеки ръб или връх на графиката, свързана с определен брой нарича тегло. Такива графики се наричат ​​окачени. Тегло може да означава клетка площ, дължина на веригата или всяка друга собственост на обекта, който се моделира. Тегло често се използва при търсенето на начини, проблемът е формулиран по следния начин: "намери пътя с най-малко тегло", т.е. намери начин, ръбове и / или върхове, които са включени в по-малките общото тегло в сравнение с всички други възможни начини. Често различни опции при търсене на ръбове и върхове са възложени на различни тежести - това се нарича търсене по различни критерии. Понякога, когато търсят пътища в графиката в задачите, които са тясно свързани с топологията на теглото на пътя се идентифицира с неговата дължина. толкова често и да каже - дължина на ръба. Можете да използвате и други функции, като ръбове. Така например ръбове на графиката могат да бъдат анизотропни, може да промени посоката горни ръбове и така нататък. Числени характеристики, но добре, че могат да бъдат използвани в стандартни алгоритми без съществена промяна.

Фигура 8. пунктирана път вече

Ойлер път (Ойлер верига) в графика - това е пътят, който преминава по всички краища на графиката, а след това само веднъж. Намирането такъв път изисква например проблемът на Кьонигсберг мостове: тя е необходима, за да мине всяко мост Кьонигсберг, докато не минава навсякъде два пъти. Ако добавим към това и класически изискването да се върне в началната си точка, вече сте получили задачата за намиране на цикъл Ойлер.

Фигура 9. Проблемът на мостовете

Euler цикъл - път Ойлер е цикъл.

Ойлер графика - графика, която съдържа цикъл Ойлер.

Polueylerov граф - граф, съдържащ Euler път (верига).

Разликата между Ойлер и polueylerova брои дали ние определено vozvraschatsya до отправната точка. Euler графика е свързан и съдържа само върховете на дори степен (т.е. с четен брой съседни ръбове). А насочено графика е Ойлеров ако всички върхове в него са силно свързани (т.е., за всяка двойка върхове съществува пряка и връщане) и при всеки връх на броя на неговите краища е равен на броя на изходящи.

По-точно: A диграфът се нарича силно свързан, ако всички два върха са силно свързани. Два върха S и Т всяка графика е силно свързани, ако е налице насочено пътя от и към Т, и режисиран път от т да е. Силно свързан компоненти диграфът наричат ​​своя максимум, за да се включи силно свързани подграфи.

Фигура 10. Силно свързан компонент на графиката

Hamiltonian графика - в теория на графите графика, която съдържа Hamiltonian схема или Hamiltonian цикъл.

Хамилтонов път (или Hamiltonian схема) - на пътя (верига), която съдържа всеки връх на графиката точно веднъж. Хамилтонов път, начален и краен връх съвпадат, се нарича Hamiltonian цикъл. Hamiltonian цикъл е прост цикъл Spanning. А Hamiltonian верига - обхваща дърво.

Фигура 11. Хамилтън (и Ойлер) цикъл

Ако графиката не съдържа ръбове с изключение на тези, включени в Хамилтонов цикъл, тогава този цикъл е и Ойлер.

Хамилтонов път и цикъл графика кръстен ирландски математик Уилям Хамилтън, който първи идентифицира тези класове, задачата на разглеждането на "световно турне" на додекаедър, възловите върховете символизират най-големите градове на земята, и по краищата - на пътя, която ги свързва.

Planar Count - брои, която може да се опише със самолет без да пресичат ребра.

Фигура 12. равнинна и с равнинна Графиката

По-точно: Графа, поставен на повърхността, ако може да се възползва от него, без да преминават ръбове. Ulozheniju графика се нарича геометрична, среща на върха - точка в равнината, и ръбовете - линия върху него. Области, за които графика разбива на повърхността, наречени аспекти. Плосък Ърл - Ърл, поставен върху една равнина. Графиката се нарича равнинна, ако тя е изоморфен на равнина графика.

За свързан планарна графика следната зависимост между броя на върховете | V (G) | , Ребра | E (G) | и е с изложение | F (G) | (Включително външната страна):

| V (G) | - | E (G) | + | F (G) | = 2

Фигура 13. Edge на планарна графика

Установено е от Ойлер в 1736 в изследване на свойствата на изпъкнал polyhedra. Тази връзка се отнася и за други повърхности до фактор, наречен Ойлер характеристика. Тази повърхност инвариантен за самолет или го сфера е равно на две.

Критерият за не-планарност:

· Достатъчно условие - ако графиката съдържа двустранен подграф K 3,3 или пълен подграф K 5, а след това не е равнинна;

· Предпоставка - ако графиката не е плоска, то трябва да съдържа повече от 4 върховете чиято степен е по-голяма от 3, 5 или повече върховете на степен по-голяма от 2.

Фигура 14. 3, 3

Фигура 15. 5

Равнинни графики са графики най-използвани в етапа на физически синтез - следи от решетъчни графики на вертикални и хоризонтални ограничения.

Практически пример:

DCCC (постоянен ток свързан компонент) или на компонент от комбинирана DC е част от електрическа схема, такава, че за всеки входен сигнал, че част от веригата токове на потока в него. Например, един инвертор или NOR елемент в CMOS схеми са DCCC, тъй като няма ток тече през портата на БНТ.

За да намерите тези компоненти във всяка част на може да се използва, насочени графики веригата, ние смятаме, че такъв елемент 2и:

Фигура 16 Схема на елемент 2I

Не веднага ясно кои части от веригата са DCCC. Разбира се, с помощта на "погледа" чрез теглене на всички възможни течения, и да се движат всички входни състояние, ние рано или късно ще избере независими компоненти. Въпреки това, какво ще стане ако на транзистори ще бъдат няколко десетки или стотици? Нека се опитаме да се формализира проблема. За тази схема представлява възли в една насочена графика на върховете и ръбовете на елементите. Тъй като няма ток може да протече през транзистор порта MOS така че транзистора ще бъдат представени като едно ребро, свързваща източника и канализация. Нека същата посока на ребрата показва посоката на ток, преминаващ през транзистора.

След р-канален транзистор ток на потоци от парапета на доставките (VDD) към изхода на веригата, и чрез N-канал от изходната шина към земя (VSS). Ние се изгради диграфът съответстваща на нашата схема.

Сега ние всички пътища, които водят от върха на VDD до връх VSS. Има три начина - (M1, M3, M4), (M2, M3, M4), (M5, M6). Ясно е, че токът изберете първия или втория път задължително минава през транзисторите М3 и М4, така че всички транзистори на първите два начина да се отнасят до DCCC. Третият път съдържа транзистори общи с никакъв друг начин, затова е още един DCCC.

Фигура 17 Графика Модел 2i вериги

Така че, за да намерите всички компоненти на DCCC във веригата CMOS е необходимо:

1. Конструкция диграфа схема, където всеки възел отговаря на връх, и всеки от транзисторите - края, ориентиран в посоката на протичане на ток през транзистора.

2. Намерете всички пътища, свързващи приземния автобуса и захранването.

3. Ако двете пътеки имат поне един общ елемент, всички елементи на тези пътища принадлежат към DCCC.

Като упражнение, намерите всички DCCC за веригата е показано на фигурата.

Фигура 18 Определяне на търсенето на самостоятелно DCCC

Въпроси и задачи за самостоятелна работа:

1. Мислете в литературата и намери алгоритъм за определяне на наличието на цикли в графиката (виж [4]).

2. Разработване на набор от формални критерии за определяне на елементарна и цикъл път в графиката (виж [2] стр. 69-83).

3. Винаги е така, за да се ориентират по ръбовете в ненасочена графиката с един цикъл, че полученият насочено графиката също съдържа цикъл? Дайте примери ([2] стр. 157-227).

4. Дайте примери за последователност на hypergraphs и двустранни графики. Възможно ли е да може еднозначно да се сдружават hypergraphs и други видове графики? Дайте примери ([6], гл. IX).

5. дава примери от равнинни и непланарни графика. Даде пример за планарна и непланарни графика, които се различават по един ръб ([1] ч. 5).

Литература:

1. Ol'shanskii. равнинни графики

2. R. Sedgwick основните алгоритми в C ++. част 5

3. http://www.univer.omsk.su/departs/compsci/kursi/disc/graphs.htm

4. http://e-maxx.ru/algo/

5. http://rain.ifmo.ru/cat/view.php/theory/list

6. http://vmg.pp.ua/books/Математика/Графы/Емеличев%20В.А.%20и%20др.%20Лекции%20по%20теории%20графов/

Лекция 6 Концепцията на дървото. каноничен код дърво. Присичайки дървото. Специални видове дървета. Двоично дърво. Черен и червен дървета. настроите дисекция. Балансираните дървета. K-г дърво. Дърво като модел на данните.

Съдържание:

1. Понятието на дървото.

2. обхваща дърво.

3. минимален обхваща дърво.

4. каноничен графика кодът.

5. Търсене в дълбочина и ширина.

6. двоично дърво.

7. двоичен купчината.

8. червено-черно дърво.

9. Системата от несвързани комплекти.

10. B-дърво.

Дървото - свързан ацикличен граф (т.е., графиката не съдържа цикли, от които има точно един път между всяка двойка върхове). Дървета свързват всички върхове.

Фигура 19. Tree

Spanning дърво на графиката е дърво, построена върху набор от върха, използвайки подмножество от неговите краища. За изграждането на дървото, можете да използвате два подхода. А конструктивен подход е първо да се избере произволно ръб, свързващ два върха. Ние наричаме получената структура на дървото. Ние намираме на ръба, който свързва върха на дървото е дърво с връх, и да го добавите към дървото. Веднага след като не можем да намерим такъв ръб - дърво строителството е завършено. Разрушителната подход, ние откриваме един цикъл в графиката и извадете от него да е край. От краищата на ребрената част на цикъла, а след това на графиката няма да загуби свързаност. Повтарянето на тази операция е в кутията няма да има цикъл получаваме обхваща дърво.

Фигура 20. Проектиране строителство дърво

Често проблемите на физическото синтез е необходимо да се намери минималната обхваща дървото. Такъв проблем е за претеглените графики. В минимум тук означава минимална сума от теглата на ръбове включени в дървото. Този проблем може да бъде полезна, например, за да намерите конфигурация верига свързване на няколко терминали на различни елементи. Тъй като тя формира решение ostavnoe дърво, всички находки ще бъдат свързани, и тъй като ние търсим минимум дърво, дължината на веригата също ще бъдат минимални.

Най-известният алгоритъм за решаване на този проблем е алгоритъм Kruskal на:

- Намери край с минимално тегло и да го добавите към дървото;

- До конструкцията на дървото не е пълен:

- За да се намери минималната ръба на тегло, не е част от дървото и не образува един цикъл в дървото

- Добавете го към дървото

Същият алгоритъм се използва Prima: строителство започва с дървото, което включва една (произволна) среща на върха. По време на дървото алгоритъм расте, докато обхване всички върховете на оригиналния графиката. На всяка стъпка на алгоритъма на настоящата дървото се присъединява към леката ребра свързваща горната част на конструираната дървото, и горната част не е от дърво.

Броят E на ръбове в дървото с броя на върховете н:

Е = N - 1

каноничен код Графиката (графика каноничен код) - уникален низ, който не зависи от реда на номериране на върховете. В същото канонични изоморфни графики кодове са nonisomorphic - различно.

Върховете и ръбовете на графиката могат да бъдат оборудвани с допълнителни маркировки (цветове). В този случай, каноничен код включва цветови идентификатори.

Canonical графики кодове позволяват да се отървете от скъпа процедура за проверка изоморфизъм (графика изоморфизъм), и графики за определяне на мача сравнение струни.

Например, как да намерите дубликати в набор от N графики? Изчислете N канонични кодове, да ги сортирате и последователно за сравнение. Тя е много по-изгодно, отколкото правите N * (N-1) / 2 проверки изоморфизъм. Можем да кажем, че каноничната код - хеш код без грешки.

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

Фигура 21. Търсене широк. Тези цифри се отнасят до реда на раздел. Запалка разходите по тъмно.

Обхождане в ширина (BFS, обхождане в ширина) - временно решение и оформление на върховете.

Обхождане в ширина се извършва в следния ред: топ заобикаляне и приписва етикета 0, върховете в непосредствена близост до него - на етикета 1. След това завъртете на околната среда се считат всички върхове с етикети 1 и всеки от членовете на околните върхове зададете етикет 2, и така нататък ..

Ако оригиналният графиката е свързан, търсенето на всичките му топ марки. Дъгите на формата (аз, аз + 1) генерират обхваща схема без насочено графика, съдържащ като част от своята Spanning ortree нарича търсене дърво.

Лесно е да се види, че като погледнете в ширината също могат да бъдат преброени връх номерация, започваща с горната част на етикета 1, и след това, означен с 2, и така нататък. D.

Фигура 22. дълбочина Search.

(. Английски обхождане в дълбочина, DFS) обхождане в дълбочина - Един от методите на прекосява на графика. Алгоритъмът за търсене е описан, както следва: за всеки некатерен пикове трябва да се намери всичко, не се предават съседни върха и повторите търсенето за тях. Използва се като подпрограма в алгоритмите на търсене просто и двойно свързан компонент, топологично сортиране.

Фигура 23. Binary Tree

Binary Tree - структура от данни дърво, където всеки възел има най-много два потомци (деца). Като правило, първият се нарича възел майка, а децата се наричат ​​леви и десни наследниците. Всеки възел съдържа някаква информация - стойността на имотите, връзки и така нататък. Можем да кажем, че едно двоично дърво е насочено дърво. На всеки връх има, с изключение на една, наречена корен или просто корен е майка. Върховете, които нямат наследници, наречени листа.

Обикновено такива дървета е разделена на нива. На ниво 0 съдържа само корена, 1 - за два неговите наследници (деца), 2 - до четири от техните наследници, и така нататък. Тя се казва, че дървото е балансиран, ако броят на неговите нива (т.е. нивата, на които има най-малко един елемент (дърво отгоре)) е равен влезете 2 (п), където N - общ брой на върха на дървото.

За практически цели, обикновено се използват два суб двоично дърво - двоично търсене дърво и двоично купчина.

Фигура 24. двоично търсене дърво

А двоичен търсене дърво съдържа всеки връх стойност на някакъв вид, който е определен за работа "по-малко". А двоичен търсене дърво се нарича дърво, ако "по-малко" за всеки връх стойност на лявата му дете на собствените си ценности, както и право "не-по-малко" от само себе си. Балансираната двоично дърво корен лежи приблизително по средата на диапазона на възможните стойности. В ляво поддърво стойности са по-малки, и правото да не е по-малко от корена. Ето защо, когато се гледа като дърво изисква влезете само 2 (п) операции (по един за всяко ниво на дървото), за да намерите желаната стойност. Най-лошо балансиран дърво, по-голям резултат ще бъде различен от логаритъм.

Фигура 25. двоичен купчината

Binary грамада е двоично дърво, в което всеки връх е не по-малък от своите деца (или повече). В допълнение към дървото е един куп е необходимо да бъде перфектно балансиран, т.е. всички върхове трябва да имат и двете дясно и ляво потомството, с изключение на всички върховете на последното ниво, а вероятно и част от предпоследния връх. Всички поддървета на всички върхове на дървото също са куповете. Купчини е полезно за сортиране множество "на място". За да направите това, което трябва да се изгради една купчина от масив, а след това се премести в корен края на масива на. Като изгради купчина върху останалите елементи ще можем отново да повторите процедурата. Този вид се нарича пирамида или стека за сортиране (пирамидално сортиране).

Фигура 26. червено-черно дърво

Red-черно дърво (. English Red-Black-Tree, RB-Tree) - е един от самостоятелно балансиране двоични търсене дървета, гарантираща логаритмична растежа на височина дърво на броя на единиците и бързо извършване на основните операции в дървото на търсене: добавяне, изтриване и търсене в сайта. Баланс се постига чрез въвеждане на допълнителен атрибут дърво възел - "цвят". Този атрибут може да бъде в една от две възможни стойности - "черен" или "червено". Red-черно дърво - двоично търсене дърво, в която всеки възел има цветен атрибут, който заема стойности на червено или черно. В допълнение към обичайните изисквания, наложени на двоични търсене дървета, червено-черно дървета, се прилагат следните изисквания:

1. Node или червено или черно.

2. Root - черен. (С други определения, това правило понякога се пропуска. Той обикновено има малък ефект върху анализа, тъй като коренът винаги може да се променя от червено до черно, но не е задължително обратното).

3. Всички листата - черно.

4. Както потомък на всеки червен възел - черен.

5. Всеки обикновен път от даден възел на всяко листо възел, като потомък му, съдържа същия брой черни възли.

Тези ограничения изпълняват критична собственост на червено-черно дървета: пътя от корена до най-външния лист е не повече от два пъти дължината на пътя от корена до най-близкия лист. Резултатът е, че балансиран дърво. От операции като поставяне, изтриване и търсене на необходимите стойности в най-лошия случай, че времето пропорционален на дължината на дървото, тази теоретична горна граница на височината позволява червено-черно дървета, за да бъдат по-ефективни в най-лошия случай, конвенционалните двоични търсене дърветата.

За да се разбере защо това е гарантирано, достатъчно е да се помисли за ефекта на свойствата 4 и 5 заедно. Да предположим, че за червено-черно дърво T брой черни възли в имота в размер на 5 Б. След това възможно най-кратък път от T коренът на всяко листо възел B съдържа черни възли. По-дълъг възможен път могат да се изграждат чрез включване на червени възела. Въпреки това, имотът не позволява 4, за да вмъкнете няколко червени възли в един ред. Ето защо, най-дългия възможен път се състои от единици 2B, последователно в червено и черно. Всяко максимална път има същия брой черни възли (от имот 5), така че няма начин за повече от два пъти по-дълго, отколкото всеки друг път.

В много приложения, дървовидна структура е възможно, че един възел има само едно дете, и листо възел съдържа данни. При тези предположения, за да изпълни червено-черно дърво е възможно, но се променят няколко свойства, и алгоритъма сложно. Поради тази причина, тази статия използва "фиктивни листните възли", които не съдържат данните и служат единствено за да покаже, където краищата на дървото. Тези възли често се пропускат, когато графичния образ, в резултат на едно дърво изглежда в противоречие с изложените по-горе принципи, но в действителност не съществува противоречие. Последицата от това е, че всички вътрешни (не-листни) възли имат две деца, въпреки че един от тях може да бъде нула приплъзване. Property 5 гарантира, че един червен възел трябва да има като деца или две черен лист нула или две черен вътрешен възел. За черен възел с едно листо възел потомък нула и друг потомък, не е такова, свойствата на 3, 4 и 5, ще гарантират, че последният трябва да бъде червен възел с две черни нула оставя като деца.

Понякога червено-черно дърво се тълкува като двоично търсене дърво, което вместо възли в червено и черно цвят боядисани ръбове, но това няма никакво значение.

Популярността на червено-черно дърво е свързано с факта, че те често се постига подходящ баланс между степента на баланс и сложността на подкрепа баланс. По-специално, когато в сравнение с перфектно балансирани дървета често се установява, че последните имат много строг състояние на равновесие и когато отстраняването на операциите на дърветата, много време се отделя за поддържане на необходимия баланс.

Фигура 27. Системата от несвързани комплекти

разместени-комплект позволява да се прилага набор от елементи, разделен на несвързани подгрупи. По този начин всяка подгрупа се определя свой представител - един елемент от тази подгрупа. В Регистъра на структурата на данните определя от множество три операции {съюз, Намери, MakeSet}.

Системата на несвързани комплекти е много удобно за съхранение на свързаните компоненти в графиката. Например, алгоритъм Kruskal изисква такава структура данни за ефективно прилагане.

В тази структура, всяка серия е представен като дърво с един корен елемент. Всеки възел в този набор има препратка единствено към своята майка. Вярно е, че за всеки връх нагоре в йерархията на родителите ще дойде в началото на снимачната площадка, и само него. Така извършена операция Find. Съюз операция, извършена назначаването на един от корена определя майка на основата на друг набор. MakeSet ви позволява да създадете нов празен комплект, съдържащ само на корен елемент.

Фигура 28. B-дърво

B-дърво - структурата на данните, дървото на търсене. По отношение на външното представителство на логическо, балансиран, силно разклонено дърво в външна памет.

Използването на B-дърво R. Байер в него за първи път е предложен (инж. Р. Bayer) и E. MacCrate през 1970.

Баланс означава, че дължината на всеки две пътеки от корена на листове варира не повече от една единица.

Green дърво - дърво всеки възел имот да се позове на голям брой деца възли.

От гледна точка на физическата организация на B-дървовидна структура на е представен като multispisochnaya страници на външна памет, тоест, всеки възел от дървото съответства на един блок на външна памет (страница). Вътрешни и листни страници обикновено имат различна структура.

Структурата на индекса на B-дърво се използва за организирането на много от съвременните RDBMS.

B-дърво може да се използва за структуриране (индексиране) информацията на твърдия диск (обикновено, метаданни). Време до произволна блок на твърдия диск е много голям (от порядъка на милисекунди), тъй като тя се определя от скоростта на въртене на диска и движещи се глави. Ето защо е важно да се намали броят на възлите да се разглеждат за всяка операция. Използвайте списъка на търсачката, за да намерите всеки път случаен блок може да доведе до прекалено голям брой диск достъп, поради необходимостта от серийния преминаването през всички негови елементи, предхождащ дадена; има предвид, че търсенето в B-дърво, благодарение на балансирани свойства и висока разклоняване значително намалява броя на тези операции.

Сравнително проста реализация на алгоритми и наличието на готови библиотеки (включително C), за да работят със структурата на B-дървото осигурява популярността на използването на такава организация на паметта в различни програми, които работят с големи обеми от данни.

Практически пример:

VLSI свързва са съставени от множество правоъгълни сегменти. С цел да се провери съответствието с диаграма на топология, което трябва да се знае как тези вериги принадлежат към сегмента. За решения на този проблем ще се опита да намери всички сегменти, които се пресичат помежду си. Такива сегменти са гарантирани, че принадлежат към една и съща верига, тъй като те са свързани електрически. Помислете за един прост пример. Да предположим, че имаме три сегмента - 1, 2 и 3. Ние ги възлагат на три различни схеми - червено, зелено и синьо.

Фигура 29 Начално състояние

Списък на сегментите, които принадлежат към една и съща верига, представени като едно дърво с едно изключение - на цикъла при корена. В горната част, която е майка на собствената си - това е коренът. Каква е корен върха, че е възможно да се посочи от всяка друга черта - в горната част на знамето, майка на нула и т.н. Това няма значение.

Произволна начин ние сега откриваме, че сегменти 1 и 2 се преминава, след като и двете принадлежат към една и съща верига. Нека тази комбинирана схема се нарича по-нататък за краткост зелено.

Фигура 30 Първата стъпка

За да покаже, че на втория сегмент отива в много, което е собственик на първия сегмент, ще направи първия сегмент от втория родител. По същия начин ние се пристъпи към сегмента 2 и 3.

Фигура 31 крайното състояние

В резултат на това ние можем да видим, че всички сегменти принадлежат на множество зелени, и следователно принадлежат към една и съща верига. Повтаряйки този алгоритъм за всички случаи на пресичане на сегментите в схемата, ние получаваме набор от вериги схема.

Въпроси и задачи за самостоятелна работа:

1. Колко дървета като подгрупа на определена графика? Дайте примери (виж [3]).

2. Може ли граф съдържа няколко минимум Spanning дърво? Дайте примери (виж [3]).

3. предлагат няколко вида каноничен код за произволна графика ([5]).

4. Изберете примери за илюстрация на превъзходството на търсене в ширина над обхождане в дълбочина на, и обратно ([1] стр. 99, 132).

5. показват съответствието между двоичен купчината и двоично дърво ([2], страница 178 -. 193).

6. Разработване на работа паста в червено-черно дърво ([2] стр. 336-364).

7. Оферта евристики за подобряване на скоростта на търсене в системата на несвързани комплекти ([2] стр. 1296).

Литература:

1. Р. Sedgwick основните алгоритми в C ++. част 5

2. Kormen Т., Чарлз Leiserson, Rivest, Р., К. Stein, Въведение в алгоритми. - 2-ро изд.

3. http://www.lvf2004.com/dop_t4r13part1.html

4. http://ric.uni-altai.ru/Fundamental/pascal3/lab7/teor7-4.htm

5. http://www.lib.tsu.ru/mminfo/000349342/01/image/1-101.pdf

Лекция 9 йерархично пространство разделяне. Плосък опаковане. БСП дървета. KD-дървета. Quadrotree.

Съдържание:

1. Въведение.

2. Разрушаване на сектори.

3. Плосък опаковане.

4. двоичен пространство разделяне.

5. KD-дърво.

6. quadrotree.

7. R-дърво.

В много проблеми, физически синтез се изисква да работят с пространствени отношения на обекти. Задължително да се търси пресечната точка на правоъгълници, вземете им разстояние помежду си. Често предмети, с които искате да работите - много хиляди. За да не се всички тях се докоснат в търсене на подходящи йерархични методи се използват (и не само) на пространството на разпределение. Основната идея на тези методи е, че обектите са групирани според тяхното местоположение в пространството, което отрязва ненужни проверки - чрез кръстосване на такива обекти в други части на кристала.

Един от най-лесните начини да се дял е даден дял на сектора. Всички пространството, в което елементи могат да бъдат разделени в сектори, обикновено правоъгълни. След това, изчислена за всеки елемент от сектора, в който се намира и (брой сектор) на стойност, съхранявана в елемента на метаданни. Сега, за да се научат на двата обекта се припокриват или не, достатъчно е да се сравни брой сектори на обектите. Ако цифрите са различни, обектите не се припокриват точно. Ако те са идентични, че може да работи по-точна процедура за проверка. По този начин, повечето от обектите ще се изключи от избора на първия етап тест, който позволява значително ускоряване изчисления.

Фигура 32. Сплит в сектори

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

Фигура 33. Позиция на субекта в кой сектор?

Проблемът е частично решен чрез същото увеличение в размера на секторите на елементите. Елементите се предоставят по-малко често в няколко сектора. Въпреки това, този подход води до по-чести проверки на пресичане, тъй като един сектор ще се хранят повече елементи.

Важен топологични алгоритъм е за апартамент - е разположението на елементите в самолета с помощта на последователно разделяне на пресичаща равнината. Существуют различные виды плоской укладки, зависящие от числа секущих на каждом шаге. Мы будем рассматривать ПУ-2 с одной секущей и соответственно двумя областями.

Рисунок 34. ПУ-2 и дерево декомпозиции

Для того чтобы применить алгоритм к какому либо множеству элементов, для начала нужно произвести его иерархическую бинарную декомпозицию. Для этого первым делом каждому элементу назначается «вес», прямо связанный с площадью, занимаемой этим элементом. Затем строится дерево декомпозиции. Дерево декомпозиции – это бинарное дерево, листьями которого являются все элементы множества, а корнем все множество в целом. На первом шаге отмечается корень дерева, включающий все множество. Затем это множество разбивается на две примерно равные (по сумме весов элементов) части. Каждый элемент может входить только в одно это подмножество. Эти подмножества отмечаются как левый и правый потомок корня дерева. Затем процедура повторяется для каждого из этих потомков. Рекурсивно повторяя данные шаги до тех пор, пока в каждом потомке не останется по одному элементу, мы и получим дерево декомпозиции.

Корень этого дерева соответствует всей области размещения элементов. Разделим эту область пополам, так чтобы отношение площадей половин было таким же, как и отношение весов потомков корня. Как вы уже догадались: проделаем ту же процедуру рекурсивно для всех потомков корня. В результате мы получим разбиение плоскости, в котором для каждого элемента определена область, куда он будет помещен. Так как разбиение плоскости на две можно провести двумя способами, выбирается тот, при котором дочерние области имеют соотношение сторон, ближайшее к соотношению сторон родителя.

Такое разбиение позволяет эффективно использовать площадь – задача, которую часто пытаются решить при расположении элементов СБИС. Однако качество решения очень сильно зависит от качества декомпозиции, кроме того не гарантируется глобальная оптимальность решения, поскольку алгоритм «жадный» - на каждом шаге принимает локально-оптимальное решение. Например если элемент, чья оптимальная позиция в левой части плоскости попадает при декомпозиции в правое поддерево, то уже нет способа вернуть его обратно.

Плотная укладка, как вы уже, наверное, заметили, является иерархическим разбиением пространства, в отличие от разбиения его на сектора. Иерархическое разбиение характеризуется более сложной, вложенной структурой данных, представляющих пространственные группы. Обычно для такой структуры выбирают дерево, так как оно является естественным представлением иерархии (вспомните например генеалогическое дерево).

BSP-дерево — это структура данных, используемая в трехмерной графике. Аббревиатура BSP означает Binary Space Partition — двоичное разбиение пространства. BSP-дерево используется для эффективного выполнения следующих операций:

· Сортировки визуальных объектов в порядке удаления от наблюдателя;

· Обнаружение столкновений.

BSP-деревья были впервые применены специалистами компании Lucas Arts в начале 80-х годов. Популярность у разработчиков они завоевали благодаря компании id Software, разработавшей движки Doom (1993) и Quake (1996).

Рисунок 35. BSP-дерево

В BSP-дереве каждый узел связан с разбивающей прямой или плоскостью в 2-мерном или 3-мерном пространстве соответственно. При этом все объекты, лежащие с фронтальной стороны плоскости относятся к фронтальному поддереву, а все объекты, лежащие с оборотной стороны плоскости относятся к оборотному поддереву. Для определения принадлежности объекта к фронтальной или оборотной стороне разбивающей прямой или плоскости необходимо исследовать положение каждой его точки. Положение точки относительно плоскости определяется скалярным произведением нормали плоскости и координат точки в однородных координатах. Возможно три случая:

1. Скалярное произведение больше 0 — точка лежит с фронтальной стороны плоскости;

2. Скалярное произведение равно 0 — точка лежит на плоскости;

3. Скалярное произведение меньше 0 — точка лежит с обратной стороны плоскости.

Рисунок 36. Скалярное произведение

Если для всех точек объекта скалярное произведение больше или равно 0, то он относится к фронтально му поддереву. Если для всех точек объекта скалярное произведение меньше или равно 0, то он относится к оборотному поддереву. Если для всех точек объекта скалярное произведение равно 0, то не играет роли к какому поддереву он принадлежит. Если скалярные произведения для точек объекта имеют разный знак, то он рассекается разбивающей плоскостью так, чтобы полученные объекты лежали только с фронтальной или только с оборотной стороны. Для каждого подузла BSP-дерева справедливо вышеприведенное утверждение, с тем исключением, что рассмотрению подлежат только те объекты, которые принадлежат к фронтальной или оборотной стороне разбивающей плоскости родительского узла.

Важным для BSP дерева является выбор рассекающих плоскостей. От этого зависит, насколько сбалансированным будет дерево, то есть насколько быстрым будет поиск элементов в нем. Как вы уже догадались, дерево декомпозиции для плоской укладки является BSP деревом. Только для него решается обратная задача – размещение объектов на плоскости так, чтобы они попали в уже сформированную структуру BSP дерева.

Рассмотрим структуру бинарного пространственного разбиения, называемая kd-дерево. Эта структура представляет собой бинарное дерево ограничивающих параллелепипедов, вложенных друг в друга. Каждый параллелепипед в kd-дереве разбивается плоскостью, перпендикулярной одной из осей координат на два дочерних параллелепипеда.

Рисунок 37. kd-дерево разбивает плоскость на области

Вся сцена целиком содержится внутри корневого параллелепипеда, но, продолжая рекурсивное разбиение параллелепипедов, можно прийти к тому, что в каждом листовом параллелепипеде будет содержаться лишь небольшое число примитивов. Таким образом, kd-дерево позволяет использовать бинарный поиск для нахождения примитива, пересекаемого лучом.

Отличием трехмерного случая является то, что кроме положения секущей плоскости есть три способа ее провести – перпендикулярно каждой из осей координат.

Плоская укладка и kd-дерево являются лишь частными случаями бинарного разбиения пространства, когда разбивающая плоскость ортогональна осям координат. Такое ограничение не случайно, оно позволяет легче считать пересечение объектов с линиями и плоскостями сечения. Действительно, для того чтобы определить, лежит точка спереди или сзади плоскости, перпендикулярной какой либо из осей, достаточно сравнить эту координату плоскости и точки. Кроме того вы видите, что для хранения информации о сечении достаточно одной координаты и указания – вертикальное это, горизонтальное или для трехмерного случая еще один вид сечения.

Рисунок 38. Разбиение плоскости квадродеревом

Стоит заметить, что для случая, когда множество элементов не меняет своего положения достаточно один раз вычислить дерево. В таком случае более выгодным может оказаться рассечение плоскости наклонными линиями, а пространства – наклонными плоскостями. Способ разбиения следует выбирать исходя из динамики разбиваемого множества, количества и размера элементов, а так же имеющихся вычислительных мощностей.

Однако что будет, если разбить пространство не на две части, а например на четыре? Такое решение сильно уменьшает высоту дерева, однако усложняет поиск. Можно назвать такое решение комбинацией иерархического разбиения и разбиения на секторы. Для двумерного случая существует квадродерево, в котором каждый узел имеет четырех потомков, а для трехмерного октодерево.

Рисунок 39. Квадродерево

В квадро- и октодереве потомки имеют одинаковый размер, это позволяет не хранить координаты секущих плоскостей (они всегда лежат посередине области текущего узла. Кроме того в таких структурах используется соглашение о перпендикулярности секущих линий и плоскостей координатным осям. Такой подход позволяет при уменьшении потребления памяти, что может быть критично для количества элементов, характерных для современных СБИС, добиваться серьезного ускорения пространственных операций.

Рисунок 40. R-дерево

Тут можно спросить: зачем мы группируем пустое место? Давайте группировать объекты! Для решения подобной задачи подходит R-дерево или дерево прямоугольников. Такое дерево больше всего похоже на B-дерево для числовых значений. Только каждая вершина представляет собой набор прямоугольников, каждый из к оторых ссылается на дочернюю вершину и включает все её прямоугольники. Такое представление позволяет снизить чувствительность дерева к добавлению и удалению элементов, однако делает важным порядок вставки. При добавлении элемента ищется вершина, в которую можно добавить его, минимально расширяя охватывающий прямоугольник этой вершины. Если в этой вершине и так достаточно элементов (максимальное количество элементов в вершине является параметром дерева), то вершина расщепляется на несколько вершин.

Иногда вместо R-дерева используют так называемое cR-дерево (c означает clustered). Основная идея в том, что для разделения вершин или точек используются алгоритмы кластеризации, такие как k-means. Сложность k-means тоже линейная, но он в большинстве случаев даёт лучший результат, чем линейный алгоритм разделения Гуттмана, в отличие от которого он не только минимизирует суммарную площадь огибающих параллелепипедов, но и расстояние между ними, и площадь перекрытия. Для кластеризации точек используется выбранная метрика исходного пространства, для кластеризации вершин можно использовать расстояние между центрами их огибающих параллелепипедов или максимальное расстояние между ними.

Алгоритмы кластеризации не учитывают то, что число потомков вершины ограничено сверху и снизу константами алгоритма. Если кластерный сплит выдаёт неприемлемый результат, можно использовать для этого набора классический алгоритм, так как на практике такое происходит не часто.

Интересна идея использовать кластеризацию на несколько кластеров, где несколько может быть больше двух. Однако надо учитывать, что это накладывает определённые ограничения на параметры структуры р-дерева.

Отметим, что помимо cR-дерева существует его вариация clR-дерево, основанное на методе кластеризации, где в качестве центра использован итерационный алгоритм решения «задачи размещения». Алгоритм имеет квадратичную вычислительную сложность, но обеспечивает построение более компактных огибающих параллелепипедов в записях вершин структуры.

Поиск в дереве довольно тривиален, надо лишь учитывать тот факт, что каждая точка пространства может быть покрыта несколькими вершинами.

Практический пример:

Предположим, что у нас имеется область кристалла, в которой две точки требуется соединить проводником. Для того чтобы определить какие препятствия возникнут на пути можно поискать пересечения с каждым элементом схемы. Однако если таких элементов большое количество, то это может занять длительное время. Посмотрим, как квадродерево поможет решить проблему поиска пересечений. Ниже представлен фрагмент нашего кристалла. Зеленым обозначены препятствия, красным – необходимый путь проводника. Область уже поделена на квадраты для построения вершин квадродерева. Разбиение остановлено, когда квадродерево достигло второго уровня, чтобы упростить пример.

Рисунок 41 Разбиение площади кристалла

Посмотрим на результирующее дерево. Зеленым отмечены вершины с препятствиями, белым – пустые области. Узлы расположенные слева направо, на плоскости расположены против часовой стрелки, начиная с левого нижнего угла.

Рисунок 42 Квадродерево

Для начала найдем какому узлу находится стартовая точка. Начнем с корневого узла, который представляет всю плоскость. Используя координаты точки найдем что она находится в нижнем левом квадрате. Это первый узел, он пуст (красная стрелка).

Рисунок 43 Порядок обхода квадродерева

Сега нека да видим коя страна на площада, на съответния възел пресичат пътя на проводника. Тя пресича горната страна. Следователно, следващият възел - четвърти (синя стрелка). Тъй като възелът не е празен, да разгледаме някои възел на второто ниво ще падне направо. Както го пресича долния десен ъгъл, след което тя ще падне през втората подсистема. Това е празна. Още линии не се пресичат на възела не монтажни елементи. Върни се на първо ниво от дървото и за следващия възел изглежда - това е третият (зелената стрелка). Тъй като възелът не е празен, ние гледаме на това, което монтажни елементи, пресича линията. Както го пресича долната дясна страна на квадрат възел, първия възел на второто ниво, в което тя ще получи първия възел на възел. Този възел зелено, това означава, че тя съдържа пречка. Въпреки това, той не разполага с дете възли, така че ние се извлече координатите на prepetstviya на пресичане и потърси с нашата линия. Пресечната точка е. На следващия възел ще бъде четвъртият, там ние също се намери пресечната точка с препятствие. И последният възел е на трето - той е свободен.

Опишете себе си quadrotree раздела за да може една отсечка, която пресича участъка на кристала, перпендикулярна на първата от горния ляв ъгъл до долния десен ъгъл.

Въпроси и задачи за самостоятелна работа:

1. Дайте примери за проблеми, за които е удобно да се използва за разделяне на пространството (виж [4]).

2. Дайте пример за успешен и неуспешен заявление за сектора на дял ([5]).

3. Дайте пример за процедурата по вкарване в двоичен пространство дърво дял ([2]).

4. Дайте пример за рейтрейсинг в KD-дървото ([4]).

5. Определяне на предимствата и недостатъците квадратен дърво. Дай примери ([6]).

6. Дайте пример на процедура за търсене на R-дървото ([7]).

Литература:

1. R-дървета: структура Dynamic Index за пространствена Searching, Proc. 1984 ACM SIGMOD Международна конференция за управление на данни, стр. 47-57

2. Shevtsov М., Soupikov А., Капустин A. Силно Parallel Fast KD-дърво Строителство за Interactive Ray Tracing на динамични сцени. В Сборник от конференцията EUROGRAPHICS, 2007.

3. Kormen Т., Чарлз Leiserson, Rivest, Р., К. Stein, Въведение в алгоритми. - 2-ро изд.

4. http://undergraduate.csse.uwa.edu.au/units/CITS4241/Handouts/Lecture14.html

5. http://www.drdobbs.com/article/print?articleId=184409694

6. http://www.cs.berkeley.edu/~demmel/cs267/lecture26/lecture26.html

Лекция 15 Екстремни проблеми в физическа синтез. Линейно и нелинейно програмиране. Алгоритми за симулация. Ant алгоритъм. Каляване симулация алгоритъм. Силови алгоритми. Vector Трейс svitchboksa.

Съдържание:

1. Въведение.

2. Математическо програмиране.

3. Методи за математически оптимизация.

4. Линейни и нелинейни програмиране.

5. мравка алгоритъм.

6. симулирана отгряване алгоритъм.

7. Електрически техники.

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

Целта на оптимизация в областта на математиката, информатиката и изследване на операциите, е проблемът за намиране на екстремум (максимум или минимум) на целевата функция в определен регион на краен двумерен вектор пространство, ограничен набор от линейни и / или нелинейни уравнения и / или неравенства.

Математическо програмиране - една дисциплина, която изучава теорията и методите за решаване на оптимизационни задачи.

Процесът на проектиране обикновено поставя задачата за определяне на най-добрите, в известен смисъл, структура или ценности обект на параметри. Този проблем се нарича оптимизация. Ако оптимизация е свързана с изчисляването на оптимални стойности на параметрите на дадена структура на обекта, той се нарича параметри оптимизация. Задачата на избора на оптимална структура е структурна оптимизация.

задачи Синопсис оптимизация определя голямо разнообразие от класове. От класа на проблема зависи от метода на селекция (ефективността на неговите разтвори). задачи Класификация определят целевата функция и осъществимо региона (дадено чрез система от уравнения и неравенства и по-сложен алгоритъм).

техники за оптимизация са класифицирани в съответствие с оптимизационни задачи:

Местните методи: съглася с всяка местна екстремум на целевата функция. В случай на unimodal обективна функция, за екстремум е уникална и ще бъде глобален максимум / минимум.

Глобални методи: справяне с многократни. В глобален търсене за основната задача е да се определят тенденциите в световната поведението на целевата функция.

сегашните методи за търсене могат да бъдат разделени на три големи групи:

1. детерминирана;

2. случаен (стохастичен);

3. комбинирани.

По критерия на измерение на възможно сет, оптимизационни методи се делят на едномерни техники и методи на многомерна оптимизация оптимизация.

Според изискванията на гладкост и наличието на целевите частични функции, те могат да бъдат разделени на:

1. Директни методи, които изискват само при изчисляването на целевата функция в точки приближения;

2. Методите от първи ред: първият изисква изчисляване на частични производни;

3. Методите от втори ред изисква изчисляване на втората частична производни, т.е. зебло на обективната функция.

Освен оптимизационни методи са разделени на следните групи:

1. Аналитичните методи (например, методът на Лагранж множители и условия Karush-Кун-Такър);

2. Числени методи;

3. графични методи.

В зависимост от естеството на X задачи математически програмиране са класифицирани като:

1. проблеми на дискретни програмиране (или комбинаторна оптимизация) - ако X е ограничен или изброимо;

2. Проблемът на число програмиране - ако X е подмножество на набор от числа;

3. Проблемът на нелинейни програмиране, ако целевата функция или ограничения съдържат нелинейни функции, и X е подмножество на крайно двумерен вектор пространство.

Ако всички ограничения и целевата функция съдържа линейна функция, тя е - линейното програмиране проблем.

В допълнение, секции от математическата програмиране са параметрично програмиране, динамично програмиране, стохастичен програмиране. Математическо програмиране, използван за решаване на оптимизационни задачи за изследване на операциите.

екстремум метод откритие е напълно определена от клас проблеми. Но преди да се математически модел, е необходимо да се извършва на етапа на симулация 4:

1. Определяне на границите на системата за оптимизация

Изхвърлете връзките оптимизиране на обект с външния свят, които не могат да повлияят значително на резултатите от оптимизацията и, по-точно, тези, без които решението е опростена

2. Избор на контролирани променливи

"замръзва" стойностите на някои променливи (неконтролируеми променливи). Други резерви вземе някаква стойност от областта на изпълними решения (контролирани променливи)

3. Определяне на ограниченията по отношение на контролираните променливи

Избор на числен критерий за оптимизация (например показатели за изпълнение)

4. Създаване на целевата функция

Линейно програмиране - математическа дисциплина, посветена на теорията и методите за решаване на екстремални проблеми на сетовете на наш тримерно линейно пространство, определени от системи линейни уравнения и неравенства.

Линейното програмиране е специален случай на изпъкнала програмиране, което от своя страна е специален случай на математическото програмиране. В същото време тя е - на основата на методите за решаване на число и нелинейно програмиране няколко проблема. Едно обобщение на линейното програмиране е линейно-фракционна програмиране.

Фигура 44. Линейно програмиране Проблем

Много от свойствата на линейни програмни проблеми може да се тълкува като свойства на polyhedra и по този начин геометрично формулира и да ги докаже.

Терминът "програмиране" трябва да се разбира "планиране" в известен смисъл. Той бе предложен в средата на 1940-те години на Джордж Dantzig, един от основателите на линейното програмиране, дори преди компютри са били използвани за решаване на линейни оптимизационни задачи.

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

Основната трудност при решаване на проблеми Н. п. Е, че тези проблеми са на мулти и известни числени методи за решаването им предоставят обикновено на сближаването на минимизиране на последователности за локален екстремум точка.

Фигура 45. нелинейно програмиране задача

Най-проучен точка Н. п. Е изпъкнала програмиране проблем се характеризира с това, че всяка точка е локален минимум точка на световната минимум.

Ant алгоритъм (алгоритъм за оптимизация имитация мравка колония, английски мравка оптимизация колония, ACO.) - Един от най-ефективните полином време алгоритми за намиране на приблизителни решения на проблема с пътуващ търговец, както и други подобни маршрути Търсене проблеми на графики. Подходът е да се анализира и се използва поведението на мравките, които търсят пътя от колонията към източник на захранване и е metaheuristic (английски metaheuristic, мета -. «Извън» и евристичен - «ТЪРСИ») оптимизация. Първата версия на алгоритъма, предложен от Marco Dorigo доктор на науките през 1992 г., е насочена към намиране на оптималния маршрут на графиката.

<== Предишна лекция | На следващата лекция ==>
| Модул 2

; Дата: 01.07.2014; ; Прегледи: 285; Нарушаването на авторските права? ;


Ние ценим Вашето мнение! Беше ли полезна публикуван материал? Да | не



ТЪРСЕНЕ:


Вижте също:



zdes-stroika.ru - Studopediya (2013 - 2017) на година. Тя не е автор на материали, и дава на студентите с безплатно образование и използва!
Page генерирана за: 0.125 сек.