Глава 10. ГАМИЛЬТОНОВЫ ЦИКЛЫ, ЦЕПИ И ЗАДАЧА КОММИВОЯЖЕРА

1. Введение

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

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

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

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

В этой главе рассматриваются следующие две задачи.

Задача i. Дан ориентированный граф требуется найти в гамильтонов цикл (или все циклы), если существует хотя бы один такой цикл.

Задача ii. Дан полный орграф дугам которого приписаны произвольные веса найти такой гамильтонов цикл (цепь), который имеет наименьший общий вес. Задача нахождения гамильтонова цикла с наименьшим весом хорошо известна в литературе как задача коммивояжера [1, 2, 15]. Следует отметить, что если орграф не полный, то его можно рассматривать как полный орграф, приписывая отсутствующим дугам бесконечный вес.

Алгоритмы решения задачи коммивояжера и ее вариантов имеют большое число практических приложений в различных областях человеческой деятельности. Рассмотрим, например, задачу, в которой грузовик выезжает с центральной базы для доставки товаров данному числу потребителей и возвращается назад на базу. Стоимость перевозки пропорциональна пройденному грузовиком расстоянию, и при заданной матрице расстояний между потребителями маршрут с наименьшими транспортными затратами получается как решение соответствующей задачи коммивояжера. Аналогичные типы задач возникают при сборе почтовых отправлений из почтовых ящиков, составлении графика движения школьных автобусов по заданным остановкам и т. д. Задача очень легко обобщается и на тот случай, когда доставкой (сбором) занимаются несколько грузовиков, хотя эту задачу можно также переформулировать как задачу коммивояжера большей размерности [9]. Другие приложения включают составление расписания выполнения операций на машинах [5], проектирование электрических сетей управление автоматическими линиями [17] и т. д.

Вполне очевидно, что сформулированная выше задача (i) является частным случаем задачи (ii). В самом деле, приписывая случайным образом дугам заданного орграфа конечные веса, получаем задачу коммивояжера. Если решение для этой задачи, т. е. кратчайший гамильтонов цикл, имеет конечное значение, то это решение является гамильтоновым циклом орграфа G (т. е.

ответом на задачу i). Если же решение имеет бесконечное значение, то не имеет гамильтонова цикла. С другой стороны можно дать еще одну интерпретацию задачи i). Рассмотрим снова полный орграф с общей матрицей весов дуг и рассмотрим задачу нахождения такого гамильтонова цикла, в котором самая длинная дуга минимальна. Эту задачу можно назвать минимаксной задачей коммивояжера, оттеняя ее «минимаксную природу» (по сравнению с классической задачей коммивояжера), которую в той же терминологии можно было бы назвать минисуммной задачей. Покажем теперь, что задача (i) действительно эквивалентна минимаксной задаче коммивояжера.

В вышеупомянутом полном орграфе мы можем наверняка найти гамильтонов цикл. Пусть это будет цикл и пусть вес самой длинной его дуги равен Удалив из любую дугу, вес которой не меньше получим орграф Найдем в орграфе гамильтонов цикл и пусть вес его самой длинной дуги равен Удалим из любую дугу, вес которой не меньше и так будем продолжать до тех пор, пока не получим орграф не содержащий никакого гамильтонова цикла. Гамильтонов цикл (с весом является тогда по определению решением минимаксной задачи коммивояжера, так как из отсутствия гамильтонова цикла в следует, что в не существует никакого гамильтонова цикла, не использующего по крайней мере одну дугу с весом, большим или равным Таким образом, алгоритм нахождения гамильтонова цикла в орграфе решает также минимаксную задачу коммивояжера. Наоборот, если мы располагаем алгоритмом решения последней задачи, то гамильтонов цикл в произвольном орграфе может быть найден с помощью построения полного орграфа с тем же самым множеством вершин, что и в дугам которого, соответствующим дугам из приписаны единичные веса, а остальным дугам — бесконечные веса. Если решение минимаксной задачи коммивояжера для имеет конечный вес (на самом деле равный единице), то в графе может быть найден соответствующий гамильтонов цикл. Если же решение имеет бесконечный вес, то в графе не существует никакого гамильтонова цикла. Следовательно, две указанные задачи можно рассматривать как эквивалентные, поскольку было продемонстрировано, что алгоритм нахождения гамильтонова цикла позволяет решать минимаксную задачу коммивояжера и наоборот.

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