Ce blog carbure actuellement à un rythme délirant, mais ne vous inquiétez pas ça va se calmer. D'abord, parce que j'en ai marre d'écrire en permanence, et ensuite parce qu'Icosien approche de la sortie !

Un peu de rôlisme.
Vous êtes un voyageur de commerce, et votre patron vous a donné une liste de 15 villes à démarcher.
Renseignements pris, toutes les villes ne sont pas vraiment reliées entre elles : les avions n'assurent que certaines liaisons.

Voici le schéma obtenu (il s'agit d'un dodécahédron issu de mathworld) :

En rouge se trouvent les villes à visiter, et en noir les liaisons possibles. Vous partez de votre ville de départ, et le but sera de visiter une ville par jour sans revenir deux fois dans la même ville, tout en finissant le vingtième et dernier jour dans votre ville de départ – après tout, c'est là que vous vivez.

Je vous laisse réfléchir au chemin que vous prendriez… et dans la suite, nous verrons comment résoudre algorithmiquement ce problème !

Présentation du problème

Les contraintes posées (passer une fois par chaque ville en utilisant les arêtes, finir au point de départ) sont la définition d'un cycle hamiltonien.

Algorithmiquement, la recherche d'un cycle hamiltonien est NP-complet : c'est-à-dire qu'on ne connaît pas d'algorithme plus efficace qu'une brute force.
Certes, on peut raffiner légèrement, mais la complexité algorithmique restera exponentielle… et pourtant, les cycles hamiltoniens ont de multiples utilités : par exemple, pour rechercher le cycle le plus long sur un graphe (un chemin hamiltonien, passant par tous les nœuds, est forcément le plus long ! ) ce qui peut être utile dans la reconnaissance d'images.

Mais attention, NP-complet ne signifie pas forcément algorithme complexe ! Au contraire même, puisque NP-complet est à peu près correspondant à une brute-force, les algorithmes ont tendance à être extrêmement simples… mais aussi extrêmement long en temps de calcul.

Ce qui est intéressant dans ce cas, c'est qu'on peut résoudre le problème en une quinzaine de lignes avec une méthode récursive. Mieux encore, on n'a pas besoin de faire de copies d'objets (qui est souvent un point long des algorithmes récursifs) : on peut travailler avec un simple pointeur, ce qui va énormément accélérer les choses.

Structure utilisée

Première chose à faire, définir la structure avec laquelle on veut travailler. On a le choix !
Je vais prendre la structure « simple » : un tableau dont les clés correspondent aux nœuds, et les valeurs aux nœuds accessibles depuis le nœud-clé.

Par exemple, pour ce graphe :

Notre tableau aura la forme suivante :

[1] => 2,5
[2] => 1,3,5
[3] => 2,4
[4] => 3,5,6
[5] => 1,2,4
[6] => 4

Il est bien évident que ce graphe n'a pas de cycle hamiltonien : il est impossible de partir du 6 sans rejoindre 4, et il est impossible de rejoindre 6 sans passer par 4…

Codage du graphe

Utilisant ce système, on en déduit le tableau suivant pour notre graphe de voyage :

[0]=>1,4,5
[1]=>0,2,6
[2]=>1,3,7
[3]=>2,4,8
[4]=>3,0,9
[5]=>0,14,10
[6]=>1,10,11
[7]=>2,11,12
[8]=>3,12,13
[9]=>4,13,14
[10]=>5,6,15
[11]=>6,7,16
[12]=>7,8,17
[13]=>9,8,18
[14]=>9,5,19
[15]=>10,19,16
[16]=>11,15,17
[17]=>12,16,18
[18]=>13,17,19
[19]=>14,15,18

Le nœud 0 correspond au point en haut, puis on tourne sur l'enveloppe externe pour obtenir 1, puis 2, 3 et 4. Cercle intérieur ensuite : 5 à 9, et ainsi de suite en réduisant les cercles.

Codage du problème

Que va-t-on faire ? Tout d'abord, prendre un point de départ. Si vous demandez lequel, vous venez de passer pour un idiot : on cherche un cycle je vous le rappelle. Me demanderiez-vous comment commencer un cercle ?
Donc on prend le premier qui nous vient sous la main, l'élément d'index 0 (à noter : contrairement à l'exemple précédent, on a un nœud d'index 0).

