Оптимизация логистики в 1С: используем алгоритм Флойда-Уоршелла для построения маршрутов

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

Для решения этих задач существует множество алгоритмов, одним из которых является алгоритм Флойда-Уоршелла. В этой статье мы рассмотрим реализацию этого мощного инструмента на платформе 1С 8.3, чтобы вы могли легко интегрировать его в свои бизнес-процессы.

Какие еще алгоритмы существуют?

Помимо алгоритма Флойда-Уоршелла, для поиска кратчайших путей часто используются алгоритм Дейкстры, алгоритм Беллмана-Форда и алгоритм A*. Каждый из них имеет свои особенности, преимущества и недостатки, определяющие область его применения.

Чем алгоритм Флойда-Уоршелла отличается от алгоритма Дейкстры?

Основное отличие заключается в том, что алгоритм Дейкстры находит кратчайшие пути от одной заданной вершины до всех остальных вершин графа. Это оптимальный выбор, если вам нужно узнать кратчайшие расстояния только от определенной точки.

Алгоритм Флойда-Уоршелла, в свою очередь, находит кратчайшие пути между всеми парами вершин в графе. Это значит, что после его выполнения вы будете знать кратчайшее расстояние и маршрут между любыми двумя точками в вашей сети.

Когда какой алгоритм выбирать?

• Используйте алгоритм Дейкстры, если вам нужно найти кратчайшие пути от одной начальной точки до всех остальных. Это более эффективно, чем Флойда-Уоршелла, если вам не нужны расстояния между всеми парами вершин.
• Используйте алгоритм Флойда-Уоршелла, если вам нужно знать кратчайшие расстояния между всеми парами вершин. Это необходимо, например, для анализа связности графа, поиска транзитивного замыкания или для решения задач, где требуется информация о кратчайших путях между любыми двумя точками.

В чем преимущества и недостатки алгоритма Флойда-Уоршелла?

• Преимущества:

1. Простота реализации.
2. Возможность найти кратчайшие пути между всеми парами вершин.
3. Возможность обнаружения циклов отрицательного веса.

• Недостатки:

1. Более высокая вычислительная сложность по сравнению с алгоритмом Дейкстры (O(n^3) против O(n^2) или O(n log n) с использованием приоритетной очереди). Это может быть критично для очень больших графов.
2. Требует больше памяти для хранения матрицы смежности и матрицы расстояний.

Что вы узнаете из этой статьи?

В этой статье мы подробно рассмотрим реализацию алгоритма Флойда-Уоршелла на платформе 1С 8.3, научимся строить матрицу смежности, применять алгоритм и выводить результаты, включая найденные пути. Также мы рассмотрим обнаружение циклов отрицательного веса и примеры практического применения этого мощного инструмента в бизнес-задачах. 

Теория алгоритма Флойда-Уоршелла:

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

• Что такое офисы? В нашем примере у нас 4 офиса (пронумерованы от 1 до 4). РазмерГрафа = 4; говорит об этом.
• Что такое дороги? Дороги – это прямые маршруты между офисами. МатрицаРасстояний показывает длину каждой прямой дороги. Если прямой дороги нет, то пишем “Бесконечность” (Бесконечность = 1000000;).

Теперь разберем код, как эта карта создается:

МатрицаРасстояний = Новый Массив();

• Это: Мы берем чистый лист бумаги, чтобы нарисовать нашу карту дорог (МатрицаРасстояний ).

  Строка1 = Новый Массив(РазмерГрафа);
  Строка1[0] = 0;
  Строка1[1] = 5;
  Строка1[2] = Бесконечность;
  Строка1[3] = 10;
  МатрицаРасстояний.Добавить(Строка1);

   

• Это: Мы рисуем первую строку карты. Эта строка показывает, как добраться из ОФИСА №1 в другие офисы:
  • Строка1[0] = 0; : Из офиса №1 в офис №1 (в себя) – расстояние 0 (никуда ехать не надо).
  • Строка1[1] = 5; : Из офиса №1 в офис №2 – расстояние 5 км (например).
  • Строка1[2] = Бесконечность; : Из офиса №1 в офис №3 – прямой дороги НЕТ (очень далеко, "Бесконечность").
  • Строка1[3] = 10; : Из офиса №1 в офис №4 – расстояние 10 км.
