Алгоритмы с оценками для некоторых задач поиска подмножества и подпоследовательности векторов в евклидовом пространстве

• Автор: Романченко, Семён Михайлович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2014
• Место защиты: Новосибирск
• Количество страниц: 81 с.

Оглавление
Введение

1 Квадратичные модели поиска похожих элементов

2 Задачи поиска подмножества векторов

2.1 Постановки задач

2.2 Несуществование схемы РРТЛЗ для общего случая

2.3 Геометрические основы алгоритмов

2.4 Алгоритмы решения задач

2.4.1 Приближённый полиномиальный алгоритм с гарантированной достижимой оценкой 2 точности

2.4.2 Точный псевдополиномиальный алгоритм

2.4.3 Схема РРТАБ для специального случая
2.5 Заключение к главе
3 Задачи поиска подпоследовательности векторов
3.1 Постановки задач
3.2 Алгоритмы решения задач

3.2.1 Вспомогательная задача и точный полиномиальный алгоритм её решения
3.2.2 2 приближённый полиномиальный алгоритм
3.2.3 Псевдополиномиальный алгоритм, гарантирующий оптимальное решение задач
3.3 Заключение к главе
Заключение
Литература

Введение
Объектом исследования настоящей работы являются проблемы дискретной оптимизации. Предмет исследования — труднорешаемые экстремальные задачи, которые индуцируются фундаментальной проблемой классификации, возникающей в широком спектре приложений. Цель исследования — построение эффективных алгоритмов с гарантированными оценками точности для решения этих задач.
Рассматриваемые в работе задачи возникают, в частности, в анализе данных и распознавании образов, в математической статистике, в теории приближения и комбинаторной геометрии. Они моделируют простейшую в содержательном плане и в то же время актуальную для многих естественно-научных и технических приложений проблему поиска в конечном множестве (или в конечной последовательности) объектов заданного числа похожих элементов. Формализация этой проблемы, например, в виде задачи аппроксимации по критерию минимума суммы квадратов уклонений индуцирует несколько полиномиально эквивалентных экстремальных задач, которые, как установлено совсем недавно, ЦР-трудиы в сильном смысле. Мотивацией исследования послужило отсутствие каких-

решения С і = {С* {щ}} U {-у} имеем
f(0 = £ II» - <=i2 = Е +11“-с*
г/єС* уєС*{и}
> 53 +||г< - с*||2 = 53 US' - c'll2 S ^(Сі),
уЄС*{и} yeCi
что противоречит оптимальности множества С*. Лемма доказана.
Лемма 2.2 показывает, что оптимальное решение задачи VS-2 — подмножество С* Q У состоит из векторов, ближайших к вектору с* по расстоянию. Она устанавливает необходимое условие минимума и указывает на изложенный ниже подход к решению задачи, основанный на построении специального семейства допустимых решений.
Для произвольного вектора х Є R9 определим множество
См(х) = {уі ||Уі - х|| < ||% - х||;
Уг,У]^У, j^i, i= 1,...,М, j = 1,...,АГ}, (2.8)
состоящее из М ближайших (по расстоянию) к х элементов множества У, и максимальное расстояние
гм{х) — шах ||z — х|| (2-9)
уеСм (х)
от этого вектора до векторов из Смх).
Из определения (2.8) очевидно следует, что для любого векторах Є К.9 подмножество См{х) С У является допустимым решением задачи VS-2. Оценку качества такого решения позволяет установить следующая
Лемма 2.3. Пусть См{х) — допустимое решение задачи VS-2, по-