<<
>>

Символьное представление решения задачи канальной трассировки

Разобьем множество горизонтальных фрагментов F на под­множества F⅛, F = {Fk | k = 1,2,..., V}, в соответствии со сле­дующими правилами:

2. Любые два участканаходятся в го­

ризонтальном конфликте и не могут быть помещены в одну магистраль.

3. Подмножества F. сформированы и пронумерованы так, что все левые концы участков F.

расположены в канале левее всех левых концов участков F.+ ι.

Рассмотрим процедуру разбиения F на F.. Обозначим через liи riлевый и правый концы горизонтального участка fi. Каж­дый liи riимеют свою абсциссу. Сформируем упорядоченный массив A, состоящий из концов отрезков fi∈F. Концы в массиве A располагаются по возрастанию их абсцисс. Если liи rj∙ имеют одну и ту же абсциссу, то rj∙ в A располагается за li.

Алгоритм Al

1. k = 1 (к — номер подмножества).

2. Выбирается очередной, начиная с первого, элемент масси­ва A, если все элементы рассмотрены, то переход к п. 5.

3. Если выбранный элемент является левым концом li,то fi включается в Fk и переход к п. 2, иначе — к п. 4.

4. Если выбранный элемент является правым концом riи fi входит в Fk, то к = к + 1. Переход к п. 2.

5. Конец.

Алгоритм разбиения F на Fk имеет линейную трудоемкость.

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

Подмножество горизонтальных фрагментов F в соответствии с приведенным алгоритмом разбивается на подмножества

В соответствии с вышеизложенной методикой [10.] рассчи­тывается оценка минимальной ширины канала ξm. Пусть в со­ответствии с некоторым алгоритмом получено решение задачи трассировки, представленное на рис. 10.8.

Рис. 10.8. Пример трассировки в канале

Для отображения решения задачи канальной трассировки (ЗКТ) формируется матрица D. Число столбцов матрицы D равно числу подмножеств Fk, а число строк равно ξm(рис. 10.9). В каждый k-й столбец заносятся элементы множества Fk.

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

При использовании символьного пред­ставления задача трассировки сводится

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

1O.5.

<< | >>
Источник: Курейчик В. В., Лебедев Б. К., Лебедев О. Б.. Поиско­вая адаптация: теория и практика. — M.: ФИЗМАТЛИТ,2006. — 272 с.. 2006

Еще по теме Символьное представление решения задачи канальной трассировки:

  1. Графическое представление решений для пластинок в виде треугольников
  2. Аналитические методы решения двумерных задач строительной механики
  3. ПРИМЕРЫ РЕШЕНИЯ ЗАДАЧ ПО РАСЧЕТУ ЖЕЛЕЗОБЕТОННЫХ ПЛИТ
  4. 4.1. ПОСТАНОВКА И АЛГОРИТМ РЕШЕНИЯ ЗАДАЧИ ОПТИМИЗАЦИИ
  5. ПРОБЛЕМЫ РАЗВИТИЯ ГЕОМЕТРИЧЕСКИХ МЕТОДОВ РЕШЕНИЯ ЗАДАЧ ТЕХНИЧЕСКОЙ ТЕОРИИ ПЛАСТИНОК
  6. Приближенные методы решения задач технической теории пластинок
  7. Шляхов Станислав Владимирович. РАЗВИТИЕ И ПРИМЕНЕНИЕ ГЕОМЕТРИЧЕСКИХ МЕТОДОВ К РЕШЕНИЮ НЕКОТОРЫХ ЗАДАЧ ТЕХНИЧЕСКОЙ ТЕОРИИ ПЛАСТИНОК C КРИВОЛИНЕЙНЫМИ УЧАСТКАМИ КОНТУРА. Диссертация на соискание учёной степени кандидата технических наук. Орёл - 2019, 2019
  8. § 3. Порядок подачи надзорных жалоб и представлений прокурора
  9. Глава II. Зависимость между признанием и приведением в исполнение отмененного арбитражного решения и признанием судебного акта, отменяющего такое решение, в зарубежной судебной практике и доктрине
  10. Генезис теоретических представлений о персональных финансах[3]
  11. 3.1 Аналитическое представление зависимости максимальный прогиб - основная частота колебаний в упругих пластинках
  12. § 3. Обязанности банков по представлению налоговым органам сведений о финансово-хозяйственной деятельности налогоплательщиков
  13. Основные нерешенные проблемы в развитии МИКФ Цели и задачи диссертационной работы
  14. 2.16.1 Тестирование функции (2.48) в задачах поперечного изгиба пластинок с жестко защемленным контуром
  15. Основные задачи и интегральные физические характеристики, рассматриваемые в работе
  16. Тестирование функции (2.48) в задачах поперечного изгиба пластинок с шарнирно опертым контуром