(1,7, 8, 2, 4, 3, 6, 5) 254

8 42 58 66 76 41 52 83 оо

Следует отметить, что на этом этапе решение подзадачи F является гамильтоновым циклом с весом 254. Этот вес меньше, чем вес предыдущего лучшего решения (с весом 264), и, следовательно, лучшим текущим решением будет решение подзадачи F. Два узла {Е и D) все еще дают решения с негамильтоновыми циклами и являются поэтому кандидатами на продолжение процесса ветвления. Однако для уэла Е нижняя граница равна 280 > 254 (текущее значение наилучшего решения), и, значит, ветвление в этом узле не может привести к лучшему результату. Поэтому

(1,6, 5, 3,2,4,7,8) 274

узел D с нижней границей 250 <;254 является единственным узлом, ветвление в котором может привести к улучшению. Исключение цикла (1, 7, 8) ИЗ решения для узла D приводит к трем подзадачам, обозначенным на рис. 10.19 как G, Н тз. I. Соответствующие этим подзадачам матрицы весов и решения задач о назначениях таковы:

(i,7,6,5,3,z,4,8) 251

0,7,8,3,2,4,6,5) 266

На этом этапе мы замечаем, что решение подзадачи Н является гамильтоновым циклом с весом 251, что меньше чем предыдущее

лучшее значение 254. Поэтому решение подзадачи Я, т. е. (1, 7, €, 5, 3, 2, 4, 8), заменяет предыдущее лучшее решение. Кроме ТОГО, значение 251 меньше, чем нишняя граница в любом конечном узле дерева, и, следовательно, найдено оптимальное решение леей задачи. (Решения во всех концевых узлах - за исключением узла Е, ветвление в котором было прекращено ранее,- являются на самом деле гамильтоновыми циклами, и здесь безотносительно к границам весов этих решений не нужно бы было производить дальнейшее ветвление.)

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

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

В венгерском алгоритме (см. гл. 12) решения задачи о назначениях элемент с {xi, xj) в окончательной относительной матрице весов должен был бы иметь значение О, а соответствующий маркер показывает, что в решении было назначение. Изменение значения элемента с {Xi, Xj) привело бы, очевидно, к перераспределению этого назначения, но оставило бы без изменения другие п - 1 назначений. Таким образом, начиная с решения (назначений) эадачи - до того как были произведены модификации матрицы Icij] - и удаляя упомянутое назначение, можно получить решение новой модифицированной задачи, повторно применяя венгерский алгоритм на последнем шаге, так как единственный прорыв , т. е. единственное увеличение числа ненулевых назначений с п - 1 до п, даЛ бы в действительности оптимальное решение новой задачи о назначениях (детали см. в гл. 12).

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

Г 0,55-10-4-/гЗ.46

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