Алгоритм решения (алгоритм Литтла)

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

Алгоритм работает следующим образом. Вначале определяется некоторое допустимое решение, после чего множество всех оставшихся маршрутов (остовных контуров) разбивается на все более мелкие подмножества. На каждом шаге разбиения легко вычисляется нижняя граница длины текущего наилучшего маршрута. С помощью найденных границ производится дальнейшее разбиение подмножеств допустимых маршрутов и в конечном итоге определяется оптимальный маршрут. Если находится маршрут, длина которого не превосходит наименьшей нижней границы всех других маршрутов, то данное промежуточное решение становится “наилучшим” допустимым решением. Основными процедурами предлагаемого алгоритма являются вычисление нижних границ длин маршрутов, выделение субоптимальных решений и ветвление с целью получения новых (более коротких) маршрутов. Подмножества множества всех маршрутов можно рассматривать как узлы дерева, а процесс разбиения - как ветвление дерева. Поэтому данный метод называется методом поиска по дереву решений (или алгоритмом ветвей и границ). Для работы алгоритма требуется матрица обобщенных стоимостей (длин дуг) рассматриваемой сети.

Алгоритм Литтла состоит из следующих блоков:

1. Редуцирование ацикличных и однонаправленныхучастков сети G (обязательный блок).

2. Вычисление верхней границы длин маршрутов (необязательный блок).

3. Итеративная процедура построения дерева маршрутов:

3.1. Редукция матрицы длин дуг по строкам и столбцам.

3.2. Вычисление нижней границы длины маршрута.

3.3. Вычисление штрафов.

3.4. Ветвление дерева маршрутов.

3.5. Анализ дерева маршрутов на возврат, подциклы и полный маршрут.

3.6. Получение новой матрицы длин дуг с учетом 3.4 и 3.5.

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

Длина L (T) маршрута T равна сумме элементов матрицы длин дуг, входящих в маршрут T. Для любого допустимого маршрута каждая строка и каждый столбец матрицы C содержат ровно по одному элементу, соответствующему этому маршруту. Величина L (T) определена для любого допустимого маршрута и длина оптимального маршрута не может превосходить значение L (T) для такого T. Следовательно, значение L (T) всякого допустимого маршрута является верхней границей длины оптимального маршрута.

Если из каждого элемента некоторой строки матрицы расстояний вычесть постоянную величину C, то длина любого маршрута, определяемая новой матрицей, меньше длины того же маршрута, определяемой старой матрицей, на величину С (верно, так как каждому маршруту соответствует ровно один элемент данной строки). Однако относительные длины всех маршрутов останутся неизменными. Таким образом, при переходе от исходной матрицы расстояний к новой останутся неизменными и все оптимальные маршруты. Такое же утверждение справедливо и для элементов столбцов матрицы расстояний. Процедуры вычитания из каждого элемента строки наименьшего элемента этой же строки и из каждого элемента столбца наименьшего элемента этого же столбца называются редукцией строк и редукцией столбцов, соответственно. Матрица с неотрицательными элементами, в каждой строке и каждом столбце которой содержится по крайней мере один нулевой элемент, называется редуцированной матрицей. Она может быть получена в результате последовательной редукции ее строк и столбцов.

Если L (T) - длина маршрута T, определяемая матрицей расстояний до выполнения редукции, L ’ (T) - длина того же маршрута, определяемая редуцированной матрицей, а H - сумма всех констант, используемых при вычислении редуцированной матрицы, то L (T) = H + L ’ (T). Поскольку редуцированная матрица содержит только неотрицательные элементы, то H является нижней границей длины маршрута T для нередуцированной матрицы расстояний.

Штрафом Ф _ij за неиспользование в полном маршруте дуги [ i, j ], для которой на данной итерации в редуцированной матрице c_ij = 0, называют увеличение стоимости полного маршрута при невключении в него этой дуги. Для вычисления штрафов используется следующее выражение:

Ф _ij = { c_kj } + { c_ik }.

Ветвление - процесс разбиения множества всех маршрутов на непересекающиеся подмножества. Может быть представлен в виде построения дерева, корень которого имеет пометку <все маршруты>, а остальные узлы могут быть двух видов: а) с пометкой о включении в рассматриваемые маршруты дуги [ i, j ] и б) с пометкой о невключении в рассматриваемые маршруты этой дуги. У каждого узла дерева должна быть проставлена величина нижней границы подмножества тех маршрутов, которое выделено цепью от корня дерева до данного узла. Из каждого узла типа а) выходит две дуги - в узлы типа а) и б) (кроме узлов предпоследнего (одна дуга) и последнего (нет дуг) уровней, причем уровнем узла считается количество разделяющих его и корень в цепи узлов; всего уровней N ₁). Из каждого узла типа б) дуг не выходит. В полном дереве маршрутов самая длинная цепь, выходящая из корня, состоит из всех узлов, входящих в минимальный остовный контур, причем величина нижней границы у последнего узла этой цепи равна стоимости оптимального маршрута. На каждом уровне в дерево маршрутов включается та дуга [ i, j ], для которой величина штрафа максимальна. При этом после анализа на возврат и подциклы при получении матрицы следующей итерации из нее удаляются i -я строка и j -й столбец. При получении матрицы 2 х 2, в которой обязательно должны содержаться два бесконечных и два конечных элемента, расположенных по диагоналям (иначе в процессе вычислений была допущена ошибка, итерации заканчиваются в случае невозникновения возврата, так как в такой матрице обязательно должны быть выбраны обе дуги, соответствующие конечным элементам.

Если в процессе построения дерева маршрутов величина нижних границ узлов типа а) и б) превысила на данном уровне величину нижней границы какого-либо узла типа б) для дуги [ i, j ] на предыдущих уровнях, производится процедура возврата к этому узлу, и все вычисления повторяются с момента, предшествующего выбору этой дуги, причем величина c_ij временно полагается равной . Величина нижней границы для узла типа б) есть сумма нижней границы предыдущей итерации и штрафа за невыбор выбранной на этой итерации дуги. Величина нижней границы для узла типа а) есть сумма нижней границы предыдущей итерации и всех констант, которые вычитались из строк и столбцов матрицы в процедуре редукции на данной итерации.

Процедура анализа на подциклы состоит в том, чтобы после каждого шага процедуры ветвления тем дугам [ i, j ], для которых в редуцированной матрице содержатся нулевые элементы, причем таким, что их выбор может замкнуть контур до определения полного маршрута (некоторые вершины цепи не войдут в полученный маршрут), в матрице следующей итерации соответствуют элементы, равные .