Система QPSLab для анализа и распознавания числовых последовательностей с квазипериодической структурой
Задача выбора подмножества векторов
(размерность пространства известна, число кластеров известно)
Эта задача редуцируется к следующей экстремальной задаче.
Дано: множество Y = { y1,...,
yN } векторов из Rq и натуральное число M >1.Найти: подмножество C ÌY векторов такое, что целевая функция
где y(C)=(1/|C|)∑yÎC y, минимальна при ограничении |C|=M на мощность искомого подмножества.
Задача NP-трудна. Алгоритм, предлагающий 2-приближенное решение задачи, и имеющий временную сложность
O(qN 2),
обоснован в [76].
|
предыдущая |
следующая |