Поиск пути на складе в 1С 8.3: реализация алгоритма волновой трассировки для управления логистикой

В современном бизнесе эффективная логистика и оптимизация перемещения объектов являются ключевыми факторами успеха.  Автоматизация этих процессов часто требует реализации алгоритмов поиска пути, которые позволяют находить оптимальные маршруты между различными точками.  В этой статье мы рассмотрим один из таких алгоритмов — алгоритм волновой трассировки (Breadth-First Search, BFS) — и покажем, как его реализовать на платформе 1С:Предприятие.

Алгоритм волновой трассировки (BFS) — это простой и эффективный способ найти кратчайший путь между двумя точками в графе.  Он идеально подходит для решения задач, где требуется найти маршрут с минимальным количеством шагов, например, при перемещении товаров на складе, обходе препятствий роботом или построении маршрутов для транспортных средств.

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

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

Теоретическая часть

Алгоритм волновой трассировки (BFS) — это метод поиска пути в графе, который исследует вершины графа в порядке увеличения расстояния от начальной вершины.  Это гарантирует, что первый найденный путь к целевой вершине будет кратчайшим (в смысле количества шагов).

**Принцип работы:**

1.  **Инициализация:**
    *   Создается структура данных для хранения расстояний от начальной вершины до всех остальных вершин графа.  Изначально расстояние до начальной вершины равно 0, а до всех остальных вершин — бесконечности (или, в нашей реализации на 1С, "Неопределено", что означает, что вершина еще не посещена).
    *   Создается очередь (FIFO - First-In, First-Out) для хранения вершин, которые необходимо посетить.  В очередь добавляется начальная вершина.

2.  **Основной цикл (пока очередь не пуста):**
    *   Извлекается первая вершина из очереди.
    *   Для каждого соседа извлеченной вершины:
        *   Если сосед еще не посещен (расстояние до него равно "Неопределено"):
            *   Расстояние до соседа вычисляется как расстояние до текущей вершины + 1 (так как мы предполагаем, что стоимость перемещения между соседними вершинами равна 1).
            *   Сосед добавляется в конец очереди.

3.  **Восстановление пути:**
    *   Когда целевая вершина достигнута (расстояние до нее отлично от "Неопределено"), путь можно восстановить, двигаясь от целевой вершины к начальной. Для этого нужно помнить, из какой вершины мы пришли в каждую вершину. В нашей реализации, это не нужно, так как мы просто берем наименьшее значение расстояния у соседей, и идем по нему.

**Визуализация:**

Представьте себе карту в виде сетки.  Начальная вершина — это точка, из которой начинает распространяться "волна".  "Волна" распространяется на все соседние клетки, которым еще не присвоено расстояние. Каждой посещенной клетке присваивается расстояние, равное расстоянию от начальной точки. Этот процесс продолжается до тех пор, пока "волна" не достигнет целевой вершины.

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

*   **Гарантированное нахождение кратчайшего пути:** BFS всегда находит кратчайший путь (в смысле количества шагов) между двумя вершинами.
*   **Простота реализации:**  Алгоритм относительно прост в реализации, что делает его доступным для начинающих разработчиков.
*   **Не требует сложной структуры данных:**  Использует простую структуру данных (очередь).

**Недостатки BFS:**

*   **Неэффективен на больших графах:**  BFS может быть медленным на больших картах, так как ему приходится посещать все вершины на каждом уровне.
*   **Не учитывает стоимость перемещения:** BFS не учитывает стоимость перемещения между различными вершинами.

**Сценарии применения:**

*   **Поиск пути на складе:** Определение кратчайшего маршрута для перемещения товаров.
*   **Планирование маршрутов:**  Построение маршрутов для транспортных средств, учитывая ограничения по проходимости.
*   **Робототехника:**  Навигация роботов в замкнутых пространствах, обход препятствий.
*   **Игры:** Поиск пути для игровых персонажей.

