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

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

2 голосов
/ 03 ноября 2011

Не будет ли продолжаться поиск 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. Счетчик (и) возврата.

Ответы [ 2 ]

0 голосов
/ 03 ноября 2011

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

И прямой, и обратный поиск основаны на одной и той же общей идентичности, а именно: 

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)
0 голосов
/ 03 ноября 2011

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

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

  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) / , то есть присваивается вес родительского элемента j / иначе, если d (j) = d (i) +1, то w (j) = w (i) + 1.

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

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

...