Оглавление
Список иллюстраций.
Список таблиц
Список сокращений
Введение
Глава 1. Обзор проблематики и постановка задачи.
Введение
Язык программирования Пролог
Механизм доказательства в Прологе
Задача удовлетворения ограничениям i ii
Представление ограничений
Алгоритмы разрешения ограничений.
Алгоритмы распространения ограничений
Метод ветвей и границ
Открытие середины х годов фазовые переходы в комбинаторных задачах
Постановка задачи исследования.
Преобразование задачи коммивояжера в
Преобразование задачи коммивояжера в .
Приближенные методы решения задачи коммивояжера
Выводы по главе 1
Глава 2. Анализ поведения метода ветвей и границ при появлении фазового
перехода и разработка методов решения в условиях фазового перехода
Раздел 2.1 Особенности метода ветвей и границ при решении задач с
топологическими особенностями класса I
Топологические особенности.
Особенности решения
Методы кластеризации
Анализ топологии.
Гипотеза о природе фазового перехода от топологии
Оценка вероятности появления топологических особенностей.
Выводы по разделу 2.1
Раздел 2.2. Особенности метода ветвей и границ при решении задач с
топологическими особенностями класса II
Топологические особенности класса II
Экспериментальные результаты
Анализ топологии
Анализ работы метода ветвей и границ на задачах топологическими
особенностями класса II.
Возможные модификации.
Геометрическая интерпретация
Анализ сложности и точности решения приближенным алгоритмом.
Выводы по разделу 2.2.
Раздел 2.3. Метод ветвей и границ при решении комбинаторных задачах с
топологическими особенностями
Задача коммивояжера.
Квадратическая задача о назначении
Задача о 01 рюкзаке
Фазовые переходы
Влияние топологических особенностей на время решения методом ветвей и
границ
Выводы по разделу 2.3.
Раздел 2.4. Методы декомпозиции
Введение
Изменение граничного значения и уровня значимости.
Алгоритм с учетом декомпозиции
Иерархическая декомпозиция
Выводы по разделу 2.4.
Раздел 2.5. Метод интеллектуального возврата.
Введение
Использование топологических особенностей исходных данных.
Подход 1
Подход 2
Алгоритм интеллектуального возврата.
Результаты тестирования
Выводы по разделу 2.5
Выводы по главе 2
Глава 3. Разработка прототипа i системы
Раздел 3.1. Введение.
Интеграция методов в Прологподобную систему.
Выводы по разделу 3.1
Раздел 3.2. Разработка прототипа i системы.
Этапы разработки.
Разработка идеологии Пролог подобной системы
Структура данных языка Пролог
Синтаксический и семантический анализ при преобразовании данных
Синтаксический и семантический анализ Выражения.
Алгоритм доказательства цели
Алгоритм доказательства предиката.
Алгоритм возврата.
Выводы по разделу 3.2.
Раздел 3.3. Интеграция методов разрешения i.
Абстрактная Машина Варрена
Использование объектноориентированного подхода.
Интеграция методов решения задачи удовлетворения ограничениям
Выводы по разделу 3.3.
Выводы по главе 3.
Глава 4. Проверка применимости предложенного подхода.
Оценка времени вычисления и точности реализованных методов, сравнение с
приближенными и точными подходами.
Сравнение с существующим программным комплексом.
Задача коммивояжера.
Задача кумулятивного расписания.
Задача о 01 рюкзаке
Выводы по главе 4.
Заключение
Направления дальнейших исследований
Научные положения работы.
Обобщенные результаты но некоторым главам
Список литературы
- Київ+380960830922