Теперь переходим к самому интересному - практической реализации алгоритма волновой трассировки (BFS) на 1С:Предприятие.

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

     Значение элемента массива определяет тип клетки:

      "0" - проходимая клетка (свободное пространство). 

      "1" - непроходимая клетка (препятствие).

Пример карты:

// Карта склада (0 - свободно, 1 - препятствие)
    Карта = Новый Массив();

    // Создаем строки карты (предположим, что размер карты 8x8)
    Строка1 = Новый Массив();
    Строка2 = Новый Массив();
    Строка3 = Новый Массив();
    Строка4 = Новый Массив();
    Строка5 = Новый Массив();
    Строка6 = Новый Массив();
    Строка7 = Новый Массив();
    Строка8 = Новый Массив();

    // Заполняем строки нулями (пустая карта)
    Для i = 1 По 8 Цикл
        Строка1.Добавить(0);
        Строка2.Добавить(0);
        Строка3.Добавить(0);
        Строка4.Добавить(0);
        Строка5.Добавить(0);
        Строка6.Добавить(0);
        Строка7.Добавить(0);
        Строка8.Добавить(0);
    КонецЦикла;
	
	// Добавляем преграды (единицы)
    Строка3[2] = 1; // Преграда в 3-й строке, 3-м столбце
    Строка3[3] = 1; // Преграда в 3-й строке, 4-м столбце
    Строка4[2] = 1;
    Строка4[3] = 1;
	Строка5[5] = 1;
	Строка6[5] = 1;
	Строка7[5] = 1;
	
    // Добавляем строки в карту
    Карта.Добавить(Строка1);
    Карта.Добавить(Строка2);
    Карта.Добавить(Строка3);
    Карта.Добавить(Строка4);
    Карта.Добавить(Строка5);
    Карта.Добавить(Строка6);
    Карта.Добавить(Строка7);
    Карта.Добавить(Строка8);

Функция Проходима(Карта, X, Y)  :

Эта функция проверяет, является ли клетка с координатами (X,Y) проходимой. Она возвращает Истина, если клетка находится в пределах карты и не является препятствием, и Ложь в противном случае.

&НаСервере
Функция Проходима(Карта, X, Y)

    // Проверяем, находится ли клетка в пределах карты и является ли она проходимой (0 - проходимая, 1 - препятствие)
    Если X < 0 ИЛИ Y < 0 ИЛИ X >= Карта.Количество() ИЛИ Y >= Карта[0].Количество() Тогда
        Возврат Ложь; // Выход за границы карты
    КонецЕсли;

    Возврат Карта[X][Y] = 0; // 0 - проходимая ячейка

КонецФункции

Функция ВолноваяТрассировка(Карта, СтартX, СтартY, ЦельX, ЦельY):

Эта функция реализует основной алгоритм волновой трассировки (BFS). Она принимает на вход карту, координаты начальной и целевой клеток, и возвращает массив координат клеток, составляющих кратчайший путь.

