Введение к работе
Актуальность темы. В диссертации исследуются две задачи комбинаторной оптимизации: задача о наибольшем независимом множестве и задача о наименьшем зависимом миожестпе наследственной системы, а также известная задача аппроксимации графа, различные варианты которой являются частными случаями задач на наследственных системах.
Оптимизационные задачи на наследственных системах и графах являются математическими моделями многих сложных в вычислительном плане практических задач, связанных с управлением процессами, протекающими в реальных системах. В русле системного подхода к изучению таких процессов, наследственные системы можно рассматривать как формализованные модели реальных систем, свойства которых сформулированы в виде абстрактных аксиом. Другой распространенной моделью реальных систем являются структурные схемы систем. Абстрагируясь от содержательной стороны структурных схем и выявляя их математическую сущность, получаем графы или гиперграфы, в которых содержится информация о наличии элементов системы и связей между ними.
Большинство оптимизационных задач на наследственных системах и графах относится к классу ^Р-трудных, в связи с чем особую актуальность приобретает анализ вычислительной сложности конкретных задач, построение приближенных алгоритмов с априорными оценками точности, а также экспериментальное исследование приближенных алгоритмов.
Цель работы. Исследование вычислительной сложности и сложности аппроксимации двух оптимизационных задач на наследственных системах и задач, сводящихся к ним - задачи о наибольшем независимом множестве вершин гиперграфа и задачи аппроксимации графа, а также разработка и анализ приближенных алгоритмов решения этих задач.
Методы исследования. При выполнении работы использовались методы дискретной оптимизации, теории графов, методы вероятностного анализа приближенных алгоритмов, а также методы экспериментального исследования алгоритмов с применением современной вычислительной техники.
Научная новизна. В работе проведено теоретическое и экспериментальное исследование общих оптимизационных задач на наследственных системах и сводящихся к ним задач на графах и гиперграфах, получены
новые результаты, касающиеся вычислительной сложности и сложности аппроксимации этих задач.
Основные результаты работы:
-
Предложен приближенный алгоритм решения задачи о наибольшем независимом множестве наследственной системы, которая рассматривается как задача о наибольшем независимом множестве вершин гипер-графа. Получена гарантированная оценка погрешности этого алгоритма в терминах средней степени вершин гиперграфа. Доказана эквивалентность задачи о наименьшем зависимом множестве наследственной системы и задачи о покрытии множества. Как следствие получена гарантированная оценка погрешности приближенного алгоритма решения задачи о наименьшем зависимом множестве в терминах максимальной степени вершин гиперграфа.
-
Показано, что невзвешенная задача аппроксимации графами с фиксированным числом компонент NP-трудиа.. Для задачи аппроксимации графами, имеющими не более двух компонент связности, доказано существование полиномиальной аппроксимационной схемы. Предложен вероятностный алгоритм решения этой задачи с константной оценкой точности. Разработаны также асимптотически точные алгоритмы решения этой задачи на редких графах.
-
Предложены эвристические алгоритмы решения задачи аппроксимации графами, имеющими не более двух компонент связности. Для поиска оптимальных решений разработан и реализован точный алгоритм на основе метода ветвей и границ. Проведенное экспериментальное исследование эвристических алгоритмов показало, что решения, найденные этими алгоритмами, как правило, достаточно близки к оптимальным.
Основные результаты диссертации, выносимые на защиту, получены автором лично.
Практическая ценность. Полученные в диссертации теоретические результаты применимы в научных исследованиях, а также в учебном процессе. Предложенные алгоритмы могут быть использованы при решении задач достаточно большой размерности.
Апробация работы. Основные результаты диссертации докладывались на Российской конференции «Дискретный анализ и исследование операций» (Новосибирск, 2002), 12-ой Всероссийской конференции «Математическое программирование и приложения» (Екатеринбург, 2003), Всероссийской конференции «Проблемы оптимизации и экономические приложения» (Омск, 2003), ХШ-ой Байкальской международной школе-
семинаре «Методы оптимизации и их приложения» (Иркутск, 2005), а также на научных семинарах в Омском филиале Института математики им. С.Л. Соболева СО РАН.
Публикации. По теме диссертации автором опубликовано 9 научных работ, список которых приведен в конце автореферата.
Структура и объем работы. Диссертация изложена па 105 страницах, состоит из введения, трех глав, заключения, списка литературы, содержащего 46 наименований, и приложения.
