Ветвление

Процесс ветвления можно представить в виде дерева, каждая вершина которого соответствует некоторому множеству маршрутов, являющемуся подмножеством множества Х. При этом начальная вершина соответствует множеству всех маршрутов Х (см. рис. 5.1.).

Рис. 5.1. Ветвление

На каждом шаге из числа кандидатов на ветвление выбирается множество Х¹ с наименьшей оценкой. Оно разветвляется на два подмножества и . Подмножество состоит из всех маршрутов множества Х¹ содержащих некоторую выбранную на данном шаге дугу (r, s), подмножество , – из всех маршрутов множества Х¹, не содержащих дуги (r,s).

Ребро дерева, соединяющее вершины Х¹ и , помечается (r, s), а ребро дерева, соединяющее Х¹ и помечается .

Пусть – редуцированная матрица, соответствующая вершине Х¹. Опишем способ выбора дуги (r, s). Он основан на стремлении сделать оценку поменьше, а оценку – больше, для того, чтобы увеличить вероятность выбора для дальнейшего ветвления множества . Стремление к уменьшению приводит к выбору такой дуги (,), для которой

(,) = 0, (5.21)

поскольку все маршруты множества содержат дугу (,). Стремление же увеличить приводит к выбору среди дуг, удовлетворяющих условию (5.21), той дуги, для которой значение функции

максимально, т.е.:

Смысл введения функции состоит в том, что величина является оценкой снизу для длины любого маршрута из Х¹, не содержащего дуги (,), так как величина выражает дополнительное расстояние, которое коммивояжер проезжает в случае, когда в маршрут не включена дуга (,).