• МатрицаРасстояний.Добавить(Строка1); : Мы добавляем эту информацию на наш “лист карты”.

  Строка2 = Новый Массив(РазмерГрафа);
  Строка2[0] = Бесконечность;
  Строка2[1] = 0;
  Строка2[2] = 3;
  Строка2[3] = Бесконечность;
  МатрицаРасстояний.Добавить(Строка2);

   

• Это: Мы рисуем вторую строку карты. Эта строка показывает, как добраться из ОФИСА №2 в другие офисы:
  • Строка2[0] = Бесконечность; : Из офиса №2 в офис №1 – прямой дороги НЕТ.
  • Строка2[1] = 0; : Из офиса №2 в офис №2 (в себя) – расстояние 0.
  • Строка2[2] = 3; : Из офиса №2 в офис №3 – расстояние 3 км.
  • Строка2[3] = Бесконечность; : Из офиса №2 в офис №4 – прямой дороги НЕТ.
• МатрицаРасстояний.Добавить(Строка2); : Мы добавляем эту информацию на наш “лист карты”.
• и т.д.

    Алгоритм берет эту "карту прямых дорог" и начинает искать пути подлиннее, через другие офисы. Например, может оказаться, что из офиса №1 в офис №3 нет прямой дороги, но можно доехать до офиса №2 (5 км), а потом из офиса №2 в офис №3 (3 км). Тогда общий путь будет 5 + 3 = 8 км. Это лучше, чем “Бесконечность”!

Алгоритм перебирает все возможные "промежуточные офисы" и запоминает самые короткие пути. В итоге он выдает вам полную карту, где указаны кратчайшие расстояния между любыми двумя офисами.

Реализация алгоритма Флойда-Уоршелла в 1С 8.3:

&НаСервере
Процедура ФлойдаУоршелла(МатрицаРасстояний, РазмерГрафа, Бесконечность, МатрицаПредков)

    Для k = 0 По РазмерГрафа - 1 Цикл  // "Промежуточный офис"
        Для i = 0 По РазмерГрафа - 1 Цикл  // Откуда едем (начальный офис)
            Для j = 0 По РазмерГрафа - 1 Цикл  // Куда едем (конечный офис)
                Если (МатрицаРасстояний[i][k] <> Бесконечность И МатрицаРасстояний[k][j] <> Бесконечность) Тогда
                    // Если из i в k и из k в j можно доехать
                    Если МатрицаРасстояний[i][j] > МатрицаРасстояний[i][k] + МатрицаРасстояний[k][j] Тогда
                        // И если путь через k короче, чем прямой путь из i в j
                        МатрицаРасстояний[i][j] = МатрицаРасстояний[i][k] + МатрицаРасстояний[k][j];
                        МатрицаПредков[i][j] = k;  // Запоминаем, что лучший путь через k
                    КонецЕсли;
                КонецЕсли;
            КонецЦикла;
        КонецЦикла;
    КонецЦикла;
	
    // Проверка на циклы отрицательного веса
    Для i = 0 По РазмерГрафа - 1 Цикл
        Если МатрицаРасстояний[i][i] < 0 Тогда
            Сообщить("Обнаружен цикл отрицательного веса!");
            Возврат; // Прерываем выполнение, если цикл обнаружен
        КонецЕсли;
	КонецЦикла;
	
КонецПроцедуры

Код ФлойдаУоршелла:

• Для k = 0 По РазмерГрафа - 1 Цикл : Этот цикл перебирает все возможные "промежуточные офисы" (офис k).
• Для i = 0 По РазмерГрафа - 1 Цикл : Этот цикл перебирает все возможные "начальные офисы" (офис i).
• Для j = 0 По РазмерГрафа - 1 Цикл : Этот цикл перебирает все возможные "конечные офисы" (офис j).
• Если (МатрицаРасстояний[i][k] <> Бесконечность И МатрицаРасстояний[k][j] <> Бесконечность) Тогда : Проверяем, можно ли вообще доехать из офиса i в офис k, и из офиса k в офис j. Если хотя бы один из этих путей равен "Бесконечности", то ехать через офис k нет смысла.
• Если МатрицаРасстояний[i][j] > МатрицаРасстояний[i][k] + МатрицаРасстояний[k][j] Тогда : Проверяем, короче ли путь из офиса i в офис j через офис k, чем прямой путь из офиса i в офис j.
• МатрицаРасстояний[i][j] = МатрицаРасстояний[i][k] + МатрицаРасстояний[k][j]; : Если путь через офис k короче, то мы обновляем расстояние в МатрицеРасстояний.
• МатрицаПредков[i][j] = k; : Запоминаем в МатрицеПредков, что лучший путь из офиса i в офис j проходит через офис k. Это поможет нам потом восстановить маршрут.

