|
|||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция |
Описание каналов
Канал описывается двумя последовательностями top и bottom, в которых размещаются верхние и нижние линейки контактных площадок каналов. Размер обеих последовательностей равен С – число колонок в канале Множество цепей определяется как Net = {N1, N2, …, Nn} (n – это число цепей)
Пр. top = {1, 0, 3, 1, 4, 2, 3, 2}; bottom = {6, 4, 6, 6, 3, 0, 5, 5}; n = 6; C = 8 Элемент 0 в top и bottom обозначают, свободный контакт на рисунке показан эскиз канала с разведенными цепями. Показан эскиз для хромосомы = (0, 0, 0) – (см. ниже)
Горизонтальные и вертикальные ограничения При канальной трассировке не допускается наложения вертикальных и горизонтальных сегментов цепей. Для решения этой задачи вводятся графы вертикальных и горизонтальных ограничений. Вертикальные ограничения описываются ориентированным графом вертикальных ограничений (г.в.о.) GV = {Enet, Ev} Enet – множество вершин, соответствующих множеству цепей net Ev – множество направляющих ребер. Ребро (n, m) существует тогда, когда цепь n расположена выше цепи m для предотворощения наложения вертикальных сегментов цепей. Для наших последовательностей г.в.о. на рис.:
Например, на рисунке выше в г.в.о. существует путь из 1 в 6. Значит, что цепь 1 должна быть расположена выше цепи 6, чтобы не было наложений вертикальных сегментов на 1 и 6 контактов. Чтобы задача решалась в рамках классической постановки задачи граф GV должен быть ацикличным, иначе задача может быть решена только с введением изломов, а это противоречит условиям клас. постан. задачи.
Далее будем использовать расширенный г.в.о. (р г.в.о.) GRV = {Enet, Erv} Enet – множество вершин, соответствующих множеству цепей net Erv – множество направляющих ребер. Ребро (n, m) принадлежащее Erv существует тогда, когда в г.в.о. существует путь из вершины n в m.
На рисунке 2а в г.в.о. есть путь из 4 в 5 через 3. Следовательно, в р.г.в.о. существует ребро (4, 5) и (4, 6) Горизонтальные ограничения представлены не ориентированным графом гориз. огран. (г.г.о) GН = {Enet, Eн} Eн – множество ребер. Ребро (n, m) принадлежащее Eн существует тогда, когда магистрали для n и m разнесены для исключения наложения горизонтальных сегментов n и m.
На рисунке 2в г.г.о. есть путь из 1 в 6, значит, что цепь 1 должны быть расположена выше 6, чтобы не было горизонтальных наложений. Цепи 1 и 5 могут быть расположены на одной магистрали. Цепь 1 и 2 тоже.
Поиск по сайту: |
Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.005 сек.) |