7. Задача коммивояжера и задача о назначениях

В разд. 5 было отмечено, что задача о назначениях, определяемая соотношениями (10.4), (10.5) и (10.6), может иметь решения, образованные некоторым числом непересекающихся циклов, и что соответствующий метод решения задачи коммивояжера требует наложения ограничений до тех пор, пока решение не будет состоять из единственного (гамильтонова) цикла. В настоящем разделе мы исследуем процедуры наложения этих ограничений в рамках алгоритма поиска, использующего дерево решений. Применяемая схема будет в основном такой же, как и в разд. 6.2 для алгоритма поиска, основанного на рассмотрении кратчайшего остова.

7.1. Алгоритм поиска, использующий дерево решений

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

Рис. 10.15. Решение задач о назначениях, (а) Решение задачи . (б) Решение задачи

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

(А) Правило простого ветвления.

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

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

для а также для то число является нижней границей для веса решения первоначальной задачи коммив ояже

Пусть, скажем, (т. е. ). Если решение задачи является гамильтоновым циклом, то оно будет решением первоначальной задачи коммивояжера. В противном случае пусть оно будет, скажем, таким, как на рис. 10.15 (б). Исключая цикл (1, 8, 2, 6, 1), мы снова составляем и решаем подзадачи показанные на рис. 10.16.

Рис. 10.16. Дерево решений с простым правилом ветвления А.

Из этого рисунка видно, отвечает задаче, для которой в матрице весов элемент положен равным (в дополнение к тому, что элемент положен равным уже ранее). То же самое относится и к Нижняя граница теперь переопределяется как Допустим, что задача соответствует весу (т. е. ). Если решение задачи является гамильтоновым циклом, то оно будет решением первоначальной задачи коммивояжера. Дальнейшее ветвление в узле с другой стороны, должно осуществляться точно так же, как это делалось в и этот процесс продолжается до тех пор, пока задача с текущим значением веса не будет иметь в качестве решения гамильтонов цикл. Когда это произойдет, то полученный цикл будет окончательным решением, так как его вес (по определению числа не превосходит нижних границ весов любых других гамильтоновых циклов, которые могут появиться при дальнейшем ветвлении в оставшихся узлах дерева.

Из приведенного описания алгоритма становится очевидным, что примененный поиск с помощью дерева решений относится к типу с «приоритетом по ширине», как это объяснено в приложении 1.

(Б) Правило исключающего ветвления.

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

Ранее описанное правило ветвления основывалось на том факте, что цикл, такой, как может быть удален посредством исключения одной из его дуг. Это, однако, не приводит в процессе ветвления к взаимно исключающим подзадачам. Так, в вышеприведенном примере решение задачи соответствующее циклам (1, 3, 6, 1) и (2, 5, 4, 7, 8, 2), является допустимым решением как подзадачи так и

Другим правилом ветвления, удаляющим цикл и приводящим к взаимно исключающим подзадачам, является следующее:

где достаточно большое отрицательное число, гарантирующее, что дуга, вес которой равен входит в оптимальное решение.

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

Рис. 10.17. Дерево решений с исключающим правилом ветвления Б.

Рис. 10.18. Дерево решений с улучшенным правилом ветвления В.

В приведенном примере первоначальная задача разбивалась бы на три подзадачи, показанные на рис. 10.17 (ср. с разбиением на первом уровне из рис. 10.16, полученным по предыдущему правилу ветвления).

(В) Лучшее правило ветвления.

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

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

В примере, данном выше, начальная задача была бы в соответствии с настоящим правилом ветвления подразделена на три подзадачи, определенные, как показано на рис. 10.18. Дальнейшие ветвления происходят аналогично.