Как найти самый длинный путь в циклическом графе между двумя узлами?
-
30-09-2019 - |
Вопрос
Я уже решил большинство вопросов, опубликованных здесь, все, кроме самый длинный путь один. Я прочитал статью Википедии о самых длинных путях, и кажется какой-либо легкой проблемой, если график был ациклическим, который мой нет.
Как я могу решить проблему тогда? Brute Force, проверяя все возможные пути? Как мне даже начать делать?
Я знаю, что это будет много на графике с ~ 18000. Но я просто хочу все равно разрабатывать все равно, потому что это требуется для проекта, и я просто проверим его и покажу его инструктору на меньшую масштабную график, где время выполнения находится всего в секунду или два.
По крайней мере, я выполнял все задачи, и у меня есть поддержание концепции, что она работает, но нет лучшего способа на циклических графах. Но у меня нет подсказки, где начать проверять все эти пути ...
Решение
Решение состоит в том, чтобы расстроить его. Вы можете сделать некоторые оптимизации, чтобы ускорить его, некоторые из них тривиальные, некоторые очень сложные. Я сомневаюсь, что вы можете заставить его работать достаточно быстро для 18 000 узлов на настольном компьютере, и даже если вы не сможете представить, как. Вот как работает BruteForce, однако.
Примечание: Dijkstra и любой другой кратчайший алгоритмы пути не будут работать на эту проблему, если вы заинтересованы в точном ответе.
Start at a root node *root*
Let D[i] = longest path from node *root* to node i. D[*root*] = 0, and the others are also 0.
void getLongestPath(node, currSum)
{
if node is visited
return;
mark node as visited;
if D[node] < currSum
D[node] = currSum;
for each child i of node do
getLongestPath(i, currSum + EdgeWeight(i, node));
mark node as not visited;
}
Давайте запустим его вручную на этом графике: 1 - 2 (4), 1 - 3 (100), 2 - 3 (5), 3 - 5 (200), 3 - 4 (7), 4 - 5 (1000)
Let the root be 1. We call getLongestPath(1, 0);
2 is marked as visited and getLongestPath(2, 4); is called
D[2] = 0 < currSum = 4 so D[2] = 4.
3 is marked as visited and getLongestPath(3, 4 + 5); is called
D[3] = 0 < currSum = 9 so D[3] = 9.
4 is marked as visited and getLongestPath(4, 9 + 7); is called
D[4] = 0 < currSum = 16 so D[4] = 16.
5 is marked as visited and getLongestPath(5, 16 + 1000); is called
D[5] = 0 < currSum = 1016 so D[5] = 1016.
getLongestPath(3, 1016 + 200); is called, but node 3 is marked as visited, so nothing happens.
Node 5 has no more child nodes, so the function marks 5 as not visited and backtracks to 4. The backtracking will happen until node 1 is hit, which will end up setting D[3] = 100 and updating more nodes.
Вот как это будет выглядеть итеративно (не тестировано, просто базовая идея):
Let st be a stack, the rest remains unchanged;
void getLongestPath(root)
{
st.push(pair(root, 0));
while st is not empty
{
topStack = st.top();
if topStack.node is visited
goto end;
mark topStack.node as visited;
if D[topStack.node] < topStack.sum
D[topStack.node = topStack.sum;
if topStack.node has a remaining child (*)
st.push(pair(nextchild of topStack.node, topStack.sum + edge cost of topStack.node - nextchild))
end:
mark topStack.node as not visited
st.pop();
}
}
(*) - Это немного проблемы - вы должны держать указатель на следующий ребенок для каждого узла, поскольку он может измениться между различными итерациями цикла во время и даже сбрасывать сам (указатель сбрасывается при выпке topStack.node
узел со стека, поэтому убедитесь, что сбросить его). Это легче всего реализовать на связанные списки, однако вы должны использовать либо int[]
списки или vector<int>
Списки, чтобы иметь возможность хранить указатели и иметь произвольный доступ, потому что вам это понадобится. Вы можете сохранить, например, next[i] = next child of node i in its adjacency list
и обновите это соответственно. У вас могут быть некоторые краевые случаи и могут понадобиться разные end:
Ситуации: нормальный и тот, который происходит, когда вы посещаете уже посещенный узел, в этом случае указатели не нужно сбрасывать. Может быть, переместите посещаемое условие, прежде чем решить что-то топить в стеке, чтобы избежать этого.
Посмотрите, почему я сказал, что не стоит беспокоить? :)