Теория диаграмм. Как найти узлы, достижимые из заданного node, в пределах определенной стоимости?

Ответ 1

Правильная терминология к проблеме, с которой вы имеете дело, находится в семействе "алгоритмов кратчайшего пути". Проблемы с достижимостью (т.е. Warshal) касаются вопроса "существует ли путь между узлами A и B?" и он имеет двоичный ответ, вам не нужны веса в этом случае, вы только смотрите на края. Но в вашем случае вам нужно учитывать время, необходимое для перехода от node A до node B в каждом случае.

Теперь для этой проблемы нет "точной" подгонки, поскольку для решения этой проблемы можно использовать небольшое изменение в Dijktra's, Floyd's, BFS или DFS, но у вас есть дополнительная сложность из-за размера графика, это важно понять, как построить свое решение. Какой алгоритм использовать зависит от вашей конкретной комбинации ограничений по времени и доступного оборудования, которое у вас есть.

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

• В идеальном (воображаемом) мире вы запускаете алгоритм Флойда, сохраняете результирующую матрицу в чем-то вроде Redis, и что он может обслуживать ваши запросы менее чем за 10 мс, если количество клиентов растет вам может добавить больше серверов redis по мере необходимости, поскольку график вряд ли изменится очень часто (потому что в вашей конкретной проблеме у вас есть информация о дороге). Проблема с этим заключается в сложности пространства решения, самое лучшее в этом состоит в том, что все предварительно вычислено, что означает, что время ответа на запросы минимально. Чтобы реализовать некоторые вариации этого, вам нужно много места, даже кластер redis с БД, хранящимся на диске (да, а не память), и все серверы с SSD должны быть достаточными, эта опция хорошо масштабируется, когда число одновременных клиентов растут, и время ответа довольно быстро. Но погода или нет вы можете использовать это решение, зависит от количества узлов в вашем графике: даже если вам нужно предварительно скопировать расстояния, используя каждый край, вам нужно только пространство для хранения матрицы NxN, где N - количество узлов в вашем графике, если эта матрица вписывается в redis, вы можете использовать этот алгоритм и прекомпретировать все "расстояния" (в вашем случае это сумма затрат aka "время в пути" ) между всеми узлами. Позже, когда вы получаете запрос, вам нужно запросить результирующую матрицу для извлечения всех узлов с временем проезда меньше заданного значения, есть дополнительная оптимизация при сохранении этой матрицы в redis, чем вы можете выбрать node номера довольно быстро, используя отсортированные наборы.

• Затем у вас есть второе решение, которое должно изменить Dijktra, BFS или DFS, чтобы обрезать поиск на основе стоимости и ее. В этом случае вы уже отбросили Floyd из-за высокой сложности пространства, а это значит, что ваш график довольно большой как в узлах, так и в краях. В этом случае решение почти то же самое, используя вариацию любого из алгоритмов, что делает разницу в том, как вы храните график. Все 3 алгоритма могут быть изменены для эффективного реагирования в нужное вам время, но для поддержки более 10 тыс. Клиентов база данных, которую вы используете для хранения графика, имеет значение. И здесь у вас есть еще 2 варианта:

  • Использование стандартной базы данных SQL/NoSQL: эта база данных должна быть каким-то образом отложена, поскольку она должна служить вашим серверам кода (множественное число, из-за проблемы C10K), выполняющее поиск на графике. Я предлагаю вам продолжить исследования в этой области в зависимости от размера самих данных графа, но если вам удастся поместить все данные в кластер Cassandra или аналогичную технологию, его можно оптимизировать до требуемого времени ответа, и это весы очень хорошо.
  • Вы используете тот факт, что график фактически является "картой", и вы находите способ запуска запросов расстояния по данным: это потенциально требует, чтобы вы изменили способ хранения графика, чтобы добавить что-то вроде широты и долготы, Поэтому вместо того, чтобы запускать алгоритм против полного графика, что абсурдно, вы оптимизируете весь процесс, используя тот факт, что с учетом определенного количества минут от данного node вы можете перевести это на расстояние D в милях (приблизительное, вы можете добавить что-то вроде 10-20 миль, чтобы быть в безопасности), и вы запускаете запрос в базе данных для извлечения всех узлов до этого расстояния D, а затем вы запускаете алгоритм по вашему выбору против этого небольшого графика. Важно отметить, что график, который вы вытаскиваете из базы данных с помощью этого метода, уже дает вам приблизительное решение, если фактическое время движения в ребрах несколько пропорционально пройденному расстоянию (это не всегда так, поэтому приближение). Чтобы реализовать это в небольшом масштабе, вы должны использовать PostgreSQL + PostGIS, который позволяет запускать такие запросы, но вам нужно будет сделать некоторые исследования здесь, чтобы попытаться найти решение, которое масштабирует/работает наилучшим образом для вас.

Надеюсь, что это поможет!

Ответ 2

Я смотрел "доступность" или "достижимость", но они кажутся чтобы быть неправильными ключевыми словами.

Да, вы правы. Это неправильные ключевые слова.

Во-первых, позвольте мне более точно определить проблему. Для графа G (V, E), a node s и константы c, мы хотим найти множество R = {(n, d) | расстояние между s и n равно d <= c}.

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

Теперь, как часть предвычисления, чтобы найти множество R, вам нужно будет определить длину кратчайшего пути между s и всеми другими узлами. Это проблема маскировки всех пар (APSP).

