1.2 Метод парных перестановок

Пусть в результате произвольного начального распределения сформированы Z блоков. Обозначим их через X, X, X,...,XZ. Подсчитав количество соединений между двумя блоками, например, между блоком Х и блоком Х, меняем взаимно местами по одному модулю из блока Х и из блока Х. После этого вновь считаем количество соединений между блоками. Если после перестановки количество соединений уменьшилось, то перестановка целесообразна. Если же увеличилось или осталось прежним, по перестановка не целесообразна. Можно производить перестановку каждого модуля блока Х с каждым модулем блоков Х, Х, ..., Хz, а затем каждого модуля блока Х с каждым модулем остальных блоков и т.д. В результате можно получить минимизацию соединений между блоками.

Целесообразность перестановки i - го элемента, находящегося в блоке Х, с j - м элементом, находящимся в блоке Х, определяется по формуле:

 (1)

где - функционал для элементов и ;

- количество внешних соединений элемента с блоком Х;

- количество внешних соединений элемента с блоком Х;

- количество внутренних соединений элемента блока Х с другими элементами этого же блока;

- количество внутренних соединений элемента блока Х с другими элементами этого же блока;

- количество общих (прямых) соединений между переставляемыми элементами и.

- первый блок; Х - множество элементов блока (обозначаются буквой i).

- второй блок; Х- множество элементов блока (обозначаются буквой j).

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