Эффективный поиск в направленном графике

StackOverflow https://stackoverflow.com/questions/4590650

  •  15-10-2019
  •  | 
  •  

Вопрос

У меня есть направленный график с миллионами вершин и краев. Приведен набор вершин, давайте предположим, что они называются «start_points». Также приведен другой набор вершин, называемый «end_points». Проблема состоит в том, чтобы найти, какие end_points можно достичь, из которых start_points.

Вот пример:

START_POINTS: S1 S2 S3 S4 S5 S6 S7 ... 
END_POINTS  : E1 E2 E3 E4 E5 E6 E7 ...

Алгоритм должен быть в состоянии сказать следующее:

S1 can reach to E1, E2, E6
S2 can reach to E9, E10
S3 cannot reach any END_POINT
S4 can reach to .....
....

Некоторые из точек end_points не могут быть достигнуты ни с одной start_point.

Теперь вопрос в том, что является наиболее эффективным способом его реализации?

Я пытался начинать с каждого начала start_point One-One и найти достигаемые end_points, используя поиск по глубине (или BFS, он сильно меняет время выполнения). Тем не менее, это занимает много времени, потому что существует так много стартовых_поинтов (есть также много end_points).

Поиск может быть оптимизирован, потому что существует огромное перекрытие между прослеженными путями start_points. Нужно помнить, какие пути могут достичь, какие end_points. Как это наиболее эффективный способ сделать это? Это может быть хорошо известной проблемой, но я еще не смог найти решение.

Редактировать 6 января:

Я попытался реализовать идею Highbandwidth (таким же образом, как предложил Кит Рэндалл): для каждого узла, если этот узел не является запуском или конечной точкой, подключите все входы к выходам, затем удалите узел.

foreach NODE in NODES
    Skip if NODE is START_POINT or END_POINT
    foreach OUTPUT_NODE of NODE
        Disconnect NODE from INPUT_NODE
    end
    foreach INPUT_NODE of NODE
        Disconnect NODE from INPUT_NODE
        foreach OUTPUT_NODE of NODE
            Connect INPUT_NODE to OUTPUT_NODE
        end
    end
    Remove NODE from NODES
end

Это начинается очень быстро и быстро становится очень медленным, в основном потому, что входные/выходные данные оставшихся узлов становятся очень большими и вложенными для петли убивают производительность. Есть идеи, как это можно сделать более эффективным?

Это было полезно?

Решение

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

Другие советы

Это может быть излишним, но вы можете проверить Дейкстра. Анкет Я использовал его в прошлом при создании собственной таблицы маршрутизации виртуальных узлов. В этом случае все ваши узлы будут иметь значение 1, что означает, что каждый узел стоит одинаково.

Во -первых, запустите сильно связанные компоненты алгоритм. Затем сжимайте все подключенные компоненты на один узел. Затем выполнить топологический вид графика. Затем, за один проход, вы можете вычислить, какие начальные узлы могут достичь каждого узла на графике (инициализируйте каждый стартовый узел S к набору {S}, затем выполнять объединение входящих краев в каждом узле в топологическом порядке).

У вас есть потенциальная проблема в том, что ответ может быть таким же большим, как # начало узлов * # конечные узлы, которые могут быть большими. Надеемся, что у вас есть несколько больших SCC, которые будут сжиматься с отдельными узлами, так как это может сделать ответ гораздо более кратким (все начальные узлы в одном и том же SCC могут достигать одних и тех же мест, поэтому вам нужно использовать только одного представителя в своих наборах).

Лицензировано под: CC-BY-SA с атрибуция
Не связан с StackOverflow
scroll top