Водителю-экспедитору необходимо, выехав из офиса ООО "Пепсико Холдингс", посетить по разу в неизвестном порядке торговые точки и вернуться в офис. Расстояния между торговыми точками известны. В каком порядке следует обходить города, чтобы замкнутый путь водителя-экспедитора был кратчайшим?

Маршрут в графе - это последовательность вершин x₁, x₂… x_n, такая, что для каждого i=1, 2… n?1 вершины x_i и x_i+1 соединены ребром. Эти n?1 ребер называются ребрами маршрута. Говорят, что маршрут проходит через них, а число n?1 называют длиной маршрута. Говорят, что, если маршрут соединяет вершины x_i и x_n, то они называются соответственно началом и концом маршрута, вершины x₂…x _n называются промежуточными. Маршрут называется замкнутым, если x₁=x_n.

Путь - это маршрут, в котором все ребра различны. Путь называется простым, ес-ли и все вершины в нем различны.

Цикл - это замкнутый путь. Цикл x₁, x₂… x_n-1, x₁ называется простым, если все вершины x₁, x₂… x_n-1 попарно различны [9].

Установим некоторые простые свойства маршрутов.

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

2) Если в графе степень каждой вершины не меньше 2, то в нем есть цикл. Доказательство этих свойств можно найти в [9].

Расстоянием между двумя вершинами графа называется наименьшая длина пути, соединяющего эти вершины. Расстояние между вершинами a и b обозначается через d(a,b). Если в графе нет пути, соединяющего a и b, то расстояние между ними считается бесконечным. Функция d(a,b) обладает следующими свойствами:

1) d(a,b)?0, причем d(a,b)=0 тогда и только тогда, когда a=b;

2) d(a,b)=d(b,a);

3) d(a,b)+d(b,c)?d(a,c) (неравенство треугольника).

Расстояние от данной вершины a до наиболее удаленной от нее вершины называется эксцентриситетом вершины a и обозначается через ecc(a). Таким образом, ecc(a)=max d(a,x). Вершину с наименьшим эксцентриситетом называют центральной, а вершину с наибольшим эксцентриситетом - периферийной. Множество всех центральных вершин называется центром графа. Сама величина наименьшего эксцентриситета называется радиусом графа и обозначается rad(G), а величина наибольшего - диаметром и обозначается diam(G). Наименьший диаметр имеет полный граф (граф, все вершины которого попарно смежны) - его диаметр равен 1 [9].

Для ориентированного графа можно определить два типа маршрутов:

1) неориентированный маршрут - это чередующаяся последовательность x ₁, e₁, x₂, e₂… e_k-1, x_k вершин и ребер графа, такая, что для каждого i=1, 2… k?1 выполняется одно из двух: e_i=(x_i, x_i+1) или e_i=(x_i+1, x_i);

2) маршрут называется ориентированным (или ормаршрутом), если e_i=(x_i, x_i+1) для каждого i.

Таким образом, при движении вдоль неориентированного маршрута в орграфе ребра могут проходиться как в направлении ориентации, так и в обратном направлении, а при движении вдоль ормаршрута (или просто маршрута) - только в направлении ориентации. Это различие очевидным образом распространяется на пути и циклы, так что в орграфе можно рассматривать пути и орпути, циклы и орциклы. Определимся, что маршрут соединяет вершины x_i и x_k, а ормаршрут ведет из x _i в x_k. При решении задачи нахождения оптимального маршрута на графе можно выделить ряд известных и хорошо зарекомендовавших себя методов.

Поиск в глубину. Работа всякого алгоритма обхода состоит в последовательном посещении вершин и исследовании ребер. Какие именно действия выполняются при посещении вершины и исследовании ребра - зависит от конкретной задачи, для решения которой производится обход. В любом случае, факт посещения вершины запоминается, так что с момента посещения и до конца работы алгоритма она считается посещенной. Вершину, которая еще не посещена, будем называть новой. В результате посещения вершина становится открытой и остается такой, пока не будут исследованы все инцидентные ей ребра. После этого она превращается в закрытую [9].

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

Поиск в глубину - это наиболее важная ввиду многочисленности приложений стратегия обхода графа. Идея этого метода - идти вперед в неисследованную область, пока это возможно, если же вокруг все исследовано, отступить на шаг назад и искать новые возможности для продвижения вперед. Метод поиска в глубину известен под разными названиями: "бэктрекинг", "поиск с возвращением" [9].

Обход начинается с посещения заданной стартовой вершины a, которая становится активной и единственной открытой вершиной. Затем выбирается инцидентное вершине a ребро (a, y) и посещается вершина y. Она становится открытой и активной. В дальнейшем, как и при поиске в ширину, каждый очередной шаг начинается с выбора активной вершины из множества открытых вершин. Если все ребра, инцидентные активной вершине x, уже исследованы, она превращается в закрытую. В противном случае выбирается одно из неисследованных ребер (x, y), это ребро исследуется. Если вершина y новая, то она посещается и превращается в открытую.

