Применение алгоритма Литтла

 

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

       Задачи подобного типа решаются в математике методом ветвей и границ, с использованием алгоритма Литтла.

       Трудность задач данного типа в том, что число возможных маршрутов равно (n-1)!.

       Постановка задачи заключается в следующем: имеется n точек, каждую из которых необходимо посетить всего один раз, выходя из начального пункта и придя в конечный.

       При решении задач для судна на переходах необходимо учитывать действие течений и метеорологические условия.

       Возможное время нахождения в разных точках можно не учитывать, если оно не зависит от порядка их посещения.

       Таким образом, в задаче требуется найти минимальный путь обхода всех заданных точек. Решим подобную задачу, показав тем самым пример использования алгоритма Литтла.

Исходные данные:

 

       Используемая карта:       № 32202

       Начальная точка (П₁):     jн=39⁰00¢N                      lн=25⁰00¢Е

       Конечная точка (П₂):      jк=39⁰20¢N                      lк=25⁰00¢Е

       Пункты назначения, которые необходимо посетить:

1. о. Комби;

2. м. Трипити;

3. м. Сигри;

4. о. Ворио-Поди;

5. о. Псатура.

Составляем матрицу № 1, в которую записываем расстояния между всеми районами. Знак «¥» введен для того, чтобы исключить такой выбор части маршрута, как 1®1, 2®2, 3®3, 4®4 и 5®5, а также чтобы запретить переход из П₁ в П₂. Затем проделаем операцию приведения исходной матрицы № 1. Эта операция заключается в том, что из всех чисел строки мы вычтем минимальное число той же строки. Такое действие эквивалентно тому, что район этой строки условно приближается ко всем другим районам на эту величину. При этом отношение порядка между расстояниями не меняется, то есть разница в путях до всех районов, указанных в строке, остается неизменной. Отношение порядка также сохраняется, если в каждом столбце из всех чисел вычесть минимальное число того же столбца. Как видно из матрицы № 2, после приведения по строкам в каждой ее строке теперь имеется нулевое значение. Так как в столбцах 1 и 3 отсутствуют нули, то произведем операцию приведения по столбцам и получим матрицу № 3.

Матрица № 1                                                                 Матрица № 2

	П2	1	2	3	4	5	n 1			П2		1		2	3	4		5	Сумма2
П1	¥	49	28	41	25	48	25		П1	¥		24		3	16	0		23
1	30	¥	23	45	59	52	23		1	7		¥		0	22	36		29
2	8	23	¥	42	36	37	8		2	0		15		¥	34	28		29
3	39	45	42	¥	64	79	39		3	0		6		3	¥	25		40
4	31	59	36	64	¥	31	31		4	0		28		5	33	¥		0
5	39	52	37	79	31	¥	31		5	8		21		6	48	0		¥
	Сумма 1						157		n2	0	6		0		16	0	0		22

 

Матрица № 3

	П2	1	2	3	4	5
П1	¥	18	3	6 0	0 0	23
1	7	¥	9 0	6	36	29
2	9 0	9	¥	18	28	29
3	0 0	9 0	3	¥	25	40
4	0 0	22	5	17	¥	23 0
5	8	15	6	32	6 0	¥

Во время приведения по строкам и столбцам мы условно уменьшили расстояние на величину, равную n= Сумма 1+Сумма 2=157+22=179 миль. Это значит, что какой бы маршрут не был избран, оценка его нижней границы критерия эффективности не может быть менее 179.

В матрице № 3 в ячейках с нулевыми значениями в правом верхнем углу записаны величины штрафов за не использование каждого нулевого элемента. Штраф определяется суммированием минимальных элементов, колонки и строки которых пересекаются в данной клетке. Например:

Р(2-П₂)=0+9=9

Эта цифра показывает, сколько лишних миль мы пройдем, если не выберем данный маршрут. Каждый маршрут разбиваем на два подмножества и рассчитываем расценки затрат в каждом подмножестве. Например:

 

Из расчета видно, что если мы не будем следовать этим маршрутом, то пройдем дополнительно 9 миль.