Ensuite, on récupère la liste des destinations disponibles depuis 0.
Puis on supprime 0 de la liste des nœuds (on n'a pas le droit d'y revenir), et on rappelle la fonction pour chacune des destinations avec le graphe nouvellement créé.

Ici, le premier appel se fera sur l'index 1.
On récupère la liste des itinéraires disponibles depuis 1, et on cherche un chemin dans cet itinéraire.

Et ainsi de suite récursivement…

Comment savoir quand on s'arrête ? Quand on a parcouru autant de nœuds qu'il y en a dans le graphe, et que le dernier nœud a un chemin d'accès vers l'élément 0 (pour boucler).
Sinon, on continue de chercher des itinéraires…
Expliquer un algorithme récursif n'est jamais facile, et je vous conseille de lire le code qui devrait clarifier la chose :

 
/**
* Trouve un cycle Hamiltonien (s'il existe !) dans le graphe passé en paramètres.
* Se base sur un algorithme récursif.
* Prend en paramètre une liste de noeuds, tel que Noeuds[i] contienne tous les noeuds liés à i.
* @param Noeuds:Vector.<Vector.<int>> la liste des points composant le niveau. Typé comme array car les vector ne sont pas sparse.
* @param Actuel le noeud sur lequel on est actuellement placé. Non spécifié au premier appel.
* @param LongueurCycle la longueur du cycle actuelle. Si longueur == noeuds.length, c'est fini :)
* @return true si un cycle a été trouvé, false sinon.
*/
private function solveHamiltonian(Noeuds:search?q=Array%20inurl:http://livedocs.adobe.com/flex/201/langref/%20inurl:Array.html&filter=0&num=100&btnI=lucky">Array,Actuel:search?q=int%20inurl:http://livedocs.adobe.com/flex/201/langref/%20inurl:int.html&filter=0&num=100&btnI=lucky">int=0,LongueurCycle:search?q=int%20inurl:http://livedocs.adobe.com/flex/201/langref/%20inurl:int.html&filter=0&num=100&btnI=lucky">int=0):search?q=Boolean%20inurl:http://livedocs.adobe.com/flex/201/langref/%20inurl:Boolean.html&filter=0&num=100&btnI=lucky">Boolean
{
  //Récupérer la liste des itinéraires possibles depuis le noeud Actuel.
  var Possibilites:Vector.<int> = Noeuds[Actuel];
  //Supprimer ce noeud de la liste (pour qu'on ne le reprenne pas)
  Noeuds[Actuel] = null;
 
  //Examiner chacun des itinéraires disponibles depuis ce noeud.
  for each(var Possibilite:search?q=int%20inurl:http://livedocs.adobe.com/flex/201/langref/%20inurl:int.html&filter=0&num=100&btnI=lucky">int in Possibilites)
  {
    //Si :
    // - on a la longueur d'un cycle, et on peut rejoindre 0 (le point de départ)
    // - le noeud n'a pas encore été pris, et qu'on peut trouver un chemin hamiltonien dessus :
    if((LongueurCycle==Noeuds.length-1 && Possibilite == 0) ||
      (Noeuds[Possibilite]!=null && solveHamiltonian(Noeuds,Possibilite,LongueurCycle+1)))
    {
      //Chemin trouvé !
      trace("Trouvé : " + Actuel);
      return true;
    }
  }
 
  //Sinon, aucun chemin hamiltonien ne passe par cette combinaison. Remettre le tableau dans son état initial, puis quitter et revenir à la fonction précédente.
  Noeuds[Actuel] = Possibilites;
  return false;
}
 

Et notre résultat :

Trouvé : 5
Trouvé : 14
Trouvé : 19
Trouvé : 18
Trouvé : 17
Trouvé : 16
Trouvé : 15
Trouvé : 10
Trouvé : 6
Trouvé : 11
Trouvé : 7
Trouvé : 12
Trouvé : 8
Trouvé : 13
Trouvé : 9
Trouvé : 4
Trouvé : 3
Trouvé : 2
Trouvé : 1
Trouvé : 0

Pour ceux qui voudraient en savoir plus sur les graphes hamiltoniens : vous pouvez lire cette thèse.

Pour les visuels (et aussi pour vous féliciter d'avoir suivi cet article) voici le résultat :