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

Возможно введение двух точек разрыва ДС. При этом два фрагмента ДС, связывающие каждый точку разрыва с терминалом исходного ДС, будут уложены, а третий фрагмент, связывающий две точки разрыва, будет укладываться в последующих магистралях. Таким образом исходное ДС трансформируется в ДС, связывающее две точки разрыва. Отметим, что ДС может в процессе укладки подвергаться нескольким последовательным трансформациям. На рис.3б в дальнейшем ДС1, ДС2, ДС4 будут рассматриваться, как ДС связывающие пары несвязных терминалов, помеченных соответственно (11,1¢2), (21,2¢2),(4¢1,4¢2).

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

На рис.4а проведены горизонтальные фрагменты от терминалов 11 до 1¢1 и от 21 до 2¢2. В дальнейшем ДС1 и ДС2 трансформируются, т.е. они будут инцидентны терминалам 1¢1  и  2¢2 соответственно. Перед резервацией анализируется состояние столбцов и если необходимо и существует возможность формируется ближайший к терминалу свободный столбец.

Если есть несколько столбцов, занятых терминалами одной цепи и эти терминалы уже связаны, то их можно объединить в один терминал, что приводит к освобождению столбцов. Например на рис.4в при резервации терминала 23 два столбца заняты терминалами 1¢2 и 12. 1¢2 входит в ДС(1¢1 , 1¢2), 12 входит в ДС (12, 13), но они связаны и их можно объединить в один терминал1¢2, при этом ДС(12,13) трансформируется в ДС (1¢2, 13). Это приводит к освобождению столбца в который можно поместить терминал 2¢3, связанный горизонтальным фрагментом с резервируемым терминалом 23.

Представим хромосому Hk виде матрицы Vk, где каждый столбец соответствует гену. Магистрали заполняются последовательно, начиная с первой. Заполнение магистралей осуществляется следующим образом. Вначале осуществляется резервация терминалов левой и правой сторон ОТ, лежащих на магистрали. Затем последовательно по строкам, начиная с первой в пределах строки слева направо просматриваются элементы матрицы Vk. Для каждого выбранного элемента матрицы (ДС) определяется возможность его размещения в формируемой магистрали. Если возможно, то ДС полностью или частично помещается в формируемую магистраль. Если ДС полностью помещается, то оно удаляется из матрицы Vk. Если ДС помещается частично, то трансформируется и остается в матрице. По окончании просмотра матрицы Vk осуществляется сжатие всех столбцов, из которых удалялись ДС, снизу вверх. После этого осуществляется переход к заполнению следующей магистрали. Процесс декодирования и заполнения магистралей показан на рис.5 и 6 для ОТ представленных соответственно  на рис.1а и 1б. Отметим, что это фактически одна и та же задача трассировки.

Рассмотрим сначала процесс укладки в ОТ1, показанный на рис.1а. На рис.5а показаны два этапа заполнения первой магистрали: резервация и укладка. Вначале осуществляется резервация терминала 33, лежащего на 1-й магистрали. Для этого от терминала 33 проводится горизонтальный фрагмент до ближайшего свободного столбца. Терминал 33 резервируется терминалом 3¢3, а ДС32=(32,33) трансформируется в ДС32¢=(32,3¢3). Затем проводится укладка ДС в первую магистраль. Просматривается матрица Vk и первым выбирается ДС31=(31,32). ДС31 укладывается частично, при этом трансформируясь в ДС31¢=(31,3¢2). Следующим из Vk выбирается ДС32¢, которое полностью помещается в первую магистраль и удаляется из Vk . Процесс заполнения завершается и Vk сжимается. На рис.5б заполняется вторая магистраль. Вначале резервируются терминалы 21 и 42, ДС21=(21,22) и ДС4=(41,42) трансформируются в ДС21¢=(2¢1,22) и ДС4¢=(41,4¢2).

Затем просматривается матрица Vk. ДС31¢ не помещается, ДС4¢ помещается полностью и удаляется из Vk , которое потом сжимается. На рис.5в,г,д, показан процесс укладки 3, 4, и 5-й магистралей.

При заполнении 3-й магистрали (рис.5в) в результате трансформации образуются ДС31¢¢=(3¢1,3¢2), ДС11¢=(11,1¢2), ДС12¢=(1¢¢2,1¢3). Полностью помещается ДС31¢, частично ДС12 и ДС11.

При заполнении 4-й магистрали (рис.5г) при трансформации образуется ДС12¢¢=(1¢¢2,1¢3). Полностью помещаются ДС12¢, ДС22,  ДС21¢.

При заполнении 5-й магистрали (рис.5д) полностью помещаются ДС11¢, ДС5.

Рассмотрим процесс заполнения ОТ2, представленной на рисунке 1б.

На рис.6а заполняется первая магистраль. Вначале резервируется терминал 51 лежащий на 1-й магистрали. ДС5=(51,52) трансформируется в ДС5¢=(5¢1,52). Затем при просмотре Vk выбирается ДС11 которое частично укладывается в 1-ю магистраль и трансформируется в ДС11¢=(11,1¢2).

При заполнении 2-й магистрали (рис.6б) вначале резервируется терминал 11 при этом ДС11¢ трансформируется в ДС11¢¢=(1¢1,1¢2). Для резервации терминала 23 формируется свободный столбец. Для этого терминалы 1¢2 Î ДС11¢¢ и 12 Î ДС12, поскольку они уже связаны, объединяются в терминал 1¢2, а столбец, занятый терминалом 12, освобождается. ДС12=(12,13)трансформируется в ДС12¢=(1¢2,13). После этого терминал 23 резервируется терминалом 2¢3, а ДС22=(22,23) трансформируется в ДС22¢=(22,2¢3). При просмотре Vk полностью во 2-ю магистраль помещается только ДС11¢¢, которое удаляется из Vk.

При заполнении 3-й магистрали (рис.6в) резервируются терминалы 21 и 52. Трансформируются: ДС21=(21,22) в ДС21¢=(2¢1,22), ДС5¢=(5¢1,52) в ДС5¢¢=(5¢1,5¢2). Полностью помещается только ДС5¢¢, которое удаляется из Vk.

При заполнении 4-й магистрали (рис.6г) резервируется терминал 41. ДС4=(41,42)  трансформируется в ДС4¢=(4¢1,42). При просмотре Vk частично

помещается ДС12¢ и полностью ДС4¢. ДС12¢ трансформируется в ДС12¢¢=(1¢¢2,13), а ДС4¢ удаляется из Vk.

При заполнении 5-й магистрали (рис.6д) резервируются терминалы 31.и 13. ДС31=(31,32) трансформируется в ДС31¢=(3¢1,32), а ДС12¢¢=(1¢¢2,13) в ДС12¢¢¢=(1¢¢2,1¢3). При просмотре Vk полностью помещаются ДС21¢, ДС22¢, ДС31¢, ДС12¢¢, которые удаляются из Vk.

При заполнении 6-й магистрали (рис.6е) полностью помещается ДС32.

При заданных способах кодирования ОТ1 и ОТ2, при декодировании хромосом Hk, соответствующих ОТ1 и ОТ2 и представляемых в виде вышеприведенных матриц Vk, конечные результаты совпали, хотя это и не является обязательным.

Матрица Vk просматривается при заполнении каждой магистрали. Размер матрицы Vk пропорционален числу as содержащихся в ней ДС.

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





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