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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

128
коммивояжера, по существу и является одной из основных целей работы.
Другой целью, которую автор ставил перед собой при разработке
материала, была попытка показать логические пути, приводящие к тем или
иным решениям при разработке или модификации предлагаемых методов.
Именно поэтому предложенные числовые примеры, иллюстрирующие
методы, решались «вручную» с сохранением всей
промежуточной
информации
как основы для неформального анализа методов и
дальнейшего их совершенствования. Подобный неформальный анализ
будет всегда недоступен для любых самых совершенных
интеллектуальных программ, т.к. в любой из них, может быть, в самых
глубинных её корнях, будет невозможно обойтись без детерминированных
алгоритмов, предусмотренных её разработчиком.
В основе рассмотренных методов лежит неформальный
(эвристический) подход, при этом центральным из них является
эстафетный метод, позволяющий с относительно небольшими затратами
машинных ресурсов получить
точное решение задачи о кратчайшем
пути
.
Задачу коммивояжера можно рассматривать как частный случай
задачи о кратчайшем пути с
дополнительным условием об обязательном
посещении всех
n пунктов. Однако это условие существенным образом
влияет на решение, для получения которого эстафетный метод в чистом
виде становится неприемлемым. На его основе в лучшем случае могут
быть получены оптимальные замкнутые маршруты (например, см. табл. 9),
как правило, не обеспечивающие выполнение дополнительного условия.
Принудительное включение не вошедших в цикл пунктов является
основным содержанием метода расширения цикла. Поскольку на каждом
шаге процесса используются
все интервалы цикла, то можно
предполагать и дальновидность решения, принимаемого на каждом шаге
процесса.
1
Анализ численных решений, полученных для рассмотренных
примеров, приводит к выводу о целесообразности включения в тот или
иной интервал цикла не просто очередного индекса
t
Gj ∈ , а совместно с
некоторыми участками кратчайших маршрутов
, соединяющими этот
элемент с границами интервала. Эта идея положена в основу
модифицированных методов решения
классической и обобщенной задач
коммивояжера
. Указанная идея позволила найти решение важного класса
задач коммивояжера для случая, когда матрица расстояний
ij
c не
является полной
( 1<
ϕ
). Рассмотренная идея, позволившая
модифицировать метод расширения цикла и расширить класс задач,
решаемых на его основе, снова приводит к необходимости применения
1
Процесс «на каждом шаге иди к ближайшему пункту» такой «дальновидностью» не
обладает и может привести к грубым ошибкам [12].

Страницы