Алгоритм проверки доступности вершины

Question

Существует ли алгоритм, который может проверить в ориентированном графе, достижима ли вершина, скажем, V2, из вершины V1, не проходя все вершины?

Answer 1

Вы могли бы найти маршрут к этому узлу, не пересекая все ребра, и если это так, вы можете дать ответ "да", как только вы это сделаете. Ничто, кроме пересечения всех ребер, не может подтвердить, что узел недоступен (если только вы не указали какое-либо другое ограничение, которое можно было бы использовать для устранения возможности ранее).

Изменить: Я должен добавить, что это зависит от того, как часто вам нужно делать запросы, в зависимости от того, насколько большой (и плотный) ваш график. Если вам нужно выполнить огромное количество запросов на относительно небольшом графике, может иметь смысл предварительно обработать данные на графике, чтобы получить матрицу с битом на пересечении любых V1 и V2, чтобы указать, есть ли соединение от V1 до V2. Это не исключает обход графика, но позволяет избежать обхода графика во время запроса. То есть, это в основном жадный алгоритм, который предполагает, что вы в конечном итоге будете использовать достаточно комбинаций, так что проще всего обойти их все и сохранить результат. В зависимости от размера графика этап предварительной обработки может быть медленным, но как только он завершится, выполнение запроса становится довольно быстрым (постоянное время, и обычно довольно небольшая константа).

Answer 2

Поиск в глубину или Поиск в ширину .Остановись, когда найдешь.Но нет никакого способа сказать, что нет ничего, не пройдя каждый, нет.Иногда вы можете улучшить производительность с помощью некоторой эвристики, например, если у вас есть дополнительная информация о графике.Например, если график представляет собой координатное пространство, похожее на реальную карту, и большую часть времени вы знаете, что это будет в основном прямой путь, тогда вы можете попытаться выполнить поиск в глубину по линиям, которые «направлены кцель".Тем не менее, представьте себе случай, когда начальная и конечная точки вправо расположены рядом друг с другом, но без промежуточного вектора, и чтобы найти его, вам нужно пройти путь с пути,Вы должны проверить каждый случай, чтобы быть исчерпывающим.

Answer 3

Я сомневаюсь, что у него есть имя, но поиск в ширину может выглядеть так:

Add V1 to a queue of nodes to be visited
While there are nodes in the queue:
    If the node is V2, return true
    Mark the node as visited
    For every node at the end of an outgoing edge which is not yet visited:
        Add this node to the queue
    End for
End while
Return false

Answer 4

Создать матрицу смежности при создании графика. В то же время вы делаете это, создавая матрицы, состоящие из степеней матрицы смежности вплоть до количества узлов в графе. Чтобы определить, существует ли путь от узла u к узлу v , проверьте матрицы (начиная с M ^ 1 и перейдя к M ^ n ) и проверьте значение в ( u , v ) в каждой матрице. Если для какой-либо из проверенных матриц это значение больше нуля, вы можете остановить проверку, потому что соединение действительно существует. (Это также дает вам еще больше информации: мощность сообщает вам количество шагов между узлами, а значение указывает, сколько путей существует между узлами для этого номера шага.)

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

Вероятно, было бы проще всего выполнить поиск в глубину или в ширину, хотя, как и другие предлагали, не только потому, что они сравнительно просты в реализации, но и потому, что вы можете генерировать путь между узлами по ходу работы. вместе. (Технически вы будете генерировать несколько путей и отбрасывать циклы / тупики по пути, но все что угодно.)

Answer 5

Вы упомянули здесь , что график представляет дорожную сеть.Если график плоский, вы можете использовать Алгоритм Торупа , который создает структуру данных пространства O (nlogn), для построения которой требуется время O (nlogn), и отвечает на запросы за время O (1).

Answer 6

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

Вы МОЖЕТЕ улучшить свою производительность, выполнив поиск в обратном направлении (поиск от пункта назначения до начальной точки) или чередуя шаги поиска вперед и назад.

Любой хороший учебник по искусственному интеллекту подробно расскажет о методах поиска. Книга Элейн Рич была хороша в этой области. Амазонка - твой ДРУГ.

Answer 7

Другой подход к этой проблеме позволит вам игнорировать все вершины. Если бы вы смотрели только на ребра, вы можете создать массив транзитивного замыкания, который покажет вам каждую вершину, достижимую из любой другой вершины.

Начните с вашего списка ребер: Va -> Vc Va -> Vd ....

Создание массива с начальным местоположением в качестве строк и конечным местоположением в качестве столбцов. Заполните массивы 0. Для каждого ребра в списке ребер поместите единицу в начальную и конечную координаты ребра.

Теперь вы выполняете итерацию несколько раз, пока V1, V2 не станут равны 1 или не произойдет никаких изменений.

For each row:
    NextRowN = RowN
    For each column that is true for RowN
        Use boolean OR to OR in the results of that row of that number with the current NextRowN.
    Set RowN to NextRowN

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

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

Answer 8

Чтобы быть уверенным, вам нужно либо найти путь, либо пройти все вершины, которые достижимы из V1 один раз.

Я бы порекомендовал реализовать поиск в глубину или поиск в ширину, который останавливается привстречает вершину, которую он уже видел.Вершина будет обработана только при первом появлении.Вы должны убедиться, что поиск начинается с V1 и заканчивается, когда у него заканчиваются вершины или встречается V2.