Вероятностный анализ алгоритмов с гарантированными оценками точности для решения некоторых трудных задач маршрутизации

• Автор: Истомин, Алексей Михайлович
• Шифр специальности: 01.01.09
• Научная степень: Кандидатская
• Год защиты: 2015
• Место защиты: Новосибирск
• Количество страниц: 101 с. : ил.

Оглавление
Введение

1 Задача нескольких коммивояжёров с входными данными специального вида

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

1.2 Алгоритм приближенного решения задачи

1.2.1 Вспомогательная процедура построения гамильтоновой цени . .

1.2.2 Описание алгоритма решения задачи

1.2.3 Описание входных данных

1.3 Вероятностный анализ алгоритма

1.3.1 Входные данные, распределённые по нормальному закону

1.3.2 Входные данные, распределённые по показательному закону . .

2 Задача двух коммивояжёров с ограничениями на пропускные способности рёбер
2.1 Постановка задачи и предварительные сведения
2.2 Новые алгоритмы решения задач на минимум и па максимум с общей весовой функцией

2.'2.1 Описание1 вспомогательной процедуры
2.3 Анализ точности алгоритмов в среднем
2.3.1 Анализ алгоритма для задачи на минимум
2.3.2 Анализ алгоритма для задачи на максимум
2.4 Новые алгоритмы решения задач на минимум и па максимум с различными весовыми функциями маршрутов
2.4.1 Описание вспомогательной процедуры
2.5 Анализ ючноети алгоритмов в среднем
2.5.1 Анализ алгоритма для задачи на минимум
2.5.2 Анализ алгоритма для задачи па максимум
3 Задача маршрутизации транспортных средств в евклидовом пространстве
3.1 Предварительные сведения
3.2 Случай равномерного распределения на круге единичной площади
Заключение
Публикации автора по теме диссертации
Благодарности
Литература

Введение
Современный Экономический прогресс во многом обусловлен научным подходом к решению задач ортанизацнп предприятий: оі дизайна изделий и эффективной ор-гапизадии производства до ценообразования н целесообразно выстроенной дени доставки продукции до конечного потреби юля.
Для эффективного решения таких проблем возникает необходимость построения математических моделей реальных процессов и алгоритмов решения возникающих при этом задач. Как правило, решение этих задач связано со значительными трудностями вычислительного харакк'ра. Общее представление о сложности таких задач дает книга [18]. В этой книге приводится более 500 задач (из самых разных областей, включая теорию графов и сетей, теорию расписаний, теорию автоматов и языков, оптимизацию программ, базы данных, игры и головоломки и т.п.), для которых построение эффективных алгоритмов их решения в настоящее время считается маловероятным.
Появление вычислительной техники привело к тому, что все реже приходится решать отдельную конкретную задачу, а все больше писать программы, рассчитанные на целый класс задач, получающихся одна из другой заменой ряда исходных данных. Поэтому имеет смысл говорить о сложности не для одной индивидуальной задачи /.

Пусть 1п п < т < /I1 " < п/Л. Положим
6 т +

Возьмем Е = а„(‘3пг + Зн?). Поскольку ь -лом случае ОТ < (Зпг + 6т)п„ = ,г, по теореме Петрова имеем:
Рг{/д > (1 +С„)ОРТ} < Рг{5 > .г} < ехр = ехр(--"Г + °Ш) < = ^
Таким образом, поскольку величины сп и 8п стремятся к 0 с ростом п. алгоритм А в условиях теоремы асимптотически точен.