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

• Автор: Щербина, Олег Александрович
• Шифр специальности: 05.13.17
• Научная степень: Докторская
• Год защиты: 2010
• Место защиты: Симферополь
• Количество страниц: 361 с. : ил.

СОДЕРЖАНИЕ

Обозначения, сокращения и определения.

ВВЕДЕНИЕ

ГЛАВА I. ДЕСКРИПТИВНАЯ ТЕОРИЯ ЛОКАЛЬНЫХ АЛГОРИТМОВ.

1.1.0 локальных алгоритмах вычисления информации

1.2. Локальные алгоритмы решения задач дискретной оптимизации

1.3. Локальный декомпозиционный алгоритм 2СВТ решения задач дискретной оптимизации е блочнодревовидной структурой.

1.4. Локачьный алгоритм для задач дискретной оптимизации,

характеризующихся блочнодревовидной структурой с дополнительными ограничениями.

1.5. О связи локальных алгоритмов с другими алгоритмами дискретной оптимизации

1.6. Распространение локального алгоритма на другие блочные структуры

Выводы по главе 1.
ГЛАВА II. ЛОКАЛЬНЫЕ ЭЛИМИНАЦИО 1НЫЕ АЛГОРИТМЫ
2.1. Основные определения.
2.2. Локальные элиминационные алгоритмы в задачах оптимизации
2.3. Локальные элиминационные алгоритмы решения дискретных задач информатики
Выводы по главе II
ГЛАВА III. РАЗРЕЖЕННЫЕ МАТРИЦЫ И ТЕОРЕТИКОГРАФОВЫЕ ПОДХОДЫ К ВЫДЕЛЕНИЮ БЛОЧНЫХ СТРУКТУР
3.1. Разреженные матрицы и выделение блочной структуры
3.2. Свойства матриц с блочнодревовидной структурой
3.3. Древовидная декомпозиция и древовидная ширина
Выводы по главе III.
ГЛАВА IV. ОЦЕНКИ ЭФФЕКТИВНОСТИ И УСЛОВИЯ ЦЕЛЕСООБРАЗНОСТИ ПРИМЕНЕНИЯ ЛОКАЛЬНЫХ АЛГОРИТМОВ
4.1. О сложности алгоритмов решения задач дискретной оптимизации, общие понятия о сложности алгоритмов.
4.2. Оценки сложности алгоритмов дискретной оптимизации.
4.3. Оценки эффективности локального алгоритма решения блочнодревовидных задач дискретной оптимизации.
4.4. О целесообразности использования локального алгоритма для решения задач дискретной оптимизации с блочнодревовидной структурой
4.5. Случай блочнодревовидной структуры с дополнительными ограничениями
Выводы по главе IV
ГЛАВА V. СРЕДНИЕ ЗНАЧЕНИЯ ОЦЕНКИ ЭФФЕКТИВНОСТИ
ЛОКАЛЬНОГО АЛГОРИТМА
5.1. Средние оценки эффективности локального алгоритма для блочнодревовидных задач дискретной оптимизации
5.2. Асимптотическая средняя оценка эффективности локального алгоритма для задач с блочнодревовидной структурой и ограниченной связностью.
5.3. Средняя оценка эффективности локального алгоритма для небулева случая
5.4. Оценка эффективности локального алгоритма в блочном случае с дополнительными ограничениями одновариантного типа
5.5. Средняя оценка эффективности локальною алгоритма на классе блочных задач в более общем случае
5.6. Асимптотические средние оценки эффективности локального алгоритма для блочнодревовидной структуры с дополнительными ограничениями многовариантного типа.
5.7. Асимптотические средние оценки эффективности локального алгоритма для блочнодревовидной структуры с дополнительными ограниченими одновариантного типа.
5.8. Средняя оценка эффективности локального алгоритма на классе всех блочно древовидных структур с дополнительными ограничениями одно вариантного типа
5.9. Средние оценки эффективности локального алгоритма при решении 7 блочных задач дискретной оптимизации
Выводы по главе V.
ГЛАВА VI. АНАЛИЗ БЛОЧНЫХ СТРУКТУР В СЛУЧАЯХ НАИЛУЧШЕГО И НАИХУДШЕГО ПОВЕДЕНИЯ ЛОКАЛЬНОГО АЛГОРИТМА.
6.1. Оценка максимального и минимального значений оценки эффективности локального алгоритма для задач дискретной оптимизации с блочнодревовидной структурой без дополнительных ограничений.
6.2. Наихудшее и наилучшее поведение локального алгоритма на классе блочнодревовидных структур с дополнительными ограничсниями многократного выбора
Выводы по главе VI
ГЛАВА VII. ВЫЧИСЛИТЕЛЬНЫЕ АСПЕКТЫ РЕАЛИЗАЦИИ ЛОКАЛЬНОГО АЛГОРИТМА
7.1. Оценочный эксперимент для локального алгоритма.
7.2. Эксперимент для локального алгоритма в сочетании с алгоритмами пакета Диспро.
7.3. Приближенные версии локального алгоритма.
7.4. Локальный элиминационный алгоритм и параллельные вычисления
Выводы но главе VII.
ЗАКЛЮЧЕНИЕ
ЛИТЕРАТУРА


