revisitant nœuds pendant DFS et le contrôle des cycles infinis

Question

Je mets en application DFS sur un graphique pondéré réalisé de la manière suivante:

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+"]"); 
    } 
} 

Je dois modifier ce qui précède pour permettre des cycles au cours de la recherche de tous les chemins entre une source nœud et un nœud de destination. Pour éviter les cycles infinis, les conditions peuvent être définies pour terminer la recherche en fonction du nombre de "arrêts" effectués, ou d'une distance maximale autorisée à partir de la source.

De cette façon, je peux trouver, par exemple, le nombre de voyages commençant à A et se terminant à D avec exactement 5 arrêts: Une solution peut être ABCDCD. Ou, je peux trouver, disons, le nombre de routes différentes de D à D avec une distance inférieure à 40: quelques solutions seraient DECD, DEBCD, DCDCD. Mon problème est que je ne suis pas sûr de savoir comment créer la logique de garder l'algorithme principal de recherche, tout en échappant à un cycle de recherche infinie qui est garanti pour ne pas atteindre le nœud de destination. Disons que je veux voyager de A à D. Un cycle sans issue possible peut être ABCEBCEBCEB .... (à l'infini). Mes conditions basées sur le nombre d'arrêts, ou la distance totale parcourue, peuvent terminer cette boucle, mais mettront également fin à toute la recherche, qui pourrait autrement trouver le bon chemin de dire ABCDCDCDCD, qui se terminera correctement lorsque l'une ou l'autre des conditions prédéfinies est remplie.

Merci pour vos idées.

Answer 1

Je pense que vous devez définir vos arrêts/distance de coupure dynamiquement. Par exemple, pour un problème "A à D dans exactement 5 arrêts", le réglage d'une valeur de coupure de 5 arrêts met fin à tous les cycles lorsqu'ils atteignent 6 arrêts. La même chose vaut pour le problème "D à D avec une distance inférieure à 40", si vous définissez une distance de coupure de 40.

Certains cycles peuvent être coupés plus tôt, en utilisant une "matrice d'accessibilité", c'est-à-dire une matrice tel que a (i, j) = 1 s'il y a un chemin de i à j ou a (i, j) = 0 autrement. Vous pouvez construire une telle matrice en trouvant d'abord les composants fortement connectés de votre graphique (en utilisant un algorithme comme this).
Vous pouvez ensuite rejeter un cycle de recherche si le noeud cible n'est pas accessible depuis le noeud actuel, c'est-à-dire un (courant, cible) = 0.