&НаСервере
Функция ВолноваяТрассировка(Карта, СтартX, СтартY, ЦельX, ЦельY)

    // 1. Инициализация

    // Создаем карту расстояний, заполненную значениями "Неопределено"
    КартаРасстояний = Новый Массив();
    Для i = 0 По Карта.Количество() - 1 Цикл
        СтрокаРасстояний = Новый Массив();
        Для j = 0 По Карта[0].Количество() - 1 Цикл
            СтрокаРасстояний.Добавить(Неопределено);
        КонецЦикла;
        КартаРасстояний.Добавить(СтрокаРасстояний);
    КонецЦикла;

    // Присваиваем начальной клетке значение 0
    КартаРасстояний[СтартX][СтартY] = 0;

    // Создаем очередь для обработки клеток
    Очередь = Новый Массив();
    НоваяКлетка = Новый Массив();
    НоваяКлетка.Добавить(СтартX);
    НоваяКлетка.Добавить(СтартY);
    Очередь.Добавить(НоваяКлетка);

    // 2. Основной цикл
    Пока Очередь.Количество() > 0 Цикл

        // 2.1 Извлекаем первую клетку из очереди
        ТекущаяКлетка = Очередь[0];
        Очередь.Удалить(0);

        X = ТекущаяКлетка[0];
        Y = ТекущаяКлетка[1];

        // 2.2 Если достигли целевой клетки, завершаем поиск
        Если X = ЦельX И Y = ЦельY Тогда
            Прервать;
        КонецЕсли;

        // 2.3 Перебираем всех соседей текущей клетки
        Для ДX = -1 По 1 Цикл
            Для ДY = -1 По 1 Цикл

                // Пропускаем текущую клетку
                Если ДX = 0 И ДY = 0 Тогда
                    Продолжить;
                КонецЕсли;

                НовыйX = X + ДX;
                НовыйY = Y + ДY;

                // 2.4 Проверяем, является ли сосед проходимым и не посещенным
                Если Проходима(Карта, НовыйX, НовыйY) И КартаРасстояний[НовыйX][НовыйY] = Неопределено Тогда

                    // 2.5 Присваиваем соседу значение расстояния
                    КартаРасстояний[НовыйX][НовыйY] = КартаРасстояний[X][Y] + 1;

                    // 2.6 Добавляем соседа в очередь для обработки
                    НоваяКлетка = Новый Массив();
                    НоваяКлетка.Добавить(НовыйX);
                    НоваяКлетка.Добавить(НовыйY);
                    Очередь.Добавить(НоваяКлетка);
                КонецЕсли;
            КонецЦикла;
        КонецЦикла;
    КонецЦикла;

    // 3. Восстановление пути
    Если КартаРасстояний[ЦельX][ЦельY] = Неопределено Тогда
        // Путь не найден
        Возврат Неопределено;
    КонецЕсли;

    Путь = Новый Массив();
    ТекущийX = ЦельX;
    ТекущийY = ЦельY;

    Пока ТекущийX <> СтартX ИЛИ ТекущийY <> СтартY Цикл

        НоваяКлетка = Новый Массив();
        НоваяКлетка.Добавить(ТекущийX);
        НоваяКлетка.Добавить(ТекущийY);
        Путь.Вставить(0, НоваяКлетка);

        // Ищем соседа с наименьшим значением расстояния
        ЛучшийСоседX = Неопределено;
        ЛучшийСоседY = Неопределено;
        МинРасстояние = Неопределено;

        Для ДX = -1 По 1 Цикл
            Для ДY = -1 По 1 Цикл

                // Пропускаем текущую клетку
                Если ДX = 0 И ДY = 0 Тогда
                    Продолжить;
                КонецЕсли;

                НовыйX = ТекущийX + ДX;
                НовыйY = ТекущийY + ДY;

                // Проверяем, является ли сосед проходимым и посещенным
                Если Проходима(Карта, НовыйX, НовыйY) И КартаРасстояний[НовыйX][НовыйY] <> Неопределено Тогда

                    // Если это первый сосед или его расстояние меньше текущего минимального
                    Если ЛучшийСоседX = Неопределено ИЛИ КартаРасстояний[НовыйX][НовыйY] < МинРасстояние Тогда
                        ЛучшийСоседX = НовыйX;
                        ЛучшийСоседY = НовыйY;
                        МинРасстояние = КартаРасстояний[НовыйX][НовыйY];
                    КонецЕсли;
                КонецЕсли;
            КонецЦикла;
        КонецЦикла;

        // Если не нашли лучшего соседа, значит что-то пошло не так
        Если ЛучшийСоседX = Неопределено Тогда
            Возврат Неопределено; // Или можно выбросить исключение
        КонецЕсли;

        ТекущийX = ЛучшийСоседX;
        ТекущийY = ЛучшийСоседY;
    КонецЦикла;

    // Добавляем начальную клетку в путь
    НоваяКлетка = Новый Массив();
    НоваяКлетка.Добавить(СтартX);
    НоваяКлетка.Добавить(СтартY);
    Путь.Вставить(0, НоваяКлетка);

    Возврат Путь;

