Определим основные положения алгоритма Литтла (АЛ) построения его как метода ветвей и границ. 1) Способ расширения ОДР.

Для расширения исходной области ограничений
X опускается ограничение замкнутости маршрута. В результате получим область ограничения в задаче о назначении. В качестве матрицы затрат применяется матрица рассмотренной задачи о КВ, приведенная по строкам и столбцам
C(0)C'' . 2) Правила ветвления.

Принцип деления для каждого из подмножеств
Xr( k) ,
r 0,
rk следующий: фиксируется дуга (
i0,
j0) наименьшей длины. По этой дуге исходное множество ГК разбивается на 2 подмножества: 1)
Xi(0kj0) , составленное из ГК, содержащих дугу (
i0,
j0) ; 2)
Xi(0kj0) , составленное из ГК, не содержащих дугу (
i0,
j0) . Требование включения или не включения
i0,
j0 в подмножество ГК реализуется путем соответствующих преобразований матрица, рассмотренной для подмножеств
Xr( k),
r 0,
rk .
3) Правила вычисления границ (оценок)
Оценкой снизу на X (0) является константа приведения исходной матрицы расширений C .
Действительно, не сложно показать, что длина пути на C равна длине пути на C" (матрица, приведенная по строкам и столбцам) с константой приведения.

Поэтому, отбрасывая длину пути на
C" получаем нижнюю границу длин ГК на
X (0) m(
X 0 ) . В качестве оценки снизу подмножества
Xr берется сумма оценки исходной для
Xrk множества – пусть это
Xrk 1 и константа приведения матрицы расширений, соответствующей подмножеству
Xrk m Xrk и трансформированной с учетом требования замкнутости мар
шрута: m Xrk m Xrk 1 mrk ,
r 1,
rk .
Для контроля некоторого состояния маршрута дополнительно вводятся множества Pr k , Pr k , r 1, rk соответственно множество дуг входящих и не входящих в маршрут по ветви r шага k .
Учитывая факт, что АЛ использует специальный математический аппарат, приведем для него детальное описание схемы ветвей и границ с интерпретацией действий в терминах теории графов.
1.3.4 Схема алгоритма Литтла
1) Итерация K 0

А: на
X 0 по исходной матрице расстояний ищется нижняя граница всех ГК как константа приведения
n n 
матрицы
C:
m 0 min
C ij min
C'
ij или
m v , где
C' -матрица, приведенная
i 1 j j 1 i
по строкам.

Б: Прежде чем перейти к шагу
K 1 по
C" определяется дуга разбиения 1-го наша
i0,
j0 1 .

При выборе
i0 ,
j0 1 логика размышлений такова: нужно стремиться к тому, чтобы множество ГК, включающее дугу
Xi0 1
j0 содержало оптимальный контур, а
Xi0 1
j0 не содержало. Поэтому в
Xi0
j0 нужно включать дуги матрицы
C" с нулевым расстоянием. Одновременно в
Xi01j0 должны оставаться дуги с наибольшим расстоянием.

Последнее требование формализуется следующим образом: по определению,
Xi01j0 не содержит дугу
i0 ,
j0 , т.е. для любого ГК путь из
i0 приводит в любую
j
j0 , а в
j0 приводит из
i i0 . При этом длина дуги пути будет не меньше, чем так называемая степень нулевого элемента:
ij io j i i0
ij0 . Здесь
R 0 - множество дуг матрицы
C , имеющих нулевое рас min
C min
C ,
i,
jj j0
стояние.

Затем, среди
ij ,
i,
j R 0 выбирается дуга
i0 ,
j0 1 так, чтобы расстояние
i0 j0 было наибольшим, т.е.
i0 ,
j0 1 argmax
ij ,
i,
j R 0 .
i,
jПолучив дугу разбиения формируем подмножество дуг, составляющих промежуточные маршруты по ветвям r 1, r 2 шага k 1 : i0 , j0 P11 , P21 , r 2
P11 i0 , j0 1 , P11 ,
P21 , P21 i0 , j0 1
2) Итерация K 1

А: разбиваем
X 0 по
i0 ,
j0 1 на 2 подмножества
Xi01j0,
Xi01j0 .

Подмножество
Xi01j0 получается из
X 0 сужением области за счет введения дополнительных условий:
-

запрещается повтор перехода из
i0 в
j0 , переходы из
i0 в
j
j0, переходы из
j0 в
i i0 , - запрещается обратный переход из
j0 в
i0 .

Чтобы это формализовать матрица
C
C" преобразуется в матрицу первого шага
Ci0 j0 следующим образом:

-

в
C строки
i0 и столбец
j0 опускаются, тем самым реализуется первая группа условий; - элемент
C (вторая группа).

Подмножество
Xi0 j0 получается из
X 0 запретом перехода
i0 ,
j0 1 , т.е.
Ci0j0 : . На каждом подмножестве вычисляется нижняя граница:
m Xi01j0 m 0 mi01j0,
m Xi01j0 m 0 i0 j0 .

Примечание. В качестве
mi0kj0 значения
i0 j0 значительно сокращается объем вычислений.
Полученная информация о ветвях, границах и множествах заносится на дерево ветвлений.

Б: по меньшему значению нижней границы находим перспективное для ветвления подмножество. По определению дуги разбиения 1-го шага, им является
Xi0 j0 , по матрице ему соответствующей приведенной по строкам и столбцам находим дугу разбиения 2-го шага
i0 ,
j0 2 .