Файл: Васильев, В. В. Гибридные модели задач оптимизации.pdf

строения искомого пути заданной допустимой длины. Кроме того, любая ветвь, лежащая на границе зоны, т. е. ветвь, для которой выражения (1.13) имеют вид равенств, позволяет легко определить путь допустимой или заданной длины. Однако в общем случае вет­ ви пути заданной длины не обязаны принадлежать границе задан­ ной зоны. Поэтому дальнейшее построение искомого пути должно производиться одним из известных методов.

К точным при определении путей заданной или допустимой дли­ ны следует отнести метод, основанный на просчете длин всех путей, ведущих в каждый узел мультисети. Числа, соответствующие ука­ занным длинам, приписываются соответствующему узлу. При этом ветвь, оканчивающаяся в конечном узле мультисети, сумма длины которой с одним из чисел, приписанных ее начальному узлу, равна заданной длине искомого пути, принадлежит этому пути. Аналогич­ но определяется каждая следующая ветвь искомого пути с той лишь разницей, что в качестве конечного узла мультисети рассматрива­ ется начальный узел последней выделенной ветви, а сравнение осу­ ществляется с величиной, равной разности заданной длины иско­ мого пути и длины его уже известного отрезка.

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

1.4. ЗАДАЧА КОММИВОЯЖЕРА

Известно, что многие практические задачи сводятся к решению задачи коммивояжера, отличающейся простотой поста­ новки и исключительной трудностью решения.

Задача формулируется следующим образом: имеем п городов, соединенных сетью дорог. Задана п X п матрица D = ||^/|| рас­ стояний между этими городами (г, / £ N, где N = 1, 2, ..., п), при­ чем d'ij — 0 при і — /. Требуется: выйдя из некоторого фиксирован­ ного города и побывав во всех остальных лишь по одному разу, вер­ нуться в исходный город, пройдя при этом минимальное расстояние. Задача коммивояжера, таким образом, состоит в нахождении цик­ лической матрицы перестановок X = || хц || так, чтобы величина

DX = 2 Лих»

t.i£N

была минимальной. Точнее, задача состоит в отыскании минимизи­ рующей перестановки из всех (п — 1)! возможных случаев. Она привлекает внимание простотой постановки и трудностью решения, которое имеет строго вычислительный характер, так как существо­ вание решения очевидно. Исследованием этой задачи занимаются

13

очень давно. Еще в 1948 г. Купманс [188] обратил внимание на ее связь с задачей распределения. Робинсон [199] установила приро­ ду родства ее с задачей о назначении. С тех пор было предложено много методов решения. Одни из них представляли чисто теорети­ ческий интерес или были неэффективными, другие давали не обя­ зательно оптимальное решение, а некоторые требовали принятия интуитивных решений, что затрудняло программирование для ма­ шин. Анализ ряда известных работ позволяет выделить три раз­ личных пути получения решения задачи.

1.Подциклическое улучшение, т. е. нахождение лучшего цикла, соседнего с выбранными. Такой путь — приближенный. Хорошие результаты получены Рейтером и Шерманом [198].

2.Ликвидация подциклов. Этот путь предполагает решение за­ дачи о назначениях. Если ее решением является цикл, то он опти­ мальный для задачи коммивояжера, если это решение не является циклом, тогда используется итерационная схема ликвидации подцик­ лов. Точные методы ликвидации подциклов — это методы цело­ численного программирования [186], метод ветвей и границ Ист­ мана [187], метод Шапиро [201], метод Гилморе—Гомори [190].

3.Построение циклагцключаются узлы в произвольно взятую последовательность иных узлов до тех пор, пока не образуется цикл. Наиболее простое при построении цикла — правило «бли­ жайшего соседа». Методы, в которых используется это правило, являются приближенными. Точным алгоритмом построения цикла есть алгоритм динамического программирования [202], метод «вет­ вей и границ» [203], алгоритм Литла и др. [208].

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

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

Существенным недостатком метода ветвей и границ является экс­ поненциальный рост времени решения с ростом размерности зада­ чи. Кроме того, при определенных условиях необходим полный пе­ ребор всех вариантов, что позволяет получить только приближенное решение. Наиболее эффективным считается метод ветвей и границ Шапиро, применяемый для несимметричных задач большого раз­ мера (вплоть до 70—100 городов), однако огромные трудности воз­ никают при решении этим методом симметричных задач.

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

14

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

Решение задачи коммивояжера может быть осуществлено мето­ дом одновременного исследования всех возможных путей, по кото­ рым может пройти коммивояжер. Этот метод предусматривает раз­ биение исходного города на начальный и конечный (рис. 3). Суть метода легко представить, рассмотрев такой наглядный пример.

