Определение кратчайших путей, критических путей одним запросом

Публикация № 271270

Разработка - Математика и алгоритмы

Граф кратчайший путь кратчайшее расстояние запрос

Еще два примера применения алгоритма каскадного матричного умножения, впервые описанного в статье «Транзитивное замыкание запросом» http://infostart.ru/public/158512/

Заслуженно или нет, но задача поиска кратчайшего пути в графе получила широкую популярность. Она часто рассматривается в учебниках по программированию. Алгоритм поиска кратчайшего пути чаще других непростых алгоритмов приходится вспоминать и на практике. Поэтому будет интересным рассмотреть решение этой задачи не совсем обычным способом: с помощью языка запросов 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.

Рисунок последовательности шагов

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

Скачать файлы

Наименование Файл Версия Размер
Отчет для нахождения кратчайшего расстояния и критического пути

.erf 22,18Kb
18.10.14
61
.erf 22,18Kb 61 Скачать

Специальные предложения

Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. Makushimo 157 09.04.14 11:21 Сейчас в теме
Сын (6 лет) подходит к отцу и спрашивает:
- Папа, а почему когда я откусываю яблоко, оно становится потом коричневым?
- Сынок, очень хорошо, что ты задаешь такие вопросы. Видишь ли, яблоко содержит очень много химического элемента феррум, который при контакте с кислородом в воздухе, которым мы дышим образует оксид железа Fe2O3, который в свою очередь имеет тот самый коричневый цвет.
- ?!? Папа, а ты с кем сейчас разговаривал ?

Я глубоко уважаю автора статьи, за недюжинные познания в математике и теории алгоритмов. Даже некоторыми идеями пользовался в работе (которые смог понять).

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

А так да - очень полезный материал... наверное.
Жду следующих публикаций -)))
McLer; creatermc; le0nid; Korolev; Prometeus2011; starik-2005; BigRig; It-developer; tindir; flyDrag; amon_ra; logarifm; Aspire1C; spetzpozh; tehas; ClockMaster; AllexSoft; moreZ; +18 2 Ответить
2. ildarovich 7120 10.04.14 13:42 Сейчас в теме
(1) Анекдот смешной и точный. Тем более, что я сам, когда смотрю со стороны, замечаю за отечественными авторами желание блеснуть ученостью и само-выразиться вместо того, чтобы объяснить по-простому. Видимо, это заразно. Буду исправляться.
В свое оправдание могу сказать, что я изначально не пишу свои публикации как tutorial (учебные пособия), хотя они могут казаться таковыми. Как правило, в каждой публикации я привожу открытый лично мной НОВЫЙ прием решения известной задачи. И надеюсь, в первую очередь, заинтересовать тех, кто уже мучился с этой задачей, то есть более-менее знает, о чем идет речь.
С этой стороны я больше чувствую себя в роли Шарика из Простоквашино, который, сделав своим подарочным фоторужьем удачную фотографию (а я изобрел прием), теперь бегает по лесу, пытаясь вручить эти фотографии (объяснить суть нового приема). Это не легко.
Но мне было бы легче, если бы задавались вопросы, что именно непонятно.
pm74; МихаилМ; +2 Ответить
5. AllexSoft 10.04.14 17:10 Сейчас в теме
(2) с видом на размещение в хабре писалось ?
6. ildarovich 7120 10.04.14 17:24 Сейчас в теме
(5) Нет, для Хабра нужно будет дописывать и переписывать. Подобрать хороший пример для поиска критического пути в сетевом графике, связанном с управлением проектами и сделать акцент именно на критическом пути. Так как для кратчайшего пути, особенно в транспортной системе, где все вершины транзитивно связаны, метод работает слишком медленно. В московском метро на расчет пути уходит целых 23 секунды (правда, при этом одновременно находятся все оптимальные пути!). Нарисовать графы. Просчитать пример последовательности таблиц. Мне кажется, для Хабра моих статей пока достаточно.
Просто хотел выполнить обещание, данное в одной из прошлых статей, прежде чем переходить к другим темам.
7. AllexSoft 10.04.14 17:50 Сейчас в теме
(6) а по-моему благодатная тема для хабра, то что надо шлифануть текст и пример - соглашусь
9. Vo-Va 169 11.04.14 13:37 Сейчас в теме
(6) мне вот интересно, сколько у вас свободного времени?)) с трудом нахожу время чтобы прочесть и вникнуть в ваши статьи, представляю сколько времени нужно чтобы их написать, да еще обработки для примера сделать. Спасибо за статью. В университете в свое время занимался вопросом создания алгоритма для квантового компьютера, для решения задачи коммивояжера, поэтому эта статься мне особенно интересна)
10. ildarovich 7120 11.04.14 15:47 Сейчас в теме
(9) Времени как у всех, когда на носу нет дедлайнов. Если не смотреть телевизор, его достаточно, тем более, если смотреть на решение задач как на развлечение. На самом деле на статью уходит не так много времени: один - два вечера, иногда больше. В моих обработках не так много кода. А обдумывать решение можно сколько угодно долго, но по дороге, а не за компьютером.
shmellevich; agrustny; Vo-Va; awk; AllexSoft; +5 Ответить
8. awk 722 10.04.14 22:32 Сейчас в теме
(2) Не надо оправдываться, редко попадаются статьи которые заставляют напрягаться мозг.
12. Makushimo 157 16.04.14 06:03 Сейчас в теме
(8) awk,
Вот маячит передо мной задача, внешне похожая на графы и поиск кратчайшего пути.
А вот не знаю как к ней подойти, с какого боку.
Вот на инфостарте статья (и не одна) на эту тему. Чую что тут ответ есть.
Но для этого нужно понять суть предлагаемого решения, чтобы взять алгоритм, потому что решение один в один не подойдет. Нужно понимание такого мышления в решении таких задач.
Статью прочитал, мозг напряг, а толку.
Лайк автору и пойду изобретать вилосипед сам.

