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

1. Для текущей вершины определяется множество инцендентных ей рёбер
2. Находим множество вершин, входящих в каждое ребро
3. Для рассматриваемой вершины подсчитываем , для которых выполняется условие
4. Повторяем пункт с 1 по 3 для
5. Определяем очередную вершину по
6. Определяем позиции для установки. Для этого формируем множество . Из множества вершин входящих в ребро выделяем подмножество размещённых элементов по цепи .
7. Подсчитываем длину покрываемого дерева, соответствующую ребру , т.е.

- координаты элемента

- координаты элемента

1. Повторяем пункт с 6 по 7 , при этом суммируя длину покрывающего дерева
2. Повторяем пункты с 6 по 8 для
3. Определяем позицию , для которой

1. Заносим вершину в множество , а позицию в множество , соответственно исключая их из и

1. Проверяем, все ли элементы размещены , переход на пункт 13, иначе на пункт 1
2. Конец работы алгоритма

Улучшение размещения перестановкой модулей

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

Правила окончания перестановок:

1. Не существует перестановок улучшающих критерии качества
2. Разных значений критериев качества для двух соседних итераций меньше некоторого заданного значения

Исходные данные:

– Соединение элементов определяется матрицей смежностей R

– Расстояние между соседними элементами определяется матрицей позиций

– Элементы матрицы R и должны полностью соответствовать друг другу по индексам. При этом элементы матрицы R должны располагаться в соответствии с порядковыми номерами, позицией и установкой, т.е. в матрице R 1-ая строка характеризует связанность элемента R с .

При перестановке элементов местами происходит перестановка соответствующих строк и столбцов матрицы .

Суммарная взвешенная длина соединений L(a) рассчитывается поэлементно перемножением матриц R и .

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

S – индекс элемента не участвующего в перестановке

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

Где номера или индексы нумеруют по убыванию

После окончания итераций подсчитают новое значение суммарной длины связи, и процесс повторяется.

Дата добавления: 2014-01-20