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

18.10.14

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

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

Скачать файл

ВНИМАНИЕ: Файлы из Базы знаний - это исходный код разработки. Это примеры решения задач, шаблоны, заготовки, "строительные материалы" для учетной системы. Файлы ориентированы на специалистов 1С, которые могут разобраться в коде и оптимизировать программу для запуска в базе данных. Гарантии работоспособности нет. Возврата нет. Технической поддержки нет.

Наименование По подписке [?] Купить один файл
Отчет для нахождения кратчайшего расстояния и критического пути
.erf 22,18Kb
62
62 Скачать (1 SM) Купить за 1 850 руб.

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

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

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

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

См. также

Математика и алгоритмы Программист Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    3580    stopa85    12    

38

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    8117    user1959478    52    

36

Математика и алгоритмы Разное Платформа 1С v8.3 Конфигурации 1cv8 Россия Абонемент ($m)

Расширение (+ обработка) представляют собою математический тренажер. Ваш ребенок сможет проверить свои знание на математические вычисление до 100.

2 стартмани

29.09.2023    3515    maksa2005    8    

26

Математика и алгоритмы Инструментарий разработчика Программист Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

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

1 стартмани

09.06.2023    11251    8    SpaceOfMyHead    19    

61

Математика и алгоритмы Программист Платформа 1С v8.3 Конфигурации 1cv8 Бесплатно (free)

Три задачи - три идеи - три решения. Мало кода, много смысла. Мини-статья.

03.04.2023    4764    RustIG    9    

25

Механизмы платформы 1С Математика и алгоритмы Программист Платформа 1С v8.3 Россия Бесплатно (free)

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

23.11.2022    3918    gzharkoj    14    

25

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

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    9116    7    kalyaka    11    

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

К вопросу хранения таких данных - чтобы оптимизировать скорость работы алгоритма, нужно хранить минимальное расстояние на каждую пару вершин, тогда можно быстро получить результат для искомой пары. Допустим, эту задачу можно решить с помощью регистра сведений. Но каждый раз, при добавлении новой вершины - думаю, не надо объяснять, что будет с размером таблицы... И чем длиннее цепочка связанных графов - тем огромнее будет таблица. Все верно?
20. ildarovich 7935 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 69 24.06.15 18:53 Сейчас в теме
Ваши статьи конечно интересные, с точки зрения умственного развития, но я не могу понять одного - почему эти задачи нужно решать именно в запросе? Если запросом выбрать нужные данные, а потом в коде обработать, разве не проще будет? А еще потом это кому-нибудь придется поддерживать...
28. friend0 24.06.15 20:02 Сейчас в теме
(26) I_G_O_R, как обычно все зависит от масштабов. Если исходных данных 10000 строк, а в результате нужно 100, то только чтоб передать с сервера 10000 строк уйдет уйма времени. А поддерживать - на мой взгляд запрос нагляднее (если написан красиво без иксов и игреков).
27. starik-2005 3091 24.06.15 19:06 Сейчас в теме
Язык запросов - штука могучая, но злоупотреблять ею можно лишь из праздного интереса и развлечения ради. Понятно, что данная задача решается и иначе за куда меньшее время. Но для 1С пойдет )))
30. vaxhab 16 13.07.18 18:14 Сейчас в теме
Оставьте свое сообщение