Мне как-то сказали: "если ты что-то узнал и не смог этому обучить другого, толку в твоем знании ноль". Для меня это верное утверждение.

На работе я стараюсь писать подробные туториалы на проблему, которую никто не смог (не захотел) решить, если сам или совместными усилиями она была решена.

Конкретные вопросы появятся, когда я свою проблему буду решать непосредственно (ни шагу назад, позади Москва). Надеюсь, автор не откажет в консультациях.
21. friend0 24.06.15 13:11 Сейчас в теме
(2) мне кажется, что сложность восприятия возникает из-за нарушения одинэсовских шаблонов:
1. Русский язык
2. Названия переменных обозначающие их содержимое
3. Каждое выбираемое поле в отдельной строке

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

Что лучше: тренировка мозга или быстрое простое понимание? Вопрос философский на мой взгляд.

Но вообще тема благородная. Мне правда для планирования бизнеспроцессов нужна была обратная задача - по поиску длинейшего пути, но суть примерно та же и с помощью запросов все считается мгновенно.

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

То бишь в приведенном примере для метро критический путь будет некорректным, потому что в метро можно ездить бесконечно.

П.С. Сорри за ворошение старой темы - почему-то инфостарт ее кинул в новое, а на даты я сначала не посмотрел.
22. ildarovich 7120 24.06.15 13:58 Сейчас в теме
(21) friend0, да, наверное, нужно было данную статью попонятнее написать. Учту на будущее.
3. Каждое выбираемое поле в отдельной строке
В T-SQL такого требования нет, колонки в таблицах рядом, их естественно записывать рядом, а то, что конструктор запросов 1С не так форматирует текст запроса вызывает необходимость мысленного транспонирования колонок и очень сильно увеличивает число строк в запросе. Тут я бы хотел, чтобы форматирование текста запроса было настраиваемым и можно было выбирать кому как удобнее. В общем, это дело привычки и не нужно быть ее рабом. В общем, все за и против хождения строем я понимаю, но тут решил повыделываться.

Что касается обратной задачи, то она здесь названа задачей поиска критического пути и так же решена простой заменой МИНИМУМА на МАКСИМУМ.

Я, честно говоря, скомкал ее описание вот почему: не нашел примера интересного сетевого графика, который можно было проанализировать. Хотя искал очень-очень долго, поверьте. Вы удивитесь, но хорошего наглядного интересного примера нет! Есть приготовление завтрака (всякие там скипятим воду, поджарим яичницу), есть строительство дома (выроем котлован, завезем металлоконструкции), есть проект с несколькими работами. Все остальное - учебные абстракции. И где эти реальные интересные сетевые графики, пример анализа данным алгоритмом можно показать, я не знаю - подскажите! При том, что ProjectManager в работе часто использую, но взять что-либо оттуда тоже не смог.

