Предыдущая страница реферата | 1  2  3  4 | Следующая страница реферата

Таким образом, путем введения "излома" в области конфликта возможна его ликвидация Отметим, что введение излома будет произведено там, где совпадут абсциссы отрезков j и -j в области введения псевдоконтактов.

Правило 3 во многом сходно с правилом 2. Однако, в отличие от последнего, поиск свободной колонки осуществляется не в области конфликта, а вне его. При этом поиск производится последовательно слева - справа от зоны конфликта. Таким образом обеспечивается нахождение ближайшей к зоне свободной колонки.

Правило 3

Если существует свободная колонка от вертикальных сегментов слева (справа) от зоны ВК с координатой Xn3. И эта колонка ближайшая среди всех свободных колонок в зоне конфликта. То в точке Pxtn3ÎT вводится псевдо контакт –j и все остальные Pj Î T получают статус –j, а в координате Pxln3ÎL  вводится псевдоконтакт j.

В том случае, когда свободные колонки в области канала отсутствуют, необходимо вводить излом в области ВК, но для того, чтобы избежать наложения отрезков в одинаковых слоях, необходима будет соответствующая модификация ГВО.

Ввиду того, что такое решение предусматривает увеличение плотности участка ВК, то правило содержит соответствующую проверку значений плотности.

Правило 4

Если Dmаxk в области конфликта меньше, чем Dmax, То проиэвольному Pk Î Т назначается дополнительный индекс -j и всем Рj Î Т назначается -j, а Pj Î L назначается дополнительный индекс j, Xpk = Xpl. При этом отрезок k в ГВО должен располагаться выше, чем -j, а отрезок l выше, чем i.

Правило 5 напоминает правило 4, однако вводит излом в той колонке i, в которой не произойдет увеличение плотности Di до Dmax. Делался это в целях минимизации ширины канала.

Правило 5

Если колонка, для которой Di = Dmax располагается в области ВК И существует колонка S вне области ВК, для которой Dmax–Ds ³ 2 И такая колонка ближайшая среди всех, удовлетворяющих ранне приведенным условиям к области ВК. ТО в колонке S назначаются доподнительные индексы -j и j с соответствующей корректировкой ГВO, а также всем Pj Î Т назначается -j. И, наконец, последнее правило, предлагаемое в работе:

Правило 6

Если существует конфликт. ТО слева (справа) от области канала ввести дополнительную колонку S, при этом Ps Î Т назначить -j и всем Pj Î T назначить -j, a Ps Î L назначить j.

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

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

Правило 1

Если между координатами n - конфликтующих отрезков x1i/min  и x2i/max , где i = 1, 2, …,n  не существует отрезков с номерами, отличными от 1, 2, …, n ТО расположить 1e и 2, …,ne соединения целиком в разныхслоях с наложением горизонтальных сегментов.

Работа правила проиллюстрирована на рис. 2. Правило эф-фективно, т.к. для разрешения конфликта n -соединений требует ( п-1 ) магистралей. Однако, такие ситуации сравнительно редко возникают на практике.

Рассмотрим следующее правило.

Правило 2

Если " из колонок с координатами x11/min=x1n/min или x21/max=x2n/max не существует пересекающих ее горизонтальных сегментов ТО расположить вертикальные и горизонтальные сегменты соединений 1 и n соответствующей колонки в разных слоях. Работа правила поясняется на рис. 1.3, откуда видно, что для решения n-звенного конфликта 3-го типа требуется n- магистралей. Заметим, что хотя Правило 2 используется чаще, чем Правило 1, но такие ситуации также сравнительно редки.

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

Правило 3

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

ТО в точке PtxaÎT вводится псевдоконтакт - 1 и все остальные P1 Î Т получают статус - 1, а в координате PlxaÎL вводится псевдоконтакт 1.

Рекомендуем скачать другие рефераты по теме: учреждения реферат, рефераты,.



Предыдущая страница реферата | 1  2  3  4 | Следующая страница реферата

Поделитесь этой записью или добавьте в закладки