Это как? Если Вы взялись сравнивать два O(nlogn), то уж точно не с такой аргументацией. Быстрая сортировка в среднем делает nln(n) сравнений (обычно в анализе приводят 2n(ln), как например тут, но там алгоритм разделения предполагает n сравнений на n элементов в то время как обычно используется алгоритм с n/2 сравнений. С пирамидальной сортировкой сложнее, потому что худший случай -- это когда во всех операциях новый/удаляемый элемент проходит полностью путь от корня до листа и наоборот, но даже тут есть нюанс, заключающийся в том, что размер кучи равномерно изменяется от 1 к n и обратно, что ведет к n(log_2(n)-2), в среднем случае как будто получается nlog_2(n) (не проверял) и разница соответственно уже на в два раза, а ln(2). Короче я это к тому, что стоит вкидывать не совсем верные утверждения без должного подкрепления где это можно детально посмотреть.
Промышленные методы сортировки - это сплав быстрой, вставок и пирамиды
Ну что за недосказанность! Это описание сортировки introsort, используемой например в качестве std::sort в gcc c неочевидной реализацией перехода на вставки для массивов длины 16. Стоит отметить, что все три используемых вспомогательных сортировок (быстрая, пирамидальная, вставками) -- inplace для массивов.
Так вроде бы KMP != построение префикс-функции для "pattern$text". KMP -- это префикс-функция для pattern и проход без доп. памяти по text, так что два последовательных цикла как раз каноничны, а конструкция "pattern$text" используется исключительно в образовательных целях
Если зафиксировать X0, то n-ый член последовательности
можно выразить как полином степени 2^n-1 по D, причем из свойств метода Ньютона получаем, что на отрезке [1.0, 2.0] его максимальное отклонение от 1/x очень маленькое. Можем ли мы найти какой-то другой полином, который можно было бы быстрее посчитать, и его отклонение было бы не хуже? Вот со вторым свойством как раз всплывают многочлены Чебышева, и основанный на нем метод Ремеза (про них не так давно была на хабре статья про вычисление синуса) -- такие методы позволяют найти многочлен фиксированной степени с наименьшим отклонением от целевой функции на отрезке. Как этот многочлен потом эффективно вычислять -- отдельный вопрос, вроде как в статье об этом отдельный параграф.
@botyaslonim это уже за гранью постиронии использовать на КДПВ генерала Лебедя при том, что он выступал не за "жесткое управление", да и хорошо его ощутил на себе
Тут нужно сделать важную оговорку, что все указанные оценки справедливы только если вы, например, делаете вычисления по модулю. Проблема в том, что длина Fn растет линейно от n из-за чего итеративный алгоритм работает на самом деле за O(n^2), а быстрый за O(nlogn) (из мастер-теоремы). Ну и соответственно если вы работаете по модулю часла длины k, то получаются оценки O(nk)/O(klogn).
Есть еще формула Бине
которая сводит вычисления чисел Фибоначчи к возведению в степень, которое можно делать за log, но из-за работы с float она не такая полезная даже для спортивного интереса, в отличии от
Также работает дейкстра с потенциалами: если в каждой вершине записать какое-то число и считать длину пути как длина всех ребер + потенциал конца - потенциал начала. На этом основан алгоритм Джонсона, который работает в графах с отрицательными ребрами, но без отрицательных циклов. Так же A* является дейкстрой со сложной функцией расстояния.
Да, про это упомянуто в статье.
Этот алгоритм работает с любой функцией расстояния, если только она удовлетворяет некоторым свойствам:
Вообще изначально я хотел добавить в статью SSSP на полукольцах, Алгоритм Витерби, beam search, альфа-бета отсечение как смежные задачи, но когда в выходной день в 5 утра дебажил ALT понял, что надо завязывать. В заглавной картинке например остался Мерияр Мори -- он обобщил scanning method и Дейкстру для весов из полукольца (кольцо без обратного по сложению). Например обычная SSSP -- это SSSP в тропическом полукольце (вдоль пути разные веса складываем, к путям разным путям с одинаковыми концами применяем минимум), для вероятностного кольца (вдоль пути умножаем, веса разных путей с одинаковыми концами складываем) SSSP -- это поиск стационарного распределения в марковской цепи, ваш пример -- мин-макс полукольцо.
И поэтому же не работает Дейкстра с орицательными ребрами, ведь нарушается третье условие.
Тут кстати стоит отметить, что реализация Дейкстры через scanning method -- это довольно простая модификация, которая делает его применимым к отрицательным рёбрам, правда уже без какой-либо оценки по сложности.
Если для вас действительно имеет значение использование рекурсии, то видимо вы работаете c системами реального времени или чем-то аналогичным по уровню требований. В такой ситуации для фундаментальных алгоритмов я бы просто не рекомендовал использовать python ибо он предназначен не для оптимизации рантайма, а для оптимизации времени разработки. Если бы я писал примеры к OSM на С++, это бы заняло примерно бесконечное время (если не привлекать питон хотя бы для обвязки), но при этом если бы стояла задача ускорить алгоритмы, то первым бы делом я их переписал на С++.
Касательно исходного вопроса: чаще всего обход в глубину можно заменить обходом в ширину, но при необходимости можно и переписать как здесь
Питон хороший язык, но не высокопроизводительный. А от библиотеки, которая заявляет, что у них
an interface to existing numerical algorithms and code written in C, C++, and FORTRAN;
я бы ожидал высокой производительности, а получаю, что все методы начиная с двунаправленного Дейкстры, которые я написал для демонстрации работают быстрее библиотечных.
А как же неравенство треугольника?
Не совсем понял вопроса. Кратчайшие расстояния от одной вершины до всех остальных удовлетворяют неравенству треугольника
Система без последействия, т.е. если кр. путь от 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* с посчитанными расстояниями и он переберет только кратчайший путь.
@wataruв соседней ветке написал, что сложность у Форда-Беллмана O(VE) и пример хороший привел где, к сожалению, отдельные оптимизации его асимптотически не ускоряют (т.е. оптимизации работают, алгоритм отрабатывает быстрее, но это все еще O(VE) с меньшей константой).
Сейчас, к сожалению, нет возможности просмотреть и изучить вами присланный материал.
Ну .... Вы сами сделали выбор попробовать допилить алгоритм вместо того, чтобы изучить материал ;)
Я не готов ручаться за мелкие баги, но в целом ваш алгоритм должен работать, так как Вы переизобрели алгоритм Форда-Беллмана с реализацией на очереди, можно про это почитать вот тут
Также стоит отметить, что по форме алгоритм очень схож со scanning method (его кстати тоже Форд придумал), который является общим видом для большинства известных алгоритмов поиска кратчайшего пути, различающихся лишь тем как выбирать очередную вершину из lst. При выборе наименьшей по расстоянию получается Дейкстра, при выборе в порядке обычной очереди получается Форд-Беллман. Про этот метод можно прочитать в том числе в презентации Гольдберга, ссылку на которую я уже присылал
А каким образом? Я изредко пишу технические статьи в области где хорошо разбираюсь, дал развернутый комментарий автору по поводу фундаментальных технических проблем статьи.
Вы пришли и сказали, что я хам, поэтому поставите мне минус, не дав при этом ни автору, ни комьюнити никакой полезной информации по теме.
Я не очень понимаю значения глагола "хейтить", но полагаю, что оно было бы более применимо, если бы я например просто молча поставил минус.
Здесь, очевидно, была шутка, но если и Вы шутили, то ок
Постирония на тему того, что если бы Ваш алгоритм действительно работал, то шутка про нобелевскую премию была бы не такой уж и шуткой.
Не совсем понял, что не так с этим примером? Вы откуда и куда хотите попасть? Если с 1 до 4 ноды, то будет 10, т.е. все правильно.
Расстояние от 1 до 2 это 12 (1->4->3->2), а алгоритм посчитал 20
Вот тут очень спорно
Каждая вершина обрабатывается во внутреннем цикле ровно один раз. Учитывая, что граф обрабатывается списками смежности, то суммарное количество итераций внутреннего цикла -- в точности количество ребер. Если быть более точным, то оценка O(V+E).
Поставил минус. Статья выглядит примерно так: "мне понравилось изучать алгоритмы, я много интересовался задачей о кратчайших путях и думаю, что мне удалось придумать что-то новое, но в моём окружении нет достаточно компетентных людей, которые бы молги объяснить получилось или нет и почему. Поэтому я напишу статью на хабре и может там мне подскажут". Рвение похвально, но хабр не место для таких статей, для этого есть например stackoverflow.
По существу: * Ваш алгоритм работает за O(E) * Ваш алгоритм НЕ выдаёт корректные кратчайшие пути
--> Минимальные стоимости от источника до ноды: {2: 20, 3: 11, 4: 10}
Если поменять местами описание 3 и 4, то расстояния будут корректными
За алгоритм поиска кратчайших путей, который работает O(E) нобелевскую премию не дадут, а вот премью Тьюринга вполне возможно, правда над этим после Дейкстры/Данцига бьются уже 60 лет, есть почти за O(E), но не совсем (надеюсь коллеги поправят если что).
По уровню материала кажется, что Вам следует разобраться с доказательствами корректности и сложности Дейкстры, Форда-Белламна и Флойда-Уоршела. Если после этого не отпадет желание изучать CS, то вот отличная обзорная презентация от Гольдберга по кратчайшим путям.
Искренне желаю удачи, молодым талантам надо помогать, но и не позволять филонить!
Это как? Если Вы взялись сравнивать два O(nlogn), то уж точно не с такой аргументацией. Быстрая сортировка в среднем делает nln(n) сравнений (обычно в анализе приводят 2n(ln), как например тут, но там алгоритм разделения предполагает n сравнений на n элементов в то время как обычно используется алгоритм с n/2 сравнений. С пирамидальной сортировкой сложнее, потому что худший случай -- это когда во всех операциях новый/удаляемый элемент проходит полностью путь от корня до листа и наоборот, но даже тут есть нюанс, заключающийся в том, что размер кучи равномерно изменяется от 1 к n и обратно, что ведет к n(log_2(n)-2), в среднем случае как будто получается nlog_2(n) (не проверял) и разница соответственно уже на в два раза, а ln(2). Короче я это к тому, что стоит вкидывать не совсем верные утверждения без должного подкрепления где это можно детально посмотреть.
Ну что за недосказанность! Это описание сортировки introsort, используемой например в качестве std::sort в gcc c неочевидной реализацией перехода на вставки для массивов длины 16. Стоит отметить, что все три используемых вспомогательных сортировок (быстрая, пирамидальная, вставками) -- inplace для массивов.
Если вы считаете, что 1 час преподавания = 1 час нагрузки, то вот краткий список вещей, которые Вы видимо не делаете/не учитываете
Подготовка и проверка домашних/контрольных работ/упражнений на практику
Подготовка к лекции накануне
Периодическое обновление материала
В местах где я работал обычно предполагалось, что 1 час преподавания = 2 часа нагрузки
Ага, а еще вот это
Так вроде бы KMP != построение префикс-функции для "pattern$text". KMP -- это префикс-функция для pattern и проход без доп. памяти по text, так что два последовательных цикла как раз каноничны, а конструкция "pattern$text" используется исключительно в образовательных целях
Если зафиксировать X0, то n-ый член последовательности
можно выразить как полином степени 2^n-1 по D, причем из свойств метода Ньютона получаем, что на отрезке [1.0, 2.0] его максимальное отклонение от 1/x очень маленькое. Можем ли мы найти какой-то другой полином, который можно было бы быстрее посчитать, и его отклонение было бы не хуже? Вот со вторым свойством как раз всплывают многочлены Чебышева, и основанный на нем метод Ремеза (про них не так давно была на хабре статья про вычисление синуса) -- такие методы позволяют найти многочлен фиксированной степени с наименьшим отклонением от целевой функции на отрезке. Как этот многочлен потом эффективно вычислять -- отдельный вопрос, вроде как в статье об этом отдельный параграф.
Главное помнить, что быстрый обратный корень выдает аппроксимацию, а не точное значение.
@botyaslonim это уже за гранью постиронии использовать на КДПВ генерала Лебедя при том, что он выступал не за "жесткое управление", да и хорошо его ощутил на себе
Range aggregation queries (SELECT average(weight) WHERE age BETWEEN 30 AND 40)
https://petsymposium.org/popets/2022/popets-2022-0128.pdf
Top-k completion (вы что-то написали в текстовом поле, а вам дают 10 продолжений)
https://dl.acm.org/doi/pdf/10.1145/2488388.2488440
Least common ancestor problem и её применения (анализ иерархии классов, зависимостей модулей)
Сбор статистики на в потоке данных
https://www.sciencedirect.com/science/article/pii/S0169023X10000753
Succint словари
https://en.wikipedia.org/wiki/Succinct_data_structure#Succinct_indexable_dictionaries
Тут нужно сделать важную оговорку, что все указанные оценки справедливы только если вы, например, делаете вычисления по модулю. Проблема в том, что длина Fn растет линейно от n из-за чего итеративный алгоритм работает на самом деле за O(n^2), а быстрый за O(nlogn) (из мастер-теоремы). Ну и соответственно если вы работаете по модулю часла длины k, то получаются оценки O(nk)/O(klogn).
Есть еще формула Бине
которая сводит вычисления чисел Фибоначчи к возведению в степень, которое можно делать за log, но из-за работы с float она не такая полезная даже для спортивного интереса, в отличии от
Да, про это упомянуто в статье.
Вообще изначально я хотел добавить в статью SSSP на полукольцах, Алгоритм Витерби, beam search, альфа-бета отсечение как смежные задачи, но когда в выходной день в 5 утра дебажил ALT понял, что надо завязывать. В заглавной картинке например остался Мерияр Мори -- он обобщил scanning method и Дейкстру для весов из полукольца (кольцо без обратного по сложению). Например обычная SSSP -- это SSSP в тропическом полукольце (вдоль пути разные веса складываем, к путям разным путям с одинаковыми концами применяем минимум), для вероятностного кольца (вдоль пути умножаем, веса разных путей с одинаковыми концами складываем) SSSP -- это поиск стационарного распределения в марковской цепи, ваш пример -- мин-макс полукольцо.
Тут кстати стоит отметить, что реализация Дейкстры через scanning method -- это довольно простая модификация, которая делает его применимым к отрицательным рёбрам, правда уже без какой-либо оценки по сложности.
Если для вас действительно имеет значение использование рекурсии, то видимо вы работаете c системами реального времени или чем-то аналогичным по уровню требований. В такой ситуации для фундаментальных алгоритмов я бы просто не рекомендовал использовать python ибо он предназначен не для оптимизации рантайма, а для оптимизации времени разработки. Если бы я писал примеры к OSM на С++, это бы заняло примерно бесконечное время (если не привлекать питон хотя бы для обвязки), но при этом если бы стояла задача ускорить алгоритмы, то первым бы делом я их переписал на С++.
Касательно исходного вопроса: чаще всего обход в глубину можно заменить обходом в ширину, но при необходимости можно и переписать как здесь
к сожалению нет, быть может есть какая-нибудь точка входа? В чем задача заключается?
Питон хороший язык, но не высокопроизводительный. А от библиотеки, которая заявляет, что у них
an interface to existing numerical algorithms and code written in C, C++, and FORTRAN;
я бы ожидал высокой производительности, а получаю, что все методы начиная с двунаправленного Дейкстры, которые я написал для демонстрации работают быстрее библиотечных.
Не совсем понял вопроса. Кратчайшие расстояния от одной вершины до всех остальных удовлетворяют неравенству треугольника
Вот еще, если не считать того, что библиотека на питоне, то в общем то вполне добротная подборка потоковых алгоритмов. Правда там только классические.
https://github.com/networkx/networkx/tree/main/networkx/algorithms/flow
Мне казалось, что это обычно называют "оптимальной подструктурой" и она вытекает из постановки. Добавлю на всякий случай
Мне кажется, что это сводится к кратчайшим путям если немного перестроить граф. Похожая ситуация в скрытых марковских цепях: там нужно найти наиболее правдоподбную последовательность в графе, есть веса на рёбрах (transition probability) и на вершинах (emission probability), но при этом все сводится к кратчайшим путям.
Нет, там про top-k completion, т.е. пользователь пишет что-то в текстовом поле, а вы ему даете самые хорошие продолжения. Вот исправленная ссылка. Алгоритм там ровно такой, который я в статье описал (есть пример с кодом), но у него есть проблема, что он может выдавать пути с циклами. Алгоритм Йена выдает только простые пути. Я не изучал вопрос подробно, но уверен, что есть алгоритмы лучше
https://madry.mit.edu/
В конце статьи есть список литературы
С потоками в opensource вообще проблематично, я к сожалению хороших пакетов не знаю. Раньше была библиотека от Гольдберга, но кажется, что он лет 20 назад на неё забил. В 2016 он давал лекцию в институте Стеклова (кстати про кратчайшие пути), я тогда у него спрашивал про библиотеку, его реакция была эпична: "О, а там даже компилирующийся код?"
А вот в том то и дело, что не гарантирует. Там еще нужно неравенство треугольника для 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* с посчитанными расстояниями и он переберет только кратчайший путь.
@wataruв соседней ветке написал, что сложность у Форда-Беллмана O(VE) и пример хороший привел где, к сожалению, отдельные оптимизации его асимптотически не ускоряют (т.е. оптимизации работают, алгоритм отрабатывает быстрее, но это все еще O(VE) с меньшей константой).
Ну .... Вы сами сделали выбор попробовать допилить алгоритм вместо того, чтобы изучить материал ;)
Комментарий по алгоритму в update 2.
Я не готов ручаться за мелкие баги, но в целом ваш алгоритм должен работать, так как Вы переизобрели алгоритм Форда-Беллмана с реализацией на очереди, можно про это почитать вот тут
https://acm.math.spbu.ru/~sk1/courses/1718s_au/conspect/conspect.pdf
https://algs4.cs.princeton.edu/44sp/
Также стоит отметить, что по форме алгоритм очень схож со scanning method (его кстати тоже Форд придумал), который является общим видом для большинства известных алгоритмов поиска кратчайшего пути, различающихся лишь тем как выбирать очередную вершину из
lst. При выборе наименьшей по расстоянию получается Дейкстра, при выборе в порядке обычной очереди получается Форд-Беллман. Про этот метод можно прочитать в том числе в презентации Гольдберга, ссылку на которую я уже присылалhttp://forskning.diku.dk/PATH05/GoldbergSlides.pdf
А каким образом? Я изредко пишу технические статьи в области где хорошо разбираюсь, дал развернутый комментарий автору по поводу фундаментальных технических проблем статьи.
Вы пришли и сказали, что я хам, поэтому поставите мне минус, не дав при этом ни автору, ни комьюнити никакой полезной информации по теме.
А точно из-за меня хабр помойкой с новостями?
Я не очень понимаю значения глагола "хейтить", но полагаю, что оно было бы более применимо, если бы я например просто молча поставил минус.
Постирония на тему того, что если бы Ваш алгоритм действительно работал, то шутка про нобелевскую премию была бы не такой уж и шуткой.
Расстояние от 1 до 2 это 12 (1->4->3->2), а алгоритм посчитал 20
Каждая вершина обрабатывается во внутреннем цикле ровно один раз. Учитывая, что граф обрабатывается списками смежности, то суммарное количество итераций внутреннего цикла -- в точности количество ребер. Если быть более точным, то оценка O(V+E).
Поставил минус. Статья выглядит примерно так: "мне понравилось изучать алгоритмы, я много интересовался задачей о кратчайших путях и думаю, что мне удалось придумать что-то новое, но в моём окружении нет достаточно компетентных людей, которые бы молги объяснить получилось или нет и почему. Поэтому я напишу статью на хабре и может там мне подскажут". Рвение похвально, но хабр не место для таких статей, для этого есть например stackoverflow.
По существу:
* Ваш алгоритм работает за O(E)
* Ваш алгоритм НЕ выдаёт корректные кратчайшие пути
Пример уже писали выше, поделюсь своим
Hidden text
graph = { 1: {2: 20, 3: 30, 4: 10}, 3: {2: 1}, 4: {3: 1} }
--> Минимальные стоимости от источника до ноды: {2: 20, 3: 11, 4: 10}
Если поменять местами описание 3 и 4, то расстояния будут корректными
За алгоритм поиска кратчайших путей, который работает O(E) нобелевскую премию не дадут, а вот премью Тьюринга вполне возможно, правда над этим после Дейкстры/Данцига бьются уже 60 лет, есть почти за O(E), но не совсем (надеюсь коллеги поправят если что).
По уровню материала кажется, что Вам следует разобраться с доказательствами корректности и сложности Дейкстры, Форда-Белламна и Флойда-Уоршела. Если после этого не отпадет желание изучать CS, то вот отличная обзорная презентация от Гольдберга по кратчайшим путям.
Искренне желаю удачи, молодым талантам надо помогать, но и не позволять филонить!