Том 19, номер 3, 2012 г., Стр. 27-38
УДК 519.2+621.391
Кельманов А. В., Романченко С. М., Хамидуллин С. А.
Приближенные алгоритмы для некоторых труднорешаемых задач поиска подпоследовательности векторов
Аннотация:
Рассматриваются некоторые труднорешаемые задачи поиска подпоследовательности в последовательности векторов евклидова пространства, состоящей из конечного числа членов. Предполагается, что искомая подпоследовательность содержит фиксированное число векторов, близких между собой по критерию минимума суммы квадратов расстояний, причем поиск векторов подчинён условию: разность между номерами последующего и предыдущего искомых векторов ограничена сверху и снизу некоторыми константами. Предложены 2-приближенные эффективные алгоритмы решения этих задач.
Библиогр. 11.
Ключевые слова: поиск подпоследовательности векторов, минимум суммы квадратов расстояний, кластерный анализ, NP-трудность, эффективный приближённый алгоритм.
Кельманов Александр Васильевич 1,2
Романченко Семён Михайлович 1
Хамидуллин Сергей Асгадуллович 1
1. Институт математики им. С. Л. Соболева СО РАН,
пр. Акад. Коптюга, 4, 630090 Новосибирск, Россия
2.
Новосибирский гос. университет,
ул. Пирогова, 2, 630090 Новосибирск, Россия
е-mail: kelm@math.nsc.ru, semenr@bk.ru, kham@math.nsc.ru
Статья поступила 11 августа 2011 г.
Исправленный вариант — 7 ноября 2011 г.
Литература
[1] Гимади Э. Х., Кельманов А. В., Кельманова М. А., Хамидуллин С. А. Апостериорное обнаружение в числовой последовательности квазипериодического фрагмента при заданном числе повторов // Сиб. журн. индустр. математики. — 2006. — Т. 9, № 1. — С. 55–74.
[2] Кельманов А. В., Михайлова Л. В. Совместное обнаружение в квазипериодической последовательности заданного числа фрагментов из эталонного набора и ее разбиение на участки, включающие серии одинаковых фрагментов // Журн. вычисл. математики и мат. физики. — 2006. —
Т. 46, № 1. — С. 172–189.
[3] Кельманов А. В., Михайлова Л. В., Хамидуллин С. А. Об одной задаче поиска упорядоченных наборов фрагментов в числовой последовательности // Дискрет. анализ и исслед. операций. — 2009. — Т. 16, № 4. — С. 31–46.
[4] Кельманов А. В., Хамидуллин С. А. Апостериорное обнаружение заданного числа одинаковых подпоследовательностей в квазипериодической последовательности // Журн. вычисл. математики и мат. физики. — 2001. — Т. 41, № 5. — С. 807–820.
[5] Кельманов А. В., Пяткин А. В. NP-полнота некоторых задач выбора подмножества векторов // Дискрет. анализ и исслед. операций. — 2010. — T. 17, № 5. — С. 37–45.
[6] Кельманов А. В., Романченко С. М. Приближённый алгоритм для решения одной задачи поиска подмножества векторов // Дискрет. анализ и исслед. операций. — 2011. — T. 18, № 1. — С. 61–69.
[7] Шенмайер В. В. Аппроксимационная схема для одной задачи поиска подмножества векторов // Математические методы распознавания образов: 15-я Всерос. конф. (ММРО-15). Сб. докл. — М.: МАКС Пресс, 2011. — С. 284–286.
[8] Anil K., Jain K. Data clustering: 50 years beyond $k$-means // Pattern Recognit. Lett. — 2010. — Vol. 31. — P. 651–666.
[9] Hastie T., Tibshirani R., Friedman J. The elements of statistical learning: data mining, inference, and prediction. — New York: Springer-Verl., 2001. — 533 p.
[10] Kel’manov A. V., Jeon B. A posteriori joint detection and discrimination of pulses in a quasiperiodic pulse train // IEEE Trans. Signal Process. — 2004. — Vol. 52, N 3. — P. 645–656.
[11] Kel’manov A. V., Khamidullin S. A. An algorithm for recognition of a vector alphabet generating a sequence with a quasi-periodic structure // Pattern Recognit. Image Anal. — 2010. — Vol. 20, N 4. —
