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

• Автор: Талевнин, Антон Степанович
• Шифр специальности: 05.13.01
• Научная степень: Кандидатская
• Год защиты: 2006
• Место защиты: Омск
• Количество страниц: 105 с. : ил.

Введение

1 Общие задачи на наследственных системах

1.1 Наследственные системы. Определения и примеры.

1.1.1 Определения и постановки задач на наследственных системах.

1.1.2 Некоторые задачи на графах и соответствующие на

следственные системы.

1.2 Задача о наибольшем независимом множестве.

1.2.1 Приближенный алгоритм для задачи о наибольшем независимом множестве

1.2.2 Оценка погрешности алгоритма для задачи о наибольшем независимом множестве

1.3 Задача о наименьшем зависимом множестве.

1.3.1 Связь задачи о наименьшем зависимом множестве

с задачей о покрытии множеств .
1.3.2 Оценка погрешности приближенного алгоритма для задачи о наименьшем зависимом множестве
2 Задача аппроксимации графа
2.1 Постановки задач
2.1.1 Определения и постановки задачи аппроксимации графа.
2.1.2 Задача о бисекции графа.
2.2 Сложность задачи аппроксимации графа.
2.2.1 Вычислительная сложность задачи аппроксимации графами с фиксированным числом компонент .
2.2.2 Полиномиальная аппроксимационная схема для задачи .
2.3 Приближенные алгоритмы для задачи .
2.3.1 Асимптотически точные алгоритмы для задачи А
на редких графах
2.3.2 Вероятностный приближенный алгоритм для задачи аппроксимации графа А.
Экспериментальное исследование приближенных алгоритмов для задачи аппроксимации графов
3.1 Описание вычислительного эксперимента
3.2 Точный и приближенные алгоритмы для задачи аппроксимации .
3.2.1 Градиентный алгоритм .
3.2.2 Алгоритм Томеску
3.2.3 Приближенный вероятностный алгоритм.
3.2.4 Метод ветвей и границ для задачи А.
3.3 Результаты экспериментального исследования.
3.3.1 Предварительный эксперимент и выдвижение гипотез
3.3.2 Экспериментальная проверка гипотез на графах большой размерности.
Заключение Список литературы
Публикации автора по теме диссертации Приложение
Введение


Например, если требуется отразить несимметричность связей, то ребра снабжают стрелками и получают ориентированный граф в случае необходимости указать другие различия между элементами или связями, приписывают вершинам или ребрам графа веса и получают взвешенный граф, и т. В процессе взаимодействия со средой система способна изменятся, переходя из одного состояния в другое. Широко трактуя будущее состояние системы как цель, можно также определить систему как средство достижения цели . Разумеется, сложные системы могут иметь не одну, а множество целей. Эти цели могут быть субъективными идеальные образы желаемых состояний искусственных систем, созданных человеком, а также систем смешанного типа, испытывающих влияние человеческого фактора и объективными будущие реальные состояния систем, в том числе естественных, существующих независимо от человека. В искусственных и смешанных системах достижение субъективных целей происходит в результате управляющих воздействий человека на систему. Человек разумный стремится найти оптимальное управление, т. Математическими моделями таких процессов управления являются, в частности, задачи комбинаторной оптимизации, допустимыми множествами в которых являются конечные математические объекты сложной структуры системы множеств, графы и т. Целыо настоящей диссертации является исследование вычислительной сложности и сложности аппроксимации общих оптимизационных задач на наследственных системах и двух задач, сводящихся к ним задачи о наибольшем независимом множестве вершин гиперграфа и задачи аппроксимации графа, а также разработка и анализ приближенных алгоритмов решения этих задач. Имеются различные подходы к анализу приближенных алгоритмов решения дискретных оптимизационных задач. Первый подход анализ алгоритма в худшем случае, когда находится гарантированная оценка точности алгоритма, справедливая для всех индивидуальных задач. Второй подход вероятностный анализ алгоритма, при котором предполагается, что на множестве всех индивидуальных задач задано некоторое вероятностное распределение, и, как правило, оцениваются математическое ожидание и дисперсия погрешности алгоритма. Третий подход основан на вычислительном эксперименте, использующем тестовые примеры индивидуальных задач. В диссертации реализуются все три названных подхода. Получены гарантированные оценки погрешности приближенных алгоритмов решения задач о наибольшем независимом множестве и наименьшем зависимом множестве наследственной системы. Определена вычислительная сложность в худшем случае задачи аппроксимации графа и для одного варианта задачи предложен вероятностный алгоритм. Для исследования качества другого приближенного алгоритма решения задачи аппроксимации графа использована идея построения алгоритмов с оценками, предложенная Э. Х. Гимади, Н. И. Глебовым и В. А. Перепелицей 3, 4. Проведено экспериментальное исследование приближенных алгоритмов решения задачи аппроксимации графа. Приведем формулировки исследуемых задач и дадим краткий обзор известных результатов. Пусть V конечное множество. Множества семейства Л называются независимыми, а все подмножества из 2У 4 зависимыми. Семейство всех зависимых множеств обозначим через V. В V и В С то В V. Очевидно, что каждое из семейств А, V однозначно определяет другое. Поэтому естественно рассматривать их как различные стороны одного и того же объекта, наследственной системы. В наследственная система Б на множестве V определяется как разбиение семейства 2У всех подмножеств V на два непересекающихся подсемейства А и Р, где V, А система независимости, а Р 2У А. Базами системы 5 называются максимальные но включению независимые, а циклами минимальные по включению зависимые множества. Семейства всех баз и всех циклов системы 5 будем обозначать через В и С соответственно. Очевидно, что каждое из семейств В, С также однозначно определяет наследственную систему . Будем записывать Б У,А, Б К 5, 5 У,С или 5 У,Т в зависимости от того, какая сторона наследственной системы нас в данный момент интересует.