КонецФункции

Чтобы визуализировать результаты работы алгоритма, можно использовать строковые реквизиты формы. Функция ЗаполнитьРезультатАлгоритмаСтрокой преобразует карту с отмеченным путем в строку и отображает ее на форме.

&НаСервере
Процедура ЗаполнитьРезультатАлгоритмаСтрокой(Карта, Путь)

    // Создаем копию карты, чтобы не изменять исходную
    КартаДляОтображения = Новый Массив();
    Для Каждого СтрокаКарты Из Карта Цикл
        НоваяСтрока = Новый Массив();
        Для Каждого Ячейка Из СтрокаКарты Цикл
            НоваяСтрока.Добавить(Ячейка);
        КонецЦикла;
        КартаДляОтображения.Добавить(НоваяСтрока);
    КонецЦикла;

    // Отмечаем путь на карте значением 2 (или другим, отличным от 0 и 1)
    Если ТипЗнч(Путь) = Тип("Массив") Тогда
        Для Каждого Точка Из Путь Цикл
            КартаДляОтображения[Точка[0]][Точка[1]] = 2;
        КонецЦикла;
    КонецЕсли;

    // Преобразуем карту в строку
    ТекстКарты = "";
    Для Каждого СтрокаКарты Из КартаДляОтображения Цикл
        ТекстСтроки = "";
        Для Каждого Ячейка Из СтрокаКарты Цикл
            ТекстСтроки = ТекстСтроки + Строка(Ячейка) + " ";
        КонецЦикла;
        ТекстКарты = ТекстКарты + ТекстСтроки + Символы.ПС; // Добавляем перенос строки
    КонецЦикла;

    // Присваиваем текст реквизиту
    ЭтаФорма.РезультатАлгоритмаСтрока = ТекстКарты;

КонецПроцедуры

Теперь, когда у нас есть работающий алгоритм волновой трассировки (BFS) на 1С, давайте рассмотрим несколько примеров его использования для решения реальных задач.

    **Пример 1: Поиск пути на складе**

    Одной из наиболее распространенных задач, где может быть полезен BFS, является поиск пути на складе. Представьте себе склад с множеством стеллажей, полок и проходов. Задача состоит в том, чтобы найти кратчайший маршрут для перемещения товара от одной точки склада к другой. Для решения этой задачи необходимо:

        1. **Представить карту склада в виде двумерного массива.** Стеллажи и другие препятствия будут представлены как непроходимые клетки (значение "1"), а проходы — как проходимые клетки (значение `0`).

        2. **Определить начальную и целевую точки.** Это координаты начального и конечного расположения товара на складе.

        3. **Вызвать функцию "ВолноваяТрассировка(Карта, СтартX, СтартY, ЦельX, ЦельY)"**, чтобы найти кратчайший путь.

        4. **Визуализировать найденный путь на форме.** Можно использовать строковые реквизиты формы, как мы делали раньше, или создать более интерактивное представление с использованием табличного поля и условного оформления. **Адаптация кода для задачи:** Чтобы адаптировать код для задачи поиска пути на складе, можно добавить возможность загрузки карты склада из внешнего файла (например, CSV или Excel) или разработать редактор карты непосредственно в 1С. Также можно добавить учет различных факторов, таких как: * **Вес товара:** Более тяжелые товары могут требовать обхода определенных участков склада или использования более длинных, но более безопасных маршрутов. * **Размер товара:** Крупногабаритные товары могут не проходить через узкие проходы. * **Расположение погрузочной техники:** Необходимо учитывать расположение погрузчиков и других механизмов, чтобы маршрут был удобным для использования. **Пример 2: Поиск пути по территории** Алгоритм BFS также можно использовать для поиска пути по территории, например, для планирования маршрута обхода территории охранником или построения маршрута для доставки посылок.

          В этом случае карта будет представлять собой план территории, где:

         "0" - проходимая территория (дороги, тротуары, газоны).

         "1" - непроходимая территория (здания, заборы, водоемы).

