Последовательные алгоритмы

Рассмотрим идеи последовательных алгоритмов. Пусть дана схема электрических связей из множества элементов Е={e₁…e_n}. Будем последовательно назначать элементы e_iÎE (i=1,n) в куски G_i i = 1,l. На каждом шаге выбирается один из нераспределенных элементов и помещается в очередной кусок.

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

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

Тактика назначения элементов в куски в самом общем виде следующая:

1. на очередном шаге выделяются те элементы, включение каждого из которых в кусок не нарушает ограничений по числу элементов и выводов узла;

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

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

Рассмотрим один из них.

Алгоритм 1 (последовательный алгоритм компоновки)

Пусть задан граф схемы G=(E,U), который необходимо разбить на l объектов G₁,G₂,…,G_l с числом вершин n₁,n₂,…,n_l в кусках, Sn_i=n, i=1,l.

1. формируем первый кусок. В графе выбирается вершина e_iÎE с максимальной степенью r(e_i)=max. Если таких вершин несколько, то предпочтение отдается той вершине, которая имеет большее число кратных ребер, идущих к одной вершине. С вершины e_i начинается построение куска G₁;

2. в кусок G₁ сначала включаем все вершины, смежные e_i и саму эту вершину. Обозначим множество таких вершин Гe_i. Если количество вершин множества Гe_i равно n₁, то кусок сформирован. Если число вершин больше n₁, то удаляем «лишние» вершины, связанные с остающимися вершинами G меньшим числом ребер. Если мощность Гe_i меньше n₁, то добавляем вершины из числа нераспределенных, имеющие наибольшее число связей с распределенными вершинами и наименьшее число связей с нераспределенными. Затем процесс повторяется для нового куска и т.д.

Описанный алгоритм достаточно прост и позволяет достаточно быстро получить результат. Однако, в общем случае он может привести к неэффективным результатам. Этот алгоритм наиболее эффективен для графа, в котором число вершин графа G значительно больше числа вершин в любом куске: n>>n₁,n₂,…,n_l, поскольку существует много возможностей для выбора вершин.

Пример:

Пусть граф задан матрицей смежности

Требуется разбить граф G на три куска по 3, 2, 2 вершины, т.е. n₁=3,. n₂=2, n₃=3.

Выбираем вершину e₅ с r(e₅) = 8. Тогда Гe₅={e₅,e₃,e₄,e₆,e₇}.

n = 5 > n1=3. Нужно убрать 2 лишние вершины.

Для этого произведем условное удаление каждой вершины из Гe₅ и подсчитаем число ребер z_ei, связывающих эту вершину с оставшимися вершинами Гe₅.

При удалении e₃ z_e3=R₃₅+R₃₄+R₃₆+R₃₇=1+0+1+0=2

При удалении e₄ z_e4=R₄₅+R₃₄+R₄₆+R₄₇=1+0+4+0=5

При удалении e₆ z_e6=R₆₅+R₆₄+R₃₆+R₆₇=1+4+1+1=7

При удалении e₇ z_e7=R₇₅+R₇₄+R₇₆+R₇₃=5+0+1+0=6

Удаляем e₃ (т.к. z_e3 min) и получим Гe₅={e₅,e₄,e₆,e₇}

Нужно удалить еще одну вершину.

При удалении e₄ z_e4=R₄₅+R₄₆+R₄₇=1+4+0=5

При удалении e₆ z_e6=R₆₅+R₆₄+R₆₇=1+4+1=6

При удалении e₇ z_e7=R₇₅+R₇₄+R₇₆=5+0+1=6

Удаляем e₄ (т.к. z_e4 = min) и получим Гe₅={e₅,e₆,e₇}

3. Первый кусок сформирован. Из оставшихся вершин E*={e1,e2,e3,e4} формируем следующий кусок. Матрица смежности принимает вид.

Выбираем вершину e₁ с r(e₁)=5. Тогда Гe₁={e₁,e₂,e₃}.

n = 3 > n1=2. Нужно убрать 1 лишнюю вершину.

Для этого произведем условное удаление каждой вершины из Гe₁ и подсчитаем число ребер z_ei, связывающих эту вершину с оставшимися вершинами Гe₁.

При удалении e₁ z_e1=R₁₂+R₁₃=2 +3=5

При удалении e₂ z_e2=R₂₁+R₂₃=2+1=3

При удалении e₃ z_e3=R₃₁+R₃₂=3+1=4

Удаляем e₂ (т.к. z_e2 = min) и получим Гe₁ = {e₁,e₃}

Гe₁=(e₁,e₃) - кусок сформирован.

Т.к. остались всего две вершины, то третий кусок будет содержать вершины e₂, и e₄: Гe₂={e₂,e₄}.

Результат разбиения графа G на три куска: Гe₅={e₅,e₆,e₇}, Гe₁={e₁,e₃}, Гe₂={e₂,e₄}. Онприведен на рис. 3.2.

Число соединительных ребер всех кусков графа к равно 10.

Суммарное число внутренних ребер (ребер подмножеств U_i) равно 11.

Коэффициент разбиения DG=11/10=1.1.

Есть другой вариант алгоритма, при котором первой вершиной первого куска берется вершина с наименьшей степенью.

Провести разбиение по этому варианту самостоятельно и сравнить результаты.

Оглавление

Лекция 3. 1

Решение задачи компоновки конструктивных узлов. 1

Постановка задачи разбиения электрических схем (компоновки) 1

Алгоритмы разбиения графов. 7

Последовательные алгоритмы.. 8

Алгоритм 1 (последовательный алгоритм компоновки) 9