Найти максимальную длину графика

Question

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

Представьте, что мы имеем следующий график:

Мне нужно построить класс, который вычисляет максимальную длину пути. У меня нет корня и вы должны использовать каждую вершину в качестве отправной точки. Метод имеет параметр максимального количества повторений, поэтому, если это 1, мы можем просто передать каждое ребро один раз, если это 2, мы можем передать максимум 2 раза каждый край.

В этом случае, если repeatts = 1, максимальный путь должен быть (B, A, C). Он повторяется = 2, тогда максимальный путь должен быть (B, A, B, A, C, C).

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

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

Thanks

Answer 1

Вы можете использовать модифицированную версию первого поиска глубины.

В этом случае вы не только пометить узел, как посетили но добавить некоторые спутниковые данные для них: раз посетили и когда она достигает repeats вы отметите их посетило.

Модифицированный псевдокод из википедии:

procedure DFS(G,v): 
    increment v.timesVisited 
    for all edges e in G.adjacentEdges(v) do 
     if edge e.timesVisited < repeats then 
      w ← G.adjacentVertex(v,e) 
      if vertex w.timesVisited < repeats then 
       e.timesVisited++ 
       recursively call DFS(G,w) 
      else 
       label e as a back edge 

Я надеюсь, что это работает, я не проверял изменения.

Answer 2

Если я правильно понял, решение аналогично для обоих случаев.

Для решения без повторов: вы берете каждый узел как корень, и запускаете DFS для своих детей. Допустимым дочерним узлом узла является узел, который еще не посетил ben.

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

Answer 3

Я вижу наивный подход. Это не эффективность, но она работает.

Два элемента:

• HashMap лучше с записью для каждого набора края до 0
• Fetch граф с помощью DFS (приращение и декремент HashMap знать свою выборку)

As у вас нет корня, я думаю, вам придется делать это для каждого узла.

Вам нужно найти все решения или вы ищете подходящее решение?

Вы не можете найти больше объяснений по википедии о таком роде проблема: http://en.wikipedia.org/wiki/Longest_path_problem