Методи и оформлението на алгоритми, поставяне и PCB следа

Московски държавен институт по електроника и математика

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

2. Алгоритми оформление

3. Алгоритми настаняване

4. Алгоритми следа

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

2. СХЕМА АЛГОРИТМИ

На етапа на строителство инженеринг за въпроси за обработка, свързани с оформлението на елементи на логиката в модул, клетките, клетките в панела, и така нататък .. Тези задачи, като цяло, са тясно свързани, и решаването им значително намалява разходите и сложността на този етап в CAD. Обикновено подреждане се считат като процес на вземане на решения в някои или несигурни условия, в резултат на което част от логическия блок са разположени в структурни елементи на I-то ниво, и тези елементи са подредени в структурни елементи (I + 1) -ти слой и т. D. където местоположението се извършва с избрания критерий оптимизация.

Схемата оформление на СЕА структурно завършен част е процес на разпределение на конструктивни елементи на по-ниско ниво на най-високата в съответствие с избрания критерий. Основният режим е критерий за съвместимост elektromagnitoteplovoy елементи по-ниско ниво. Този критерий се определя границите на допустима схема за делба, в която са формулирани други критерии. Тези критерии могат да бъдат: Минималният конструктивно видове готови части, плътност договореност, минимум връзки между устройства, лекота на диагноза и т.н. Очевидно е, че връзката между външните вериги често е един от най-важните фактори, определящи надеждността на CEA .. Ето защо, най-често срещаната критерий е критерия за минимален брой външни връзки. Правейки този критерий намалява взаимното намеса, опростяване на дизайна, подобряване на надеждността, и така нататък. Г.

За изграждане на формални проблеми математически модел на оформлението е удобно да се използва теорията на графики. В тази схема тълкува ненасочена мултиграф, където всеки структурен елемент (модул) определя в съответствие мултиграф връх, и електрически комуникационни вериги - ръбове. Тогава проблемът оформление е формулиран, както следва, да зададете мултиграф G (X, U). Това изисква "отрязани" то в отделни парчета G1 (X1, U1), G2 (Х2, U2), ..., Gk (Xk, UK), така че броят на ръбове, свързващи тези парчета до минимум, т.е.

С други думи, части от дяловете на снимачната площадка на графики G считат, ако някоя част от тази група, не е празна; за всеки две пресечните части на набор от ребра могат да бъдат не-празен; обединението на всички части е точно равна на графиката Г.

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

1. алгоритми, използващи методи число програмиране.

2. последователни алгоритми

3. итеративни алгоритми

4. смесени алгоритми

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

последователни оформление алгоритми "рязане" първоначален графика G (X, U) на парчета G1 (X1, U1), G2 (Х2, U2), на ..., Gk (Xk, UK) е както следва. В графиката G (X, U) са най XI

Хе местната минимална степен

Ако няколко такива върхове, след това предпочитание се дава в началото на максималния брой на множество ръбове. От множеството от върховете съседни върха образуват част графика G1 (X1, U1), е избран този, който осигурява минимални нарастване парче връзки с още неразпределени върхове. Като се има предвид връх XI

X \ X1 включват G1 (X1, U1), ако няма нарушение на ограниченията за броя на парчета на външните отношения, т.е.

където # 945; J # 949; - елемент близост матрица първоначалното графика G (X, U); # 948 (XG) - относително тегло върховете XG ,. нарастване равен брой външни ребра парче G1 (X1, U1), когато върховете на множество XG X1 А; Е - набор от индекси връх включени в формира част от графика на предходните етапи на алгоритъм; м - максимално допустимия брой на външните контакти на едно парче с всички останали.

Този процес продължава, докато множество X1 не трябва да съдържат нищо nelementov присъединяване запазва редовен върхове XJ за парче G1 (X1, U1) няма да доведе до нарушение на ограниченията за броя на външни връзки парче връстници

Трябва да се отбележи, че стойността на

не е монотонна функция на | X1 | следователно да бъдат убедени в невъзможността на по-нататъшното формиране на парчето поради нарушение на последното ограничение е необходимо да се провери неговата неприложимост в следните стъпки, за да се увеличи множеството X1 до п. Като последен вариант е избран парче 0 G1 (X1 0, U1 0) съдържащ максималния възможен брой на върховете на G (X, U), за които следните ограничения за броя на външни връзки, и на неговите съставни пикове (Nmin -nmax).

След превръщане парче 0 G1 (X1 0, U1 0), процесът се повтаря до получаване на втори, трети и т.н. оригинални парчета на графиката, с единствената разлика, че трябва да се взема най-добрите не са включени в предишните парчета.

Ние формулира алгоритъм съвместими компоненти оформление.

Където Т, # 920; - серийни номера на образуван парче и свързващите върховете; # 945; - ограничение на броя на върховете, на парче.

3) В началния графика близост матрица | # 945; к.с. | NxN. където N- изходен брой върхове (с голяма стойност на N за намаляване на размера на паметта в самия компютър не използва близост матрица и нейното прилагане код), определяне на степента на местни пикове

4) От множеството от върховете неразпределени Xvybiraem връх XJ с # 961 (XJ) =

. Обръщаме се към твърдението 6. Ако няколко такива върхове, след което се процедира претенция 5

5) От Xl подгрупа от върха със същата локална степен XJ избран връх с максимален брой от множество ребра (минимален брой съседни върха), т.е. | Gxj | =

6) на съхранение като се излиза връх графика образува парче

. Продължете претенция 10

7) В близост матрица