Это не Инфостарт кинул тему в новые, а я сам, заплатив некоторое количество стартманей. Так тут и делается, иначе статьи забываются.
25. friend0 24.06.15 15:06 Сейчас в теме
(22) про наглядный пример я как-то даже и не знаю, мне это и на уровне Этап1, Этап2 достаточно. Собственно у себя я сделал спровочник этапов с ТЧ с предшествующими этапами и отдал юзерам - какие хотят проекты делать, такие пускай и делают. Мое дело по длительности этапов в рабочих днях вычислить дату завершения каждого этапа. Это если упрощенно. На самом деле там еще всякие заморочки, что по некоторым этапам наоборот задается жесткая дата окончания и надо вычислить длительность, плюс сразу посчитать дату окончания группы этапов и т.д.

Но даже со всеми наворотами и без особых заморочек с оптимизацией: 11 тыщ этапов (примерно по 40 на проект, 1-2 предшествующих, МаксимальнаяДлинаЗамыканий = 64 ) считаются за 1.5-2 секунды.

За ссылку спасибо - я уже и забыл, что там оно было.
23. ildarovich 7120 24.06.15 14:09 Сейчас в теме
(21) friend0, насчет анализа циклов: как решается эта задача описано в другой, более ранней статье Уровни, глубина, прародители, циклы и аналоги запросом .
3. bulpi 177 10.04.14 16:09 Сейчас в теме
(1)
Это вы балованные. Он то как раз объясняет толково. Тут полно народу с худшим стилем изложения.
4. Gendalf_beliy 10.04.14 16:51 Сейчас в теме
Сын (6 лет) подходит к отцу и спрашивает:
- Папа, а почему когда я откусываю яблоко, оно становится потом коричневым?
- Сынок, очень хорошо, что ты задаешь такие вопросы. Видишь ли, яблоко содержит очень много химического элемента феррум, который при контакте с кислородом в воздухе, которым мы дышим образует оксид железа Fe2O3, который в свою очередь имеет тот самый коричневый цвет.
- ?!? Папа, а ты с кем сейчас разговаривал ?

Я глубоко уважаю автора статьи, за недюжинные познания в математике и теории алгоритмов. Даже некоторыми идеями пользовался в работе (которые смог понять).

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

А так да - очень полезный материал... наверное.
Жду следующих публикаций -)))