При поиске в глубину в качестве активной выбирается та из открытых вершин, которая была посещена последней. Для реализации такого правила выбора наиболее удобной структурой хранения множества открытых вершин является стек: открываемые вершины складываются в стек в том порядке, в каком они открываются, а в качестве актив-ной выбирается последняя вершина [9].

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

Итак, рассмотрим метод поиска в ширину. Отметим, что в рассмотренном в предыдущем разделе методе поиска в глубину чем позднее будет посещена вершина, тем раньше она будет использована - точнее, так будет при допущении, что вторая вершина посещается перед использованием первой. Это прямое следствие того факта, что просмотренные, но еще не использованные вершины скапливаются в стеке. Поиск в ширину, грубо говоря, основывается на замене стека очередью [11].

Идея поиска в ширину состоит в том, чтобы посещать вершины в порядке их удаленности от некоторой заранее выбранной или указанной стартовой вершины a. Иначе говоря, сначала посещается сама вершина a, затем все вершины, смежные с a, то есть находящиеся от нее на расстоянии 1, затем вершины, находящиеся от a на расстоянии 2, и далее по удаленности [9].

Рассмотрим алгоритм поиска в ширину с заданной стартовой вершиной a. Вначале все вершины помечаются как новые. Первой посещается вершина a, она становится единственной открытой вершиной. В дальнейшем каждый очередной шаг начинается с выбора некоторой открытой вершины x. Эта вершина становится активной. Далее исследуются ребра, инцидентные активной вершине. Если такое ребро соединяет вершину x с новой вершиной y, то вершина y посещается и превращается в открытую. Когда все ребра, инцидентные активной вершине, исследованы, она перестает быть активной и становится закрытой. После этого выбирается новая активная вершина, и описанные действия повторяются. Процесс заканчивается, когда множество открытых вершин становится пустым.

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

Оба метода поиска в графе - в глубину и в ширину могут быть использованы для нахождения пути между фиксированными вершинами a и b. Достаточно начать поиск в графе с вершины a и вести его до момента посещения вершины b. Преимуществом поиска в глубину является тот факт, что в момент посещения вершины b стек содержит последовательность вершин, определяющую путь из a в b. Это становится очевидным, если отметить, что каждая вершина, помещаемая в стек, является смежной с предыдущей. Однако недостатком поиска в глубину является то, что полученный таким образом путь в общем случае не будет кратчайшим путем из a в b. От этого недостатка свободен метод нахождения пути, основанный на поиске в ширину [11].

Кратчайшие пути. В этом и 3 последующих разделах будем рассматривать ориентированные графы G=(V,E), дугам которых приписаны веса. Это значит, что каждой дуге (u,v) поставлено в соответствие некоторое вещественное число a(u,v), называемое весом данной дуги. Пола-гаем a(u,v)=?, если дуга (u,v) не существует.

Под длиной пути будем понимать сумму весов дуг, из которых состоит путь. Длину кратчайшего пути будем обозначать d(s,t) и называть расстоянием от s до t. Если не существует ни одного пути из s в t, то полагаем d(s,t)=?.

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

Зная расстояние между парой вершин, можно легко определить кратчайший путь. Так как для двух произвольных вершин s и t (s?t) существует такая вершина v, что d(s,t)=d(s,v)+d(v,t). Этим свойством обладает и предпоследняя вершина в кратчайшем пути от s к t. Следовательно, определяя таким образом предпоследнюю вершину, можно пройти от конца кратчайшего пути к его началу [11].

Большинство известных алгоритмов нахождения расстояния между двумя вершинами s и t можно описать следующей последовательностью действий.

1) При заданной матрице весов дуг A [u,v], вычисляем некоторые верхние ограничения D [v]на расстояния от s до всех вершин v.

2) Каждый раз, когда выясняется, что D [u]+A [u,v]<D [v], улучшаем оценку:

D [v]=D [u]+A [u,v].

3) Процесс заканчивается, когда дальнейшее улучшение ни одного из ограничений невозможно. Значение каждой D [u]получается равным расстоянию d(s,u). Вершину s в данном случае называют источником.

Алгоритм нахождения расстояния от источника до всех вершин, реализующий вышеизложенные действия в общем случае (при отсутствии контуров с отрицательной дли-нй) называется методом Форда-Беллмана [13].

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

Работу алгоритма Дейкстры можно описать следующей последовательностью действий:

1) начинаем поиск путем помещения источника в просмотренную зону;

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