Размещение очередного элемента методом максимальной связности




 

В последовательных алгоритмах размещение каждой вершинывыполняется в два шага.

На первом выбирается очередная вершина для размещения. Дляее выбора используются те же правила, что и при компоновке –вершина должна иметь максимальное число связей с ужеразмещенными вершинами. Для ее выбора можно использовать коэффициентвнешней связности

 

.

Но здесь – количество связей вершины с уже размещенными.

На втором шаге выбирается позиция для размещения вершины.В этой позиции должна быть минимальна суммарная длина связейвершины

 


Обычно просматриваются свободные позиции, соседние с занятыми.Рассмотрим пример. Матрицей смежности R описан кусок графа,который необходимо отобразить в координатную решетку 3х3. Вершины 1, 4 и 7, соответствующие разъему, размещены слева (наоси s), как это показано на рис.1, а. Справа от матрицы приведены локальные степени неразмещенных вершин.

Рисунок 1 – Размещение вершин графа:

а – координатная решётка с вершинами разъема;

б - размещение вершины 2; в – результат размещения

Размещение начинаем с выбора очередной вершины. Для этого выделим подмножество еще неразмещенных вершин, имеющих связи с уже размещенными γ = {2, 3, 5, 8, 9}. На первом шаге это вершины, имеющие связи с разъемом. Для каждой из этих вершин вычислим коэффициент внешней связности. Для первой вершины, получим

 

 

Вычисляя аналогичным образом, получим для остальных вершин из γ: , , , . Максимальное значение имеет , поэтому первой размещаем вершину 2 (рис. 1, б). В позициях 2.1, 2.2 и 2.3 вычисляем суммарную длину связей вершины. Для каждой из позиций

. Как видно из рисунка, минимальна и равна 4 в позиции 2.1. В позиции 2.2 = 5, а в 2.3 - = 7. Аналогично производится выбор и размещение остальных вершин. В данном примере вершины будут выбраны в следующем порядке: 5, 3, 6, 8 и 9. Для 8-й и 9-й вершин порядок их выбора и позиции размещения равноценны. При решении задачи первой из них была размещена 8-я вершина, и в единственную оставшуюся незанятой позицию поместили вершину 9 (рис. 1, в). Суммарная длина связей для полученного варианта размещения равна 41.

 

Размещение очередного элемента методом относительной связности

 

В качестве метода выбора очередного элемента, возможно использовать правило, основанное на оценке числа связей неразмещённого элемента как с размещенными, так и с неразмещенными элементами:

 

В этом случае выбирается элемент с максимальным значением сi. Заметим, что данный выбор аналогичен принципу максимальной конъюнкции – минимальной дизъюнкции, применяемому в алгоритмах компоновки.

К этому же типу относится характеристика относительной связности:

 

где – множество размещенных элементов, Е – множество всех элементов, – определенный элемент.

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

 

Диаграммы

3.1 Диаграмма вариантов использования

Диаграмма вариантов использования состоит из актеров, для которых система производит действие и собственно действия UseCase, которое описывает то, что актер хочет получить от системы. Актер обозначается значком человечка, а UseCase - овалом.

 

Рисунок 1 – Диаграмма вариантов использования (usecase)



Поделиться:




Поиск по сайту

©2015-2024 poisk-ru.ru
Все права принадлежать их авторам. Данный сайт не претендует на авторства, а предоставляет бесплатное использование.
Дата создания страницы: 2016-02-16 Нарушение авторских прав и Нарушение персональных данных


Поиск по сайту: