Кластеризация

Иногда требуется равномерное распределение элементов по имеющимися блокам. Тогда возникает задача кластеризации, которую можно рассматривать как разновидность задачи компоновки, отличающуюся типом ограничений: вместо ограничения типа неравенства на объем внутренних для кластера (блока) связей вводится ограничение типа равенства на число элементов (компонентов) в кластере. Т.е. ограничение (2) принимает вид

(4)

где — число элементов в -м кластере, — целая часть частного от деления числа элементов на число кластеров . Другими словами, требуется равномерное распределение элементов по кластерам, минимизирующее связность кластеров друг с другом. В частности, в некоторых алгоритмах размещения микросхем на платах предварительно решается задача дихотомической кластеризации — разделения множества микросхем на два минимально связанных подмножества одинаковой (при четном ) мощности.

Очевидно, что в задаче кластеризации после соответствующей корректировки можно использовать правила выбора очередного элемента и его размещения в одном из кластеров, аналогичные правилам в задаче компоновки. Так, в правиле загрузка кластера будет оцениваться не его внутренним трафиком (связностью), а числом размещенных в нем элементов, во всех правилах , и возможным кластером-кандидатом может быть только тот кластер, в котором еще не исчерпан лимит на размещение. Правила используются без изменений. При вычислении целевой функции штрафы за нарушение ограничений не предусматриваются, так как учет ограничений введен в эвристики.

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

· ) в строке которого в матрице связей находится максимальный элемент матрицы;

· ) имеющий максимальную суммарную связность с уже размещенными элементами;

· ) имеющий минимальную суммарную связность с еще не размещенными элементами.

Для выбранного по одному из правил элемента определяется кластер, в котором:

· ) имеется элемент, максимально связанный c ;

· ) уже размещенные элементы максимально связаны с (максимальна суммарная связность).

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