Не обращая внимания на то, что никакой линии не добавлено, чего это у вас там N^0.74? N это вроде было количество вершин. Так если вы сделали поиск оптимального пути в графе за O(N^0.74), то вам полагается написать научную статью, открывающую глаза всему миру, который использует алгоритм Дейкстры, который по-определению не лучше чем O(N*log(N)).
N в тексте — это не количество вершин в графе, а количество точек, до которых требуется найти кратчайший путь. Статью, к сожалению, писать не придётся, потому что сложность Дейкстры, о которой вы пишите, зависит от количества вершин.
Только вот, боюсь, или я что-то недопонял или вы написали что-то не так. Ну просто потому что поиск путей от одной вершины до всех остальных даже в теории не может быть лучше O(N), потому что… внезапно, поиск *до всех остальных*, и каждая вершина должна быть посещена хотя бы раз.
Да, есть такая интуитивная ловушка, что для вычисления ряда алгоритм должен быть не хуже, чем O(n). На самом деле, если время прохода по ряду пренебрежимо мало (1 мс) относительно других вычислений (1 минута), то сложность может быть лучше линейной. Простой способ это показать — построить график, что и сделано в тексте.
Вот тут можно ознакомиться с современным состоянием дел в решении задачи коммивояжёра. Решение задачи оптимального обхода 50000 пабов Великобритании — это был прорыв, который решали днями на суперкомпьютере.
Нет же. В соседнем треде я попытался объяснить, что мы не считаем маршрут с 5000 фиксированными остановками. Упрощая, мы ищем оптимальный порядок их объезда.
Да, в итоге нам нужно решить CVRPTW — задача коммивояжёра, только коммивяжёров у нас много и надо решить, какому коммивояжёру какой заказ отдать. Перед тем, как начать её решать, нужно посчитать матрицу расстояний между всеми точками. Текст как раз про то, как мы эту матрицу решаем.
После того, как матрицу посчитали, можно решать уже саму задачу нахождения оптимального пути. Задача коммивояжёра на 5000 точек проще, чем эта же задача с многими коммивояжёрами. Тем не менее, чтобы её решить точно, нужно перебрать 5000! вариантов — это число с 16000 знаками. Атомов в видимой вселенной — это число с 80 знаками. Такие задачи решаются приближённо, но всё равно оптимальный путь между 5000 точек за секунды не найти. Мне кажется, что PgRouting всё же за секунды считает просто длину маршрута через фиксированный порядок из 5000 точек.
На графе дорог с пробками такие алгоритмы, как A*, плохо работают. Грубо говоря, ехать прямо через центр Москвы может быть дольше, чем по МКАДу и наоборот — всё зависит от того, где пробка.
Простой алгоритм Дейкстры правда неоптимален, поэтому мы используем иерархический вариант, которому помогает естественная декомпозицая дорожного графа на города, округа и районы. Нам поэтому не приходится обсчитывать честную волну по огромному графу. Большая часть расстояний (вроде расстояния Москва — Санкт-Петербург) посчитаны заранее и не вычисляются в рантайме.
Нам нужно знать все кратчайшие расстояния из 5000 точек в 5000 точек. Это 25 млн полноценных маршрутов, не рёбер. Мы их точно высчитываем за 115 секунд на одном ядре. Делим одно на другое — получаем 200к маршрутов в секунду на ядро.
Пример с 5000 остановок несколько не про то, как мне кажется. Там считается 5000 маршрутов, а не 25 млн.
N в тексте — это не количество вершин в графе, а количество точек, до которых требуется найти кратчайший путь. Статью, к сожалению, писать не придётся, потому что сложность Дейкстры, о которой вы пишите, зависит от количества вершин.
Да, есть такая интуитивная ловушка, что для вычисления ряда алгоритм должен быть не хуже, чем O(n). На самом деле, если время прохода по ряду пренебрежимо мало (1 мс) относительно других вычислений (1 минута), то сложность может быть лучше линейной. Простой способ это показать — построить график, что и сделано в тексте.
После того, как матрицу посчитали, можно решать уже саму задачу нахождения оптимального пути. Задача коммивояжёра на 5000 точек проще, чем эта же задача с многими коммивояжёрами. Тем не менее, чтобы её решить точно, нужно перебрать 5000! вариантов — это число с 16000 знаками. Атомов в видимой вселенной — это число с 80 знаками. Такие задачи решаются приближённо, но всё равно оптимальный путь между 5000 точек за секунды не найти. Мне кажется, что PgRouting всё же за секунды считает просто длину маршрута через фиксированный порядок из 5000 точек.
Простой алгоритм Дейкстры правда неоптимален, поэтому мы используем иерархический вариант, которому помогает естественная декомпозицая дорожного графа на города, округа и районы. Нам поэтому не приходится обсчитывать честную волну по огромному графу. Большая часть расстояний (вроде расстояния Москва — Санкт-Петербург) посчитаны заранее и не вычисляются в рантайме.
Пример с 5000 остановок несколько не про то, как мне кажется. Там считается 5000 маршрутов, а не 25 млн.