Адаптация кода для задачи:

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

Результаты:

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

См. скриншоты, прикрепленные к статье, как алгоритм выбирает маршруты.

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

Отличия BFS от других алгоритмов поиска пути:

1. Отличие от алгоритма A (A-star):*

   • BFS (Волновая трассировка):
     • Принцип работы: Исследует граф "вширь", то есть сначала все соседние вершины, потом их соседей и так далее. Гарантированно находит кратчайший путь (по количеству шагов) в невзвешенном графе.
     • Использование эвристики: Не использует эвристическую функцию.
     • Производительность: Может быть медленным на больших графах, особенно если целевая вершина находится далеко от начальной.
     • Применимость: Хорошо подходит для задач, где важно найти кратчайший путь по количеству шагов, и где граф не очень большой.
   • A (A-star):*
     • Принцип работы: Использует эвристическую функцию для оценки стоимости пути от текущей вершины до целевой. Это позволяет алгоритму выбирать наиболее перспективные направления поиска и быстрее находить путь.
     • Использование эвристики: Активно использует эвристическую функцию (например, расстояние по прямой до цели).
     • Производительность: Обычно работает быстрее, чем BFS, особенно на больших графах.
     • Применимость: Хорошо подходит для задач, где важна скорость поиска пути, и где можно использовать хорошую эвристическую функцию. Может не найти оптимальный путь, если эвристика неточная.

   Ключевое отличие: A* использует эвристику для оценки перспективы каждого пути, в то время как BFS просто "распространяется" во все стороны, пока не найдет цель. A* обычно быстрее, но требует хорошей эвристической функции.

2. Отличие от алгоритма Dijkstra (Дейкстры):

   • BFS (Волновая трассировка):
     • Применимость: Работает только на невзвешенных графах (где все переходы имеют одинаковую стоимость).
     • Сложность: Проще в реализации, чем алгоритм Дейкстры.
   • Dijkstra (Дейкстры):
     • Применимость: Работает на взвешенных графах (где переходы могут иметь разную стоимость).
     • Сложность: Более сложный в реализации, чем BFS.
     • Результат: Гарантированно находит кратчайший путь (по сумме весов) во взвешенном графе.

   Ключевое отличие: Алгоритм Дейкстры может работать с графами, где "стоимость" перехода между вершинами различна (например, разное время прохождения разных участков пути). BFS предполагает, что все переходы имеют одинаковую стоимость.

3. Отличие от алгоритма Jump Point Search (JPS):

   • BFS (Волновая трассировка):
     • Принцип работы: Исследует каждую соседнюю вершину.
     • Производительность: Может быть медленным на больших картах с большими открытыми пространствами.
   • JPS (Jump Point Search):
     • Принцип работы: Оптимизированная версия A*, которая "прыгает" через прямые участки пути, минимизируя количество вершин, которые необходимо исследовать.
     • Производительность: Значительно быстрее, чем A* и BFS на картах с большими открытыми пространствами.
     • Сложность: Более сложный в реализации, чем BFS и A*.

   Ключевое отличие: JPS "интеллектуально" пропускает множество вершин, которые очевидно не ведут к цели, что делает его значительно быстрее на определенных типах карт.

Сравнение в таблице:

Когда какой алгоритм использовать:

• BFS: Когда важна простота реализации и гарантированный кратчайший путь (по количеству шагов) на небольших невзвешенных графах.
• A:* Когда важна скорость поиска пути на больших графах, и можно использовать хорошую эвристическую функцию.
• Dijkstra: Когда необходимо найти кратчайший путь на взвешенном графе.
• JPS: Когда необходимо быстро найти путь на больших картах с большими открытыми пространствами (например, карты игр).

P.S. по-простому "как пользоваться" в модуле обработки задаете свои данные, преграды, меняете размер массива, запускаете обработку и смотрите результат: "2" - это путь алгоритма на массиве. На скриншотах показал где менять, и какие результаты получаются: наглядный массив и "найденный путь"

Или можете использовать процедуры из статьи.