(1) Makushimo, спасибо за комментарий, улыбнуло
29. Prometeus2011 97 13.10.15 09:50 Сейчас в теме
(1) Makushimo. В общем-то самое важное, что идеи-то имеют практическое применение. Это чрезвычайная редкость. Обычно просто люди умничают, но чтобы применить на практике результаты этих измышлений чего-то не хватает. В случае же со статьями Сергея - все очень даже применяется на практике. Я применил пару теорий для разработки решений и внедрил их в работу нашей довольно не мелкой, но в общем-то, заурядной торговой организации. Отлично все работает. Этим решился ряд серьезных проблем и отпала необходимость в использовании традиционных, более громоздких, алгоритмов.
11. Eugene_Life 3 14.04.14 13:57 Сейчас в теме
Восхищаюсь автором и некоторыми другими присутствующими на ИС личностями, которые без зазнайства демонстрируют уровень математического мышления выше среднего.
13. ksuman 19.04.14 22:30 Сейчас в теме
На мой взгляд, практического эффекта это решение не вносит. При увеличении точек, время расчета будет расти по экспоненте и приближаться к бесконечности... К тому же тут расчет зиждется на транзитивности, а по факту расстояние между А и Б может сильно отличаться от Б к А и быть не прямым.
Стоит ли тратить время на решение бесполезных задач.
С точки зрения специфик математических задач, то их решение вообще неприемлемо считать в языках высокого уровня или средствами запросов SQL, т.к. по факту, на примере данной задачи, если её развернуть до низкого уровня будет: банальное сложение всех точек между собой + огромное число ненужных операций.
14. ildarovich 7120 20.04.14 09:50 Сейчас в теме
(13) Я бы сказал, что решение имеет ограниченную область применения. Его можно применять тогда, когда число точек относительно невелико (до 100-200 в компонентах связности). Вы же, например, не отказываетесь вообще использовать чайную ложечку, хотя ей трудно поливать огород. Определить оптимальный порядок обновления релизов конфигураций, оптимальный маршрут перелетов с пересадками, маршрут поездки в питерском метро, критический путь в проекте обычного размера - все это задачи, доступные методу.
При увеличении числа вершин время расчета будет расти не по экспоненте, а как O(ln(N)*N^2) или O(ln(N)*N^4).
Любое решение этой задачи не обойдется без транзитивности. Случай, когда расстояние А->Б и Б->А разные, в этом решении прекрасно отрабатывается (про непрямое расстояние не понял).
У математических задач нет единой специфики. На языках высокого уровня подавляющее большинство из них прекрасно решаются, а иногда и средствами запросов SQL. Тут не должно быть предубеждений. Для каждой задачи можно взять метод, произвести оценку его сложности и трудоемкости и, если они удовлетворительны, применять этот метод, не взирая на выразительные средства решения.
15. STivO 59 21.04.14 12:33 Сейчас в теме
В последнее время стал активно читать ваши статьи и действительно получается вникнуть и понять разбираемые темы. Спасибо за Ваш труд!)
16. brunet 43 24.05.14 21:04 Сейчас в теме
Интересно было посмотреть конфигурацию где все это используется.
17. Yimaida 35 28.05.14 12:20 Сейчас в теме
Автору огромный плюс за статью. Решение задач оптимизации на любом языке будет иметь ограничение по времени при увеличении числа элементов (это в поддержку). Для меня ценность данной статьи именно в НОВОМ методе и взгляде на задачу поиска пути, потому как самому приходилось реализовывать задачу оптимизации (не на 1с). Что касается практического применения, так это только вопрос времени, когда известен инструмент, то и задачи быстро найдутся. Я, например, стараюсь по максимуму выносить всю логику в запросы где это возможно.
Статья, не смотря на свой небольшой объем, очень "сильная", единственное, что я бы добавил, так это ссылки на литературу (если такая имеется). По подаче я бы не сказал, что все очень мудрено написано, т.к. все равно надо "щупать", а для понимания общей идеи достаточно.
+ + +
31. kirinalex 2 25.12.18 08:06 Сейчас в теме
(17)
Я, например, стараюсь по максимуму выносить всю логику в запросы где это возможно
для чего?
18. jobkostya1c8 19.10.14 10:02 Сейчас в теме
Интересные решения на запросах. Может, когда будет критично по времени исполнения где-нибудь пригодится.
19. Dach 300 10.01.15 00:40 Сейчас в теме
"С точки зрения определения кратчайшего расстояния между конкретной парой вершин он довольно избыточен, поскольку требует на промежуточном этапе определения и запоминания кратчайшего расстояния между всеми транзитивно-связанными вершинами графа.

Но, во-первых, эту операцию можно выполнять один раз, сохранив ее результат в базе данных."

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

К вопросу хранения таких данных - чтобы оптимизировать скорость работы алгоритма, нужно хранить минимальное расстояние на каждую пару вершин, тогда можно быстро получить результат для искомой пары. Допустим, эту задачу можно решить с помощью регистра сведений. Но каждый раз, при добавлении новой вершины - думаю, не надо объяснять, что будет с размером таблицы... И чем длиннее цепочка связанных графов - тем огромнее будет таблица. Все верно?
20. ildarovich 7120 10.01.15 01:15 Сейчас в теме
(19) Dach, да, все правильно. Нужно будет хранить минимальное расстояние для каждой пары вершин. Число строк в "огромной таблице" - N*(N - 1) / 2, где N - число узлов транспортной сети. Если число вершин - 1000, то строк в таблице будет 500 000. Не так уж и много, на самом деле.

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

Ну и обратите внимание на задачу нахождения критического пути, которую можно применять при управлении проектами - там тоже подходящее число вершин.

У меня, кстати, есть обработка, которая построена на базе того же алгоритма, распределяющая заказы (привязанные к станциям метро) между курьерами. Вполне практичная вещь. Работает очень быстро именно за счет сохранения матрицы минимальных расстояний в параметрах обработки.
24. Зеленоград 24.06.15 14:23 Сейчас в теме
Надо будет почитать, а пока возьмусь комментировать комментарии :)

