3

私は DAG を持っており、リージョン内で特定の長さのすべての可能なパスを見つけることができる必要があります。たとえば、頂点が 3 つ以上 7 つ以下のすべてのパスを見つけたいとします。最初に考えたのは、すべてのパスを見つけて、それらを取り除くアルゴリズムを見つけることでした。

誰でもアドバイスを提供できますか？

4

1 に答える 1

3

長さ K のすべてのパスを列挙すると、一般に O(2^K) になるため、考えられるすべてのパスを列挙しないという上記の提案は適切であると思います。例えば：

グラフ

このグラフのすべてのエッジが左から右に向けられているとしましょう (つまり、これは DAG です)。次に、3 つの「ダイヤモンド」のそれぞれについて、上または下のパスを選択できるため、左端から右端のノードまで 2^3 パス (つまり、長さ 6 の 2^3 パス) があります (したがって、 3 つのバイナリ選択のすべての順列)。パターンに従ってグラフを拡張することができます (ひし形を追加することによって)。K 個のひし形の場合、長さ 2K の 2^K パスが存在します。

したがって、必要なパスのみを列挙することをお勧めします (特に、例のように短い場合)。

幅優先検索を使用するという上記の提案は、すべてのパスを列挙するのに役立つと思いますが、より大きなケースでは、必要なスペースは 2^K になります (長さ K 以下のすべてのパスを検索する場合)。長さ n のすべてのパスを見つけるには、長さ n-1 のすべてのパスを覚えておく必要があるためです。深さ優先検索 (またはそれを修正したバージョン) も同様に機能します。

DFS(int maxLen, Node node):
    list<Node> path
    path.add(node)
    DFS_Helper(maxLen, path)

DFS_Helper(int maxLen, list<Node> path):
    print(path)
    if (path.size() >= maxLen)
        return
    set<Node> targets = graph.getNodesPointedToBy(path.last())
    for Node target in targets:
        path.append(target)
        DFS(maxLen, path)
        path.removeLastNode()

スペース使用量は O(|V|) です (グラフが非循環であるため、頂点のセット V の任意の頂点は、最大 1 つの再帰呼び出しの「ターゲット」セットに表示できます)。これにはまだ O(2^k) ランタイムがあることに注意してください (上記で説明したように避けられません)。そのブーストのために、これを行うための既製のアルゴリズムがないと推測しています (これが、いくつかの疑似コードを含めた理由です)。その上）。これには下限が含まれていませんが、含めるのはそれほど悪いことではありません。

編集: 私は当初、DFS のスペース使用量は O(K) であり、K は最大パス長であると主張しました。DFS_Helper への各再帰呼び出しで設定された「ターゲット」によって使用されるスペースを含めることを怠ったため、これは正しくなく、実際のスペース使用量よりも低くなっています。スペースの使用量は、BFS よりも大幅に少なくなります。

于 2012-07-21T00:06:44.110 に答える