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