О, а с каких пор про witness passing говорят "работает", а не "будет работать"?

Не совсем. Алгоритм-то такой и останется, потому что другого нет (и едва ли мы придумаем). Партицировать можно следующим образом: каждая нода имеет полную копию графа (хуй с ним на память) и отвечает на вопрос: ДАЙ МНЕ КРАТЧАЙШЕЕ РАССТОЯНИЕ ОТ А В Б?

Помогайте, умные головы. Я в Уклоне в отделе RND, конкретно сейчас занимаюсь улучшением расчетов кратчайших путей от водителя до заказчика(ков) в режиме псевдореального времени (шаг планируется каждые 1 или, в худшем случае, 3 секунды). Дорожный граф того же Киева предполагает 120 тысяч вершин и это картографы еще жадничают, т.е. потенциально количество вершин может дойти и до 250 тысяч. Есть разновидность Дейкстры, основанной на геоэвристике, который сейчас НЕ будем обсуждать, он есть и считаем что он работает хорошо, он стремится к *линейному* времени, что очень хорошо, все рады, все довольны. Но 250 тысяч это все равно, даже для этого алгоритма, очень много. Поэтому есть этап пре-обработки дорожного графа, а именно - разделение вершин на первичные и вторичные, чтобы кратчайший путь считать только между парами первичных вершин. То есть, все то же самое, просто граф будет меньше. И вот это сейчас болит.

Таких вариантов дейкстр под крупные графы очень дофига и все они есть в литературе

Забудь про Дейкстру на минутку, сейчас упомянутую мной разновидность Дейкстры апрувнули специально нанятые для этого математики, у меня даже нет власти это отменить на данном этапе. Но они хотят Дейкстру считать не на графе в 250к вершин, а сперва его «разрядить», разметив вершины на первичные и вторичные (по принципу радиуса). И вот ту. Про лема.

Ну ок, а как именно вы вершины размечаете? Как, например, происходит нахождение вершин в радиусе от данной первичной?

Disjoint set, шоле?

Есть геоиндекс, который отвечает на вопрос дай мне все вершины, в таком-то радиусе, с учетом кривизны Земли. Он работает очень быстро и считается заранее, т.е. на момент разметки он уже есть и считай, что стоит O(1). Дальше вычисляется реальное, а не эвклидово (с учетом радиуса кривизны нашей чудесной планеты) расстояние от текущей (еще не размеченной) вершины до всех уже найденных (первая принудительно в крайней левой точке, например). Если текущая точка в радиусе уже известной первичной, она маркируется как принадлежащая ей; если в радиусе нескольких привичных, есть детерменированное правило, по которой выигрывает строго одна из первичных; если после расчета реального пути список ближайших первчиных пуст, она сама становится первичной. Примерно так.

Это работает не так быстро из-за расчета реального расстояния по графу. То есть, геоиндекс тебе возвращает { A, B, C, D }, но теперь тебе надо рассчитать реальное расстояние (текущая_врешина, A), (текущая_вершина, B)... на графе в 120к вершин и 300к ребер. Даже оптимизированный Дейкстра (которого математики подсунули), не выгребает быстрее чем 700 в час при загрузке CPU 70-80%

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

Надо прям реальное и все тут

А у вас веса ребер меняются?

А почему не объяснили им, что они ебанаты и кусок метра им роли не сыграют?

Тебе прямо самое оптимальное?

Просто он не даст такой выигрыш, чтобы с 700 в час на 20к в час.

Собственно, там целая команда математиков в два чесловека сидит и вот это дело ковывряет.

Они знают, им побоку, я не на тех должностях, меня туда не зовут

И да, реальное расстояние можно по разному считать. Как точно считается?

В смысле? Как это по разному? Есть путь в графе, у каждого ребра свой вес, сумма весов есть стоимость пути.

Так это ты опять про кратчайший путь. Забей ты пока на это, сначала граф разметить надо.

Погоди тут про другое речь: ты написал, что вычисляется реальное расстояние с учётом кривизны для каждых из пар найденных индексом точек и что оно и тормозит

Первчиные вершины высчитываются очевидным образом, есть полный порядок вершин, первая первичная вершина это, например, крайняя левая (юго-запад) точка на графе, а дальше все, что в радиусе N метров - вторично по отношению к этой вершине. Расписывать глубоко алгоритм не вижу смысла, он интуитивный. По сути, это разделение города на маленькие области. Есть правило, по которому разруливается кейс, когда вторичная вершина принадлежит сразу нескольким первичным, выигрывает всегда одна и та же детерменированным образом.

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

@vshapenko

Странный подход

Почему? Это пре-обработка графа. Те же самые алгоритмы на выходе будут по расчету пути, просто не на 120к вершин, а на 30к вершин.

Честный расчет расстояний с кривизной нифига не дешёвый

А Яндекс как делает, интересно?

Да, но на данном этапе по условиям задачи можно допустить, что эвристика О(1)