ab

Рис. 3

Пусть из начального города ко всем другим городам выходят коммивояжеры. Когда коммивояжер приходит в город і, он разре­ шает выйти из этого города коммивояжерам ко всем другим городам, за исключением конечного города. Эти коммивояжеры имеют жето­ ны, которые указывают, что они посетили і-й город. Когда какойлибо коммивояжер, имеющий жетон посещения города, придет в город /', он разрешает выход коммивояжеров из него во все другие города. Причем, эти коммивояжеры получают жетоны, указываю­ щие, что их предшественник, выйдя из начального города, побывал в городах і и /. Если какой-нибудь коммивояжер имеет жетон с ука­ занием того, что п — 2 города пройдено, то он разрешает выход коммивояжера из (п — 1)-го города в конечный. Таким образом, первый коммивояжер, который появится в конечном городе, прой­ дет кратчайшим путем. Порядок отметок на жетоне будет соответ­ ствовать последовательности прохождения городов коммивояжером по кратчайшему пути. При этом, если все пути одинаковы то число коммивояжеров, прошедших т городов из всех п, определяется чис­ лом перестановок из п элементов по т, т. е.

Р п = п ( п — 1) . . . (п — т — 1).

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

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

15

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

< Ы 4 )

Итак, построение полного дерева маршрутов связано с огромными трудностями, так как уже для задачи с 9 городами оно будет со­ стоять из 149 920 ветвей, а для числа городов п > 9 построить де­ рево почти невозможно. Поэтому очень интересно исследование воз­ можностей сокращения объема памяти или уменьшения числа вет­ вей в дереве путей коммивояжера.

Если из двух вершин, лежащих на одном уровне, исходят ветви, определяющие одни и те же варианты последующего движения ком­ мивояжера, то эти вершины имеют одинаковые продолжения. При анализе полного дерева обнаруживаем, что уже на третьем и на каждом последующем уровнях есть вершины с одинаковыми продол­ жениями, которые можно объединить между собой, причем в 3-й зоне они объединяются по два, в 4-й — по три и т. д., в л-й — по я — 2. После объединения получаем новое унифицированное дере­ во маршрутов. Если в полном дереве количество ветвей, исходящих из соответствующих уровней, распределяется по зонам следующим образом:

I — я — 1,

II— (я — 1) (л — 2),

III — (л — 1) (л — 2) (л — 3),

IV — (л — 1) (л — 2) (л — 3) (л — 4),

л — (л — 1) 1

то в унифицированном дереве с 4-го уровня будет исходить коли­ чество ветвей в 2 раза меньшее, чем в полном дереве, так как в 3-й зоне произошло объединение по 2, с 5-го — в 2 • 3 = 3! (после объединения в 3-й и 4-й зонах), с 6-го — в.41 и т. д., с л-го уровня в (л — 2)! раз меньше, т. е. количество ветвей в унифицированном дереве распределится в зонах соответствующих уровней следующим образом: * '

I— л — 1

II — (л — 1) (л — 2),

III— (л — 1) (я — 2) (л — 3)г

Таблица 1

Тогда общее выражение для количества ветвей унифицирован­ ного дерева примет вид

18

Выражением (1.19) оценивается объем памяти, необходимый для решения задачи с п городами.

Интересным в исследовании унифицированного дерева является вопрос о количестве одноименных ветвей в каждой зоне уровня. Из выражения (1.15) видно, что повторение одноименных ветвей начинается в зоне третьего и продолжается до (п — 2)-го уровня. Число повторений определяется как частное от суммы ветвей в каж­ дой зоне и количества повторяющихся (гг — 1) (п — 2) ветвей. Сум­ ма ветвей в зоне определяется на основании выражения (1.16): над каждым слогаемым Sy поставлена цифра, означающая принадлеж­

Mâ выражения (1.20) следует, что в унифицированном дереве ветви повторяются в зонах 3-го, 4-го, ..., (п — 2)-го уровней.

Повторение ветвей в зонах наглядно представлено на треуголь­ нике повторений, построенном на основании (1.20) для задач от 5 до 13 городов (табл. 1).

семи — три и т. д., т. е. основание треугольника определяет коли­ чество зон, в которых повторяются одноименные ветви, причем ес­ ли число этих зон в дереве нечетное, то существует одна зона, если четное, то две с максимальным числом повторений. Вследствие симметрии число повторений достаточно вычислять только для од­

соответственно 2, 3, 4 и т. д., а в остальных зонах определяется по принципу треугольника: сумма двух рядом стоящих чисел есть