Основные результаты главы V являются подтверждением для локального алгоритма известной гипотезы Дясерослоу 1 о несуществовании полиномиальных комбинаторных алгоритмов в то же время они свидетельствуют о возможности эффективного применения локального алгоритма для решения блочнодревовидных задач ДО с небольшой связностью блоков. Глава VI посвящена выявлению условий наилучшего и наихудшего поведения локального алгоритма путем анализа экстремальных значений оценки эффективности локального алгоритма, что позволяет выделить наилучшие и наихудшие для применения локального алгоритма структуры, а также оценить максимальный и минимальный объем перебора. В параграфе 6. ЛЭА на множестве всех блочнодревовидных структур без дополнительных ограничений, приведены соответствующие оценки для квазиблочных структур. В параграфе 6. ЛЭА на вышеуказанном классе структур, приведены точные значения минимума в случае квазиблочных структур. В параграфах 6. ЛЭА получены таюке на блочнодиагональных структурах с дополнительными ораничениями многократного выбора. Результаты, полученные в главе VI, позволяют качественно оценивать поведение ЛЭА на тех или иных блочнодревовидных структурах, позволяют также определять, каких структур следует избегать, а к каким стремиться при использовании ЛЭА. Глава VII посвящена вычислительным аспектам реализации ЛЭА и анализу возможностей снижения перебора при использовании ЛЭА. В параграфе 7. ЛЭА в сочетании с различными алгоритмами ДО. Особо выделены результаты использования ЛЭА в сочетании с приближенными алгоритмами ДО. В параграфе 7. ДО с помощью ЛЭА на основе использования релаксаций при реализации локального алгоритма. В параграфе 7. Здесь исследуется приближенная версия локального элиминационного алгоритма, основанная на выборе перемычек между блоками с помощью некоего оракула, который использует либо анализ релаксированной блочнодревовидной задачи ДО, либо случайный выбор, при больших перемычках используется перебор всех значений перемычек, принадлежащих некоторой окрестности Хелшинга радиуса И. Параграф 7. ДО параллелизм, присущий ЛЭА параллелизация, соответствующая каждому блоку и параллелизм, возникающий из разреженности задачи распараллеливание на основе элиминационного дерева. ГЛАВА I. При изучении сложных объектов не всегда возможно получить или вычислить полную информацию об объекте в целом, поэтому представляет интерес получение информации об объекте, рассматривая его по частям, т. В работах , , Ю. И. Журавлев ввел и исследовал локальные алгоритмы вычисления информации. Локальный алгоритм задается следующим образом. Для заданной системы множеств я,т ,, 1,2,. Если на паре II, т определены окрестности 5, , я,. Эк и, я, говорят, что на множестве я введена система окрестностей. Приведенное определение окрестности является весьма общим. В качестве конкретного примера может служить понятие окрестности3 вершины графа. Ниже, в параграфе 1. Если для некоторого к выполнено условие , т 1 и, т для всех пар и, т, то система окрестностей Я,,. Отметим существование иных определений понятия окрестности вершины графа. Так, н 6 число элементов этой окрестности включаются только вершины, в работе 8 вводится также понятие окрестности ребра графа. Рхи,пг,. Рки,п которая разбита на два непересекающихся подмножества ,. Вектор называется информационным, если аг. Вектор ссх,. Ц в т9 если для всех а1 ФА выполнено соотношение а. Пусть т 1и1,т , 1,2,. Л,,вг,Л,. РХ,. РЯ. Понятно, что окрестность 5 и,т определяет окрестность и. С,да Д,. Функции р. Рк допустимо для т т е ш. Пары т обозначим , а,,. Если Л, 0,1, А, то А О, А 1. Пусть М2 множество информационных векторов длины тогда а,,. Л1Рц . В0К, если и В а1Р. ЛА ея2, то . Я В5г3 е, следует,что . Пусть А VI В элементы одного из множеств, перечисленных выше в п. Если А В и В А, то элементы А и В назовем равными по информации и обозначим это так А В. Функцию р. Б2 следует, что рх и, ах,. Я2, 1,. Для определения локального алгоритма введем также алгоритм упорядочения Ая и А оператор по системе предикатов. Пусть М произвольное множество, составленное из элементов с информационными векторами 1,2,.