Solutions du TD-7, Promenade dans le labyrinthe

Étaient fournies, les classes Sommet, ListeSommets, Laby et AnimLaby.

1  Parcours

1.1  En profondeur

Source Profondeur. C'est du cours. La seule difficulté est de bien gérer l'animation et de comprendre que les sommets sont indexés par une paire d'entiers.

1.2  En largeur

Source Largeur, qui a besoin du source File des files de sommets. Pour les détails, voir la section 5.6 du poly.

2  Le chemin le plus long

2.1  les chemins

La solution est la classe Tous. Si on fait abstraction de l'animation graphique et du calcul de la plus grande longueur on obtient cette méthode de parcours, on obtient une méthode sortir qui compte les chemins vers la sortie : 
   1   static int sortir (Sommet pere, Sommet s, boolean [] [] vu) {
         if (vu[s.i][s.j])
           return 0;
         vu[s.i][s.j] = true;
   5 
         if (s.equals(laby.sortie)) {
           vu[s.i][s.j] = false ;
           return 1 ;
         }
  10     int r = 0 ;
         for (ListeSommets l = laby.voisins[s.i][s.j] ;
              l != null ; l = l.suivant) {
           int t = sortir (s, l.cont, vu) ;
           r += t ;
  15     }
         vu[s.i][s.j] = false ;
         return r ;
       }
Comparons avec la méthode de parcours de la classe Profondeur, pareillement simplifiée en une méthode sortir qui renvoie true si on peut atteindre la sortie et false sinon : 
   1  static boolean sortir (Sommet pere, Sommet s, boolean [] [] vu) {
         if (vu[s.i][s.j])
           return false;
         vu[s.i][s.j] = true;
   5 
         if (s.equals(laby.sortie))
           return true ;
     
         for (ListeSommets l = laby.voisins[s.i][s.j] ;
  10          l != null ; l = l.suivant) {
           boolean t = sortir (s, l.cont, vu) ;
           if (t) {
             return true;
           }
  15     }
         return false;
       }
On remarquera que seule différence est que, dans le cas de du parcours de tous les chemins, on remet vu[s.i][s.j] à false avant de retourner, et que l'on ne retourne pas de l'intérieur de la boucle de visite des voisins.

Ces petites modifications changent totalement le coût du programme, qui explose littéralement dans le cas de la recherce de tous les chemins et est borné par le nombre de cases dans le cas de la recherche d'un chemin.

Par conséquent lorsque l'on cherche seulement à savoir si le labyrinthe a une solution, mieux vaut tester ``Profondeur.sortir(...)'' que ``Tous.sortir(...) >= 0''.

Pour ce qui est du source complet de Tous, vous noterez aussi l'utilisation d'une variable global len pour calculer la longueur des chemins, variable qui est incrémentée avant l'appel récursif et décrémentée après.

2.2  Promenade heuristique

Comme l'indique l'énoncé, il s'agit de trier les listes de voisins, en mettant ceux qui éloigent de la sortie en premier. Une façon objet de le faire est d'étendre la classe Laby en une classe SLaby qui contient les méthodes de tri (un bête tri par insertion, suffisant pour les petites listes (un sommet a au plus quatre voisins).

Le constructeur de cette classe, se contente ensuite d'appeler d'abord le constructeur de sa classe parente (mot-clé super) et de trier les voisins. 
class SLaby extends Laby {

  SLaby(BufferedReader in) {
    super(in);
    trie() ;
  }

  void trie () {
    ...
  }  
}
De même, la classe Promenade étend la classe Profondeur dont elle profite de la méthode de parcours sortir. 
import java.io.*;

class Promenade extends Profondeur {

  public static void main (String args []) {
    laby =
      new SLaby (new BufferedReader (new InputStreamReader(System.in)));

    AnimLaby.start(laby);

    int length =  sortir(null, laby.entree,
             new boolean [laby.hauteur] [laby.largeur]) ;
    if (length < 0)
      System.out.println("Pas de solution...");
    else
      System.out.println("Longueur : " + length) ;
  }
}
On peut aussi programmer ceci plus classiquement en écrivant une classe Promenade qui est une copie de Profondeur, augmentée des méthodes de tri. L'avantage de la programmation objet est que le code de sortir est commun aux deux classes, alors qu'il est dupliqué avec la solution classique.

2.3  Détours

Ça devient plus sioux, car il y a pas mal de manipulations de chemins. Pour faciliter la recherche des détours, le plus long chemin à un instant donné est représenté par deux structures de données : une liste de ses sommets pris dans l'ordre, qui est gérée par des variables locales, et un tableau global d'entiers path, qui est tel : À partir de là, je propose deux solutions, l'une Detour calcule les détours par un recherche en profondeur d'abord (zyva et zyvaRec), suivant une heuristique spécifique (les voisins dont les voisins sont des cases vides en premier) ; l'autre DetourBound effectue une recherche exhaustive (zyva et zyvaRec) de tous les détours à partir d'un sommet donné et selectionne l'un des détours possible parmi les plus longs.

Dans les deux cas les chemins sont détournés de l'entrée vers la sortie par la méthode betterRec, qui est appelée jusqu'à plus soif par la méthode better.

2.4  Un peu de culture

On peut se demander s'il existe un algoritme exact et raisonnable (la classe Tous n'est pas raisonnable) qui calcule la plus longue promenade dans le labyrinthe. En effet, il existe bien un algorithme raisonnable qui trouve la promenade la plus courte (parcours avec une file).

Il semble bien que non, car la recherche du plus long chemin dans un graphe est un problème particulièrement coûteux à résoudre. C'est un problème NP-complet, c'est à dire qu'il existe un algorithme en temps polynomial (une définition de raisonnable) pour le résoudre si et seulement si il en existe un pour résoudre une serie de problèmes classiques, dont la satisfiabilité des formules booléennes, pour lequels on sèche depuis un demi-siècle. Voir http://www.nada.kth.se/~viggo/wwwcompendium/wwwcompendium.html et en particulier ici.

3  Composantes biconnexes

La solution est la classe source Bi, qui suit exactement l'article. (Les sources Arc et Pile étaient donnés.)

La seule subtilité concerne le statut de la racine de chaque arbre de recouvrement. Cette racine n'est un point d'articulation que si l'arbre de recouvrement a deux fils ou plus à la racine. Soit dans le cas d'affichage d'une composante biconnexe, quand le père u du sommet en cours d'examen s est inexistant (u == null) et il reste au moins un voisin non-encore parcourru (méthode voisinPasVu).

Ce document a été traduit de LATEX par HEVEA.