Алгоритм парных перестановок для решения задач оптимизации компоновки и размещения элементов РЭС: Учебное пособие, страница 36

Весь массив из N элементов делится сначала на 2 одинаковые части (если число элементов нечетное, то в одной из частей на 1 элемент больше), потом каждая часть делится еще пополам и так далее, до получения нужного количества элементов в группе (рис. 6.2).

Алгоритм работает следующим образом. Сначала определяется четность массива. Если N - нечетное число, то элемент, имеющий минимальную температуру, изымается из массива. Если же N - четное число, то изъятие не производится. Разбиение на 2 части (массивы А и В) массива N производится  следующим образом: сначала в массив А заносится элемент с самой высокой температурой, а в массив В элемент с максимальной температурой из оставшихся, затем в массив А заносится элемент с минимальной температурой, а в массив В также с минимальной температурой из оставшихся и так далее до тех пор, пока все элементы начального массива не разделятся между массивами А и В. В случае нечетного количества элементов в массиве N изъятый элемент с минимальной температурой присоединяется к тому массиву А или В, который имеет меньшую суммарную температуру.

Разделение каждого массива А и В проводится аналогичным образом. Разделение соответствующих массивов проводится до тех пор, пока число элементов в любом массиве окажется более заданного не более, чем на 1.

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

В качестве примера приведем следующий. Пусть требуется разбить 80 элементов (N = 80) на группы по 10 элементов, так, чтобы суммарная температура каждой группы была одинакова. Температуры элементов приведены в табл. 6.1. Результаты разбиения представлены в табл. 6.2. Анализ результатов показывает, что суммарная температура для каждой группы отличается от средней не более, чем на 0,6 %.

Таблица 6.1

Температура элементов