1.   Последовательный алгоритм размещения

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

В качестве первоначально размещенных элементов обычно выбирают разъемы, местоположение которых задается вручную. Далее на каждом -м шаге для установки на МКП выбирают компонент  из числа еще не размещенных, имеющий максимальную степень связности с ранее закрепленными элементами .оценку степени связности  можно выполнить по формуле: , где  - множество индексов элементов, закрепленных на предыдущих шагах, - элемент матрицы смежности.

Если установочные размеры элементов, размещаемых на плате элементов одинаковы, то выбранный элемент закрепляют в той позиции zt из числа незанятых, для которой значение целевой функции минимально. В частности, если критерием является минимум суммарной взвешенной длины соединений, то , где - расстояние между ячейкой  для установки элемента  и позицией  размещенного ранее компонента; t – множество незанятых позиций после (l-1) – шага алгоритма.

Процесс размещения заканчивается после выполнения n шагов алгоритма.

2.   Алгоритм парных перестановок

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

Работа алгоритма заключается в процессе перестановки пар элементов с целью дальнейшей минимизации длины соединений. Изменение длины соединений при перестановке местами двух элементов  и , закрепленных в t-й и r-й позициях, может быть определено по формуле:

.

На очередной итерации выбирается элемент , начиная с закрепленного на первой позиции, и для него отыскивается второй элемент (путем проб перестановок) , для которого величина и максимальна.

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

 

Сайт управляется системой uCoz