САПР в задачах конструкторского проектирования. Тюрин И.В. - 9 стр.

UptoLike

ВУЗ: 

ТГТУ | Тамбов

Составители: 

Рубрика: 

n
vv
n
ji
ji
RQ
,...,
1,
,
1
min→=
∑
=
,
где R
i
,
j
– мощность множества ребер R
i
,
j
, инцидентных частям G
i
(V
i
, R
i
) и G
j
(V
j
, R
j
).
При этом должны выполняться следующие ограничения на компоновку: число вершин в каждой части должно быть за-
дано; одна вершина должна принадлежать лишь одной части; объединение всех частей должно быть равно исходному графу.
Для последовательно-итерационного алгоритма решения задачи компоновки первоначальное формирование частей графа
производится не произвольно, а приближенно к оптимальному группированию на основе простых операций последовательного
алгоритма, что позволяет затем относительно небольшим числом итераций получить окончательное решение. С помощью этого
алгоритма решение задачи компоновки осуществляется в два этапа. На первом используется процедура последовательного ал-
горитма, т.е. производится быстрое формирование частей, близких к оптимальному решению, а на втором реализуются проце-
дуры итерационного алгоритма.
Принцип работы итерационного алгоритма основан на перестановке вершин или группы вершин из одной части графа в
другую до тех пор, пока не будет получено минимальное число связей между частями.
В общем случае алгоритм состоит из двух этапов:
1)
вспомогательный этап, предусматривающий начальное разбиение графа, например, разделение матрицы смежности
на части;
2)
основной этап, в ходе которого производится итерационное улучшение решения на основе парного или группового
обмена вершин из различных частей.
Рассмотрим алгоритм на примере решения задачи разбиения графа G
(V, R) с числом вершин (мощностью) V = 8 на n
= 3 части, с количеством вершин в каждой части N
1
= 2; N
2
= 3 и N
3
= 3 соответственно (рис. 1).
При решении задачи используем критерий оптимальности — минимум связей между частями. Блоки матрицы сверху вниз
следует располагать по мере увеличения их размерности. Для нашего примера внешних связей семь, т.е. Q = 7. Разбиение графа
в соответствии с выбранным критерием тем лучше, чем больше связей сосредотачивается в диагональных блоках матрицы.
Поэтому вместо минимизации числа связей между частями можно максимизировать суммарное число ребер внутри всех
частей графа G(V, R). Полученный таким образом критерий оптимальности примет вид:
∉
∈
=αα=
∑∑
==
,,0
;,1
,
11
jj
j
i
jj
j
i
j
i
l
j
R
i
j
i
Rr
Rr
Q
jj
где
j
i
r – i-е ребро j-й части; R
jj
– подмножество «внутренних» ребер части G
j
(V
j
, R
j
); l – число частей.
Этап 2. В ходе выполнения этого этапа при каждой итерации выполняются следующие операции:
1.
Подсчитываются перестановочные коэффициенты ∆R(v
i
, v
j
) при v
i
∈ V
p
, v
j
∈ V
q
для пар вершин, принадлежащих раз-
личным частям и характеризующих изменение числа соединительных ребер R
pq
между частями G
p
и G
q
в результате пере-
становки вершин v
i
и v
j
.
2.
Отбираются пары вершин с максимальным значением ∆R, перестановка которых уменьшает число связей между частями.
При этом ∆R(v
i
, v
j
) > 0.
3.
Производится перестановка вершин и строится матрица S.
4.
Итерации заканчиваются, когда все коэффициенты ∆R принимают отрицательные значения или равны нулю, т.е.
∆R(v
i
, v
j
) ≤ 0.
Расчет коэффициентов ∆R(v
i
, v
j
) является наиболее сложной частью алгоритма, их оценка производится по формуле
(
)
ijjpqiqpqjpiji
SvSvSVvVvvvR 2)()(,/, −∆+∆=∈∈∆
, (1)

Страницы