Вопрос по algorithm – Самый длинный путь в DAG

9

Чтобы найти самый длинный путь в группе обеспечения доступности баз данных, я знаю 2 алгоритма: алгоритм 1: выполнить топологическую сортировку + использовать динамическое программирование с результатом ~ или ~ алгоритм 2: перечислить все пути в группе обеспечения доступности баз данных с использованием DFS, и записать самое длинное. Кажется, что перечисление всех путей с помощью DFS имеет лучшую сложность, чем алгоритм 1. Это правда?

Ваш Ответ

3   ответа
8

DFS не исследует все возможные пути, если ваш граф не является деревом или лесом, и вы начинаете с корней. Второй алгоритм, который я знаю, сводит на нет веса и находит кратчайший путь, но он несколько медленнее, чемТоп сортировки + алгоритм DP что вы перечислили как # 1.

Даже если вы начнете с источников, рассмотрите график с бриллиантами:A->B,C ; B->D ; C->D ; D->E,F ; E->G ; F->G. A является источником, поэтому вы начинаете изучать его. Ты идиA-B-D-E,G, вернуться кD, пытатьсяA-B-D-F-G, вернуться кA, пытатьсяA-C-Dи остановись, потому чтоD был полностью изучен сейчас. Если самый длинный путь по весуA-C-D-E-G, DFS не собирается его найти.
Почему вы начали с B? Вы должны запустить DFS из источников. Frank
@dasblinkenlight, DFS (в группе DAG), которая маркирует текущий исследуемый узел по сумме максимального веса от цели, и дочерний элемент, который его дал, найдет самый длинный путь. Вы можете сказать, что это замаскированное динамическое программирование.
Хорошо, я имел в виду DFS с перезапуском с любой вершины, которая не посещалась на предыдущих проходах DFS. Это будет исследовать весь DAG. Разве это не должно быть быстрее, чем topo sort + DP? Frank
@Frank DFS с перезапуском с вершин, которые не были посещены, не исследует все пути. Рассмотрим графикA->B->C; вы запускаете DFS из B, идете в C и останавливаетесь; затем перезапустите с A, перейдите к B и остановитесь снова, потому что вы уже посетили C. Оба пути, которые нашел DFS,B-C а такжеA-Bимеют длину 1; самый длинный путьA-B-C имеет длину 2.
2

Алгоритм: принимает DAG G. Каждая дуга содержит одну переменную E

for each node with no predecessor :
    for each of his leaving arcs, E=1.
for each node whose predecessors have all been visited :
    for each of his leaving arcs, E=max(E(entering arcs))+1.

max_path - это самый высокий E в пределах ребер, когда все узлы были обработаны.

Это правильный ответ; увидетьen.wikipedia.org/wiki/…
3

используя & quot; DFS & quot ;:

def enumerate_dag(g):

  def enumerate_r(n, paths, visited, a_path = []):
    a_path += [n]
    visited[n] = 1
    if not g[n]:
        paths += [list(a_path)]
    else:
        for nn in g[n]:
            enumerate_r(nn, paths, visited, list(a_path))

  paths, N = [], len(g)
  visited = np.zeros((N), dtype='int32')

  for root in range(N):
    if visited[root]: continue
    enumerate_r(root, paths, visited, [])

  return paths
Вы пытались передать в этот код граф с двумя ромбами? Похоже, у него есть 50/50 шанс пропустить самый длинный путь.
Я неправильно понял использованиеvisited в вашем коде: вы устанавливаете его, но не используете его, чтобы решить, следует ли продолжить обход. Это не то, что называетсяDFSпотому что DFS не посещает узлы, которые были полностью исследованы. Самое большое различие между DFS и вашим кодом в том, что ваш код чрезвычайно неэффективен. Попробуйте повторить один и тот же ромбовидный узор пятьдесят раз, чтобы понять, что я имею в виду: ваша программа изучит все2^50 пути, и это много путей для изучения.
Я только что попробовал с: [[1,2], [3], [3], [4], [5,6], [7], [7], [8], [9], [] ]. Я получаю 4 пути: [[0, 1, 3, 4, 5, 7, 8, 9], [0, 1, 3, 4, 6, 7, 8, 9], [0, 2, 3, 4 , 5, 7, 8, 9], [0, 2, 3, 4, 6, 7, 8, 9]], и я считаю, что это правильный ответ. Насколько я могу судить (из многих других тестов), этот алгоритм правильно перечисляет пути в DAG. Топографическая сортировка основана на очень похожем использовании DFS. При условии, что вы запускаете / перезапускаете источники, DFS изучитall узлы достижимы из каждого источника, следовательно, код вышеcompletely исследует DAG, ни одна вершина не пропущена. Frank
Но я могу видеть, как перечисление всех путей, чтобы найти самый длинный, будет иметь плохую сложность по сравнению с сортировкой топологий + упорядочением. Frank
@dasblinkenlight стратегия исследования группы обеспечения доступности баз данных - «DFS»: она расширяет каждый путь к приемнику, а затем возвращает его обратно. Что касается "чрезвычайно неэффективного", то цель состоит в том, чтобы перечислять все пути для этой функции. Так что да, он должен посещать некоторые узлы много раз. Frank

Похожие вопросы