Rivalry2

HTML Diff

2 added 4 removed

Original 2026-01-01

Modified 2026-02-26

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

2 <h2>Формулируем задачу в теории графов</h2>

3 Сформулируем данную задачу, как оптимизационную в теории графов. Все пункты приема на складе образуют узел в графе, где ребра - разрешенные коридоры и расстояния между узлами. Начнем с упрощенного примера:

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

5 Если мы можем представить маршруты движения в виде графа, значит, мы можем использовать математические методы, известные из теории графов. Это поможет найти оптимальный маршрут движения между узлами - пунктами.

6 Приведенный выше пример графа можно описать с помощью матрицы смежности:

7 <ul><li>Пример 1: разрешено перемещаться из узла 2 в 3, но не из 3 в 2. На это указывает единица в матрице смежности справа</li>

8 <li>Пример 2: разрешено ехать как из узла 8 в 3, так и из 3 в 8, на что опять же указывают единица в матрице смежности. В данном случае симметрична</li>

9 </ul><h3>Вернемся к проблеме со складом</h3>

10 Реальный склад больше и сложнее, чем приведенный выше пример. Однако основные принципы работы с графиками остаются теми же. Чтобы упростить реальную задачу, представим небольшой склад:

11 Рассмотрим подробнее эту сложную схему:

12 <ul><li>Здесь показано общее количество полок (точек комплектации) - включена каждая 50-я полка, они отмечены черными квадратами</li>

13 <li>Всем точкам подбора присвоен адрес (номер узла) от 1-74</li>

14 <li>Стрелками показаны разрешенные направления движения, поворотные точки и короткие пути между коридорами</li>

15 </ul>Опишем этот граф в виде матрицы смежности. Еще включим в нее расстояние между различными узлами, так как нам нужно найти оптимальный маршрут:

16 В этой матрице снова указаны все ограничения:

17 <ul><li>Разрешенное направление движения</li>

18 <li>Разрешенные короткие пути</li>

19 <li>Расстояние между узлами</li>

20 </ul>Также на матрице мы четко видим короткий путь между узлами 21 и 41. Белые области матрицы представляют неразрешенные пути, обозначенные через бесконечное расстояние между этими узлами.

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

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

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

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

23 - Существует несколько методов и алгоритмов, которые могут решить этот тип задачи. В данном примере мы использовали алгоритм Флойда-Уоршалла - он помогает искать кратчайшие пути во взвешенном графе. Его мы разберем в других уроках этого курса.

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

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

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

26 Например, визуализируем результаты для короткого списка комплектации:

24 Например, визуализируем результаты для короткого списка комплектации:

27 Начнем с узла 0 и заберем товары в узлах 15, 45, 58 и 73. Алгоритм находит кратчайший допустимый маршрут между этими точками путем вычисления матрицы расстояний D. Затем ее можно использовать, чтобы определить общее расстояние между всеми узлами в списке комплектации:

25 Начнем с узла 0 и заберем товары в узлах 15, 45, 58 и 73. Алгоритм находит кратчайший допустимый маршрут между этими точками путем вычисления матрицы расстояний D. Затем ее можно использовать, чтобы определить общее расстояние между всеми узлами в списке комплектации:

28 <ol><li>D[0][15] → 90 m</li>

26 <ol><li>D[0][15] → 90 m</li>

29 <li>D[15][45] → 52 m</li>

27 <li>D[15][45] → 52 m</li>

30 <li>D[45][58] → 34 m</li>

28 <li>D[45][58] → 34 m</li>

31 <li>D[58][73] → 92 m</li>

29 <li>D[58][73] → 92 m</li>

32 </ol>Общее расстояние =268m - это самый короткий путь

30 </ol>Общее расстояние =268m - это самый короткий путь

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

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

34 <h2>Выводы</h2>

32 <h2>Выводы</h2>

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

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