Последовательный алгоритм компоновки и списковые страницы данных
Будем описывать схему с помощью ГГ:
Задача: требуется разбить схему на блоки В рассматриваемом алгоритме процесс формирования очередного блока начинается с выбора первого, так называемого базового элемента (БЭ). В качестве БЭ выбирается элемент, имеющий максимальное число общих цепей со всеми еще нераспределенными элементами (элемент e0 уже распределен). далее блок последовательно заполняется элементами из числа еще нераспределенных. Для этого из множества всех нераспределенных элементов выделяется подмножество таких элементов, распределение которых в блок не приводит к превышению заданного числа выводов из блока. Из них в блок распределяется элемент, имеющий максимальное число общих цепей со всеми элементами, уже распределенными в блок. Если таких элементов несколько, то среди них выбирается элемент, при добавлении которого в блок число выводов из блока минимально. Если и таких элементов несколько, то выбирается элемент с максимальным порядковым номером (для формализации задачи). Рассмотрим более подробно процедуру формирования блока bj. Будем считать, что блоки b1, b2, …, bj-1 уже сформированы. Пусть Ij – множество элементов, нераспределенных в эти предшествующие блоки, т. е.
где E(bk) – множество элементов блока bk. Последовательный алгоритм компоновки можно представить в следующем виде. П. 1. При выборе БЭ для всех элементов
Здесь qk – связи элемента со всеми нераспределенными элементами, V(x) – множество цепей, инцидентных элементу x, E(vk) – множество элементов, инцидентных цепи vk,
L1(x) – число связей элемента x со всеми еще неразмещенными элементами. В блок распределяется элемент с максимальной оценкой L1(x). Если таких элементов несколько, то выбирается элемент с большим порядковым номером (для формализации задачи). П. 2. Пусть на t -м шаге формирования блока bj имеется множество элементов
Здесь L2(x) – число выводов блока bj на шаге t с учетом элемента x. П. 3. Для всех элементов x, для которых выполняется условие
В блок bj включается элемент с максимальной оценкой L3(x). Если таких элементов несколько, то среди них выбирается элемент с минимальной оценкой L2(x). Если и таких элементов несколько, то выбирается элемент с максимальным порядковым номером (для формализации задачи). П.4. Если ни для одного элемента П. 5. Алгоритм заканчивает работу когда все элементы схемы распределены в блоки. При практической реализации алгоритма вместо формулы (4.2) для определения числа выводов из блока удобно использовать формулы для приращения числа выводов из блока bj при добавлении в него элемента x.
где
Последнее выражение (для ∆ pk) можно пояснить с помощью рисунка 4.1. 14.Алгоритм Рабина. Увеличение быстродействия в алгоритме Рабина достигается за счёт преимущественного распространения волны в направлении ячейки-цели. В алгоритме Ли, который является реализацией метода динамического программирования, такая целенаправленность при поиске трассы отсутствует.
Алгоритм Рабина, который реализует метод ветвей и границ, позволяет также, как и алгоритм Ли, находить глобальный оптимум целевой функции. Пусть требуется найти путь минимальной длины между ячейками А и В. Рассмотрим некоторую ячейку Сi, включаемую в очередной фронт волны. Значение волновой функции Pi, приписываемое Сi ячейки фронта, определяется из выражения:
Нетрудно видеть, что Согласно методу ветвей и границ, оптимальное решение следует искать в подмножестве решений, имеющем наилучшую оценку. Согласно методу ветвей и границ, оптимальное решение следует искать в подмножестве решений, имеющем наилучшую оценку. В соответствии с этим в сформированном очередном фронте волны выделяют подмножество ячеек с min оценкой 1 и распространение волны на следующем шаге осуществляется из ячеек этого подмножества. Заметим, что для сокращения зоны поиска, распространение волны в алгоритме Рабина осуществляется в первую очередь, из тех ячеек с min оценкой, которые получили эту оценку последними.
Эффективность алгоритма Рабина по сравнению с алгоритмом Ли показана на рис. 1, на котором для каждой ячейки ДПР указано значение весовой функции Pi. Цифрами в правых углах ячеек обозначена последовательность просмотра ячеек на этапе распространения волны стрелками указаны путевые координаты ячеек.
Примечание. Волна распространяется от ячейки с минимальным значением весовой функции и большим порядковым номером. В данном примере рассмотрено всего45ячеек ДРП вместо84ячеек обычного алгоритма Ли.
Воспользуйтесь поиском по сайту: ![]() ©2015 - 2025 megalektsii.ru Все авторские права принадлежат авторам лекционных материалов. Обратная связь с нами...
|