Этот код берет вашу "карту дорог" и улучшает ее, находя самые короткие пути между всеми офисами, даже если нет прямых дорог!

Мы уже определили карту дорог (МатрицаРасстояний) в примере выше (4 офиса, расстояния между ними). Нажимаем кнопку "Запустить алгоритм" в нашей обработке.

В текстовом поле "РезультатАлгоритма" мы должны увидеть следующую информацию (это пример, значения могут отличаться в зависимости от реализации функции ВосстановитьПуть):

Расстояние от 1 до 1: 0
Путь: 1

Расстояние от 1 до 2: 5
Путь: 1 -> 2

Расстояние от 1 до 3: 8
Путь: 1 -> 2 -> 3

Расстояние от 1 до 4: 9
Путь: 1 -> 2 -> 3 -> 4

Расстояние от 2 до 1: Бесконечность

Расстояние от 2 до 2: 0
Путь: 2

Расстояние от 2 до 3: 3
Путь: 2 -> 3

Расстояние от 2 до 4: 4
Путь: 2 -> 3 -> 4

Расстояние от 3 до 1: Бесконечность

Расстояние от 3 до 2: Бесконечность

Расстояние от 3 до 3: 0
Путь: 3

Расстояние от 3 до 4: 1
Путь: 3 -> 4

Расстояние от 4 до 1: Бесконечность

Расстояние от 4 до 2: Бесконечность

Расстояние от 4 до 3: Бесконечность

Расстояние от 4 до 4: 0
Путь: 4

Анализ результатов (построчно):

• Расстояние от 1 до 1: 0, Путь: 1: Всё верно, расстояние от вершины 1 до самой себя равно 0.
• Расстояние от 1 до 2: 5, Путь: 1 -> 2: В МатрицеРасстояний[0][1] (от 1 до 2) изначально было 5. Алгоритм не нашел более короткого пути. Всё правильно.
• Расстояние от 1 до 3: 8, Путь: 1 -> 2 -> 3: В МатрицеРасстояний[0][2] (от 1 до 3) изначально было Бесконечность. Алгоритм нашел путь через вершину 2: 1 -> 2 (5) + 2 -> 3 (3) = 8. Это и есть кратчайший путь.
• Расстояние от 1 до 4: 9, Путь: 1 -> 2 -> 3 -> 4: В МатрицеРасстояний[0][3] (от 1 до 4) изначально было 10. Алгоритм нашел путь через вершины 2 и 3: 1 -> 2 (5) + 2 -> 3 (3) + 3 -> 4 (1) = 9. Это и есть кратчайший путь.
• Расстояние от 2 до 1: Бесконечность: В МатрицеРасстояний[1][0] (от 2 до 1) изначально было Бесконечность. Значит, из вершины 2 в вершину 1 нет пути (или он очень длинный). Алгоритм не смог найти путь короче.
• Расстояние от 2 до 2: 0, Путь: 2: Всё верно, расстояние от вершины 2 до самой себя равно 0.
• Расстояние от 2 до 3: 3, Путь: 2 -> 3: В МатрицеРасстояний[1][2] (от 2 до 3) изначально было 3. Алгоритм не нашел более короткого пути. Всё правильно.
• Расстояние от 2 до 4: 4, Путь: 2 -> 3 -> 4: В МатрицеРасстояний[1][3] (от 2 до 4) изначально было Бесконечность. Алгоритм нашел путь через вершину 3: 2 -> 3 (3) + 3 -> 4 (1) = 4. Это и есть кратчайший путь.
• Расстояние от 3 до 1: Бесконечность: В МатрицеРасстояний[2][0]  (от 3 до 1) изначально было Бесконечность. Алгоритм не смог найти путь короче.
• Расстояние от 3 до 2: Бесконечность: В МатрицеРасстояний[2][1] (от 3 до 2) изначально было Бесконечность Алгоритм не смог найти путь короче.
• Расстояние от 3 до 3: 0, Путь: 3: Всё верно, расстояние от вершины 3 до самой себя равно 0.
• Расстояние от 3 до 4: 1, Путь: 3 -> 4: В МатрицеРасстояний[2][3] (от 3 до 4) изначально было 1. Алгоритм не нашел более короткого пути. Всё правильно.
• Расстояние от 4 до 1: Бесконечность: В МатрицеРасстояний[3][0] (от 4 до 1) изначально было Бесконечность Алгоритм не смог найти путь короче.
• Расстояние от 4 до 2: Бесконечность: В МатрицеРасстояний[3][1] (от 4 до 2) изначально было Бесконечность. Алгоритм не смог найти путь короче.
• Расстояние от 4 до 3: Бесконечность: В МатрицеРасстояний[3][2] (от 4 до 3) изначально было Бесконечность. Алгоритм не смог найти путь короче.
• Расстояние от 4 до 4: 0, Путь: 4: Всё верно, расстояние от вершины 4 до самой себя равно 0.