1. 23 секунды на несильно связный граф... Или модель данных неверная, или я прям не знаю. Перебор даёт 1е6 простых вычислений в секунду (это я в цикле погонял и понял, что встроенный язык не так плох). 120, кажется, станций. 120*119 (если туда<>обратно) = 1.4е4 За (1е6/1.4е4 = 700 вычислений мы успеем сложить все пути в табличку) Годится ИМХО только если даный способ даст гарантированное решение любой задачи из широкого класса.

А вот задача прикладная, кажется, есть. Сейчас сформулирую и вечером попробую написать.
26. I_G_O_R 63 24.06.15 18:53 Сейчас в теме
Ваши статьи конечно интересные, с точки зрения умственного развития, но я не могу понять одного - почему эти задачи нужно решать именно в запросе? Если запросом выбрать нужные данные, а потом в коде обработать, разве не проще будет? А еще потом это кому-нибудь придется поддерживать...
28. friend0 24.06.15 20:02 Сейчас в теме
(26) I_G_O_R, как обычно все зависит от масштабов. Если исходных данных 10000 строк, а в результате нужно 100, то только чтоб передать с сервера 10000 строк уйдет уйма времени. А поддерживать - на мой взгляд запрос нагляднее (если написан красиво без иксов и игреков).
27. starik-2005 2212 24.06.15 19:06 Сейчас в теме
Язык запросов - штука могучая, но злоупотреблять ею можно лишь из праздного интереса и развлечения ради. Понятно, что данная задача решается и иначе за куда меньшее время. Но для 1С пойдет )))
30. vaxhab 13 13.07.18 18:14 Сейчас в теме
Оставьте свое сообщение

См. также

Нечеткое сравнение строк. Метод Джаро-Винклера на 1С Промо

Математика и алгоритмы v8::УФ 1cv8.cf Абонемент ($m)

Схожесть строк. Метод Джаро-Винклера. В обработке реализован алгоритм нечеткого сравнения строк.

3 стартмани

20.04.2018    20091    80    Serg1701    19    

Решение задачи Эйнштейна на платформе 1с

Математика и алгоритмы v8 Абонемент ($m)

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

1 стартмани

12.08.2020    1051    0    itmind    2    

Treemapping. Демонстрационная обработка

Математика и алгоритмы Работа с интерфейсом v8 1cv8.cf Абонемент ($m)

Пример реализации диаграммы вида Treemap на 1С

1 стартмани

27.02.2020    3058    9    randomus    4    

Рекомендательный сервис на основе коллаборативной фильтрации на 1С. Расширение формы подбора для УТ 11.4

Оптовая торговля Розничная торговля Практика программирования Математика и алгоритмы v8 ERP2 УТ11 КА2 Розничная и сетевая торговля (FMCG) Оптовая торговля, дистрибуция, логистика Россия УУ Абонемент ($m)

В данной разработке реализован механизм рекомендаций товаров по принципу схожести товаров в корзине на основе алгоритма Item-to-Item от Amazon. Разобран алгоритм с демо базой и сделано расширение для УТ11.4 которое добавляет в форму подбора таблицу рекомендаций. Протестировано на 8.3.13.1865 на Управление торговлей, редакция 11 (11.4.8.63)

3 стартмани

25.09.2019    10272    12    informa1555    24    

Минимализмы 2 Промо

Практика программирования v8 Бесплатно (free)

