Автоматика и телемеханика, № 1, 2017 Системный анализ и исследование операций 2017 г. А.В. КЕЛЬМАНОВ, д-р физ.-мат. наук (kelm@math.nsc.ru) (Институт математики им. <...> С.Л. Соболева СО РАН, Новосибирск, c Новосибирский государственный университет), С.А. ХАМИДУЛЛИН, канд. техн. наук (kham@math.nsc.ru) (Институт математики им. <...> С.Л. Соболева СО РАН, Новосибирск, Новосибирский государственный университет) ТОЧНЫЙ ПСЕВДОПОЛИНОМИАЛЬНЫЙ АЛГОРИТМ ДЛЯ ОДНОЙ ЗАДАЧИ РАЗБИЕНИЯ ПОСЛЕДОВАТЕЛЬНОСТИ1 Рассматривается NP-трудная в сильном смысле задача разбиения конечной последовательности векторов евклидова пространства на два кластера заданных размеров по критерию минимума суммы по обоим кластерам сумм квадратов расстояний от элементов кластеров до их центров. <...> Центр первого кластера является оптимизируемой величиной и определяется как среднее значение по всем векторам, образующим этот кластер. <...> При этом разбиение подчинено условию: разность между номерами последующего и предыдущего векторов, включаемых в первый кластер, ограничена сверху и снизу заданными константами. <...> Предложен точный псевдополиномиальный алгоритм для случая задачи, в котором размерность пространства фиксирована, а компоненты входных векторов целочисленны. <...> Ключевые слова: разбиение, векторная последовательность, евклидово пространство, минимум суммы квадратов расстояний,NP-трудность, точный псевдополиномиальный алгоритм. <...> Введение Предметом исследования настоящей работы является одна из NP-трудных в сильном смысле задач дискретной оптимизации. <...> Цель исследования — обоснование точного псевдополиномиального алгоритма для специального случая этой задачи. <...> В постановочном плане рассматриваемая задача близка к задаче MSSC (Minimum Sum-of-Squares Clustering) [1–5] — одной из известных (более полувека) задач кластерного анализа данных, которая относится к числу труднорешаемых задач дискретной оптимизации [6]. <...> 80 эта задача имеет краткое название k-means (k-средних). <...> В простейшем базовом <...>