Структурное программирование сверху-вниз: дополнительные соображения 3 страница

По определению ветвления путь (3,5) содержится в каждом туре множества {3,5}, следовательно путь (5,3) в нем не может содержаться, исходя из условий задачи (поездка осуществляется по одному пути только один раз) и, поэтому, значение (5,3) в матрице стоимостей равно бесконечности. Строку 3 и столбец 5 также можно исключить из дальнейшего рассмотрения потому что путь (3,5) уже существует. (строка 3 предполагает выезд из 3, а столбец 5 приезд в 5). Таким образом матрица приведенная на рис. 5.9. может быть нарисована в виде, изображенном на рис. 5.10. На рис.5.10а показана матрица после вычеркивания из нее строки 3 и столбца 5 и соблюдения условия, что стоимость (5,3) равна бесконечности, а на рис.5.10б показана уже приведенная матрица.

Нижняя граница для множества {3,5} равна сумме Н для предыдущего значения 47 и полученного 15, т.е. нижняя граница равна 62.

Нижняя граница множества {3,5} получается несколько иным способом. Путь (3,5) не может находится в этом множестве, поэтому полагаем его равным бесконечности (для матрицы расположенной на рис.5.9). Но в любой вариант решения задачи будет входить путь из 3 в какой либо другой город и путь входящий в город 5 из какого либо другого города. Выбираем минимальные значения стоимостей для этих путей. Самое меньшее из города 3 равно 2 (полагая (3,5) бесконечности), а самое меньшее входящее в 5 равно 0. Следовательно нижняя граница равна 47+2=49.

Значения 62 и 49 указаны на рис. 5.8. Естественно, что теперь необходимо рассматривать множество {3,5}.

В основных чертах блок-схема этого алгоритма ветвей и границ показана на рис.5.11.

Рис. 5.11 Блок-схема алгоритма ветвей и границ.

Здесь используются следующие обозначения. Буква Х обо­значает текущую вершину на дереве поиска, a w (X) — соответствующую нижнюю границу. Вершины, следующие непосредственно за X, назовем Y и Y, они выбираются ветвлением по некоторому ребру (k, l). Символ Zo обозначает стоимость самого дешевого варианта, извест­ного на данный момент. В начальный момент Zo =oo.

Теперь раскроем более детально содержание некоторых блоков этой схемы.

Блок 1. Установление начальных значений переменных, или ини­циализация.

Блок 2. Первое приведение — это непосредственная реализация описанной ранее процедуры.

Блок 3. Выбор следующего ребра ветвления (k, 1) определяет множества Y и Y, непосредственно следующие за текущим X. Ребро (k, 1) нужно выбирать так, чтобы попытаться получить большую по величине нижнюю границу на множестве Y={k, 1), что облегчит проведение оценки для множества Y. Обычно предпочтительнее про­вести оценку для Y, так как размер этого множества и соответству­ющая ему матрица стоимостей обычно больше, чем у Y (из матрицы для Y вычеркнуты строка k и столбец l). Можно надеяться также, что Y с большей вероятностью содержит оптимальный вариант.

Как применить эти идеи к выбору конкретного ребра ветвления (k, l). В приведенной матрице стоимостей С, связанной с X, каждая строка и столбец имеют хотя бы по одному нулевому элементу (если нет, то С не полностью приведена). Можно предположить, что ребра, соответствующие этим нулевым стоимостям, будут с большей веро­ятностью входить в оптимальный вариант, чем ребра с большими стои­мостями. Поэтому мы выберем одно из них. Но какое? Пусть ребро (i,j) имеет Cij=0 в С. Мы хотим, чтобы у Y = {i, j) была как можно большая нижняя граница. Вспоминая метод вычисления нижней границы для {3, 5} в нашем примере, мы видим, что для Y эта граница задается в виде

W(Y)=w(X)+ (наименьшая стоимость в строке i, не включая Cij)+(наименьшая стоимость в столбце j, не включая Сij).

Следовательно, из всех ребер (i, j) с Cij=0 в текущей матрице С мы выбираем то, которое дает наибольшее значение для W(Y).

Учитывая, что данный метод довольно трудный для понимания ниже приводится решение транспортной задачи с указанными выше данными.

Дата добавления: 2014-12-16