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

UptoLike

ВУЗ: 

ТвГТУ | Тверь

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

Рубрика: 

75
методом расширения цикла, может быть улучшено путём удаления тех
повторяющихся элементов, каждый из которых совместно с двумя
смежными элементами
не составляет кратчайший маршрут. Для
обобщенной задачи коммивояжера это правило справедливо только для
транзитных элементов. Активный элемент удаляется, если его удаление в
целом приводит к уменьшению энергозатрат. Однако и совместного
выполнения обоих необходимых условий недостаточно для утверждения
об оптимальности полученного решения.
6. В отличие от классической задачи коммивояжера, решение
обобщенной задачи коммивояжера не инвариантно относительно
начального пункта цикла. Среди
n пунктов существует, по крайней мере,
один, выбор которого в качестве исходного обеспечит минимум
энергозатрат по сравнению с оптимальными решениями при других
исходных пунктах.
5. СРАВНИТЕЛЬНАЯ ОЦЕНКА РАССМОТРЕННЫХ МЕТОДОВ
РЕШЕНИЯ ЗАДАЧ КОММИВОЯЖЕРА
Для наиболее трудоёмких методов решения рассмотренных задач
объем элементарных операций оценивается полиномом не выше третьей
степени, при этом для повышения гарантии оптимальности решения
требуется некоторое увеличение объема вычислений. На одном общем для
всех методов тестовом примере проиллюстрируем их вычислительные
схемы, что позволит провести сравнение методов и выявить их
особенности.
5.1. Решение тестового примера задачи коммивояжера
методом расширения цикла
Исходные данные тестового примера представлены матрицей
расстояний, записанной в табл. 30. Элементы матрицы расстояний
с
выбраны произвольно от 1 до 30. Матрица полная )1(
=
ϕ
, что позволит
для решения наряду с модифицированным использовать и
немодифицированный метод расширения цикла.
Вычислительная схема метода расширения цикла подробно описана и
проиллюстрирована в подразделе 3.2. Порядок решения представлен блок-
схемой (рис. 3), поэтому рассмотрим только результаты решения
классической задачи коммивояжера, представленные в табл. 32
для всех
вариантов возможных начальных циклов
.
Оптимальными являются (табл. 32) только 5 из 15 возможных

Страницы