Итак, первый шаг - предварительная компиляция - поиск в исследовательских библиотеках по очень быстрому алгоритму APSP, который соответствует типу графиков, с которыми вы имеете дело. Алгоритм и его реализация определяют время выполнения предварительной обработки.

Второй шаг - найти способ хранения как можно больше из результатов алгоритма и настолько эффективно, насколько возможно, потому что структуры данных и алгоритмы, которые вы выбираете здесь, будут определять время выполнения запроса. Рассматривая миллиард вершин, количество кратчайших путей, вычисленных по алгоритму, будет составлять около 10 18 (от, до, расстояние) триплетов. Если размер каждого значения составляет 4 байта, тогда вам понадобится около 7 экзабайт, если мы сохраним все эти данные в распределенной хэш-таблице (что требует дополнительного хранения). В этом случае мы можем достичь времени запроса не более нескольких миллисекунд.

В противном случае, если вы не можете сохранить все эти данные, вам придется либо сжать данные, либо отказаться от некоторых из них. Это другая проблема. Возможно, вам захочется разбить график на многие подграфы малого диаметра (диаметр должен быть определен экспериментально), а затем хранить кратчайшую информацию о пути только для узлов в центрах подграфов, и во время запроса вам придется перезапустить очень эффективную реализация SSSP (кратчайший путь с одним источником). Существует много других методов оптимизации, которые могут легко охватывать книгу. Независимо от того, что вы делаете, достижение времени запроса < 200мс очень сложно.

Результаты кэширования запросов в DRAM и локальных дисках - отличная идея. Это может сильно помочь, если большой процент запросов одинаковый.

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

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

Ответ 3

Расстояния в кратчайшем пути в взвешенном графе дают график структуры метрического пространства. В метрической пространственной терминологии вы пытаетесь найти замкнутый шар радиуса c с центром в s. Возможно, есть некоторые исследования по обработке графов как дискретных метрических пространств с возможностью вычисления. Можно также ввести понятие эксцентриситета, где эксцентриситет a node является максимальным расстоянием от этой точки до любой другой точки. Похоже, вы пытаетесь найти максимальный подграф с тем свойством, что эксцентриситет s в подграфе ограничен c.

Алгоритм Дейкстры может быть явно изменен, чтобы дать то, что вы ищете. Если в любой точке алгоритма Дейкстры вы включили бы вершину в множество посещенных узлов (узлы, для которых известно конечное расстояние), но с результирующим расстоянием, которое превышает c, выбросьте это node, а не добавьте его в список посещенных узлов. Это приведет к обрезке дерева узлов, доступных из s. Должна быть разумно эффективной.

Ответ 4

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

К сожалению, алгоритм O (V ^ 3) в отношении временной сложности и O (V ^ 2) в сложности пространства, поэтому он довольно дорог. Учитывая, что ваша примерная проблема звучит довольно большой, относительно количества узлов, вы, вероятно, не захотите запускать этот алгоритм на весь набор данных, если только у вас нет тонны памяти, которую вы хотите использовать, сохраняя предварительно вычисленные результат этого.

В зависимости от типов поисковых запросов, которые вы делаете, вы можете разбить дорожную сеть на более мелкие секции, а затем запустить алгоритм Floyd-Warshall на меньшем наборе данных, чтобы вам не приходилось хранить весь результат. время. Это будет работать только в том случае, если люди ищут небольшие расстояния, например, на вашем месте в 1 час. Если люди искали что-либо в пределах 1000 миль, разбить его на куски не помогло бы, и вычисление этого не могло бы быть сделано в режиме реального времени в течение ограничений времени, которые вы предоставили. Так же эффективно, как вы могли бы это сделать, поиск всего в таком огромном радиусе займет значительное время, чтобы вычислить (вероятно, гораздо больше, чем ваше ограничение по времени).

Реально, лучшее решение будет зависеть от того, как люди его используют и как распространены поисковые запросы.

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

Если вас беспокоит скорость и напряжение вычислений на вашем сервере, вам может потребоваться ограничить количество расстояний, которые вы собираетесь принять.

Ответ 5

Когда я работал с этим, мы называли Dijkstra со значением отсечки, где отсечка - это максимальная стоимость, которую мы интересуем.

Например, как используется здесь алгоритмы arcgis.

Ответ 6

Эти алгоритмы будут работать. Первая будет быстрой для мягких сред, где стоимость перехода из одного места в другое довольно велика. Второй - менее восприимчивый.

Пусть G - ориентированный граф, v a node, с которого мы начинаем, C стоит.

//in case, there is no cycle of cost 0, but in metrical environment there won't be one
GLOBAL SET result = {};
def AchievableNodes(G,v,C):
    for each w: e = (v,w) in Edges:
        if c(e) < C:
            result.addIfNotInResult(w) 
            AchievableNodes(G, w, C-c(e))

AchievableNodes(G, root, C)
print(result)


GLOBAL ARRAY result[|V|] - initialized with 0s.
def AchievableNodes(G, v, C):
    for each w: e = (v,w) in Edges:
        if c(e) < C:
            if result[w] > result[v] + c(e):
                result[w] = result[v] + c(e)
                AchievableNodes(G, w, C-c(e))

AchievableNodes(G, v, C)
print(result)

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