2

ソース頂点から宛先頂点へのすべての非循環パスを一般的な有向グラフに格納することを含む研究問題に取り組んでいます(循環的である場合とそうでない場合があります)。入力は、有向グラフ、ソース頂点、および宛先頂点で構成されます。

このアクションを実行するメソッドを Java で作成しました。メソッドの再帰呼び出し中に同じ頂点に到達した場合でも、保存された「ルート」を使用できるように、ソース頂点から宛先までのすべての非循環パスを保存することにより、メモ化の概念を使用しました。多くの計算を節約します。

私は自分のアルゴリズムの再帰的なステップのどこかで間違っていると思います (私は思います)。何が間違いなのかを考えるのに時間を費やしましたが、それを見つけることができません。この点で何か助けていただければ幸いです。前もって感謝します！

ああ、コード ブロックの目的に関して説明が必要な場合は、コメントしてください。

私は基本的に、問題を解決するためのアプローチで DFS を使用しました。私のコードは次のとおりです。

//'allEdges' is an ArrayList of all edges of the input graph

/*'Route' is a class that stores the 'src', 'dest' and 'edgeIndices' of 'allEdges'
that comprise the route from 'src' to 'dest'*/

/*'hashMap' is a HashMap<Integer, ArrayList<Route>>. It maps an integer source vertex
 to a list of all routes from that vertex to the actual destination vertex to which
the method is initialized from main()*/


static void findPaths(int source, int dest)
{
    int i,j,k;
    for(i=0;i<allEdges.size();i++)
    {
        if(allEdges.get(i).getStartNode()==source)
        {
            ArrayList stack = new ArrayList();
            stack.add(i);   //pushing edge index to stack
            if(allEdges.get(i).getEndNode()==dest)
            {
                ArrayList<Route> list1 = hashMap.get(source);   

                if(list1!=null)
                {
                    list1.add(new Route(source,dest,stack));
                    hashMap.put(source, list1);
                }
                else
                {
                    ArrayList<Route> list2 = new ArrayList();
                    list2.add(new Route(source,dest,stack));
                    hashMap.put(source, list2);
                }

            }
            else
            {
                int nextNode = allEdges.get(i).getEndNode();
                ArrayList<Route> temp = hashMap.get(nextNode);
                if(temp!=null)
                {
    for1:           for(j=0;j<temp.size();j++)
                    {
                        ArrayList path = temp.get(j).getEdgeIndices();

                        for(k=0;k<path.size();k++)
                        {
                            int edgeIndex = (int)path.get(k);
                            Edge ed = allEdges.get(edgeIndex);
                            if(ed.getStartNode()==source)
                            {
                                continue for1;
                            }
                        }

                        stack.addAll(path);

                        ArrayList<Route> list3 = hashMap.get(source);
                        if(list3!=null)
                        {
                            list3.add(new Route(source,dest,stack));
                            hashMap.put(source,list3);
                        }
                        else
                        {
                            ArrayList<Route> list4 = new ArrayList();
                            list4.add(new Route(source,dest,stack));
                            hashMap.put(source,list4);
                        }


                        stack.removeAll(path);
                    }
                }
                else
                {
                    findPaths(nextNode, dest);
                }
            }    
        } 
    }

}

編集1：

次の入力グラフの場合:

頂点の数 = 5

ソース頂点 = 1

宛先頂点 = 5

有向辺: 1 -> 2、1 -> 3、1 -> 4、2 -> 4、4 -> 5

1 から 5 までのすべてのパスは次のとおりです。

1 -> 2 -> 4 -> 5

1 -> 4 -> 5

findPaths(1, 5) を呼び出したときの出力 'hashMap' は次のとおりです。

頂点「1」の場合、「hashMap」には「ルート」が 1 つだけ格納されており、そのルートには「エッジ」が 1 つだけあります: 1 -> 4

頂点 '2' の場合、'hashMap' には 'Route' が保存されていません。つまり、'null' にマップされます。

頂点 '3' の場合、'hashMap' には 'Route' が保存されていません。つまり、'null' にマップされます。

頂点「4」の場合、「hashMap」には「ルート」が 1 つだけ格納されており、そのルートには「エッジ」が 1 つだけあります: 4 -> 5

頂点 '5' の場合、'hashMap' には 'Route' が格納されていません。つまり、'null' にマップされます。

明らかに、「hashMap」は間違った「ルート」を格納しています。

編集2：

ブレインストームが提案した変更を行った後、プログラムは非循環グラフで機能します。巡回グラフでも機能するようにしています。いくつかの入力を試してみたところ、興味深いことに、Brainstorm によって提案された変更により、循環エッジがArrayList 'allEdges'. つまり、エッジが入力に現れる順序によって違いが生じますが、これは理想的ではありません。

今、再帰で現在「処理中」のノードにラベルを付けるのを忘れていたため、コードが無限の再帰呼び出しシーケンスでスタックしていることに気付きました。だから私がしたことは、再帰呼び出しの処理中に同じノードが再びトラバースされないように、再帰呼び出しの1つinProcessとして機能するノードを含むグローバルスタックを作成することでした。sourceしかし、まだ正しい出力が得られません。私が行った変更は次のとおりです。

初期コードブロック:

if(temp==null)
{
   findPaths(nextNode,dest);
   temp = hashMap.get(nextNode);
}

上記のブロックを次のように変更しました。

if(temp==null)
{

      if(!inProcess.contains(nextNode))
      {
           inProcess.add(nextNode);
           findPaths(nextNode,dest);
           inProcess.remove(inProcess.indexOf(nextNode));
           temp = hashMap.get(nextNode);
      }
      else
      {
           continue main_for1;  //main_for1 labels the very first for() loop of this method
      }


}

この改造ではどこか足りない気がします。誰かが私に何が間違っているのか教えてくれますか?

4

2 に答える 2

0

あなたの問題は、メインのelseステートメントの最初の行である可能性があると思います:

int nextNode = allEdges.get(i).getEndNode();

これは正確に何をしますか？i の終了ノードがわからない場合、初めてパスを通過するときに null を返すように思えます。

于 2013-07-08T17:18:34.737 に答える