Следующая серия "минимализмов" [http://infostart.ru/public/306536/]. Также, как и в предыдущей статье, здесь приведена подборка коротких оригинальных решений некоторых задач. Ранее эти решения были разбросаны по моим комментариям к чужим публикациям.

23.02.2016    50327    ildarovich    83    

Конвейер проверки качества кода

Инструментарий разработчика Практика программирования Математика и алгоритмы v8 1cv8.cf Абонемент ($m)

Jenkinsfile для выполнения проверки качества кода. Собирает информацию с АПК, EDT и BSL-LS. Сопоставляет ошибки с гит-репозиторием, выгруженным ГитКонвертором. Отправляет в Сонар.

3 стартмани

04.09.2019    24578    22    Stepa86    45    

Алгоритмы и регламентные задания (расширение)

Математика и алгоритмы Прочие инструменты разработчика v8 v8::УФ 1cv8.cf Абонемент ($m)

Универсальный механизм для создания алгоритмов и регламентных задач.

5 стартмани

28.05.2018    11734    7    pm74    39    

Многопоточная выгрузка одного сообщения обмена

Практика программирования Математика и алгоритмы Перенос данных из 1C8 в 1C8 v8 Абонемент ($m)

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

1 стартмани

05.12.2016    15599    1    zhichkin    24    

Полная методичка к курсу "Программирование 8.2" Промо

Математика и алгоритмы v8 1cv8.cf Абонемент ($m)

580 страниц знаний! Публикую методичку, а точнее стенограмму курса по подготовке программистов 8.2.

10 стартмани

09.01.2014    52362    110    GROOVY    100    

1С+Классы. Версия-0

Разработка внешних компонент Математика и алгоритмы v8 1cv8.cf Абонемент ($m)

Разработано ООП-расширение языка 1С, включающее (но не ограничивающееся): Классы как абстрактные типы данных с элементами «переменная», «свойство», «функция», «процедура»; Интерфейсы как абстрактные классы без элементов состояния («переменная») и без привязки к реализации методов (свойств, процедур, функций) при определении; Имплементация (реализация) интерфейсов классами; - одиночное открытое наследование; Области видимости «внутренняя» (private), «экспорт» (public), «защищенная» (protected); Статические элементы классов (общие для всех экземпляров класса); Замещение (переопределение реализации) методов при наследовании – «виртуальные методы, свойства»; Сокрытие (затенение) обычных (не замещаемых) элементов при наследовании; Перегрузка процедур и функций по количеству и типам данных аргументов; Конструкторы класса; Деструктор класса; Слабые ссылки; Делегаты.

1 стартмани

28.10.2016    20578    1    IntelInside    68    

Генетический алгоритм для решения простой задачки

Математика и алгоритмы v8 1cv8.cf Абонемент ($m)

Генетический алгоритм в решении задачи: Необходимо расставить правильно (по другому) скобки, чтобы получилось 850 (1 + 2) (3 + 4) (5 + 6) (7 + 8) (9 + 10) (11 + 12) (13 + 14) + 15

1 стартмани

26.09.2016    9869    5    eugeniezheludkov    4    

Объектные блокировки

Практика программирования Математика и алгоритмы v8 Россия Абонемент ($m)

При работе с объектными данными (справочники, документы, планы счетов и т.д.) система «1С:Предприятие» обеспечивает два вида объектных блокировок: пессимистическую и оптимистическую. Они позволяют выполнять целостные изменения объектов при одновременной работе нескольких пользователей.

1 стартмани

17.08.2016    30867    9    Ranis1286    5    

Разработка синтаксического анализатора языка запросов на языке 1С Промо

Математика и алгоритмы v8 1cv8.cf Абонемент ($m)

Пример разработки генератора для PEG парсера

1 стартмани

03.12.2014    25049    1    so-quest    70    

Использование методов глобального контекста в системе компоновки данных или недокументированные возможности СКД

Практика программирования Математика и алгоритмы v8::УФ v8::СКД 1cv8.cf Абонемент ($m)

Прочитал на форуме, что СтрРазделить() и ТекущаяДата() работают в языке выражений системы компоновки данных. Почитал справку, там ничего не нашёл, поэтому не поверил. Посмотрел на практике – и правда работает… В данной статье попытался привести весь перечень методов, работающих в СКД, но не описанных в документации.

1 стартмани

05.08.2016    37340    26    klinval    40    

Еще один способ расчета остатков на каждый день в запросе

Математика и алгоритмы Практика программирования v8 Абонемент ($m)

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

1 стартмани

24.04.2016    34509    48    ildarovich    23    

Пример рекурсивной выгрузки иерархической структуры в XDTO

Математика и алгоритмы Внешние источники данных WEB v8 1cv8.cf Абонемент ($m)

Решил реализовать иерархию в пакете XDTO и выгрузить ее рекурсивно. Задача оказалась нетривиальной, хотя и весьма простой. Изысканиями решил поделиться с народом, чтобы не пропадало народное добро.

1 стартмани

26.02.2016    33750    16    starik-2005    3    

Еще один взгляд на проблему «жизнь без последовательностей». Часть вторая (практическая) Промо

Математика и алгоритмы v8 КА1 БП2.0 УТ10 Розница УПП1 УНФ Россия Абонемент ($m)

В [1 - http://infostart.ru/public/62938/] был предложен метод корректировки списаний по партиям при изменении документов задним числом. Использование данного метода позволяет контролировать остатки при неоперативном проведении и поддерживать учет по партиям всегда в актуальном состоянии, то есть обходиться без механизма последовательности документов. Собственно метод заключался в решении задачи правильного списания по партиям как задачи линейного программирования. В доказательство работоспособности метода приводится следующая «каркасная» конфигурация «Полигон», в которой этот метод реализован.

1 стартмани

19.08.2010    29853    18    ildarovich    35    

Нелинейная многомерная оптимизация - это просто. Часть 3. Имитация отжига

Инструментарий разработчика Математика и алгоритмы Универсальные функции v8 1cv8.cf Абонемент ($m)

Метод имитации отжига для поиска оптимального решения. И, как обычно, универсальная функция поиска этого самого решения.

1 стартмани

13.10.2015    18678    24    dusha0020    5    

Нелинейная многомерная оптимизация - это просто. Часть 1. Градиентный спуск

Математика и алгоритмы Универсальные функции Практика программирования v8 Абонемент ($m)

Рассказ с демонстрацией возможностей градиентного метода поиска оптимального решения.

1 стартмани

07.07.2015    18368    8    dusha0020    19    

Пример сериализации объектов в 1С 8.3 и их восстановления из сериализованных данных

Математика и алгоритмы Обмен через XML Перенос данных из 1C8 в 1C8 v8 1cv8.cf Россия Абонемент ($m)

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

1 стартмани

05.07.2015    28431    75    katkov_a    29    

Включаем звук в 1С. Доступно и всерьез. Промо

Математика и алгоритмы Универсальные функции v8 1cv8.cf Абонемент ($m)

Как сделать воспроизведение звука в 1С без внешних компонентов? Решаем средствами интернета. Для тонкого, толстого и web-клиента.

1 стартмани

30.12.2013    81580    151    sikuda    37    

Написание простой обработки через тестирование

Математика и алгоритмы Практика программирования v8 1cv8.cf Абонемент ($m)

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

1 стартмани

24.02.2015    27701    12    Alien_job    40    

Парсинг сайта без использования встроенного браузера для начинающих

Практика программирования Математика и алгоритмы WEB v8 1cv8.cf Абонемент ($m)

Данная статья показывает пример парсинга одного конкретного сайта со своей структурой, на основе которого можно понять суть, методы и без особых проблем парсить другие сайты. Здесь описано: подключение к серверу, сохранение html-страницы на диск, загрузка и цикличный обход ее структуры, рекурсивный парсинг, загрузка картинок по ссылке на диск.

1 стартмани

20.11.2014    40767    117    angernaughts    37    

Куайн (Программа, выводящая свой исходный код на экран)

Математика и алгоритмы Практика программирования v8 1cv8.cf Абонемент ($m)

Обработка позволяет насладится реализацией этой интересной, и совершенно бесполезной с практической точки зрения задачей.

1 стартмани

25.08.2014    9897    0    atridis    7    

Конспект лекций по курсу «Автоматизированные информационные системы» Промо

Математика и алгоритмы v8 1cv8.cf Россия Абонемент ($m)

Конспект лекций по курсу «Автоматизированные информационные системы» составлен на основании требования Государственного образовательного стандарта среднего профессионального образовании к содержанию и уровню подготовки выпускника по специальности 230103 «Автоматизированные системы обработки информации и управления». В конспекте есть общие сведения о методике 1С:Профкейс. Конспект лекций разработал: канд. техн. наук, доцент Космачев С.Н.

1 стартмани

07.06.2012    24841    9    ksnik    19    

Пророк в своем отечестве или Читаем XML с помощью XDTO

Математика и алгоритмы v8 1cv8.cf Абонемент ($m)

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

1 стартмани

29.01.2014    45655    24    majmyl    53    

БСП, использование типового механизма 1с для запуска регламентных заданий с заранее подготовленными настройками.

Математика и алгоритмы БСП (Библиотека стандартных подсистем) v8 1cv8.cf Абонемент ($m)

Описание варианта запуска регламентного задания на БСП, без изменения типовой конфигурации.

1 стартмани

03.01.2014    36838    114    almas    7    

Методический материал. Работа с запросами

Практика программирования Математика и алгоритмы v8 Абонемент ($m)

Краткое методическое пособие для изучения запросов в 1С

1 стартмани

23.12.2013    18208    12    rayastar    27    

Автоформатирование кода Промо

Сервисные утилиты Обработки Чистка базы Справки Производительность и оптимизация (HighLoad) Инструментарий разработчика Практика программирования Универсальные обработки Решение задач на 1С:Специалист Математика и алгоритмы Администрирование данных 1С Разработка Тестирование и исправление Стартеры 1С v8 1cv8.cf Абонемент ($m)

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

1 стартмани

19.12.2012    40629    46    Sibars    57    

Определитель матрицы

Практика программирования Математика и алгоритмы v8 Абонемент ($m)

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

1 стартмани

28.11.2013    12788    8    zaxarovsky    8    

Квадратный корень в запросе 1С

Практика программирования Математика и алгоритмы v8 Абонемент ($m)

Язык запросов 1С не позволяет вычислить квадратный корень 1С. Квадратный корень может пригодиться при вычислении среднеквадратического отклонения или геометрических вычислениях.

1 стартмани

24.10.2013    27293    4    Elisy    53    

Задачи о 5 и 9 ферзях

Математика и алгоритмы v8 Абонемент ($m)

Задача о ферзях-часовых. На шахматной доске надо расставить 5 ферзей, чтобы они держали под боем все клетки доски. Задача В. Франгена, расставить на шахматной доске 10 “белых” и 9 “чёрных” ферзей так, чтобы ни один из них не находился под ударом противника

1 стартмани

31.08.2013    21016    0    scientes    4    

Расчет SHA-1 хеша средствами 1С. Битовые операции в 1С или урок двоичной математики

Практика программирования Математика и алгоритмы v8 1cv8.cf Россия Абонемент ($m)

Расчет хеша SHA-1 без использования каких-либо внешних компонет - возможно ли это в 1Cv8? Оказывается вполне возможно!

1 стартмани

13.03.2013    31437    76    Антон Ширяев    40    

Анализ цикломатической сложности кода

Инструментарий разработчика Разработка внешних компонент Математика и алгоритмы v8 1cv8.cf Абонемент ($m)

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

1 стартмани

13.12.2012    25394    66    Spitfire    30    

Подсистема допроведения документов

Практика программирования Математика и алгоритмы v8 БП2.0 УТ10 УПП1 Россия Абонемент ($m)

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

1 стартмани

01.10.2012    14369    4    SergAn    40    

Основы тестирования доработок

Математика и алгоритмы v8 1cv8.cf Россия Абонемент ($m)

Попытался 1С консультантам-новичкам объяснить принципы тестирования доработок, принимаемых у программистов 1С. И описать частые ошибки в самих доработках, и какие действия нужны для обнаружения этих ошибок (без погружения в код).

1 стартмани

20.08.2012    27097    8    1СERP    17    

Простая и элегантная форма выбора из ТЗ

Математика и алгоритмы v8 1cv8.cf Россия Абонемент ($m)

Простая в использовании форма выбора из ТЗ. Можно использовать как общюю форму (весь код в модуле формы).

1 стартмани

31.05.2012    11099    0    mozz    3    

"Внешний" справочник или Хранение данных между сеансами работы внешних обработок

Математика и алгоритмы v8 Россия Абонемент ($m)

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

1 стартмани

29.02.2012    21767    10    Damian    34    

Перенос строк из табличной части в табличную часть любого документа (обычное приложение)

Математика и алгоритмы v8 1cv8.cf Абонемент ($m)

Перенос строк из табличной части в табличную часть любого документа (обычное приложение)

1 стартмани

15.11.2011    7209    10    alexnikolas    16    

Горячие клавиши 1С 8

Математика и алгоритмы v8 1cv8.cf Россия Абонемент ($m)

Порядка 200 комбинаций сочетаний клавиш для работы в 1с - конфигуратор и само приложение. По предложению pumbaE список команд был дополнен и расширен, за что ему отдельное спасибо :)

1 стартмани

09.03.2011    12770    10    nzass    29