Элементарные решения неэлементарных задач на графах. Берзин Е.А. - 27 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

Составители: 

Рубрика: 

29
однако для практических целей более приемлемым является некоторое
ослабление этого требования, когда коммивояжер должен посетить
каждый пункт
по крайней мере один раз. Ослабление жесткости
ограничения в ряде случаев будет способствовать уменьшению длины
пути коммивояжера.
Классическая задача коммивояжера относится по степени сложности
к классу NP-полных задач [13, 14], и ее постановка в форме задачи
математического программирования со скалярными переменными [5, 12]
не позволяет создать достаточно эффективные алгоритмы, особенно для
решения задач больших размеров. Поэтому нужны специальные методы,
не связанные с классическим подходом, основанным на аппарате анализа
бесконечно малых. В [12] приведен анализ существующих наиболее
эффективных методов решения, при этом все они при решении задач
больших размеров носят неформальный характер. Наиболее успешные
реализации приближенных алгоритмов связаны с двумя схемами решения:
улучшения исходного цикла (схема А) и последовательного
построения цикла
(схема В). Предлагаемый метод расширения цикла
ближе примыкает к схеме В, однако отличается от нее тем, что в качестве
исходного берется уже готовый (начальный) цикл с одной или
несколькими промежуточными вершинами.
Комбинаторная постановка задачи коммивояжера состоит в поиске
такого замкнутого маршрута с началом и концом в одной вершине,
который включает в себя все остальные вершины и длина
его при этом
минимальна. Формальную постановку задачи можно записать в виде
(
)
()
,min
,
1
k
k
ji
ij
n
k
cL
μ
μ
μ
→=
∑
∈
−
{
}
11
,...,,...,
−−
∈=
n
k
n
k
kjk
μμ
1
,
где
(
)
1−n
k
L
μ
– длина цикла как сумма длин дуг (i, j), входящих в цикл
1−n
k
μ
;
1−n
k
μ
– контур (цикл), содержащий в качестве промежуточных все n – 1
остальных вершин графа (гамильтонов цикл).
Как отмечалось, можно рассматривать постановку классической
задачи с
жестким или ослабленным требованием на количество вершин
каждого типа в конечном цикле. Это влияет на метод решения. Метод
существенно зависит и от полноты матрицы расстояний
c . Рассмотрим
наиболее простую версию метода расширения цикла, позволяющую
достаточно эффективно решать классическую задачу коммивояжера при
жестком требовании на число вершин в решении и максимальной полноте
матрицы
c (φ = 1).
1
Множество
{
}
1−n
k
μ
содержит по крайней мере (n – 1)! элементов.

Страницы