Комментарии 14
Вот например старая статейка от разработчиков майкрософт,
Здравствуйте, огромное спасибо за такую содержательную статью! Не всё поняла, к сожалению, и статейка не открылась. Сразу сделаю одно небольшое замечание, а потом уже задам все свои вопросы. Раз уж вы затронули ДП, наверно, нужно было четко сформулировать основное предположение для всех этих задач о поиске кр. путей. Система без последействия, т.е. если кр. путь от s до t проходит через k, то пути s-k и k-t тоже кратчайшие. Есть задачи, где это не так, например, поиск кр. пути со штрафами за повороты.
Статейка - это случайно не алгоритм Йена, который ищет первые k путей за O(kn^4) и O(kn^3) в случае неотрицательных весов? Или уже есть что-то получше?
Всю жизнь избегала ЛП, считая, что специализированные потоковые алгоритмы более эффективны: метод фаз Диница и другие алгоритмы, модифицированные методом фаз Диница. Алгоритм дефекта (поиск циркуляции минимальной стоимости), например, который единственный может работать с контурами отр. стоимости. Если нетрудно, дайте, пожалуйста, ссылку на применение метода внутренней точки для потоковых задач. В каких-то матпакетах этот метод есть?
Ну и с A* алгоритмом как-то неожиданно. Я с ним знакома по книге Нильса Нильсона "Принципы ИИ". Там вроде всё просто: эвристическая оценочная функция h(u), которая оценивает неизвестное нам расстояние от u до стока t, гарантирует нахождение кр. пути, если h(u)<= h*(u), где h*(u) - настоящее минимальное расстояние от u до t. И вдруг на сцене опять появляется линейное программирование. Тот же вопрос: где про это можно почитать?
Восстановление кр. пути по вектору расстояний - вы упомянули процедуру, где для каждой вершины храним последнее ребро. Вопрос: если в графе есть контуры нулевого веса, всё корректно будет работать?
Система без последействия, т.е. если кр. путь от s до t проходит через k, то пути s-k и k-t тоже кратчайшие.
Мне казалось, что это обычно называют "оптимальной подструктурой" и она вытекает из постановки. Добавлю на всякий случай
Есть задачи, где это не так, например, поиск кр. пути со штрафами за повороты.
Мне кажется, что это сводится к кратчайшим путям если немного перестроить граф. Похожая ситуация в скрытых марковских цепях: там нужно найти наиболее правдоподбную последовательность в графе, есть веса на рёбрах (transition probability) и на вершинах (emission probability), но при этом все сводится к кратчайшим путям.
Статейка - это случайно не алгоритм Йена, который ищет первые k путей за O(kn^4) и O(kn^3) в случае неотрицательных весов? Или уже есть что-то получше?
Нет, там про top-k completion, т.е. пользователь пишет что-то в текстовом поле, а вы ему даете самые хорошие продолжения. Вот исправленная ссылка. Алгоритм там ровно такой, который я в статье описал (есть пример с кодом), но у него есть проблема, что он может выдавать пути с циклами. Алгоритм Йена выдает только простые пути. Я не изучал вопрос подробно, но уверен, что есть алгоритмы лучше
Если нетрудно, дайте, пожалуйста, ссылку на применение метода внутренней точки для потоковых задач
В конце статьи есть список литературы
В каких-то матпакетах этот метод есть?
С потоками в opensource вообще проблематично, я к сожалению хороших пакетов не знаю. Раньше была библиотека от Гольдберга, но кажется, что он лет 20 назад на неё забил. В 2016 он давал лекцию в институте Стеклова (кстати про кратчайшие пути), я тогда у него спрашивал про библиотеку, его реакция была эпична: "О, а там даже компилирующийся код?"
Там вроде всё просто: эвристическая оценочная функция h(u), которая оценивает неизвестное нам расстояние от u до стока t, гарантирует нахождение кр. пути, если h(u)<= h*(u), где h*(u) - настоящее минимальное расстояние от u до t.
А вот в том то и дело, что не гарантирует. Там еще нужно неравенство треугольника для h. На вики про это небольшая история есть.
Тот же вопрос: где про это можно почитать?
Goldberg, A. (2005). Basic shortest path algorithms. DIKU Summer School on Shortest Paths. Microsoft Research. Silicon Valey.
Goldberg, A. V., & Harrelson, C. (2005). Computing the shortest path: A search meets graph theory. SODA, 5, 156–165.
Или введение любой статьи Гольдберга поновее
Восстановление кр. пути по вектору расстояний - вы упомянули процедуру, где для каждой вершины храним последнее ребро. Вопрос: если в графе есть контуры нулевого веса, всё корректно будет работать?
Есть дерево кратчайших путей (кстати оно на заглавной картинке выделено красными линиями) -- это prev в scanning method, он корректно работает с циклами нулевого веса. Чтобы восстановить путь, нужно просто в цикле пройти по prev, пока не дойдем до s. Если же по какой-то причине мы посчитали расстояния, но не посчитали prev, то можно запустить A* с посчитанными расстояниями и он переберет только кратчайший путь.
Да, в задаче со штрафами за повороты после перестройки графа можно избавиться от последействия. (Вроде бы про отсутствие последействия говорят в постановке задачи ДП, если я ничего не путаю). А вот алгоритмы для задач с фиксированными платежами мне как-то не попадались.
А вы не интересовались задачами оптимального размещения обслуживающих центров (в частности, абсолютных центров)? На русском языке нет почти ничего, как было бы замечательно, если бы кто-нибудь написал по сути первую обзорную статью.
Ещё раз огромное спасибо за любезный и обстоятельный ответ!
А вы не интересовались задачами оптимального размещения обслуживающих центров
к сожалению нет, быть может есть какая-нибудь точка входа? В чем задача заключается?
Там целая серия весьма прикладных задач, во-первых разные типы обслуживающих центров (центры - минимизируем расстояние от центра до самого удалённого клиента и медианы - минимизируем сумму расстояний от всех клиентов до центра), в разных вариациях: обслуживающие центры в вершинах или посреди ребра (дуги); клиенты в вершинах или в любой точке ребра (дуги). Один обслуживающий центр размещается за полиномиальное время, далее - NP-hard. Из P нетривиальная задача только одна - размещение абсолютного центра на неор. графе. У нас по старинке её до сих пор графическим алгоритмом Хакими решают, для графа с невзвешенными вершинами.
Я сделала размещение абс. центра с ограничениями (ребру приписан вектор весов), вроде на тот момент не было таких постановок или я плохо искала, во всяком случае, опубликовали в ИТ и ВС в 20-м году. Вот мой список литературы, не знаю, как в спойлер убрать:
1. Hakimi, S.L. 1964. Optimum Locations of Switching Centers and the Absolute Centers and Medians of a Graph. Operations Research 12:450–459. doi:10.1287/opre.12.3.450.
2. Kariv, O. & Hakimi, S.L. 1979. Algorithmic approach to network location problems, I: The p-Centers, SIAM J. Appl. Math. 37(3):513–537. doi:10.1137/0137040.
3. Goldman, A.J. Minimax location of a facility in a network. Transp. Sci. 6(4):407–418. doi:10.1287/trsc.6.4.407.
4. Megiddo, N. 1983. Linear-time algorithms for linear programming in R3 and related problems. SIAMJ. Comput. 12(4): 759–776. doi:10.1137/0212052.
5. Ding, W. & Qiu., K. 2017. FPTAS for generalized absolute 1-center problem in vertex-weighted graphs. Journal of Combinatorial Optimization. 34(4):1084–1095. doi: 10.1007/s10878-017-0130-4.
6. Ramos, R.M., Sicilia, J. & Ramos, M.T. 1997. The biobjective absolute center problem. TOP, 5(2): 187-199. doi: 10.1007/BF02568548.
7. Ding, W. & Qiu., K. 2015. Approximating the Restricted 1-Center in Graphs. In: Lu Z., Kim D., Wu W., Li W., Du DZ. (eds) Combinatorial Optimization and Applications. Lecture Notes in Computer Science, vol 9486: 647-659. doi: 10.1007/978-3-319-26626-8_47.
8. Minieka, E. 1981. Polynomial Time Algorithm for Finding the Absolute Center of a Network. Networks, 11: 351-355. doi:10.1002/net.3230110404
9. Minieka, E. 1978. Optimization Algorithms for Networks and Graphs. New York: Marcel Dekker. 356 p.
10. Christofides, N. 1975. Graph Theory: Algorithmic Approach. New York: Academic. 400 p.
С потоками в opensource вообще проблематично, я к сожалению хороших
пакетов не знаю. Раньше была библиотека от Гольдберга, но кажется, что
он лет 20 назад на неё забил.
Могу посоветовать LEMON, https://lemon.cs.elte.hu/pub/doc/1.3.1/modules.html . Там много хороших, накочегаренных алгоритмов для графов и оптимизации на них, в том числе комбинаторной.
Вот еще, если не считать того, что библиотека на питоне, то в общем то вполне добротная подборка потоковых алгоритмов. Правда там только классические.
https://github.com/networkx/networkx/tree/main/networkx/algorithms/flow
Очень хорошо, что на питоне, как раз его изучаю.
Еще один вопрос возник, см. цитату. А как же неравенство треугольника?
Если же по какой-то причине мы посчитали расстояния, но не посчитали prev, то можно запустить A* с посчитанными расстояниями и он переберет только кратчайший путь.
Питон хороший язык, но не высокопроизводительный. А от библиотеки, которая заявляет, что у них
an interface to existing numerical algorithms and code written in C, C++, and FORTRAN;
я бы ожидал высокой производительности, а получаю, что все методы начиная с двунаправленного Дейкстры, которые я написал для демонстрации работают быстрее библиотечных.
А как же неравенство треугольника?
Не совсем понял вопроса. Кратчайшие расстояния от одной вершины до всех остальных удовлетворяют неравенству треугольника
Теперь поняла, это не для исходного графа, а для для построенного дерева.
С питоном только начала разбираться. Меня больше всего огорчило, что питон не оптимизирует хвостовую рекурсию + ограничивает глубину рекурсии. Как быть, все алгоритмы, основанные на поиске в глубину, переписывать без рекурсии? Или лучше заменять глубину на ширину?
Если для вас действительно имеет значение использование рекурсии, то видимо вы работаете c системами реального времени или чем-то аналогичным по уровню требований. В такой ситуации для фундаментальных алгоритмов я бы просто не рекомендовал использовать python ибо он предназначен не для оптимизации рантайма, а для оптимизации времени разработки. Если бы я писал примеры к OSM на С++, это бы заняло примерно бесконечное время (если не привлекать питон хотя бы для обвязки), но при этом если бы стояла задача ускорить алгоритмы, то первым бы делом я их переписал на С++.
Касательно исходного вопроса: чаще всего обход в глубину можно заменить обходом в ширину, но при необходимости можно и переписать как здесь
Еще раз спасибо. В данный момент я думаю, как переписать свои программы с графами с паскаля на питон. Видимо, питон был не лучший выбор, но не хочется бросать на полпути.
Что касается вашего вопроса о постановке задачи для поиска абсолютного центра. Сейчас открыла статью, вспомнила, какую "реальную" постановку я придумала (придумала, т.к. в редакции просили дать практическое приложение для алгоритма). В качестве вектора весов используются две характеристики ребра: длина и стоимость.
Задача о платных дорогах.
Условие. Дан неор. граф, каждому ребру приписаны положительная длина и положительная стоимость. Вершины взвешены, веса неотр. (вес вершин - "важность" клиентов. Если все клиенты одинаковы, то веса единичные). Задана положительная граница стоимости B. Требуется разместить абсолютный центр (в любой точке графа) так, чтобы стоимость проезда от центра до любого клиента не превосходила B, а взвешенное расстояние до самого удалённого клиента было минимально.
В такой обширной и фундаментальной статье считаю достойным упоминуть интересные свойства алгоритма Дейкстры.
Этот алгоритм работает с любой функцией расстояния, если только она удовлетворяет некоторым свойствам:
1) Если к двум путям p1 и p2 приписать одно и то же ребро e, если len(p1) < len(p2), то len(p1+e) <= len(p2+e)
2) Если к двум путям p1 и p2 приписать одно и то же ребро e, если len(p1) = len(p2), то len(p1+e) = len(p2+e)
3) Удлинение пути каким-то ребром делает путь не короче (len(p+e) >= len(p)).
Например, можно Дейкстрой искать кратчайший путь, если длина пути - это размер максимального ребра в пути, надо только код пересчета расстояния до вершины заменить на max вместо сложения.
Также работает дейкстра с потенциалами: если в каждой вершине записать какое-то число и считать длину пути как длина всех ребер + потенциал конца - потенциал начала. На этом основан алгоритм Джонсона, который работает в графах с отрицательными ребрами, но без отрицательных циклов. Так же A* является дейкстрой со сложной функцией расстояния.
И поэтому же не работает Дейкстра с орицательными ребрами, ведь нарушается третье условие.
Также работает дейкстра с потенциалами: если в каждой вершине записать какое-то число и считать длину пути как длина всех ребер + потенциал конца - потенциал начала. На этом основан алгоритм Джонсона, который работает в графах с отрицательными ребрами, но без отрицательных циклов. Так же A* является дейкстрой со сложной функцией расстояния.
Да, про это упомянуто в статье.
Этот алгоритм работает с любой функцией расстояния, если только она удовлетворяет некоторым свойствам:
Вообще изначально я хотел добавить в статью SSSP на полукольцах, Алгоритм Витерби, beam search, альфа-бета отсечение как смежные задачи, но когда в выходной день в 5 утра дебажил ALT понял, что надо завязывать. В заглавной картинке например остался Мерияр Мори -- он обобщил scanning method и Дейкстру для весов из полукольца (кольцо без обратного по сложению). Например обычная SSSP -- это SSSP в тропическом полукольце (вдоль пути разные веса складываем, к путям разным путям с одинаковыми концами применяем минимум), для вероятностного кольца (вдоль пути умножаем, веса разных путей с одинаковыми концами складываем) SSSP -- это поиск стационарного распределения в марковской цепи, ваш пример -- мин-макс полукольцо.
И поэтому же не работает Дейкстра с орицательными ребрами, ведь нарушается третье условие.
Тут кстати стоит отметить, что реализация Дейкстры через scanning method -- это довольно простая модификация, которая делает его применимым к отрицательным рёбрам, правда уже без какой-либо оценки по сложности.
Век поиска кратчайшего решения задачи о кратчайшем пути