Что произойдет при изменении МатрицаРасстояний[2][3] = -1; и наличии проверки на цикл отрицательного веса:

1. Изменение матрицы смежности: Значение МатрицаРасстояний[2][3] меняется на -1.

2. Выполнение алгоритма Флойда-Уоршелла: Алгоритм начинает свою работу, перебирая все возможные пути между вершинами.

3. Обнаружение цикла отрицательного веса:

   • В какой-то момент алгоритм обнаружит, что расстояние от вершины 3 до самой себя можно уменьшить, пройдя через вершину 4:
     • Путь от 3 до 3 через 4: 3 -> 4 (-1) + 4 -> 3 (Бесконечность). Изначально Бесконечность не даст обнаружить, но при этом 4 -> 4 = 0. Надо проверить.
   • Т.е. нужно сделать проверку 4 -> 3 и 3 -> 4.

4. Сработает проверка на цикл отрицательного веса:

   • Когда алгоритм дойдет до этапа, когда k = 3 и i = 3 (то есть, рассматривает вершину 3 как промежуточную для пути из 3 в 3), условие МатрицаРасстояний[i][i] < 0 станет истинным.
   • Потому что он найдет, что путь из вершины 3 в вершину 3 (через вершину 4) стал отрицательным.

5. Вывод сообщения и прерывание выполнения:

   • Будет выведено сообщение: "Обнаружен цикл отрицательного веса!"
   • Функция ЗапуститьАлгоритмНаСервере прервет свое выполнение (Возврат;).

Результат:

• Алгоритм Флойда-Уоршелла не завершится. Он прервет свое выполнение, как только обнаружит цикл отрицательного веса.
• В текстовых полях НачальныеДанные и РезультатАлгоритма вы увидите только исходную матрицу смежности (в НачальныеДанные) и сообщение об обнаруженном цикле отрицательного веса (в сообщении). Значения в текстовом поле РезультатАлгоритма  либо не изменятся, либо будут частично изменены (в зависимости от того, как быстро сработает проверка).

Важно:

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

P.S упоминался в статье Алгоритм A*.  Алгоритм A* (А звезда) – это алгоритм поиска пути, который эффективно находит оптимальный маршрут от начальной до конечной точки. Он комбинирует в себе преимущества алгоритма Дейкстры (гарантия нахождения кратчайшего пути) и эвристического поиска (скорость). A* использует эвристическую функцию, оценивающую "стоимость" достижения цели из текущей точки. Алгоритм выбирает для расширения вершину с наименьшим значением функции f(n) = g(n) + h(n), где g(n) – стоимость пути от начальной точки до текущей, а h(n) – эвристическая оценка стоимости пути от текущей до конечной точки. A* гарантирует нахождение оптимального пути, если эвристика допустима (не переоценивает расстояние до цели).

Статья была протестирована на платформе 1С:Предприятие 8.3, в среде разработки и на реальных примерах, демонстрирующих применение алгоритма Флойда-Уоршелла в типовых конфигурациях.

Статья ориентирована на:

• Разработчиков 1С: которые хотят углубить свои знания в области алгоритмов и научиться применять их в своих проектах.
• Внедренцев 1С: стремящихся оптимизировать бизнес-процессы клиентов с помощью эффективных решений.
• Пользователей 1С: интересующихся возможностями платформы для решения сложных задач, таких как логистика, анализ данных и оптимизация.