Итерационный алгоритм размещения с использованием групповой перестановки

Итерационный алгоритм используется для оптимизации первоначального произвольного или полученного другим методом размещения графа с целью уменьшения суммарной длины связей. Суть алгоритма в следующем.

Для любой пары вершин x_i и x_j, занимающих до перестановки текущие позиции р_i и р_j соответственно, по матрице смежности R и матрице расстояний D можно подсчитать суммарную длину их связей .

(5.18)

где и – суммарная длина связей вершин x_i и x_j до перестановки;

– длина связей между вершинами x_i и x_j;

n – количество вершин графа.

Если выполнить перестановку пары вершин x_i и x_j, то вершина x_i переместится в позицию р_j, а вершина x_j – в позицию р_i. В этом случае суммарная длина их связей

(5.19)

 

Вывод формулы для вычисления приращения суммарной длины связей, полученного в результате перестановки вершин x_i и x_j, рассмотрим на следующем примере.

Пример 5.3. На рис. 5.6. представлен граф G = (X, U), содержащий шесть вершин, размещённых в решётке Gr = 3 × 2. Вершины x₁, x₂, …, x_i, …, x₆ занимают позиции p₁, p₂, …, p_i, …, p₆ соответственно.

 

Рис. 5.6

 

1) Матрица смежности данного графа

 

R=		x1	x2	x3	x4	x5	x6	(5.20)
x1
x2
x3
x4
x5
x6

 

 

2) Матрица расстояний для решётки заданной размерности

 

D=		p1	p2	p3	p4	p5	p6	(5.21)
p1
p2
p3
p4
p5
p6

 

3) Определим перестановочный коэффициент для вершин, x₃ и x₅:

а) суммарная длина связей вершины x₃ до перестановки:

 

(5.22)

 

 

б) суммарная длина связей вершины x₅ до перестановки:

 

(5.23)

 

 

в) суммарная длина связей вершин x₃ и x₅ до перестановки:

 

(5.24)

 

 

г) после перестановки вершина x₃ переместится в позицию p₅, а вершина x₅ – в позицию p₃ (рис. 5.7).

 

 

Рис. 5.7

 

г) суммарная длина связей вершины x₃ после перестановки:

 

д) суммарная длина связей вершины x₅ после перестановки:

 

е) суммарная длина связей вершин x₃ и x₅ после перестановки:

 

Изменение суммарной длины связей вершин p_i и p_j определяется по формуле

(5.20)

Отрицательное значение означает уменьшение суммарной длины связей.

Работа алгоритма производится циклически. В течение одного цикла:

1) по формуле (5.20) вычисляются величины приращений суммарной длины связей для всех возможных парных перестановок и строится матрица приращений;

2) из множества пар вершин, перестановка которых даст отрицательные приращения суммарной длины связей, выделяется некоторое подмножество, которое должно удовлетворять следующим условиям:

а) выбранное подмножество перестановок максимально уменьшает суммарную длину связей;

б) любая вершина может менять свою позицию только один раз;

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

Несоблюдение условий б) и в) (особенно в)) может ухудшить результат размещения по сравнению с первоначальным на любой итерации.

Алгоритм реализации описанного метода содержит следующие шаги:

Шаг 1. Построить матрицу расстояний D=||d_ij||, исходя из заданных параметров решетки. Перейти на шаг 2.

Шаг 2. Построить матрицу смежности R=||r_ij|| графа G=(P,U). Перейти на шаг 3.

Шаг 3. Вычислить матрицу приращений ΔL=||Δl_ij||_n по формуле (5.20). Перейти на шаг 4.

Шаг 4. Проверить наличие в матрице приращений отрицательных элементов. Если отрицательные элементы обнаружены, то перейти на шаг 5, в противном случае – на шаг 7.

Шаг 5. По отрицательным элементам матрицы приращений выбрать подмножества парных перестановок. При этом вершины одного подмножества (пары) не должны иметь связей с вершинами из любого другого подмножества. Перейти на шаг 6.

Шаг 6. Переставить в матрице смежности R строки и столбцы, соответствующие выбранным вершинам подмножеств. Перейти на шаг 3.

Шаг 7. Вывод результатов размещения. Перейти на шаг 8.

Шаг 8. Конец работы алгоритма.

 

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

Пример 5.3. На рис 5.8 представлено произвольное размещение графа G=(P,U) (рис. 4.10) в решетку G_r=4х3. Вершины p₁, p₂,…,p₁₂ занимают позиции р₁, р₂, …, р₁₂ соответственно.

 

Рис. 5.8

 

Задание: оптимизировать размещение графа.

 

Решение

1. Построить матрицу расстояний для решетки G_r = 4p3. Такой матрицей является матрица (5.4).

2. Матрице смежности заданного графа соответствует матрица (4.11).

3. Вычислить матрицу приращений суммарной длины связей по формуле (5.20). Матрица приращений имеет вид:

			p1	p2	p3	p4	p5	p6	p7	p8	p9	p10	p11	p12	(5.21)
ΔL	=	p1			-4		-3	-4	-3		-6	-4
p2			-1		-4	-2	-6		-11
p3					-3	-6	-1		-4	-2
p4					-6	-1
p5					-4	-14		-1
p6						-8		-2			-2
p7									-9	-2
p8
p9
p10
p11
p12

 

4. В матрице приращений (4.19) выбрать максимальный отрицательный элемент. Таким элементом является элемент Δl(p₅, p₇). Вершины p₅, и p₇ образуют первое подмножество переставляемых вершин. Из всех остальных 25 отрицательных перестановок только элемент Δl(p₂, p₆) определяет подмножество {p₂, p₆}, у которого ни одна из вершин не связана ни с вершиной p₅, ни с вершиной p₅ первого подмножества. Парная перестановка вершин p₂ и p₆ и вершин p₅ и p₇ позволит уменьшить суммарную длину связей графа на 16 единиц.

