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

   1.  , " (ij) [i Çj =0]

   2.  В пределах каждого  k все участки накладываются друг на друга, т.е

" (ij ½i Îk & j Îk) [(O(lj) £ O(li) £ O(rj))Ú((O(lj) £ O(ri) £ O(rj))].

Подмножество k пронумерованы и сформированы так, что все левые          концы участков k расположены левее левых концов участков k+1, т.е.          " (ij ½i Îk & j Îk+1) [(O(li) < O(lj) )].

Линейный алгоритм разбиения представлен в работе [7]. Разбиению  соответствует разбиение  S.

       Для участков, представленных на рис.2а, разбиение S имеет вид:

  S1={21,31,11} ,S2={32,4,12,22,5};

Для участков, представленных на рис.2б, разбиение S имеет вид:

  S1={11,21,4,31},  S2={22,32},  S3={12,5}.

Для ОТ1, представленной на рисунке 1а, m=5, для ОТ2, представленной на рис.1б, m=6, где m - число горизонтальных линий на ОТ.

Формируем на основе каждого Sk вектор Vk путем добавления в Sk нулевых элементов, так, чтобы мощность Vk была равна m, и фиксируем взаимное расположение элементов.

Для ОТ1:   V1=; V2=.

Для ОТ2: V1=; V2=; V3=.

Полученный после дополнения набор векторов V={Vi} будем называть решением задачи трассировки коммутационного блока.

Представим решение в виде хромосомы. Хромосома Hm является упорядоченной совокупностью генов . Ген  является одним из вариантов вектора Vi, т.е. значением  является некоторый вектор . Гены  и  хромосом Hm и Hl гомологичны, они одинаковы по составу элементов, соответствуют одному и тому же подмножеству Si двухтерминальных соединений, но отличаются порядком расположения элементов.

Декодирование хромосомы осуществляется с помощью процедуры декодирования, использующей идеи алгоритма «левого конца» при канальной трассировке. Как и при канальной трассировке будем называть горизонтальные линии опорной сетки ОТ магистралями, пронумерованными сверху вниз.

Процедура декодирования заключается в последовательном заполнении магистралей, начиная с первой,  фрагментами двухтерминальных соединений.

Порядок в котором ДС выбирают для заполнения магистралей задается соответствующей хромосомой и фактически определяется порядком расположения элементов в генах.

Заполнение магистралей двухтерминальными соединениями базируется на трех основных процедурах: укладки, трансформации, резервации.

В процессе укладки  ДС в заполняемую магистраль оно может быть уложено либо полностью, либо частично, либо не укладываться вообще.

При полной укладке в заполняемую магистраль полностью помещаются все горизонтальные составляющие ДС и осуществляется подвод к ним всех вертикальных составляющих. Для этого необходимо, чтобы были свободны с одной стороны соответствующий участок горизонтальной магистрали, а с другой стороны вертикальные столбцы, по которым осуществляется прокладка вертикальных составляющих.

Вертикальный столбец считается занятым (зарезервированным) для любой цепи ni не равной nf если в нем расположен выше заполняемой магистрали терминал, помеченный цепью nf и еще не связанный. Если терминал, расположенный выше n-ой магистрали, связывается по вертикали с горизонтальным участком, расположенным на n-ой магистрали, то столбец начиная с магистрали n+1, считается свободным. Изначально все столбцы, подходящие к помеченным цепями терминалам, расположенным на верхней стороне ОТ, считаются занятыми (зарезервированными). Например на рис.3а полностью размещены ДС1, ДС2 ДС3. На рис.3б частично размещены ДС1,ДС2,ДС4. При частичной укладке вводится точка разрыва ДС. Частично уложенное ДС связывает точку разрыва с одним из терминалов исходного ДС.

Точка разрыва вводится таким образом, чтобы у горизонтальной составляющей была максимально возможная длина.

После частичного размещения ДС проводится его трансформация, заключающаяся в том, что терминал, связанный с частично размещенным ДС переносится в точку разрыва. В дальнейшем ДС рассматривается как ДС, связывающее еще не связный терминал с терминалом в точке разрыва.

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



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

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