1.
Последовательный алгоритм размещения
Последовательные алгоритмы основаны
на допущении, что для получения минимальной суммарной длины соединений в соседних позициях должны быть размещены
элементы, максимально связанные друг с другом.
В качестве первоначально
размещенных элементов обычно выбирают разъемы, местоположение которых задается
вручную. Далее на каждом -м шаге для установки на МКП выбирают компонент
из числа еще не
размещенных, имеющий максимальную степень связности с ранее закрепленными
элементами
.оценку степени связности
можно выполнить по
формуле:
, где
- множество индексов
элементов, закрепленных на предыдущих шагах,
- элемент матрицы смежности.
Если установочные размеры
элементов, размещаемых на плате элементов одинаковы, то выбранный элемент
закрепляют в той позиции zt из числа незанятых, для которой
значение целевой функции минимально. В частности, если критерием является
минимум суммарной взвешенной длины соединений, то , где
- расстояние между ячейкой
для установки элемента
и позицией
размещенного ранее
компонента; t – множество незанятых позиций после (l-1) – шага алгоритма.
Процесс размещения заканчивается
после выполнения n шагов алгоритма.
2.
Алгоритм парных перестановок
Алгоритмы парных перестановок
предполагают наличие начального размещения, поэтому говорят, что они
предназначены для улучшения размещения.
Работа алгоритма заключается в
процессе перестановки пар элементов с целью дальнейшей минимизации длины
соединений. Изменение длины соединений при перестановке местами двух элементов и
, закрепленных в t-й и r-й
позициях, может быть определено по формуле:
.
На очередной
итерации выбирается элемент , начиная с закрепленного на первой позиции, и для него
отыскивается второй элемент (путем проб перестановок)
, для которого величина
и максимальна.
Аналогичным образом оценивается
целесообразность перестановки очередного элемента, находящегося на второй, третьей
и т.д. позициях, пока не будут просмотрены все позиции платы. После завершения
просмотра производится парная перестановка элементов, для которых изменение
длины соединений максимально. На этом итерация заканчивается. В последующих
итерациях процесс повторяется, пока не будет выполнено заданное число итераций,
либо изменение суммарной длины на последней итерации не станет меньше
заданного.