Аннотация:
Рассматривается задача разбиения конечного множества точек евклидова пространства на кластеры по критерию минимума суммы по всем кластерам внутрикластерных сумм квадратов расстояний между элементами кластеров и их центрами. Центры одной части кластеров заданы на входе задачи, а центры другой части кластеров неизвестны и определяются как центроиды (геометрические центры). Известно, что в общем случае эта задача NP-трудна в сильном смысле. В работе конструктивно доказано, что одномерный случай задачи разрешим за полиномиальное время. Библ. 20.
Ключевые слова:евклидово пространство, кластеризация, разбиение, минимум суммы квадратов расстояний, NP-трудная в сильном смысле задача, одномерный случай, полиномиальная разрешимость.
УДК:519.72
Поступила в редакцию: 03.04.2019 Исправленный вариант: 03.04.2019 Принята в печать: 15.05.2019