АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Описание каналов

Читайте также:
  1. II. ОПИСАНИЕ МАССОВОЙ ДУШИ У ЛЕБОНА
  2. XI. Описание заболевания
  3. Анализ основных конкурентов (схема и описание)
  4. Античное историческое сознание и историописание
  5. Античное историческое сознание и историописание – с. 74-75
  6. Библиографическое описание
  7. Библиографическое описание как форма свертывания информации
  8. Блокаторы кальциевых каналов
  9. Вопрос1 Кинематическое описание движения материальной точки
  10. Вопрос№3 Виды механического движения, графическое описание, харакеристики.
  11. Время ожидания при прохождении проливов и каналов
  12. Выбор каналов сбыта

                   
   
top
 
 
       

                 
                 
             
               
*
*
*
*
*
*
*

 

 
*

           

 
 
bottom

 

 


Канал описывается двумя последовательностями 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 для предотворощения наложения вертикальных сегментов цепей.

Для наших последовательностей г.в.о. на рис.:

 

 

 
 
рис. 2а

 


Например, на рисунке выше в г.в.о. существует путь из 1 в 6. Значит, что цепь 1 должна быть расположена выше цепи 6, чтобы не было наложений вертикальных сегментов на 1 и 6 контактов. Чтобы задача решалась в рамках классической постановки задачи граф GV должен быть ацикличным, иначе задача может быть решена только с введением изломов, а это противоречит условиям клас. постан. задачи.



 

Далее будем использовать расширенный г.в.о. (р г.в.о.)

GRV = {Enet, Erv}

Enet – множество вершин, соответствующих множеству цепей net

Erv – множество направляющих ребер.

Ребро (n, m) принадлежащее Erv существует тогда, когда в г.в.о. существует путь из вершины n в m.

 

       
 
   
рис. 2б
 

 


На рисунке 2а в г.в.о. есть путь из 4 в 5 через 3. Следовательно, в р.г.в.о. существует ребро (4, 5) и (4, 6)

Горизонтальные ограничения представлены не ориентированным графом гориз. огран. (г.г.о)

GН = {Enet, Eн}

Eн – множество ребер.

Ребро (n, m) принадлежащее Eн существует тогда, когда магистрали для n и m разнесены для исключения наложения горизонтальных сегментов n и m.

       
 
   
рис. 2в
 

 


На рисунке 2в г.г.о. есть путь из 1 в 6, значит, что цепь 1 должны быть расположена выше 6, чтобы не было горизонтальных наложений. Цепи 1 и 5 могут быть расположены на одной магистрали. Цепь 1 и 2 тоже.

 


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 | 24 |


Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.007 сек.)