Применение кластеризации ситуаций в эвристических алгоритмах для задач дискретной оптимизации

• Автор: Мельникова, Елена Анатольевна
• Шифр специальности: 05.13.18
• Научная степень: Кандидатская
• Год защиты: 2009
• Место защиты: Тольятти
• Количество страниц: 152 с. : ил.

1.1. Постановка задач дискретной оптимизации

1.2. О возможных подходах к решению

1.3. Задачи дискретной оптимизации более подробное описание

1.4. Жадные эвристики и метод ветвей н границ

1.5. Возможный мультнэвристнческин подход

Глава 2.
Описание оригинального алгоритма кластеризации и некоторые предметные области его применения

2.1. Введение

2.2. Описание алгоритма кластеризации

. Некоторые другие предметные области применения

2.4. Пример метрики для задачи вершинной минимизации недетерминированных конечных автоматов
2.5. Заключение главы
Глава 3.
Предлагаемые подходы к организации незавершнного метода ветвей и гранцц и к оценке качества эвристических алгоритмов
3.1. Введение
3.2. Об одном подходе к организации незавершнного метода ветвей и границ
3.3. Описание общего алгоритма
3.4. Предлагаемый подход к сравнительной оценке качества эвристических алгоритмов
3.5. Заключение главы
Глава 4.
Применение кластеризации ситуаций в задачах дискретной оптимизации
4.1. Введение
4.2. Задача вершинной минимизации НКА некоторые результаты счта
4.3. Задача минимизации ДНФ матричная метрика и некоторые результаты счта
4.4. Задача коммивояжера матричная метрика и результаты счта
4.6. Заключение главы
Глава 5.
Кластеризация ситуаций и сопутствующие алгоритмы в недетерминированных играх
5.1. Введение
5.2. Предварительные сведения
5.3. Общие эвристики в недетерминированных играх
5.4. Некоторые вспомогательные эвристики
5.5. Подход к построению статической оценки с использованием нейросети
5.6. Пример использования алгоритма обработки вершин
5.7. Заключение главы
Глава 6.
Возможный подход к реализации алгоритмов с помощью объектноориентированного программирования
6.1. Введение
6.2. Программная реализация одной несложной олнмпиадной проблемы
6.3. Подход к программной реализации задачи вершинной минимизации недетерминированных конечных автоматов
6.4. Заключение главы
Заключение
Приложения
Приложение А.
Текст программы минимизации недетерминированных конечных автоматов
Приложение Б.
Часть текста программы решения задачи коммивояжра
Литература


Но в отличие ог нисходящего метода разделяйивластвуй делающего ото рекурсивно, метод динамического программирования работает восходящим способом. Решение задачи начинается с вычисления решений подзадач наименьшей размерности простейших подзадач. Далее решаются подзадачи вс большей и большей размерности до тех пор, пока не будет решн исходный частный случай проблемы. В процессе своей работы любой алгоритм, основанный на методе динамического программирования, сохраняет все промежуточные решения в некоторой специальной таблице. Эго является главным преимуществом динамического программирования по сравнению с методом разделяйивластвуй, который теоретически может приводить к возникновению экспоненциально многих подзадач исходной задачи несмотря даже на то, что число различных вариантов подзадач оценивается полиномиально т. Широко известными приложениями динамического программирования построения кратчайших путей в графе, алгоритм оптимального сопоставления с образцом, а также псевдонолшюмпалъный алгоритм решения задачи о рюкзаке. При этом остатся много задач дискретно оптимизации, для которых применение динамического программирования приводит к алгоритмам экспоненциальной сложности ,. Бэктрекинг. Этот метод решения , оптимизационных задач путм поиска возможно исчерпывающего на множестве всех допустимых решений. Чтобы применить его для решения некоторой оптимизационной задачи необходимо ввести специальную структуру на множестве всех е допустимых решений. Пусть О множество всех допустимых решений для входа х некоторой оптимизационной задачи. Каждое допустимое решение можно считать кортежем из п элементов риръ, Р, где каждый элемент р, может быть выбран из конечного множества Р,. Тогда структуру можно определить в виде дерева следующим образом. Корень помечен С. Каждая вершина некоторым подмножеством О. При этом подмножества решений, соответствующие дочерним вершинам, определяют разделение множества решений, соответствующего родительской вершине. Листья соответствуют допустимым решениям. Можно начать строить дерево, положив рга для некоторого аеР. При этом левая дочерняя вершина корня соответствует множеству допустимых решений, таких что Р1а, а правая множеству допустимых решений, таких что р1 фа. Продолжая эту стратегию, молено построить дерево прямым путм. Если дерево уже построено, то бэктрекинг фактически является поиском в глубину или в ширину в этом дереве. Однако на самом деле необязательно реализовывать бэктрекинг в два этапа сначала создание дерева, а потом поиск в нм гакой подход потребовал бы слишком большого объма памяти компьютера. Дерево рассматривается только как виртуальное, и поиск в глубину начинается в нм сразу т. При таком подходе достаточно сохранять в памяти компьютера только описание пути из корня в текущую вершину. Преимущество бэктрекинга по сравнению с полным перебором, состоит следующем. Если найдено некоторое допустимое решение со стоимостью т, и если для некоторой вершины V дерева можно узнать вычислить, тто все решения соответствующие поддереву с корнем V, не могут быть по стоимости лучше т, то можно полностью пропустить поиск в поддереве с корнем V. И, если повезт, то удастся пропустить поиск во многих поддеревьях и бэктрекинг станет значительно более эффективным. В худшем случае бэктрекинг сводится к полному перебору на множестве допустимых решений. При использовании точных методов приходится преодолевать трудности, связанные с возрастанием трудомкости решения задачи с ростом числа переменных, с доказательством оптимальности полученного решения. Кроме того, в прикладных задачах математическая модель является приближнным описанием реальной задачи, получение точного решения может представлять академический интерес. Поэтому кроме точных методов для решения ЗДО применяются также приближенные методы. В приближнных методах решепие может проходить в два этапа построение начального решения и улучшение начального решения. На первом этапе применяются эвристические алгоритмы например, жадные алгоритмы. Ыа втором этапе применяются алгоритмы локального поиска.