5

深さ優先探索を使用して、有向加重グラフのパスを特定し、サイクルに属するノードを再検討し、移動した合計距離またはソースノードからの停止に基づいてカットオフ条件を設定しています。

私が理解しているように、再帰では、深さ優先探索に明示的なスタック構造は必要ありません。したがって、明示的なスタックを使用せずに、以下のコードをさらに単純化できるかどうか疑問に思いました。

public class DFSonWeightedDirectedGraph {

    private static final String START = "A";
    private static final String END = "E";
    private int pathLength = 0;
    private int stops = 0;

    public static void main(String[] args) {
        //this is a directed weighted graph
        WeightedDirectedGraph graph = new WeightedDirectedGraph();
        graph.addEdge("A", "B", 15);
        graph.addEdge("A", "D", 15);
        graph.addEdge("A", "E", 27);
        //(...) more edges added


        Stack<String> visited = new Stack<String>();        
        visited.push(START);

        new DFSonWeightedDirectedGraph().depthFirst(graph, visited);
    }

    private void depthFirst(WeightedDirectedGraph graph, Stack<String> visited) {

        Collection<Map.Entry<String, Integer>> tree_of_children 
            = graph.get_tree_of_children(visited.peek());

        for (Map.Entry<String, Integer> child : tree_of_children) {


            if(pathLength + child.getValue()>= 20){
                continue;
            }       


            visited.push(child.getKey());
            pathLength += child.getValue();
            stops += 1;         

            if (child.getKey().equals(END)) {
                printPath(visited);
            }

            depthFirst(graph, visited); 
            visited.pop();  
            pathLength -= child.getValue();
            stops -= 1; 
        }
    }

    private void printPath(Stack<String> visited) {
        for (String node : visited) {
            System.out.print(node);
            System.out.print(" ");
        }
        System.out.println("[path length: "+pathLength +
                " stops made: " + stops +"]");
    }
}

ただし、明示的なスタック構造を持たない他の再帰的な実装では、通常、すでにアクセスしたノードを白、灰色、または黒に色付けして考慮します。それで、再訪が許可され、パスを記録する必要がある私の場合、明示的なスタックは絶対に必要ですか？より簡単な代替案の提案をありがとう。

4

4 に答える 4

1

パスを保存する必要がある場合は、このためのデータ構造が必要です。スタックはOKです。別のデータ構造に置き換えることはできますが、削除することはできません。

パスを直接印刷する（記録しない）ことができる場合は、スタックは必要ありません。次に、メソッドシグネチャを変更して、グラフと実際のノード（およびおそらく実際のパスの長さと「ストップ」）を取得することができます。

于 2010-01-09T11:15:50.917 に答える
0

訪問したノードは必要ありません。訪問先ノードパラメータの代わりに現在の子ノードを再帰メソッドに渡し、パスを運ぶために戻り値を使用するだけです。

パスを要素ごとに処理できる場合、つまりprintPath（）を書き直して、要素ごとに1回呼び出すことができる場合は、リターンタイプとしてキータイプのみが必要です。パス全体を受け取りたい場合は、戻りタイプとしてキー値のリストが必要です。

実際、あなたは解決策に比較的近いです。パスを表すには、再帰的なメソッド呼び出しの呼び出しスタックを使用するだけです。

于 2010-01-13T17:31:40.433 に答える
0

「訪問済み」フィールドであるノード構造に追加のフィールドを追加するだけです。これが最速になります。その後（または検索を行う前に）、すべてのノードのマークを外す必要があります。

または、ハッシュテーブルでノードの ID をハッシュするだけです。これは、スタックよりもチェックが高速になります。ノードの ID がない場合は、作成してデバッグや出力などに役立てることをお勧めします。

余分なスペースが必要ですが、ノードごとに 1 ビットになるのに対し、スタックの場合はノードごとに 1 ポインターになるため、各ノードにブール フィールドを追加すると、必要なスペースが最小になります。

有限グラフを検索していて、各ノードに 1 回しかアクセスしないため、実際には距離カットオフは必要ありません。そのため、N ノード グラフでは最大で N ノードにアクセスします。状態空間検索を行う場合など、無限空間を検索する場合は、深さのカットオフが必要になります (例は、証明を検索するプロローグ インタープリターです)。

于 2010-01-09T22:11:19.210 に答える
-1

編集：この回答は完全にトピックから外れており、質問の誤解に基づいて投稿されました。

DFS の実装にはいくつか問題があります。はい、深さ優先の方法ですべてのノードを訪問し、最終的に START と END の間のパスを見つけることができますが、既に訪問したノードをチェックしようとせず、本当の理由もなくスタックを保持します。サイクルで無限再帰に陥らない唯一の理由は、パスの最大長を制限しているためであり、頂点のすべてのペア間に複数の異なるパスがあるグラフでは依然として長い時間がかかります。

スタックを使用する唯一のことは、アクセスするノードを dfs 関数の隣に渡すことです。単純にスタックを取り除き、ノードを直接渡すことができます。

だから、代わりに

private void depthFirst(WeightedDirectedGraph graph, Stack<String> visited) {
   ...
   visited.push(child);
   ...
   depthFirst(graph, visited);

これを次のように簡単に書くことができます

private void depthFirst(WeightedDirectedGraph graph, String node) {
   ...
   //visited.push(child); <-- No longer needed
   ...
   depthFirst(graph, child);

「訪問済み」という名前のデータ構造 (スタック) を使用していますが、それを使用して、再訪問を避けるために既に訪問したノードを保存/マークしません。

既存のコードを変更して、 Visited と呼ばれる Set を持つようにすることができます (グローバル/クラス変数にするか、スタックで行ったように再帰呼び出しに沿って渡します)。そのセットにはまだありません。

これにより、コードは次のようになります

private void depthFirst(WeightedDirectedGraph graph, String node, Set<String> visited) {
   visited.add(node); // mark current node as visited
   ...
   //visited.push(child); <-- No longer needed
   ...
   if (!visited.contains(child)){ // don't visit nodes we have worked on already
      depthFirst(graph, child);
   }

これまでの私の答えは、コードを修正して機能させることでした。しかし、DFS が実際に何であり、実際にどのように機能するかをよりよく理解する必要があるように思われます。優れたアルゴリズム/グラフ理論の本の関連する章を読むと、非常に役立ちます。CLRS をお勧めします (単純なグラフ トラバーサルに関する非常に優れた章があります) が、優れた本であれば何でも構いません。シンプルで正確な再帰的 DFS は、スタックやセットに頼ることなく、配列を使用してはるかに簡単な方法で実装できます。

編集:スタックを置き換えた後にパスを取得する方法については言及していません。これは、探索される各ノードの親を格納する Map を使用することで簡単に実行できます。パス (見つかった場合) は、再帰的な printPath(String node) 関数を使用して取得できます。この関数は、渡されたノードを出力し、その親で自身を再度呼び出します。

于 2010-01-09T12:58:42.920 に答える