Trouver tous les cycles possibles hamiltonien dans un graphe partiellement orienté

Question

Ceci est mon algorithme pour trouver un cycle hamiltonien dans un graphe:

private SolutionArray solution; 
private int V, pathCount; 
private int[] path; 
private int[][] graph; 

/** 
* Constructor 
*/ 
public ConcreteSolver() { 
    solution = new SolutionArray(); 
} 

@Override 
public SolutionArray solve(PathMatrix input) { 

    V = input.getNbVertex(); 
    path = new int[V]; 

    /** Set all path to non-visited **/ 
    boolean[] visited = new boolean[V]; 
    for (int i = 0; i < V; i++) { 
     visited[i] = false; 
    } 

    Arrays.fill(path, -1); 
    graph = input.getMatrix(); 

    try { 
     path[0] = input.getFirstVertex(); 
     pathCount = 1; 

     findPaths(0); 

     System.out.println("No solution"); 
    } catch (Exception e) { 

     System.out.println("\nSolution found"); 
     //input.printMatrix(); 
     displayAndWrite(); 
    } 

    return solution; 

} 

/** 
* function to find paths recursively 
*/ 
private void findPaths(int vertex) throws Exception { 


    /** solution **/ 
    if (graph[vertex][0] >= 1 && pathCount == V) { 
     throw new Exception(); 
    } 
    /** all vertices selected but last vertex not linked to 0 **/ 
    if (pathCount == V) 
     return; 

    for (int v = 0; v < V; v++) { 
     /** if connected **/ 
     if (graph[vertex][v] >= 1) { 
      /** add to path **/ 
      path[pathCount++] = v; 

      /** if vertex not already selected solve recursively **/ 
      if (!isPresent(v)) 
       findPaths(v); 

      /** remove path **/ 
      path[--pathCount] = -1; 

     } 

    } 

} 

/** 
* function to check if path is already selected 
*/ 
private boolean isPresent(int v) { 
    for (int i = 0; i < pathCount - 1; i++) 
     if (path[i] == v) 
      return true; 
    return false; 
} 

Je suis en mesure de trouver un premier cycle hamiltonien. Est-il possible de l'adapter pour trouver tous les cycles hamiltoniens possibles trouvés dans le graphique?

L'entrée est une matrice non symétrique (certains liens entre les nœuds sont à sens unique) et certains nœuds peuvent avoir 2 ou 3 liaisons avec d'autres nœuds.

Merci

EDIT:

Pour clarifier les choses, l'algorithme peut déjà trouver une solution, mais ne peut pas trouver un deuxième et ainsi de suite. De la lecture, A * en utilisant bactracking pourrait résoudre le problème mais je ne suis pas sûr si elle peut être ajoutée à ce que j'ai déjà.

Answer 1

Actuellement, vous avez un seul tableau pour capturer le chemin actuel en cours d'exploration. Votre méthode displayAndWrite utilise probablement cette information pour imprimer la solution.

Pour enregistrer toutes les solutions, vous devez prendre une copie du chemin lorsque vous trouvez un cycle hamiltonien.

Somthing comme:

private static final int MAX_SOLUTIONS = 100; 
private int[][] solutions = new int[MAX_SOLUTIONS][]; 
private int solutionCount = 0; 

private void addSolution(int[] path) { 
    if (solutionCount < MAX_SOLUTIONS) 
     solutions[solutionCoun++] = Arrays.copyOf(path, path.length); 
} 

Vous devez appeler addSolution dans la méthode récursive où vous actuellement par l'exception. En outre, lancer une exception pour indiquer le succès serait considéré comme un mauvais style par presque tous les codeurs Java expérimentés. Je pense la même chose est vrai dans d'autres langues - exceptions sont des exceptions :-)

Answer 2

En ce moment, vous jetez une exception lorsque vous avez détecté un cycle:

if (graph[vertex][0] >= 1 && pathCount == V) { 
    throw new Exception(); 
} 

Mis à part le fait que jeter une exception est la mauvaise chose à faire ici parce que ce n'est pas vraiment une condition exceptionnelle - voir mon commentaire sur la question - tout ce que vous devez faire est de faire l'action à prendre lorsque vous avez trouvé le cycle moins "explosif". Sans connaître la définition de SolutionArray Je ne peux pas donner une réponse en faisant usage de cela.

Puisque vous ne savez pas combien de cycles que vous pourriez trouver, ajouter un List pour recueillir vos solutions:

private List<int[]> solutions = new ArrayList<>(); 

Maintenant, quand vous trouvez une solution, il suffit d'ajouter quelque chose à cette liste - puis retour de la méthode:

if (graph[vertex][0] >= 1 && pathCount == V) { 
    solutions.add(java.util.Arrays.copyOf(path, V)); 
    return; 
} 

Parce que cela renvoie simplement de la méthode, plutôt que de lancer une exception, l'exécution de la fonction d'appel continue à vérifier le prochain chemin possible.

Il est important que vous preniez une copie du chemin, car sinon vous ajouterez simplement une référence au tableau que vous utilisez comme copie de travail - de sorte qu'ils seront tous dans le même tableau, et, parce que vous pourriez mettre à jour après, ne sera même pas nécessairement contenir une solution valide à la fin.

Ensuite, dans votre principale méthode, il suffit de vérifier si cette liste est non vide:

if (!solutions.isEmpty()) { 
    System.out.println("\nSolution(s) found"); 
    displayAndWrite(); 
}