0

次の方法で、重み付き有向グラフに DFS を実装しています。

    public class DFSonWeightedDirectedGraph {

    private static final String START = "A";
    private static final String END = "C";
    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", 5);
        graph.addEdge("A", "D", 5);
        graph.addEdge("A", "E", 7);
        graph.addEdge("B", "C", 4);
        graph.addEdge("C", "D", 8);
        graph.addEdge("C", "E", 2);
        graph.addEdge("D", "C", 8);
        graph.addEdge("D", "E", 6);
        graph.addEdge("E", "B", 3);

        LinkedList<String> visited = new LinkedList<String>();
        visited.add(START);
        new DFSonWeightedDirectedGraph().depthFirst(graph, visited);
    }

    private void depthFirst(WeightedDirectedGraph graph, LinkedList<String> visited) {
        Collection<Map.Entry<String, Integer>> nodes = graph.adjacentNodes(visited.getLast());      
        // examine adjacent nodes
        for (Map.Entry<String, Integer> node : nodes) {
            if (visited.contains(node.getKey())) {
                continue;
            }
            if (node.getKey().equals(END)) {
                visited.addLast(node.getKey());  
                pathLength += node.getValue();
                stops += 1;
                printPath(visited);
                visited.removeLast();
                pathLength -= node.getValue();
                stops -= 1;
                break;
            }
        }
        // recursion
        for (Map.Entry<String, Integer> node : nodes) {
            if (visited.contains(node.getKey()) || node.getKey().equals(END)) {
                continue;
            }
            visited.addLast(node.getKey());
            pathLength += node.getValue();
            stops += 1;
            depthFirst(graph, visited);
            visited.removeLast();
            pathLength -= node.getValue();
            stops -= 1;
        }
    }

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

ソース ノードと宛先ノード間のすべてのパスの検索中にサイクルを許可するように上記を変更する必要があります。無限サイクルを回避するために、行われた「停止」の数、またはソースからの最大許容移動距離に基づいて検索を終了する条件を設定できます。

このようにして、たとえば、A で始まり D で終わり、ちょうど 5 つの停留所があるトリップの数を見つけることができます。1 つの解は ABCDCD です。または、たとえば、D から D までの距離が 40 未満のさまざまなルートの数を見つけることができます。いくつかの解は、DECD、DEBCD、DCDCD です。

私の問題は、宛先ノードに到達しないことが保証されている無限の検索サイクルを回避しながら、メインアルゴリズムの検索を維持するロジックを作成する方法がわからないことです。

A から D に移動したいとしましょう。考えられる行き止まりのサイクルは ABCEBCEBCEB....(無限大まで) です。停留所の数、または移動距離の合計に基づく私の条件は、このループを終了させることができますが、検索全体を終了させることもできます。それ以外の場合は、たとえば ABCDCDCDCD の正しいパスを見つけることができ、いずれかの事前設定された条件が満たされたときに正しく終了します。

アイデアをありがとう。

4

1 に答える 1

1

カットオフストップ/距離を動的に設定する必要があると思います。たとえば、「正確に 5 ストップで A から D まで」という問題の場合、カットオフ値を 5 ストップに設定すると、6 ストップに達した時点ですべてのサイクルが終了します。問題「距離が 40 未満の D と D」でも、カットオフ距離を 40 に設定すると、同じことが言えます。

「アクセシビリティ マトリックス」、つまり、i から j へのパスがある場合は a(i, j) = 1、そうでない場合は a(i, j) = 0 のようなマトリックスを使用して、一部のサイクルを早期に切断できます。このような行列を作成するには、最初にグラフの強連結成分を見つけます (このようなアルゴリズムを使用します)。
次に、現在のノードからターゲット ノードにアクセスできない場合、つまり a(current, target) = 0 の場合、検索サイクルを拒否できます。

于 2010-01-03T20:59:38.673 に答える