Гуральник Роман Игоревич Инкрементальные алгоритмы решения задач оптимизации на больших графах

Краткое описание

Гуральник Роман Игоревич Инкрементальные алгоритмы решения задач оптимизации на больших графах
ОГЛАВЛЕНИЕ ДИССЕРТАЦИИ
кандидат наук Гуральник Роман Игоревич
ВВЕДЕНИЕ

Актуальность темы

Цель работы

Задачи работы

Положения, выносимые на защиту

Методология и методы исследования

Степень разработанности темы

Соответствие диссертации паспорту научной специальности

Научная новизна работы

Теоретическая и практическая значимость работы

Апробация работы и публикации

Объем и структура диссертации

ГЛАВА 1. ЗАДАЧИ ПОИСКА И АНАЛИЗА ПУТЕЙ В БОЛЬШИХ ГРАФАХ

1.1 Задача анализа схожести узлов графа

1.2 Задача максимизации влияния

1.3 Задача сопоставления с образцом

1.4 Задача обнаружения сетевых мотивов

1.5 Задача ресурсно-ограниченного кратчайшего пути

1.5.1 Постановка задачи

1.5.2 Алгоритм Muhandiramge и Во1а^

1.6 Задача маршрутизации транспорта

1.7 Инкрементальный подход к решению задач

1.7.1 Задача инкрементального сопоставления с образцом

1.7.2 Задача инкрементальной оценки схожести узлов

ГЛАВА 2. ИНКРЕМЕНТАЛЬНЫЙ АЛГОРИТМ ПЕРЕСТРОЕНИЯ МАРШРУТОВ ДЛЯ ЗАДАЧИ МАРШРУТИЗАЦИИ ТРАНСПОРТА С ОДНИМ ТРАНСПОРТНЫМ СРЕДСТВОМ

2.1 Постановка задачи

2.2 Инкрементальный алгоритм перестроения маршрутов

2.3 Вычислительная сложность и эксперименты

ГЛАВА 3. ЗАДАЧА РЕСУРСНО-ОГРАНИЧЕННОГО КРАТЧАЙШЕГО ПУТИ

3.1 Постановка инкрементальной задачи ресурсно-ограниченного кратчайшего пути

3.2 Описание базового алгоритма

3.2.1 Простое отсеивание узлов

3.2.2 Ликвидация разрывов

3.3 Инкрементальное обновление деревьев кратчайших путей

3.4 Алгоритм инкрементального обновления ДКП

3.4.1 Вычислительная сложность алгоритма обновления ДКП в контексте задачи RCSP

3.5 Описание инкрементальной предварительной обработки

3.6 Общий подход к реализации ликвидации разрывов

3.7 Эксперименты

ЗАКЛЮЧЕНИЕ

СПИСОК ЛИТЕРАТУРЫ