4128-1 (662804), страница 2

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

Гораздо чаще работает следующее правило. Заметим, что работа нижеследующих правил во многом совпадает с аналогичными правилами для ликвидадии ВК 1-го и 2-го типов, в тоже время, имея существенные отличия.

Правило 3

Если существует свободная колонка в зоне между x¹_i/min и x²_i/max где i=1,2,...,n с координатой X

ТО в точке P^t_xT вводится псевдоконтакт - 1 и все остальные P₁ Т получают статус - 1, а в координате P^l_xL вводится псевдоконтакт 1.

Правило 4

Если существует свободная от вертикальных сегментов слева (справа) от зоны n-звенного ВК с координатой Х. И эта колонка ближайшая среди всех свободных колонок к зоне ВК ТО в точке P^t_xT вводится псевдоконтакт - 1 ( -n ) и все остальные P₁ T (P_n T) получают статус - 1 (-n), а в координате P^l_xL вводится псевдоконтакт 1(n). Решение может быть получено, если X располагается слева от зоны ВК и решение получается, если X - справа от зоны ВК. Получение двух различных решений, в зависимости от того, с какой стороны ВК располагается ближайшая свободная колонка, связано с тем, чтобы одновременно с ликвидацией ВК минимизировать длину соединений.

Дальнейшие правила по ликвидации ВК 3-го типа полностью совпадают с правилами № 4, 5, 6 ддя ликвидации ВК 1-го, 2-го рода. Только в данном случае дни получат номера соответственно 5, 6, 7.

Особо стоит вопрос о ликвидации ВК 4-го типа. Несмотря на то, что в практических задачах ВК 4-го типа встречаются крайне редко, их ликвидация представляет наибольшие сдожности. В рабо-те предлагается подход к решению указанных ВК на основе их де-композиции и приведению к ВК 1-го, 2-ro и 3-го типов с после-дующей ликвидацией последних на основе вышеописанной технологии.

Отметим, что возможны два варианта ВК 4-го типа. Для того, чтобы определить вариант ВК 4-го типа необходимо организовать просмотр направленных дуг ГВО. Если из последней по номеру вершины ГВО существует направленное ребро к первой вершине, то ВК вложенного типа. Если такого ребра не существует, то ВК секционного типа с числом секций равным числу ребер, организующим путь из n-вершины в 1-ю, при этом на каждом шаге выбирается то ребро среди альтернативных, которое ведет к вершине с минимально возможным номером.

Решение секционных ВК 4-го рода очевидно. Необходимо разбить такой ВК на секции и обрабатывать каждую секцию по отдельности (заметим, что ВК может быть 1-го, 2-го, 3-го, а так же ВК 4-го рода вложенного типа).

ВК вложенного типа можно решить последовательным "раскрытием" внешних ВК. На первом шаге применено правило 4 для ВК 3-го типа. На втором шаге ликвидирован ВК 1-го типа путем применения правила 2 для ликвидации ВК 1-го типа

В результате произведен анализ существующих алгоритмов канальной трассировки и на его основе сделан выбор в пользу применения в САПР безизломных канальных трассировщиков ввиду того, что в мире разработано большое число безизломных канальных трассировщиков с широким спектром характеристик от очень быстрых с низким качеством решения до точных получающих решения близкие к оптимальным. Такая ситуация дает возможность гибкой тактике применения различных трассировщиков. Кроме того безизломные канальные трассировщики наиболее щироко применяються практически. Ввиду того, что безизломные канальные трассировщики имеют резервы повышения качества решения, а также исключают возможность решения ВК предлагается повышение качества автоматической трассировки на основе метода систем продукций. Предлагаемая система содеркит эвристические полиномиальные процедуры ликвидации ВК.4 Разработаны группы решающих правил по форме "ЕСЛИ" - "ТО" для ликвидации ВК и сокращения m^* за счет свойств ВК и декомпозиции горизонтальных сегментов. Форма представления правил позволяет легко их модифицировать или изменить в случае появления новых знаний о предметной области.

Список литературы

Для подготовки данной работы были использованы материалы с сайта http://pitis.tsure.ru

Характеристики

Список файлов реферата