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

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

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

Трудность задач данного типа в том, что число возможных маршрутов равно (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