Поиск кратчайшего пути между точками (складами) по алгоритму Флойда-Уоршелла
Скачать файл
ВНИМАНИЕ:
Файлы из Базы знаний - это исходный код разработки.
Это примеры решения задач, шаблоны, заготовки, "строительные материалы" для учетной системы.
Файлы ориентированы на специалистов 1С, которые могут разобраться в коде и оптимизировать программу для запуска в базе данных.
Гарантии работоспособности нет. Возврата нет. Технической поддержки нет.
Алгоритм Флойда — Уоршелла — динамический алгоритм для нахождения кратчайших расстояний между всеми вершинами взвешенного ориентированного графа. Разработан в 1962 году Робертом Флойдом и Стивеном Уоршеллом (англ.), хотя в 1959году Бернард Рой (англ.) (Bernard Roy) опубликовал практически такой же алгоритм, но это осталось незамеченным.
Обработка содержит функцию расчета пути и пример вызова.
В функцию передаётся начальная точка, конечная точка и таблица значений содержащая маршруты между точками с расстоянием между ними.
Таблица значений маршрутов должна содержать 3 колонки: "СкладОткуда", "СкладКуда" и "Расстояние".
Функция возвращает значение "Неопределено" (если нет пути) или строки из исходной таблицы значений (с маршрутами) по которым проложен путь.
Пример использования :
тзМаршруты = Новый ТаблицаЗначений;
тзМаршруты.Колонки.Добавить("СкладОткуда");
тзМаршруты.Колонки.Добавить("СкладКуда");
тзМаршруты.Колонки.Добавить("Расстояние");
ДобавитьЗапись(тзМаршруты, "Склад1", "Склад2", 1);
ДобавитьЗапись(тзМаршруты, "Склад1", "Склад3", 2);
ДобавитьЗапись(тзМаршруты, "Склад1", "Склад4", 3);
ДобавитьЗапись(тзМаршруты, "Склад3", "Склад2", 4);
ДобавитьЗапись(тзМаршруты, "Склад4", "Склад3", 5);
ДобавитьЗапись(тзМаршруты, "Склад4", "Склад5", 6);
СкладОткуда = "Склад1";
СкладКуда = "Склад5";
тзПути = КратчайшийПутьПоФлойду(СкладОткуда, СкладКуда, тзМаршруты);
Если тзПути<>Неопределено Тогда
Сообщить("Минимальный путь: "+тзПути.Итог("Расстояние"));
Сообщить("Найденные маршруты:");
Для Каждого ТекМаршрут Из тзПути Цикл
Сообщить(""+ТекМаршрут .СкладОткуда+" - "+ТекМаршрут.СкладКуда+"-"+ТекМаршрут.Расстояние);
КонецЦикла;
КонецЕсли;
На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL.
Я же покажу как можно сократить объем данных в 49.9 раз при этом:
1. Сохранить значения локальных экстремумов
2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.
Что ж... лучше поздно, чем никогда.
Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.
В статье анализируются средства платформы для решения системы линейных уравнений в 1С. Приводятся доводы в пользу некорректной работы встроенных алгоритмов, а значит потенциально некорректного расчета себестоимости в типовых конфигурациях.
Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса
Кому интересно есть продвинутая версия.
Которая умеет считать маршруты когда они не постоянные статичные.
А разные (периодические) по разным по дням недели.
Попытался сравнить быстродействие приведенного здесь метода с методом из статьи . По идее, алгоритм Флойда должен иметь сравнимое быстродействие. Его оценка трудоемкости ~O(N^3), метода "матричного умножения" ~O(Log(K)*N^3), где К - диаметр графа. Множитель Log(K) нивелируется тем, что массовые вычисления в запросе делаются "пакетом" и поэтому быстрее в 10-50 раз.
Однако столкнулся с тем, что на схеме метро функция не работает. Насколько я понял, отрезки пути, найденные алгоритмом, не находятся в исходном графе.
Прилагаю файл связности станций питерского метро, полученный сохранением в текстовом файле строки, равной ЗначениеВСтрокуВнутр(ТаблицаМаршрутов).
(6) ildarovich, боюсь некорректно сравнивать эти два метода.
Флойд долго думает, но считает сразу одновременно все длины и находит кратчайшие пути между всеми парами вершин.
Т.е. после расчета и сохранения в массивы результат выдается мгновенно для любой пары вершин.
(7) думаю, вы невнимательно прочитали , на которую я неоднократно ссылался. Это метод, решающий ту же задачу "All Pairs Shortest Paths (APSP) problem". Так же находятся кратчайшие расстояния между всеми парами вершин. Поэтому сравнивать эти решения можно и нужно.
Проблема в том, что практическая реализация метода, сделанная здесь, пока, на мой взгляд, попросту НЕ РАБОТАЕТ. Вообще не находит путь в графе, пример которого приведен в (6) (вываливается с ошибкой).
Кстати, проблема восстановления кратчайшего пути по кратчайшим расстояниям между всеми парами в решается гораздо проще. В кратчайший путь включаются все вершины ПунктПути, обладающие свойством:
Пункты упорядочиваются по КратчайшееРасстояние(Откуда, ПунктПути). При этом никаких предыдущих вершин вычислять и хранить вообще не нужно. Дополнительно это дает возможность вывода нескольких равнозначных вариантов равной длины. Затраты на проверку лишних вершин, которые потом не войдут путь, очень малы (по отношению к основным затратам метода).
(10) я взял функцию из вашей обработки, вставил в свою, получил ошибку (см.скриншоты). - Что я делаю не так?
Отладчик показал, что отрезок пути, который ищется в ТЗМаршруты, там не находится, из-за этого ТекСтр = Неопределено и функция вылетает.
Кстати, создавать колонку поиска было необязательно, достаточно было проиндексировать ТЗ по двум колонкам: тзМаршруты.Индексы.Добавить("СкладОткуда, СкладКуда").
Про
потому что 140 станций * 7 дней вершин
не понял. В Питере ~65 станций. 140 - это число связей между станциями.
В общем, хотелось бы разобраться и получить результат сравнения по скорости, не отлаживая самому вашу разработку.
(11) ildarovich, проверял на доработанном алгоритме который умеет считать маршруты между складами когда они не по каждым дням недели ездят.
Причем с ожиданием если в этот день недели когда приехали нет маршрутов отправления.
для простоты проверил на доработанном, там из екселя как раз загрузка идет, при расчете он каждую вершину (склад, станцию) превращает в 7 по количеству дней в неделе, и даты которые показывает это сколько дней едем
и да ошибся не 140*7, а 65*7
насчет ошибки все правильно, восстановление пути для Флойда возможно двумя способами :)
в выложенном сделан "...В этом случае значение массива C[j][k] после окончания алгоритма будет указывать одну из вершин, через которую проходит путь от j к k ..."
выложенный алгоритм правильно считает кратчайший путь, но не всегда может его восстановить
(12) в общем, пришлось свою реализацию сделать. Вот что получилось у меня:
Функция КратчайшийПутьФлойд(Откуда, Куда, Дуги) Экспорт
// загрузка графа в "соответствие соответствий" так, что Пути[Откуда][Куда] = Длина
Пути = Новый Соответствие;
Для каждого Дуга Из Дуги Цикл
Пути[Дуга.Откуда] = ?(Пути[Дуга.Откуда] = Неопределено, Новый Соответствие, Пути[Дуга.Откуда]);
Пути[Дуга.Откуда][Дуга.Куда] = Дуга.Длина
КонецЦикла;
// три вложенных цикла по узлам графа
Для каждого Узел1 Из Пути Цикл // тогда Узел.Ключ - это одна вершина из полного множества вершин
Для каждого Узел2 Из Пути Цикл
Если Пути[Узел2.Ключ][Узел1.Ключ] <> Неопределено Тогда
Для каждого Узел3 Из Узел1.Значение Цикл // здесь только вершины, связанные с Узел1.Ключ
Длина = Пути[Узел2.Ключ][Узел3.Ключ];
Обход = Пути[Узел2.Ключ][Узел1.Ключ] + Узел3.Значение; // Узел3.Значение == Пути[Узел1.Ключ][Узел3.Ключ]
Пути[Узел2.Ключ][Узел3.Ключ] = ?(Длина = Неопределено, Обход, Мин(Длина, Обход))
КонецЦикла
КонецЕсли
КонецЦикла
КонецЦикла;
// восстановление пути
Путь = Дуги.СкопироватьКолонки("Куда, Длина");
Путь.Добавить().Куда = Откуда;
Путь.Добавить().Куда = Куда;
Путь[1].Длина = Пути[Откуда][Куда];
Для каждого Узел Из Пути Цикл
Если Пути[Откуда][Узел.Ключ] <> Неопределено И Пути[Узел.Ключ][Куда] <> Неопределено
И Пути[Откуда][Узел.Ключ] + Пути[Узел.Ключ][Куда] = Пути[Откуда][Куда] Тогда
ЗаполнитьЗначенияСвойств(Путь.Добавить(), Новый Структура("Куда, Длина", Узел.Ключ, Пути[Откуда][Узел.Ключ]))
КонецЕсли
КонецЦикла;
Путь.Сортировать("Длина");
Возврат Путь
КонецФункции // КратчайшийПуть()
Показать
На примере московского метро примерно на 30% быстрее запроса получается.
По ходу дела нашел на ИС статью на смежную тему: . В статье также заявлена и реализация Флойда.
... Ну и еще. Поскольку , попробовал, как и автор, на всякий случай вариант с массивом:
Функция КратчайшийПуть(Откуда, Куда, Дуги) Экспорт
// нумерация вершин
Номер = Новый Соответствие;
Номер[Откуда] = 0;
Номер[Куда ] = 1; // Если Откуда = Куда Тогда Возврат Новый ТаблицаЗначений КонецЕсли;
Для каждого Дуга Из Дуги Цикл
Номер[Дуга.Откуда] = ?(Номер[Дуга.Откуда] = Неопределено, Номер.Количество(), Номер[Дуга.Откуда]);
Номер[Дуга.Куда ] = ?(Номер[Дуга.Куда ] = Неопределено, Номер.Количество(), Номер[Дуга.Куда ])
КонецЦикла;
// инициализация массива-матрицы инцидентности
ВГраница = Номер.Количество() - 1;
Пути = Новый Массив(ВГраница + 1, ВГраница + 1);
Много = 999999999;
Для ё = 0 По ВГраница Цикл
Для ж = 0 По ВГраница Цикл
Пути[ё][ж] = ?(ё = ж, 0, Много)
КонецЦикла
КонецЦикла;
// загрузка графа в массив
Для каждого Дуга Из Дуги Цикл
Пути[Номер[Дуга.Откуда]][Номер[Дуга.Куда]] = Дуга.Длина
КонецЦикла;
// тело алгоритма Флойда-Уоршолла
Для к = 0 По ВГраница Цикл
Для ё = 0 По ВГраница Цикл
Для ж = 0 По ВГраница Цикл
Пути[ё][ж] = Мин(Пути[ё][ж], Пути[ё][к] + Пути[к][ж])
КонецЦикла
КонецЦикла
КонецЦикла;
// восстановление пути
Путь = Дуги.СкопироватьКолонки("Куда, Длина");
Для каждого Элемент Из Номер Цикл
Если Пути[0][Элемент.Значение] + Пути[Элемент.Значение][1] = Пути[0][1] Тогда
ЗаполнитьЗначенияСвойств(Путь.Добавить(), Новый Структура("Куда, Длина", Элемент.Ключ, Пути[0][Элемент.Значение]))
КонецЕсли
КонецЦикла;
Путь.Сортировать("Длина");
Возврат Путь
КонецФункции // КратчайшийПуть()
Показать
Но получилось медленнее (в два раза к запросу)! Наверное, из-за экономия на переборе во вложенном цикле, где при использовании соответствия учитываются только существующие на данной итерации связи. В итоге для большой реальной задачи все же рекомендую использовать вариант с соответствием. Он на данный момент самый быстрый, да и кода там меньше.
(13) ildarovich, на 30% быстрее получилось потому что соединили алгоритмы Флойда и Дейкстры.
И еще потому что вершин и ребер мало. Особенно потому что количество ребер практически равно количеству вершин - линии метро однако.
Попробуйте на 500 вершинах и 5000 ребер? Запрос в этом случае умрет, вариант с соответствием будем в 2-2.5 раза медленнее чем с массивами. Точно будет зависеть от отношения количества вершин к количеству ребер.
Это не так. В алгоритме Дейкстры требуется минимум в неразвитых ветвях искать. Здесь поиска минимума и развития ветвей нет.
Какая разница каким образом оптимизировать алгоритм?
Алгоритм Дейкстры просматривает ребра (получая из них вершины), обычный Флойда все вершины парами (не важно есть ли между ними ребро).
Модернизированный Флойд:
"Но существует решение и за \sum_{n,\;n,\;n}O(1) = O(n^2), где хранятся значения не для всех вершин, а только значения для предыдущей вершины, так как следующая получается рекурсивно."
Я написал это, чтобы побудить вас поспорить на что-нибудь, чтобы мне было интереснее сравнительное тестирование провести. Задача я бы не сказал, чтобы популярная, поэтому пока не решил, стоит ли этим заниматься.
Статью в Википедии я и раньше видел, этот оборот (про N^2) не понял, честно говоря (источник там не указан). В английской версии этой фразы нет. Если вы поняли о чем там речь или знаете где можно про прочитать, подскажите.
Так что битовые маски не ЕЩЕ быстрее, а просто быстрее. Ну а так как битовых масок в 1С нет, то соответствие а последнем цикле и играет роль маски - позволяет не проверять не существующие дуги.
(17) ildarovich, понимаете мне это тестирование совершенно неинтересно.
Потому что прекрасно понимаю что при разных исходных данных будет разный результат.
Про N^2 это то что вы и сделали по сути.
Просто за счет "Если Пути[Узел2.Ключ][Узел1.Ключ] <> Неопределено Тогда" исключили из алгоритма обработку несуществующих ребер.
Если число ребер во много раз больше чем число вершин эта доработка за счет лишнего действия (проверка по условию в выниманием значения из структур и сравнение) даст замедление.
А битовые маски это то что и сделали (доп условие перед 3-м циклом) только проверка очень быстрая с помощью бинарных операций.
Бинарные операции в 1С реализуемы через числа и деление нацело с остатком (%).
ЗЫ при операциях с получением данных из памяти, в случае массива нужное значение (адрес ячейки) получается просто умножением, в случае разных коллекций (в т.ч. структура) используются "ключи"
получение данных "по ключу" медленнее, так как нужно преобразовать значение ключа в адрес ячейки со значением
но это существенно сказывается только с большими наборами данных
ЗЗЫ еще тонкость с 1С, когда запускают тестирование из "конфигуратора через отладку", и напрямую запускают "режим предприятия"
в этом случае отладчик слегка портит результаты
