Заслуженно или нет, но задача поиска кратчайшего пути в графе получила широкую популярность. Она часто рассматривается в учебниках по программированию. Алгоритм поиска кратчайшего пути чаще других непростых алгоритмов приходится вспоминать и на практике. Поэтому будет интересным рассмотреть решение этой задачи не совсем обычным способом: с помощью языка запросов 1С. Тем более, что и исходные данные и результат решения задачи представляют собой таблицы.
Исходные данные задачи поиска кратчайшего пути в графе представляют собой таблицу G дуг графа и их весов как расстояний, соединяющих пункты — вершины графа
|
i |
V |
W |
F |
|
1 |
V1 |
W1 |
F1 |
|
2 |
V2 |
W2 |
F2 |
|
… |
… |
… |
… |
|
m |
Vm |
Wm |
Fm |
и параметры &А, &Б, задающие начальную и конечную вершины пути.
В задаче требуется определить путь P – таблицу вида
|
i |
V |
|
1 |
&A |
|
2 |
V2 |
|
3 |
V3 |
|
… |
… |
|
k |
&B |
такой, чтобы сумма расстояний переходов между пунктами на этом пути была минимальной по сравнению с другими возможными путями, соединяющими пункты &A и &B.
В реальности расстояние Fi не обязательно должно быть именно длиной перехода в геометрическом смысле. Это может быть еще или время или стоимость – то, чем предпочтительнее измерить величину затрат на перемещение между пунктами. То есть задачи выбора самого короткого или самого быстрого или самого дешевого маршрута перемещения – это тоже задачи поиска кратчайшего пути.
Предлагаемый алгоритм состоит из пролога, рефрена и эпилога.
Пролог заключается в том, что к строкам исходной таблицы приписываются (union) строки таблицы
|
i |
V |
W |
F |
|
1 |
V1 |
V1 |
0 |
|
2 |
V2 |
V2 |
0 |
|
… |
… |
… |
0 |
|
n |
Vn |
Vn |
0 |
по числу вершин в графе.
Для этого используется запрос
SELECT V, W, F
INTO G1
FROM G
UNION
SELECT V, V, 0
FROM G
UNION
SELECT W, W, 0
FROM G
Рефрен состоит в том, чтобы соединить полученную на предыдущем шаге таблицу саму с собой по условию равенства конца дуги первого образа с началом дуги второго образа. При этом формируются все возможные пути из соединения пар смежных дуг. Сгруппировав полученное произведение таблиц по началу первой и концу второй дуги и выбрав агрегатной функцией минимумы сумм длин состыкованных дуг, мы получим таблицу минимальных расстояний для путей длины в две дуги (и менее). Очень важным является наличие в соединяемых таблицах строк вида (Vi, Vi, 0), отражающих соединение каждой вершины самой с собой путем нулевой длины. Именно их наличие включает во множество путей, из которых выбирается минимум, пути меньшей длины и, таким образом, помогает «накапливать» результат.
Рефрен состоит в выполнении запроса
SELECT L.V, H.W, MIN(L.F + H.F) AS F
INTO G2
FROM G1 AS L
JOIN G1 AS H
ON L.W = H.V
GROUP BY L.V, H.W
При каждом повторении рефрена охват длин путей будет увеличиваться в два раза, поэтому рефрен нужно повторить минимум ]Log2(N)[ раз, где N – число вершин или известный «диаметр» графа.
После завершения повторов рефрена таблица будет содержать минимальные расстояния между парами всех транзитивно-связанных вершин.
Теперь, чтобы выбрать собственно путь, нужно выбрать вершины графа по условию, чтобы сумма расстояния до нее от начальной вершины пути &A и расстояния от нее до конечной вершины &B была равна длине найденного кратчайшеuj пути. Первый элемент суммы также удобно использовать для упорядочивания пунктов найденного пути. Таким образом, эпилог запроса выглядит следующим образом:
SELECT H.V, L.F
FROM G2 AS L
JOIN G2 AS H
ON L.W = H.V
JOIN (SELECT F FROM G2 WHERE V = &a AND W = &b) AS X
ON (X.F = L.F + H.F)
WHERE L.V = &a AND H.W = &b
ORDER BY L.F
Безусловно, предложенный алгоритм не претендует на рекорд быстродействия. С точки зрения определения кратчайшего расстояния между конкретной парой вершин он довольно избыточен, поскольку требует на промежуточном этапе определения и запоминания кратчайшего расстояния между всеми транзитивно-связанными вершинами графа.
Но, во-первых, эту операцию можно выполнять один раз, сохранив ее результат в базе данных. В расчете на каждую пару вершин, между всеми которыми будет сразу определено минимальное расстояние, алгоритм весьма эффективен.
А, во-вторых, при относительно небольших размерах графа в 100-200 вершин, лишними затратами можно попросту пренебречь, взамен получив очень несложный и удобный алгоритм.
Ну и, в третьих, еще есть возможности оптимизации алгоритма путем его некоторого усложнения.
Тот же алгоритм позволяет определить и критический путь.
Под критическим путем понимается путь из заданной вершины &A в вершину &B, сумма расстояний переходов между пунктами на котором МАКСИМАЛЬНА. Определение «критического пути» используется тогда, когда исходный граф представляет собой сетевой график какого-либо комплекса работ (проекта). Этот путь показывает ключевые (критические) работы проекта, продолжительность выполнения которых непосредственно влияет на время выполнения проекта в целом. Чтобы определить критический путь, можно даже не переписывать приведенный запрос, заменяя агрегатную функцию с функции МИНИМУМ на МАКСИМУМ. Достаточно в исходной таблице использовать отрицательные значения расстояний.
Для того, чтобы работа алгоритма была понятнее, приведем весь запрос целиком в записи на русском языке для случая ограничения длины искомого пути тридцатью двумя дугами (этого достаточно, например, для московского и питерского метро).
ВЫБРАТЬ G.V, G.W, G.F
ПОМЕСТИТЬ G
ИЗ &G КАК G
;
ВЫБРАТЬ V, W, F
ПОМЕСТИТЬ G1
ИЗ G
ОБЪЕДИНИТЬ
ВЫБРАТЬ V, V, 0
ИЗ G
ОБЪЕДИНИТЬ
ВЫБРАТЬ W, W, 0
ИЗ G
;
ВЫБРАТЬ L.V, H.W, МИНИМУМ(L.F + H.F) КАК F
ПОМЕСТИТЬ G2
ИЗ G1 КАК L СОЕДИНЕНИЕ G1 КАК H ПО L.W = H.V
СГРУППИРОВАТЬ ПО L.V, H.W
;
ВЫБРАТЬ L.V, H.W, МИНИМУМ(L.F + H.F) КАК F
ПОМЕСТИТЬ G4
ИЗ G2 КАК L СОЕДИНЕНИЕ G2 КАК H ПО L.W = H.V
СГРУППИРОВАТЬ ПО L.V, H.W
;
ВЫБРАТЬ L.V, H.W, МИНИМУМ(L.F + H.F) КАК F
ПОМЕСТИТЬ G8
ИЗ G4 КАК L СОЕДИНЕНИЕ G4 КАК H ПО L.W = H.V
СГРУППИРОВАТЬ ПО L.V, H.W
;
ВЫБРАТЬ L.V, H.W, МИНИМУМ(L.F + H.F) КАК F
ПОМЕСТИТЬ G16
ИЗ G8 КАК L СОЕДИНЕНИЕ G8 КАК H ПО L.W = H.V
СГРУППИРОВАТЬ ПО L.V, H.W
;
ВЫБРАТЬ L.V, H.W, МИНИМУМ(L.F + H.F) КАК F
ПОМЕСТИТЬ G32
ИЗ G16 КАК L СОЕДИНЕНИЕ G16 КАК H ПО L.W = H.V
СГРУППИРОВАТЬ ПО L.V, H.W
;
ВЫБРАТЬ F
ПОМЕСТИТЬ X
ИЗ G32 КАК G2
ГДЕ V = &a И W = &b
;
ВЫБРАТЬ H.V, L.F
ИЗ G32 КАК L СОЕДИНЕНИЕ G32 КАК H ПО L.W = H.V СОЕДИНЕНИЕ X ПО (X.F = L.F + H.F)
ГДЕ L.V = &a И H.W = &b
УПОРЯДОЧИТЬ ПО L.F
На следующем рисунке приведена последовательность шагов 1-5 определения кратчайшего пути между вершиной 1 и 17 в графе, вершины которого связаны последовательно: 1-2-3-4-5-6-7-8-9-10-11-12-13-14-15-16-17.
Для тестирования предложенного алгоритма приведена обработка «Путепровод». Она позволяет задавать дуги графа и их вес и находить кратчайший или критический путь. Кроме того, в обработке запрограммирована возможность автоматически заполнить таблицу исходных данных связями станций московского или питерского метро. Тогда с помощью нее можно находить кратчайший путь между заданными станциями метро.
Related Posts
Получение логина и пароля техподдержки 1С из базы
Класс для вывода отчета в Excel
Счет-фактура для УПП
Библиотека классов для создания внешней компоненты 1С на C#- Акт об оказании услуг (со скидками) — внешняя печатная форма для Управление торговлей 11.1.10.86
Прайс-лист с артикулом в отдельной колонке
Сын (6 лет) подходит к отцу и спрашивает:
— Папа, а почему когда я откусываю яблоко, оно становится потом коричневым?
— Сынок, очень хорошо, что ты задаешь такие вопросы. Видишь ли, яблоко содержит очень много химического элемента феррум, который при контакте с кислородом в воздухе, которым мы дышим образует оксид железа Fe2O3, который в свою очередь имеет тот самый коричневый цвет.
— ?!? Папа, а ты с кем сейчас разговаривал ?
Я глубоко уважаю автора статьи, за недюжинные познания в математике и теории алгоритмов. Даже некоторыми идеями пользовался в работе (которые смог понять).
Всякий раз упиваюсь стилем изложения, но нихрена не понимаю ни с первого ни 10-го раза. Видимо из-за того, что не имею профильного математического образования.
А так да — очень полезный материал… наверное.
Жду следующих публикаций -)))
(1) Анекдот смешной и точный. Тем более, что я сам, когда смотрю со стороны, замечаю за отечественными авторами желание блеснуть ученостью и само-выразиться вместо того, чтобы объяснить по-простому. Видимо, это заразно. Буду исправляться.
В свое оправдание могу сказать, что я изначально не пишу свои публикации как tutorial (учебные пособия), хотя они могут казаться таковыми. Как правило, в каждой публикации я привожу открытый лично мной НОВЫЙ прием решения известной задачи. И надеюсь, в первую очередь, заинтересовать тех, кто уже мучился с этой задачей, то есть более-менее знает, о чем идет речь.
С этой стороны я больше чувствую себя в роли Шарика из Простоквашино, который, сделав своим подарочным фоторужьем удачную фотографию (а я изобрел прием), теперь бегает по лесу, пытаясь вручить эти фотографии (объяснить суть нового приема). Это не легко.
Но мне было бы легче, если бы задавались вопросы, что именно непонятно.
(1)
Это вы балованные. Он то как раз объясняет толково. Тут полно народу с худшим стилем изложения.
— Папа, а почему когда я откусываю яблоко, оно становится потом коричневым?
— Сынок, очень хорошо, что ты задаешь такие вопросы. Видишь ли, яблоко содержит очень много химического элемента феррум, который при контакте с кислородом в воздухе, которым мы дышим образует оксид железа Fe2O3, который в свою очередь имеет тот самый коричневый цвет.
— ?!? Папа, а ты с кем сейчас разговаривал ?
Я глубоко уважаю автора статьи, за недюжинные познания в математике и теории алгоритмов. Даже некоторыми идеями пользовался в работе (которые смог понять).
Всякий раз упиваюсь стилем изложения, но нихрена не понимаю ни с первого ни 10-го раза. Видимо из-за того, что не имею профильного математического образования.
А так да — очень полезный материал… наверное.
Жду следующих публикаций -)))
(1) Makushimo, спасибо за комментарий, улыбнуло
(2) с видом на размещение в хабре писалось ?
(5) Нет, для Хабра нужно будет дописывать и переписывать. Подобрать хороший пример для поиска критического пути в сетевом графике, связанном с управлением проектами и сделать акцент именно на критическом пути. Так как для кратчайшего пути, особенно в транспортной системе, где все вершины транзитивно связаны, метод работает слишком медленно. В московском метро на расчет пути уходит целых 23 секунды (правда, при этом одновременно находятся все оптимальные пути!). Нарисовать графы. Просчитать пример последовательности таблиц. Мне кажется, для Хабра моих статей пока достаточно.
Просто хотел выполнить обещание, данное в одной из прошлых статей, прежде чем переходить к другим темам.
(6) а по-моему благодатная тема для хабра, то что надо шлифануть текст и пример — соглашусь
(2) Не надо оправдываться, редко попадаются статьи которые заставляют напрягаться мозг.
(6) мне вот интересно, сколько у вас свободного времени?)) с трудом нахожу время чтобы прочесть и вникнуть в ваши статьи, представляю сколько времени нужно чтобы их написать, да еще обработки для примера сделать. Спасибо за статью. В университете в свое время занимался вопросом создания алгоритма для квантового компьютера, для решения задачи коммивояжера, поэтому эта статься мне особенно интересна)
(9) Времени как у всех, когда на носу нет дедлайнов. Если не смотреть телевизор, его достаточно, тем более, если смотреть на решение задач как на развлечение. На самом деле на статью уходит не так много времени: один — два вечера, иногда больше. В моих обработках не так много кода. А обдумывать решение можно сколько угодно долго, но по дороге, а не за компьютером.
Восхищаюсь автором и некоторыми другими присутствующими на ИС личностями, которые без зазнайства демонстрируют уровень математического мышления выше среднего.
(8) awk,
Вот маячит передо мной задача, внешне похожая на графы и поиск кратчайшего пути.
А вот не знаю как к ней подойти, с какого боку.
Вот на инфостарте статья (и не одна) на эту тему. Чую что тут ответ есть.
Но для этого нужно понять суть предлагаемого решения, чтобы взять алгоритм, потому что решение один в один не подойдет. Нужно понимание такого мышления в решении таких задач.
Статью прочитал, мозг напряг, а толку.
Лайк автору и пойду изобретать вилосипед сам.
Мне как-то сказали: «если ты что-то узнал и не смог этому обучить другого, толку в твоем знании ноль». Для меня это верное утверждение.
На работе я стараюсь писать подробные туториалы на проблему, которую никто не смог (не захотел) решить, если сам или совместными усилиями она была решена.
Конкретные вопросы появятся, когда я свою проблему буду решать непосредственно (ни шагу назад, позади Москва). Надеюсь, автор не откажет в консультациях.
На мой взгляд, практического эффекта это решение не вносит. При увеличении точек, время расчета будет расти по экспоненте и приближаться к бесконечности… К тому же тут расчет зиждется на транзитивности, а по факту расстояние между А и Б может сильно отличаться от Б к А и быть не прямым.
Стоит ли тратить время на решение бесполезных задач.
С точки зрения специфик математических задач, то их решение вообще неприемлемо считать в языках высокого уровня или средствами запросов SQL, т.к. по факту, на примере данной задачи, если её развернуть до низкого уровня будет: банальное сложение всех точек между собой + огромное число ненужных операций.
(13) Я бы сказал, что решение имеет ограниченную область применения. Его можно применять тогда, когда число точек относительно невелико (до 100-200 в компонентах связности). Вы же, например, не отказываетесь вообще использовать чайную ложечку, хотя ей трудно поливать огород. Определить оптимальный порядок обновления релизов конфигураций, оптимальный маршрут перелетов с пересадками, маршрут поездки в питерском метро, критический путь в проекте обычного размера — все это задачи, доступные методу.
При увеличении числа вершин время расчета будет расти не по экспоненте, а как O(ln(N)*N#k8SjZc9Dxk2) или O(ln(N)*N#k8SjZc9Dxk4).
Любое решение этой задачи не обойдется без транзитивности. Случай, когда расстояние А->Б и Б->А разные, в этом решении прекрасно отрабатывается (про непрямое расстояние не понял).
У математических задач нет единой специфики. На языках высокого уровня подавляющее большинство из них прекрасно решаются, а иногда и средствами запросов SQL. Тут не должно быть предубеждений. Для каждой задачи можно взять метод, произвести оценку его сложности и трудоемкости и, если они удовлетворительны, применять этот метод, не взирая на выразительные средства решения.
В последнее время стал активно читать ваши статьи и действительно получается вникнуть и понять разбираемые темы. Спасибо за Ваш труд!)
Интересно было посмотреть конфигурацию где все это используется.
Автору огромный плюс за статью. Решение задач оптимизации на любом языке будет иметь ограничение по времени при увеличении числа элементов (это в поддержку). Для меня ценность данной статьи именно в НОВОМ методе и взгляде на задачу поиска пути, потому как самому приходилось реализовывать задачу оптимизации (не на 1с). Что касается практического применения, так это только вопрос времени, когда известен инструмент, то и задачи быстро найдутся. Я, например, стараюсь по максимуму выносить всю логику в запросы где это возможно.
Статья, не смотря на свой небольшой объем, очень «сильная», единственное, что я бы добавил, так это ссылки на литературу (если такая имеется). По подаче я бы не сказал, что все очень мудрено написано, т.к. все равно надо «щупать», а для понимания общей идеи достаточно.
+ + +
Интересные решения на запросах. Может, когда будет критично по времени исполнения где-нибудь пригодится.
«С точки зрения определения кратчайшего расстояния между конкретной парой вершин он довольно избыточен, поскольку требует на промежуточном этапе определения и запоминания кратчайшего расстояния между всеми транзитивно-связанными вершинами графа.
Но, во-первых, эту операцию можно выполнять один раз, сохранив ее результат в базе данных.»
Уважаемый Сергей, я верно понимаю, что при добавлении новой вершины графа (станции метро, точки маршрута, локации на карте и т.д.), нужно будет производить этот расчет для всех транзитивно-связанных элементов?
К вопросу хранения таких данных — чтобы оптимизировать скорость работы алгоритма, нужно хранить минимальное расстояние на каждую пару вершин, тогда можно быстро получить результат для искомой пары. Допустим, эту задачу можно решить с помощью регистра сведений. Но каждый раз, при добавлении новой вершины — думаю, не надо объяснять, что будет с размером таблицы… И чем длиннее цепочка связанных графов — тем огромнее будет таблица. Все верно?
(19) Dach, да, все правильно. Нужно будет хранить минимальное расстояние для каждой пары вершин. Число строк в «огромной таблице» — N*(N — 1) / 2, где N — число узлов транспортной сети. Если число вершин — 1000, то строк в таблице будет 500 000. Не так уж и много, на самом деле.
Но все же алгоритм предназначен, в первую очередь, для небольших графов — не более 250 — 300 вершин. Это может быть схема метро, схема движения между стеллажами на складе, диаграмма состояний объекта управления и так далее.
Ну и обратите внимание на задачу нахождения критического пути, которую можно применять при управлении проектами — там тоже подходящее число вершин.
У меня, кстати, есть обработка, которая построена на базе того же алгоритма, распределяющая заказы (привязанные к станциям метро) между курьерами. Вполне практичная вещь. Работает очень быстро именно за счет сохранения матрицы минимальных расстояний в параметрах обработки.
(2) мне кажется, что сложность восприятия возникает из-за нарушения одинэсовских шаблонов:
1. Русский язык
2. Названия переменных обозначающие их содержимое
3. Каждое выбираемое поле в отдельной строке
Ну и гольная математика, вместо решения конкретной понятной задачи тоже не облегчает понимание.
Что лучше: тренировка мозга или быстрое простое понимание? Вопрос философский на мой взгляд.
Но вообще тема благородная. Мне правда для планирования бизнеспроцессов нужна была обратная задача — по поиску длинейшего пути, но суть примерно та же и с помощью запросов все считается мгновенно.
Вот только для длинейшего пути возникает дополнительная задача по определению зацикливания процесса. И вот как ее решить, чтоб работало быстро и наглядно (чтобы можно было вывести «кольцо», чтобы пользователь его исправил) я пока придумать не могу.
То бишь в приведенном примере для метро критический путь будет некорректным, потому что в метро можно ездить бесконечно.
П.С. Сорри за ворошение старой темы — почему-то инфостарт ее кинул в новое, а на даты я сначала не посмотрел.
(21) friend0, да, наверное, нужно было данную статью попонятнее написать. Учту на будущее.
В T-SQL такого требования нет, колонки в таблицах рядом, их естественно записывать рядом, а то, что конструктор запросов 1С не так форматирует текст запроса вызывает необходимость мысленного транспонирования колонок и очень сильно увеличивает число строк в запросе. Тут я бы хотел, чтобы форматирование текста запроса было настраиваемым и можно было выбирать кому как удобнее. В общем, это дело привычки и не нужно быть ее рабом. В общем, все за и против хождения строем я понимаю, но тут решил повыделываться.
Что касается обратной задачи, то она здесь названа задачей поиска критического пути и так же решена простой заменой МИНИМУМА на МАКСИМУМ.
Я, честно говоря, скомкал ее описание вот почему: не нашел примера интересного сетевого графика, который можно было проанализировать. Хотя искал очень-очень долго, поверьте. Вы удивитесь, но хорошего наглядного интересного примера нет! Есть приготовление завтрака (всякие там скипятим воду, поджарим яичницу), есть строительство дома (выроем котлован, завезем металлоконструкции), есть проект с несколькими работами. Все остальное — учебные абстракции. И где эти реальные интересные сетевые графики, пример анализа данным алгоритмом можно показать, я не знаю — подскажите! При том, что ProjectManager в работе часто использую, но взять что-либо оттуда тоже не смог.
Это не Инфостарт кинул тему в новые, а я сам, заплатив некоторое количество стартманей. Так тут и делается, иначе статьи забываются.
(21) friend0, насчет анализа циклов: как решается эта задача описано в другой, более ранней статье .
Надо будет почитать, а пока возьмусь комментировать комментарии 🙂
1. 23 секунды на несильно связный граф… Или модель данных неверная, или я прям не знаю. Перебор даёт 1е6 простых вычислений в секунду (это я в цикле погонял и понял, что встроенный язык не так плох). 120, кажется, станций. 120*119 (если туда<>обратно) = 1.4е4 За (1е6/1.4е4 = 700 вычислений мы успеем сложить все пути в табличку) Годится ИМХО только если даный способ даст гарантированное решение любой задачи из широкого класса.
А вот задача прикладная, кажется, есть. Сейчас сформулирую и вечером попробую написать.
(22) про наглядный пример я как-то даже и не знаю, мне это и на уровне Этап1, Этап2 достаточно. Собственно у себя я сделал спровочник этапов с ТЧ с предшествующими этапами и отдал юзерам — какие хотят проекты делать, такие пускай и делают. Мое дело по длительности этапов в рабочих днях вычислить дату завершения каждого этапа. Это если упрощенно. На самом деле там еще всякие заморочки, что по некоторым этапам наоборот задается жесткая дата окончания и надо вычислить длительность, плюс сразу посчитать дату окончания группы этапов и т.д.
Но даже со всеми наворотами и без особых заморочек с оптимизацией: 11 тыщ этапов (примерно по 40 на проект, 1-2 предшествующих, МаксимальнаяДлинаЗамыканий = 64 ) считаются за 1.5-2 секунды.
За ссылку спасибо — я уже и забыл, что там оно было.
Ваши статьи конечно интересные, с точки зрения умственного развития, но я не могу понять одного — почему эти задачи нужно решать именно в запросе? Если запросом выбрать нужные данные, а потом в коде обработать, разве не проще будет? А еще потом это кому-нибудь придется поддерживать…
Язык запросов — штука могучая, но злоупотреблять ею можно лишь из праздного интереса и развлечения ради. Понятно, что данная задача решается и иначе за куда меньшее время. Но для 1С пойдет )))
(26) I_G_O_R, как обычно все зависит от масштабов. Если исходных данных 10000 строк, а в результате нужно 100, то только чтоб передать с сервера 10000 строк уйдет уйма времени. А поддерживать — на мой взгляд запрос нагляднее (если написан красиво без иксов и игреков).
(1) Makushimo. В общем-то самое важное, что идеи-то имеют практическое применение. Это чрезвычайная редкость. Обычно просто люди умничают, но чтобы применить на практике результаты этих измышлений чего-то не хватает. В случае же со статьями Сергея — все очень даже применяется на практике. Я применил пару теорий для разработки решений и внедрил их в работу нашей довольно не мелкой, но в общем-то, заурядной торговой организации. Отлично все работает. Этим решился ряд серьезных проблем и отпала необходимость в использовании традиционных, более громоздких, алгоритмов.
нужная вещь
(17)
для чего?