7.3. Вычислительные комментарии и характеристики

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

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

Рабочие качества вышеописанного алгоритма поиска с исключением циклов по правилу ветвления В исследовали Беллмор и Мэлоун [2]. На любой стадии ветвление в узле продолжалось так, чтобы исключить циклы наименьшей длины в решении задачи о назначениях, соответствующей этому узлу. Задача коммивояжера с произвольной асимметричной матрицей весов может быть решена на ИБМ 7094 II за секунд, где

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

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

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