5. Поменять местами p₂ и p₆ строки и столбцы и p₅ и p₇ строки и столбцы матрицы смежности. Матрица смежности примет вид

 

p1

p6

p3

p4

p7

p2

p5

p8

p9

p10

p11

p12

(5.22)

R(1)

=

p1

p6

p3

p4

p7

p2

p5

p8

p9

p10

p11

p12

 

Размещение графа после выполненных перестановок показано на рис.5.9.

 

Рис. 5.9

 

6. Вычислить матрицу приращений для размещения, представленного на рисунке 5.9.

 

p1

p6

p3

p4

p7

p2

p5

p8

p9

p10

p11

p12

L(1)

=

p1

-6

p6

-3

p3

p4

p7

-1

(5.23)

p2

-4

-1

p5

p8

p9

p10

p11

p12

 

7. В матрице приращений (5.23) максимальным отрицательным элементом является элемент Δ_l(p₁, p₉), определяющий первое подмножество {p₁, p₉} переставляемых вершин. Подмножество {p₂, p₁₀} единственное из четырёх оставшихся, которое не имеет связей с первым.

 

Размещение графа после выполненных перестановок показано на рис.5.10.

Рис. 5.10

 

8. Поменять местами p₁ и p₉ строки и столбцы и p₂ и p₁₀ строки и столбцы матрицы смежности R⁽¹⁾.

9. Вычислить матрицу приращений суммарной длины связей для размещения, представленного на рис. 5.10.

p9

p6

p3

p4

p7

p10

p5

p8

p1

p2

p11

p12

(5.24)

L(2)

=

p9

p6

p3

p4

p7

p10

p5

p8

p1

p2

p11

p12

 

 

10. В матрице приращений нет отрицательных элементов, следовательно, размещение, представленное на рис. 5.10 оптимизировать данным алгоритмом нельзя.

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

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

В первом случае разобьем множество Х графа G на n классов х₁, х₂, …, х_n и отнесем в них вершины, лежащие в строках решетки внутри области размещения. В каждом классе выделим внутренние и внешние соединительные ребра. Заменим класс p_i одной вершиной C₁. В результате будет получен линейно расположенный мультиграф.

Факторизация размещенного в решетке графа (рис. 5.8) по строкам представлена на рис. 5.11. Класс P₁= {p₉, p₆, p₃, p₄} заменим вершиной С₁; класс P₂= {p₇, p₁₀, p₅, p₈} – вершиной С₂; а класс P₃= {p₁, p₂, p₁₁, p₁₂} заменим вершиной С₃.

Рис. 5.11

 

Матрица смежности линейного мультиграфа

 

		c1	c2	C3
	c1
c2				(5.25)
c3

 

Матрица расстояний

	c1	c2	c3
c1
c2				(5.26)
c3

 

Матрица приращений суммарной длины соединений

		c1	c2	c3
c1
c2				(5.27)
c3

 

Для факторизации по столбцам множество Х вершин Х графа G разобьём на m=4 классов, и каждый класс заменим вершиной С_i. Соответствие вершин С и классов:

С₁: Х₁={х₉, х₇, х₁}

С₂: Х₂={х₆, х₁₀, х₂}

С₃: Х₃={х₃, х₅, х₁₁}

С₄: Х₄={х₄, х₈, х₁₂}

Факторизация размещенного в решетке графа (рис. 5.10) по столбцам представлена на рис. 5.12.

Рис. 5.12

Матрица смежности линейного мультиграфа

 

		с1	c2	c3	с4
с1
c2					(5.28)
c3
с4

 

Матрица расстояний графа

 

		с1	с2	c3	с4
с1
c2					(5.29)
c3
с4

 

Матрица приращений суммарной длины соединений

 

		с1	с2	c3	с4
с1		-1		-1
c2			-1		(5.30)
c3				-1
с4

 

В матрице (5.30) четыре элемента имеют одинаковые отрицательные значения: Δl (c₁, c₂), Δl (c₁, c₄), Δl (c₂, c₃), Δl (c₃, c₄). Выбираем элемент с наименьшим индексом Δl (c₁, c₂) и меняем местами классы c₁ и c₂.

Матрица смежности после перестановок c₁ и c₂ строк и столбцов:

 

		c2	с1	c3	с4
c2
с1					(5.31)
c3
с4

Матрица приращений суммарной длины соединений:

 

		с2	с1	c3	с4
c2
с1				-6	(5.32)
c3				-1
с4

 

По результатам вычислений в матрице приращений следует поменять местами c₁ и c₄ строки и столбцы. Получим:

		c2	c4	c3	c1
c2
c4					(5.33)
c3
c1

 

Матрица приращений суммарной длины соединений:

 

		c2	c4	c3	c1
c2
c4					(5.34)
c3
c1

 

В матрице приращений (5.34) нет ни одного отрицательного элемента, следовательно, факторизация графа по столбцам закончена. Полученное отображение графа в решетку представлено на рис. 5.13.

Рис. 5.13

 

Примечание: в процессе реализации описанного метода вершина х₂ переставлялась дважды: на первой итерации в паре с вершиной х₆, и на второй итерации в паре с вершиной х₁₀. Если бы при решении задачи была бы принято во внимание условие 2б), то от повторной перестановки вершины х₂ на второй итерации следовало бы отказаться и тогда результат размещения был бы не таким оптимальным (рис. 5.14). Суммарная длина соединений была бы на единицу больше.

 

Рис. 5.14