Асимметричная и симметричная задачи

Представление в виде графа

Формальное определение

Симметричная задача для четырех городов.

Для возможности применения математического аппарата для решения проблемы, ее следует представить в виде математической модели. Проблему коммивояжёра можно представить в виде модели на графе, то есть, используя вершины и ребра между ними. Таким образом, вершины графа (на рис.: От A до D) соответствуют городам, а ребра между вершинами и — пути сообщения между этими городами. Каждому ребру можно сопоставить критерий выгодности маршрута (На рис.: 20, 42, …), который можно понимать как, например, расстояние между городами, время или стоимость поездки. Маршрутом (также гамильтоновым маршрутом) называется маршрут на таком графе, в который входит по одному разу каждая вершина графа. Задача заключается в отыскании кратчайшего маршрута.

В целях упрощения задачи и гарантии существования маршрута, обычно считается, что модельный граф задачи является полностью связным, то есть, что между произвольной парой вершин существует ребро. В тех случаях, когда между отдельными городами не существует сообщения, этого можно достичь путем ввода рёбер с максимальной длиной. Из-за большой длины такое ребро никогда не попадет к оптимальному маршруту, если он существует.

В зависимости от того, какой критерий выгодности маршрута сопоставляется величине ребер, различают различные варианты задачи, важнейшими из которых являются симметричная и метрическая задачи.

В общем случае, асимметричная задача коммивояжера отличается тем, что она моделируется ориентированным графом. Таким образом, следует также учитывать, в каком направлении находятся ребра.

В случае симметричной задачи все пары ребер между одними и теми же вершинами имеют одинаковую длину, то есть, для ребра одинаковы длины. В симметричном случае количество возможных маршрутов вдвое меньше асимметричного случая. Симметричная задача моделируется неориентированным графом (см. рисунок).

На самом деле, задача коммивояжёра в случае реальных городов может быть как симметричной, так и асимметричной в зависимости от длительности или длины маршрутов и от направления движения.

Метрическая задача

Симметричную задачу коммивояжера называют метрической, если относительно длин ребер выполняется неравенство треугольника. Условно говоря, в таких задачах обходные пути длиннее прямых, то есть, ребро от вершины до вершины никогда не бывает длиннее пути через промежуточную вершину:

Такое свойство длины ребер определяет измеримое пространство на множестве ребер и меру расстояния, удовлетворяющую интуитивному пониманию расстояния.

Распространенные на практике функции расстояния являются также метриками и удовлетворяют неравенству треугольника:

• Евклидово расстояние в евклидовой задаче коммивояжёра,
• Манхэттенская метрика (также квартальная метрика) прямоугольной задачи коммивояжёра, в которой расстояние между вершинами на решетке равно сумме расстояний по оси ординат и абсцисс,
• Максимальная метрика, определяющая расстояние между вершинами решетчатого графа как максимальное значение расстояния вдоль оси ординат и абсцисс.

Две последние метрики находят применение, например, при сверлении отверстий в печатных платах, когда станок должен сделать больше отверстий за наименьшее время и может перемещать сверло в обоих направлениях для перехода от одного отверстия к следующему. Манхэттенская метрика соответствует случаю, когда передвижение в обоих направлениях происходит последовательно, а максимальная — случаю, когда передвижение в обоих направлениях происходит синхронно, а общее время равно максимальному времени передвижения вдоль оси ординат или абсцисс.

Не-метрическая задача коммивояжёра может возникать, например, в случае минимизации длительности пребывания при наличии выбора транспортных средств в различных направлениях. В таком случае обходной путь самолетом может быть короче прямого сообщения автомобилем.

Если на практике в условиях задачи разрешается посещать города несколько раз, то симметричную задачу можно свести к метрической. Для этого задачу рассматривают на так называемом графе расстояний. Этот граф имеет такое же множество вершин, как и исходный, и является полностью связным. Длина ребер между вершинами и на графе расстояний соответствует длине кратчайшего расстояния между вершинами и в исходном графе. Для определенных таким образом длин выполняется неравенство треугольника, и каждому маршруту на графе расстояний всегда соответствует маршрут с возможными повторениями вершин в исходном графе.

Дата добавления: 2014-01-04