6.1.5. Алгоритм Литтла.
Другое название алгоритма Литтла - метод «ветвей и границ». Так же как и в целочисленном программировании, при использовании алгоритма Литтла необходимо определить верхнюю и нижнюю оценки для разделения множества решений на два класса. Различают две группы задач, решаемых этим алгоритмом: задачи на минимум (определяют нижнюю оценку или границу) и задачи на максимум (определяют верхнюю границу или оценку) [12, 13].
Идея алгоритма такова: определяют нижнюю оценку (для задачи на минимум) и разделяют исходную матрицу на две примерно равные части. Затем уменьшают размер матрицы и определяют «плату» за уменьшение размера матрицы. Размер платы может быть или положительный или нулевой, т.е. увеличивать или не изменять размера нижней оценки. Размер матрицы уменьшается до 2 х 2. Затем выполняют движение в обратном порядке и получают оптимальный (по стоимости) маршрут.
Рассмотрим работу алгоритма Литтла на примере.
Пример 5. Выполним «зануление» матрицы так, как это было в дельта-методе при решении транспортной задачи.
|
Город |
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
|
6 |
4 |
12 |
14 |
22 |
|
2 |
6 |
|
3 |
8 |
7 |
20 |
|
3 |
4 |
3 |
|
10 |
11 |
18 |
|
4 |
12 |
8 |
10 |
|
9 |
16 |
|
5 |
14 |
7 |
11 |
9 |
|
10 |
|
6 |
22 |
20 |
18 |
16 |
10 |
|
1) Зануление по строкам
|
Город |
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
|
2 |
0 |
8 |
10 |
18 |
|
2 |
3 |
|
0 |
5 |
4 |
17 |
|
3 |
1 |
0 |
|
7 |
8 |
15 |
|
4 |
4 |
0 |
2 |
|
1 |
8 |
|
5 |
7 |
0 |
4 |
2 |
|
3 |
|
6 |
12 |
10 |
8 |
6 |
0 |
|
2) Зануление по столбцам
|
Город |
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
|
2 |
0 |
6 |
10 |
15 |
|
2 |
2 |
|
0 |
3 |
4 |
14 |
|
3 |
0 |
0 |
|
5 |
8 |
12 |
|
4 |
3 |
0 |
2 |
|
1 |
5 |
|
5 |
6 |
0 |
4 |
0 |
|
0 |
|
6 |
11 |
10 |
8 |
4 |
0 |
|
После «зануления» матрицы ее элементы должны содержать или положительные, или нулевые значения. Сумма вычтенных значений со строкам равна 35 (4 +- 3 + 3 + 8 + 7 + 10), по столбцам — 6 (1 +0 + 0 + 2 + 0 + 3). Общая сумма всех вычитаний — 41. Это и есть нижняя оценка.
Из условия задачи ясно, что надо побывать в каждом городе один раз. То есть замкнутый маршрут (цикл) должен содержать уникальные номера городов и переходы из одного города в другой должны выполняться по одному разу в каждой строке и в каждом столбце. Также надо помнить, что стоимость маршрута не может быть меньше нижней оценки (общей суммы выполненных вычитаний).
Далее для каждой клетки матрицы, содержащей ноль, надо вычислить частную оценку клетки или просто оценку клетки.
Оценка клетки определяется как сумма минимальных элементов соответствующей строки и столбца.
Клетка 1-3 содержит значение ноль. Оценка этой клетки будет равна сумме минимального элемента по первой строке и минимального элемента но третьему столбцу 2 + 0 = 2. Для клетки 2-3 оценка составит 2 + 0 = 2. Для клетки 3-2 оценка будет 0 + 0 = 0. Оценки клеток представлены в виде верхнего индекса на рисунке.
Оценки клеток:
|
№ |
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
|
2 |
02 |
6 |
10 |
15 |
|
2 |
2 |
|
02 |
3 |
4 |
14 |
|
3 |
02 |
00 |
|
5 |
8 |
12 |
|
4 |
3 |
01 |
2 |
|
1 |
5 |
|
5 |
6 |
00 |
4 |
03 |
|
05 |
|
б |
11 |
10 |
8 |
4 |
05 |
|
Начиная с этого момента приступаем к построению дерева ветвления алгоритма. Максимальная оценка 5 принадлежит двум клеткам 5-6 и 6-5. Поэтому за «нулевое» ребро принимается или ребро 5-6, или ребро 6-5. Возьмем ребро 5-6. Все маршруты разобьем на содержащие ребро 5-6 и не содержащие это ребро. Обе группы маршрутов (содержащие и не содержащие ребро 5-6) будут иметь стоимость не менее нижней оценки (более может быть).
Из дальнейшего рассмотрения исключаем пятую строку и шестой столбец. Этим действием снижаем размер матрицы. Ребро 5-6 помечено как запрещенное (серым цветом) для рассмотрения. К уменьшенной матрице применяем процедуру «зануления». Из последней строки вычтем 4, а из последнего столбца — 1. Заново определяем оценки нулевых клеток.
Первый шаг:
|
№ |
1 |
2 |
3 |
4 |
5 |
|
1 |
|
2 |
02 |
6 |
10 |
|
2 |
2 |
|
02 |
3 |
4 |
|
3 |
02 |
00 |
|
5 |
8 |
|
4 |
3 |
01 |
2 |
|
1 |
|
6 |
11 |
10 |
8 |
4 |
05 |
|
№ |
1 |
2 |
3 |
4 |
5 |
|
1 |
|
2 |
02 |
6 |
9 |
|
2 |
2 |
|
02 |
3 |
3 |
|
3 |
02 |
00 |
|
5 |
7 |
|
4 |
3 |
01 |
2 |
|
0 |
|
6 |
7 |
6 |
4 |
0 |
05 |
|
№ |
1 |
2 |
3 |
4 |
5 |
|
1 |
|
2 |
02 |
6 |
9 |
|
2 |
2 |
|
02 |
3 |
3 |
|
3 |
02 |
00 |
|
5 |
7 |
|
4 |
3 |
00 |
2 |
|
03 |
|
6 |
7 |
6 |
4 |
07 |
05 |
Клетка 6-4 имеет наибольшую оценку 7. За «нулевое» ребро возьмем 6-4. Далее процедура снижения размера матрицы повторяется. Результат преобразований показан на рисунке.
Второй шаг:
|
№ |
1 |
2 |
3 |
5 |
|
1 |
|
2 |
02 |
9 |
|
2 |
2 |
|
02 |
3 |
|
3 |
02 |
00 |
|
7 |
|
4 |
3 |
00 |
2 |
03 |
|
№ |
1 |
2 |
3 |
5 |
|
1 |
|
2 |
02 |
6 |
|
2 |
2 |
|
02 |
0 |
|
3 |
02 |
00 |
|
4 |
|
4 |
3 |
00 |
2 |
03 |
|
№ |
1 |
2 |
3 |
5 |
|
1 |
|
2 |
02 |
6 |
|
2 |
2 |
|
02 |
04 |
|
3 |
02 |
00 |
|
4 |
|
4 |
3 |
00 |
2 |
03 |
Третий шаг:
|
№ |
1 |
2 |
3 |
|
1 |
|
2 |
02 |
|
3 |
02 |
00 |
|
|
4 |
3 |
00 |
2 |
|
№ |
1 |
2 |
3 |
|
1 |
|
2 |
02 |
|
4 |
3 |
02 |
2 |
|
3 |
02 |
00 |
|
|
№ |
1 |
2 |
3 |
|
1 |
|
2 |
02 |
|
4 |
1 |
02 |
0 |
|
3 |
02 |
00 |
|
|
№ |
1 |
2 |
3 |
|
1 |
|
2 |
02 |
|
4 |
1 |
02 |
01 |
|
3 |
01 |
02 |
|
Четвертый шаг:
|
№ |
1 |
3 |
|
1 |
|
02 |
|
4 |
1 |
01 |
|
№ |
1 |
3 |
|
1 |
|
02 |
|
4 |
0 |
01 |
Проанализируем выполненные преобразования и построим дерево алгоритма. В результате расчета «зануления» исходной матрицы была получена нижняя оценка — 41. Таким образом, стоимость любого допустимого маршрута будет не менее 41. После вычисления оценок нулевых клеток, была выбрана клетка 5-6 с максимальной оценкой 5. Соответственно, ребро, соединяющее города 5 и 6, было объявлено «нулевым», и все возможные маршруты были разделены на две группы: содержащие ребро 5-6 и не содержащие этого ребра. Новая нижняя оценка для маршрутов, не содержащих ребра 5-6, должна быть увеличена на оценку клетки 5-6 и составит 41 + 5 = 46.
На первом шаге (см. рисунок) нулевое ребро было помечено серым цветом и изъято из дальнейшего рассмотрения. Далее рассматривалась только левая ветвь (рисунок) дерева ветвления алгоритма. Общая сумма «зануления» (по строкам и столбцам) равна 5. Нижняя оценка для левой группы маршрутов (включающих ребро 5-6) составит 41 + 5 = 46.
На втором шаге была выбрана клетка 6-4 с оценкой 7. Новая нижняя оценка для маршрутов группы, не содержащей ребро 4-5, будет 53 и ветвление будет выполнено но ребру 6-4. Общая сумма «зануления» (по строкам и столбцам) составит 3. Нижняя оценка для левой группы маршрутов (содержащих ребро 4-5) будет 46 + 3 = 49.
На третьем шаге будет удалено ребро 2-5. Оценка клетки 2-5 составляет 4. Следовательно, нижняя оценка правой группы маршрутов будет 49 + 4 = 53. Общая сумма «зануления» — 2. Нижняя оценка левой группы маршрутов равна 49 + 2 = 51.
На четвертом шаге выбрана клетка 3-2 с оценкой 2. Нижняя оценка правой группы маршрутов равна 51 + 2 = 53. Общая сумма «зануления» — 1. Нижняя оценка левой группы маршрутов равна 51 + 1 = 52. В результате анализа было составлено дерево ветвления алгоритма.
На последнем (четвертом шаге) остались два свободных (не запрещенных) ребра 1-3 и 4-1. Оба ребра включаем в маршрут и добавляем ребра из левой ветви.
Оптимальный маршрут будет
состоять из ребер: 1 -3; 4- 1; 3 - 2; 2-5; 6-4 и
5-6. После упорядочения получим:
Ответ: длина оптимального маршрута не менее 52, порядок объезда
городов:
Из исходной матрицы подставим значения ребер и определим стоимость маршрута: 4 + 3 + 7 + 10 + 16 + 12 = 52.
Для того чтобы убедиться, действительно ли найден оптимальный маршрут, надо проанализировать «правые» группы маршрутов. Все правые группы, кроме первой, имеют нижнюю оценку более 52. Следовательно, эти группы не могут содержать лучшего решения. Остается проверить первую правую группу, нижняя оценка которой составляет 46. Маршруты этой группы не содержат ребра 5 — 6. Анализ ребра 5 — 6 выполнялся в начале работы алгоритма. Поэтому из исходной матрицы надо исключить ребро 5-6. Исключение ребра выполним следующим способом: ребрам 5-6 и 6-5 поставим значение . Так как исходная задача симметричная, то исключались два ребра 5 — 6 и 6-5. Если задача несимметричная, то исключается одно ребро, и доказательство правильности алгоритма увеличивается на один шаг.
|
Город |
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
|
6 |
4 |
12 |
14 |
22 |
|
2 |
6 |
|
3 |
8 |
7 |
20 |
|
3 |
4 |
3 |
|
10 |
11 |
18 |
|
4 |
12 |
8 |
10 |
|
9 |
16 |
|
5 |
14 |
7 |
11 |
9 |
|
10 |
|
6 |
22 |
20 |
18 |
16 |
10 |
|
Исключение ребра 5-6:
|
№ |
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
|
2 |
0 |
8 |
10 |
18 |
|
2 |
3 |
|
0 |
5 |
4 |
17 |
|
3 |
1 |
0 |
|
7 |
8 |
15 |
|
4 |
4 |
0 |
2 |
|
1 |
8 |
|
5 |
7 |
0 |
4 |
2 |
|
|
|
6 |
6 |
4 |
2 |
0 |
|
|
|
№ |
1 |
2 |
3 |
4 |
5 |
6 |
|
1 |
|
2 |
02 |
8 |
9 |
10 |
|
2 |
2 |
|
02 |
5 |
3 |
9 |
|
3 |
02 |
00 |
|
7 |
7 |
7 |
|
4 |
3 |
00 |
2 |
|
03 |
07 |
|
5 |
6 |
02 |
4 |
2 |
|
|
|
6 |
5 |
4 |
2 |
04 |
|
|
Первый шаг (исключение 4-6)
|
№ |
1 |
2 |
3 |
4 |
5 |
|
1 |
|
2 |
02 |
8 |
9 |
|
2 |
2 |
|
02 |
5 |
3 |
|
3 |
02 |
00 |
|
7 |
7 |
|
5 |
3 |
00 |
4 |
2 |
|
|
6 |
5 |
4 |
2 |
04 |
|
|
№ |
1 |
2 |
3 |
4 |
5 |
|
1 |
|
2 |
02 |
8 |
9 |
|
2 |
2 |
|
02 |
5 |
3 |
|
3 |
02 |
00 |
|
7 |
7 |
|
6 |
5 |
4 |
2 |
04 |
|
|
5 |
3 |
02 |
4 |
2 |
|
|
№ |
1 |
2 |
3 |
4 |
5 |
|
1 |
|
2 |
02 |
6 |
6 |
|
2 |
2 |
|
02 |
3 |
0 |
|
3 |
02 |
00 |
|
5 |
4 |
|
6 |
3 |
2 |
0 |
04 |
|
|
5 |
3 |
02 |
4 |
0 |
|
Таким образом, в результате проведенного анализа установлено что оба разветвления правой ветви «Без ребра 5-6» дают оценки 58. Строить последующие ветви не имеет смысла, так как все маршруты будут иметь большую стоимость по сравнению с левой ветвь алгоритма.