11

ここに投稿されたほとんどの質問は、最長のパスを除いてすべて解決しました。最長パスに関するウィキペディアの記事を読んだことがありますが、グラフが非循環的である場合は簡単な問題のようですが、私の場合はそうではありません。

どうすれば問題を解決できますか？可能性のあるすべてのパスをチェックして、力ずくで？どうすればそれを始められますか?

〜18000のグラフで多くの時間がかかることはわかっています。しかし、とにかくそれを開発したいのは、プロジェクトに必要なためです。テストして、実行時間がわずか 1 秒または 2 秒の小さなスケールのグラフでインストラクターに表示します。

少なくとも私は必要なすべてのタスクを実行し、それが機能するという概念実証を実行していますが、巡回グラフにはこれ以上の方法はありません。しかし、これらすべてのパスのチェックをどこから開始すればよいかわかりません...

4

1 に答える 1

9

解決策は、力ずくで攻撃することです。速度を上げるためにいくつかの最適化を行うことができます。いくつかは些細なもので、いくつかは非常に複雑です。デスクトップ コンピューターで 18,000 ノードを処理するのに十分な速度で動作させることができるとは思えません。ただし、ブルートフォースの仕組みは次のとおりです。

注:正確な答えに関心がある場合、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();
    }
}

(*) - これは少し問題です - 各ノードの次の子へのポインターを保持する必要があります。これは、while ループの異なる反復間で変更され、それ自体をリセットすることさえできるためです (ポインターは、ノードをポップすると自身をリセットします)。topStack.nodeノードがスタックから外れているため、必ずリセットしてください)。これは、リンクされたリストで実装するのが最も簡単ですが、必要になるため、ポインターを格納してランダムアクセスできるように、int[]リストまたはリストのいずれかを使用する必要があります。vector<int>たとえばnext[i] = next child of node i in its adjacency list、それを維持し、それに応じて更新することができます。いくつかのエッジケースがあり、異なる必要がある場合がありますend:状況: 通常の状況と、既に訪問したノードを訪問したときに発生する状況 (この場合、ポインターをリセットする必要はありません)。これを回避するために、スタックに何かをプッシュすることを決定する前に、訪問済みの条件を移動してください。

気にするなと言った理由がわかりますか？:)

于 2010-04-22T06:41:24.653 に答える