Блог

Главная - Вопросы по программированию - Почему в этом решении говорится, что DFS должна выполняться в обратном порядке?

Почему в этом решении говорится, что DFS должна выполняться в обратном порядке?

#algorithm #depth-first-search

#алгоритм #поиск в глубину

Вопрос:

Разве он не будет продолжать находить t, если мы начнем с s?

Дайте алгоритм линейного времени, который принимает в качестве входных данных ориентированный ациклический граф G = (V, E) и две вершины s и t и возвращает количество путей от s до t в G.

решение:

Основная идея здесь состоит в том, чтобы начать с вершины t и использовать поиск в глубину в обратном направлении, пока мы не достигнем вершины s. Каждый и поддерживает счетчик, который указывает количество уникальных обратных путей, найденных из вершины t.

  1. Инициализируйте счетчики равными 0 для всех вершин.
  2. Запустите поиск в глубину в обратном направлении, используя вершину t в качестве корня.
  3. Для каждого ребра (u, y), проверенного при поиске в ширину. Counter(v) = max{ Counter(v) 1, Counter(v) Counter(u) }
  4. Возвращаемый счетчик (ы).

Комментарии:

1. В вопросе явно указано начать с t, а не s . И дело в том, чтобы посмотреть, как могут существовать уникальные обратные пути от t до s.

2. В приведенном тексте сначала говорится о DFS, а затем о BFS, так что же это? Я не думаю, что DFS будет работать в любом направлении, потому что вы всегда Counter(s) будете иметь значение 1 (или 0).

3. И я не понимаю, как это будет работать и с BFS.

4. джон Уэлдон: Я разделил вопрос и решение, которое я нашел, чтобы сделать его более понятным.

Ответ №1:

Вы можете попробовать это: (это из http://arxiv.org/PS_cache/cond-mat/pdf/0308/0308217v1.pdf , стр. 5).

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

  1. Начните с wt (S) = 1 и d (s) = 0;
  2. Каждой вершине i, смежной с S, присваивается вес = w (s) = 1 и d (i) = (d) 1;

  3. Для каждой вершины j, смежной с одной из этих вершин, и d (j) еще не определено, если w (j) = 0, тогда присваивается w(i) = w (j) / то есть присваивается wt родительского элемента j / else, если d (j) = d (i) 1, тогда w(j) = w (i) 1.

  4. Повторяйте шаг 3 до достижения T. wt (t) даст количество кратчайших путей от s до T.

Соответственно, в документе объясняется, почему это линейно.

Ответ №2:

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

Как прямой, так и обратный поиск основаны на одном и том же общем идентификаторе, который заключается в том, что

 number-of-paths(s, t) =
  sum over nodes 'c' of any cut of the graph that separates s from t:
    number-of-paths(s, c) * number-of-paths(c, t)