Так как для нулевой клетки 4-5 штраф самый большой (23 мили) по сравнению с другими нулевыми клетками, то этот маршрут необходимо обязательно использовать. Аналитически это выполняется, если исключить из матрицы № 4 строку и колонку, содержащие эту ячейку. Одновременно надо запретить включать в дальнейшие решения путь 4-5, если такой путь еще остался в матрице после сокращения, то есть на пересечении строки и столбца 5-4 ставится знак ¥.

Произведем описанные действия и получим матрицу № 4. В полученной матрице в строке 4 отсутствуют нулевые значения, поэтому применим операцию приведения и получим матрицу № 5. Во время приведения мы еще условно уменьшили расстояние на 6 миль и общее уменьшение теперь составило 179+6=185 миль.

 

Матрица № 4                                                                 Матрица № 5

	П2	1	2	3	4	n 3			П2	1	2	3	4
П1	¥	18	3	0	0	0		П1	¥	18	3	6 0	25 0
1	7	¥	0	6	36	0		1	7	¥	6 0	6	36
2	0	9	¥	18	28	0		2	9 0	9	¥	18	28
3	0	0	3	¥	25	0		3	0 0	9 0	3	¥	25
5	8	15	6	32	¥	6		5	2	9	2 0	26	¥
	Сумма 3					6

 

В матрице № 5 самый большой штраф – для клетки П₁-4. Поэтому исключаем из матрицы № 5 строку П₁ и столбец 4. Получаем матрицу № 6, в которой в столбце 3 отсутствует нулевое значение. После приведения получаем матрицу № 7, а общее условное уменьшение увеличивается на 6 миль, то есть 185+6=191 миля.

Матрица № 6                                                                            Матрица № 7

	П2	1	2	3	Сумма4			П2	1	2	3
1	7	¥	0	6			1	7	¥	0 0	12 0
2	0	9	¥	18			2	9 0	9	¥	12
3	0	0	3	¥			3	0 0	9 0	3	¥
5	2	9	0	26			5	2	9	2 0	20
n4	0	0	0	6	6

В матрице № 7 наибольший штраф – для ячейки 1-3, поэтому вычеркиваем строку 1 и столбец 3, одновременно запрещаем выбор маршрута 3-1. Таким образом, получаем матрицу № 8, у которой в столбце 1 отсутствует нулевое решение. Снова применяем операцию приведения и получаем матрицу № 9. При этом общее условное уменьшение увеличивается еще на 9 единиц и теперь оно составляет 191+9=200 миль, то есть какой бы маршрут не был выбран, оценка его нижней границы критерия эффективности не может быть менее 200 миль.

Матрица № 8                                                                            Матрица № 9

	П2	1	2	Сумма			П2	1	2
2	0	9	¥			2	0 0	0 0	¥
3	0	¥	3			3	3 0	¥	3
5	2	9	0			5	2	0 0	3 0
n 5	0	9	0	9

 

В матрице № 9 находятся две нулевые ячейки с одинаковым максимальным значением штрафа: 3-П₂ и 5-2. Выбираем ячейку 5-2 и вычеркиваем строку 5 и столбец 2. Одновременно запрещаем переход 2-П₂, так как это привело бы к окончанию вычислений, а у нас остался неиспользован еще один переход. Так получается матрица № 10.

Матрица № 10

	П2	1
2	¥	¥ 0
3	¥ 0	¥

 

Из матрицы № 10 выбираем маршрут 2-1, после чего выбираем оставшийся маршрут 3-П₂.

Таким образом, мы получили следующие наивыгоднейшие маршруты:

       4-5;            П₁-4;          1-3;            5-2;            2-1;            3-П₂

Расположив их в порядке следования получим следующее:

П₁®4®5®2®1®3®П₂

25+31+37+23+45+39=200 миль

Полученный результат совпадает с оценкой нижней границы критерия эффективности и является наиболее оптимальным из всех возможных вариантов.

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

Алгоритм Литтла не является самым оптимальным по отношении к количеству общей вычислительной работы, но он, несомненно, лучше, чем простой перебор всех возможных решений.

⇐ Предыдущая18192021222324252627Следующая ⇒

Поделиться: