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

ПОСЛЕДОВАТЕЛЬНЫЙ АЛГОРИТМ КОМПОНОВКИ

Читайте также:
  1. XII. ЭЛЕМЕНТЫ ТЕОРИИ АЛГОРИТМОВ
  2. Алгоритм
  3. Алгоритм MD4
  4. Алгоритм RC6
  5. Алгоритм RSA
  6. Алгоритм Брезенхема для окружности
  7. Алгоритм Брезенхема.
  8. Алгоритм взятия мазка из носа и зева.
  9. Алгоритм вибіркового методу
  10. Алгоритм вставки элемента в список после элемента с указанным ключом
  11. Алгоритм выполнения прически
  12. Алгоритм вычисления кодов Шеннона — Фано

Будем описывать схему с помощью ГГ:

,

Задача: требуется разбить схему на блоки так, чтобы каждый блок содержал не более чем заданные число элементов и число внешних выводов .

В рассматриваемом алгоритме процесс формирования очередного блока начинается с выбора первого, так называемого базового элемента (БЭ). В качестве БЭ выбирается элемент, имеющий максимальное число общих цепей со всеми еще нераспределенными элементами (элемент e0 уже распределен). далее блок последовательно заполняется элементами из числа еще нераспределенных. Для этого из множества всех нераспределенных элементов выделяется подмножество таких элементов, распределение которых в блок не приводит к превышению заданного числа выводов из блока. Из них в блок распределяется элемент, имеющий максимальное число общих цепей со всеми элементами, уже распределенными в блок. Если таких элементов несколько, то среди них выбирается элемент, при добавлении которого в блок число выводов из блока минимально. Если и таких элементов несколько, то выбирается элемент с максимальным порядковым номером (для формализации задачи).

Рассмотрим более подробно процедуру формирования блока bj. Будем считать, что блоки b1, b2, …, bj-1 уже сформированы. Пусть Ij – множество элементов, нераспределенных в эти предшествующие блоки, т. е.

,

где E(bk) – множество элементов блока bk.

Последовательный алгоритм компоновки можно представить в следующем виде.

П. 1.

При выборе БЭ для всех элементов вычисляется оценка L1(x).

,

Здесь qk – связи элемента со всеми нераспределенными элементами,

V(x) – множество цепей, инцидентных элементу x,

E(vk) – множество элементов, инцидентных цепи vk,

L1(x) – число связей элемента x со всеми еще неразмещенными элементами.

В блок распределяется элемент с максимальной оценкой L1(x). Если таких элементов несколько, то выбирается элемент с большим порядковым номером (для формализации задачи).

П. 2.

Пусть на t -м шаге формирования блока bj имеется множество элементов , распределенных к этому шагу в блок bj (). При определении очередного элемента для всех нераспределенных элементов вычисляется оценка L2(x).

,

Здесь – множество цепей, инцидентных всем элементам блока bj к шагу t, включая элемент x,

L2(x) – число выводов блока bj на шаге t с учетом элемента x.

П. 3.

Для всех элементов x, для которых выполняется условие , вычисляется оценка L3(x) – число связей элемента x с формируемым блоком .

,

В блок bj включается элемент с максимальной оценкой L3(x). Если таких элементов несколько, то среди них выбирается элемент с минимальной оценкой L2(x). Если и таких элементов несколько, то выбирается элемент с максимальным порядковым номером (для формализации задачи).

П. 4.

Если ни для одного элемента условие не выполняется, то дополнение блока bj прекращается и начинается формирование следующего блока (переход к п.1).

П. 5.

Алгоритм заканчивает работу когда все элементы схемы распределены в блоки.

При практической реализации алгоритма вместо формулы (4.2) для определения числа выводов из блока удобно использовать формулы для приращения числа выводов из блока bj при добавлении в него элемента x.

,

где – количество выводов блока bj до добавления в него элемента x.

,

Последнее выражение (для ∆ pk) можно пояснить с помощью рисунка 4.1.

Рис. 4.1.

Рассмотрим работу последовательного алгоритма компоновки на примере.

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

Перед началом компоновки множество нескомпонованных элементов I1 содержит все элементы схемы кроме e0 (элемент e0 уже распределен).

Рис. 4.2.

Для выбора БЭ вычислим оценку L1(x) по формуле (4.1) для всех элементов множества I1.

В соответствии с формулой (4.1) .

Вычисляя подобным образом оценки L1(x) для элементов e2, e3, …, e9 определим, что максимальным числом связей со всеми еще неразмещенными элементами обладает элемент e7.

Аналогично вычисляются оценки L2(x) и L3(x). Вычислим, например, L3(e9) – связи элемента e9 с элементами формируемого блока, в который вошли элементы e7 и e8 (см. ниже).

Таким образом .

Результаты вычислений удобно свести в таблицу.

  L1 L2 L2 L3 L1 L2 L1 L2 L3
                   
e1   5+3>6 4+3>6 –– 4* –– –– –– ––
e2   5+3>6 4+3>6 ––   4+1   4+1 2*
e3   5+3>6 4+2=6     4+3 –– 4+3 ––
e4   5+2>6 4+2=6     4+0 3* –– ––
e5   5+2>6 4+0<6*   –– –– –– –– ––
e6   5+2>6 4+2=6     4+1   4+1  
e7 5* –– –– –– –– –– –– –– ––
e8   5-1<6* –– –– –– –– –– –– ––
e9   5+3>6 4+2=6     4+2   4+2  

 

В качестве БЭ блока b1 выбираем элемент e7 с максимальной оценкой L1(x)=5.

Для остальных элементов схемы вычисляем оценку L2(x) – выводы. Результаты сведем в графу 3 таблицы.

Всего один элемент e8 может быть включен в блок b1 без нарушения контактного ограничения . Таким образом, , количество выводов из блока – четыре.

Для выбора очередного элемента блока b1 вычислим оценки L2(x) для нескомпонованных элементов (графа 4 таблицы).

Для элементов () e3, e4, e5, e6, e9 вычислим оценки L3(x) – связи (графа 5таблицы).

При одинаковых максимальных оценках L3max=2 элемент e5 дает меньшее число выводов из блока (четыре) чем элемент e4, поэтому состав блока b1={e7, e8, e5}; P1=4, S1=3.

Формирование второго блока проведем аналогично первому (графы 6 – 10).

Состав b2={e1, e4, e2}.

Оставшиеся элементы распределим в блок b3 с P3=6.

Количество межблочных связей при данном варианте компоновки – десять.

При решении задачи компоновки на ПЭВМ целесообразно использовать списки элементов по цепям и списки цепей по элементам с соответствующими разделителями (см. § 2, Гиперграф).

Для схемы рис. 4.2 список элементов по цепям и соответствующий список разделителей имеют следующий вид:

Аналогично составляются список цепей по элементам ST и список разделителей RST.

Схема последовательного алгоритма компоновки приведена на рисунке 4.3.

Рис. 4.3. Схема последовательного алгоритма компоновки


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 сек.)