Оптимальная группировка взаимосвязанных упорядоченных объектов

Рассматривается задача группировки объектов на основе матрицы их взаимосвязи при условии, что объекты обладают заданным упорядочением и группировка не должна ему противоречить. Описан метод точного решения этой задачи при сравнительно слабых ограничениях на вид максимизируемого функционала. Метод основан на динамическом программировании. Его реализация требует $(c_1n+c_2)N^2$ алгоритмических операций, где $N$ — число объектов, $n$ — число групп, $c_1,c_2$ — константы.