Ch. 5 — Configurations et affectation

Le graphe de configurations

Un casse-tête se résout par un graphe de configurations : chaque configuration — un état complet du problème — est un sommet, et chaque action valide est une arête. Le casse-tête loup-chèvre-chou en est l'exemple du cours : une configuration est une chaîne de quatre caractères, une position par personnage — berger (position 0), loup (1), chèvre (2), chou (3), chacun sur la rive gauche (G) ou droite (D). Ainsi "GDGD" signifie : berger et chèvre à gauche, loup et chou à droite. Les successeurs d'une configuration sont obtenus en faisant traverser le berger, seul ou avec un personnage : les successeurs de "GDGD" sont "DDGD" (traverse seul) et "DDDD" (traverse avec la chèvre). La configuration initiale est "GGGG", la solution "DDDD", et les configurations perdantes (loup + chèvre, ou chèvre

• chou, sans le berger) sont simplement exclues du graphe.

Le graphe implicite en Java

Un graphe implicite étend la classe AbstractImplicitGraph de la bibliothèque Grapp (grapp.jar) en implémentant quatre méthodes :

import java.util.ArrayList;
import fr.ulille.grapp.graph.AbstractImplicitGraph;

public class Exemple extends AbstractImplicitGraph {
  @Override
  public String type() { return "digraph"; }        // ou "diwgraph"
  @Override
  public String name() { return "exemple-implicite"; }
  @Override
  public ArrayList<String> initialNodes() {          // les sommets initiaux
    ArrayList<String> result = new ArrayList<>();
    result.add("a");
    return result;
  }
  @Override
  public ArrayList<String> successors(String node) { // les successeurs d'un sommet
    ArrayList<String> resultat = new ArrayList<>();
    // ajouter à resultat les configurations atteignables en un pas
    return resultat;
  }
}

La compilation se fait en ligne de commande (javac -cp /home/public/graphes/Grapp/lib/grapp.jar:. Exemple.java) et le chargement avec Grapp load -implicit Exemple — on donne le nom de la classe, pas du fichier. Deux conséquences importantes : seuls les sommets accessibles depuis les sommets initiaux sont découverts (un sommet jamais atteint, même écrit dans successors, n'apparaît pas), et rendre initial un sommet supplémentaire change la partie visible du graphe.

Le parcours en profondeur d'abord

Le parcours en profondeur (DFS) est le jumeau du parcours en largeur : même entrée, même résultat (un arbre de parcours décrit par Pred), mais la pile remplace la file — le dernier sommet découvert est exploré en premier.

soit Pred(y) = indéfini pour tout y sommet de G   // table des prédécesseurs
soit D = { s0 }                                   // ensemble des sommets découverts
soit P = [ s0 [                                   // pile d'exploration
tant que NON P.estVide()
  soit s = P.sommet()
  si s possède un successeur x qui n'est pas dans D alors
    ajouter x à D
    P.empiler(x)
    Pred(x) = s
  sinon
    P.dépiler()
retourner l'arbre défini par Pred

DFS et BFS explorent les mêmes sommets accessibles, mais les arbres de parcours diffèrent. Pour résoudre un casse-tête, le parcours en largeur est le plus intéressant : il atteint la solution en un nombre minimal d'étapes, alors que le DFS peut s'enfoncer dans une branche longue. Grapp implémente les deux (traversal -algorithm BFS ou DFS) et la commande find-path -on ri.1 -from a -to h extrait le chemin d'un résultat de parcours — pratique quand le graphe est trop grand pour lire la solution à l'œil.

Les casse-têtes de TD et TP

• les seaux : obtenir exactement 4 litres avec un seau de 3 L et un de 5 L — une configuration est un couple d'entiers (contenus des seaux), codé en une chaîne de deux caractères ; six actions (remplir, vider, transvaser dans les deux sens) donnent les successeurs ;
• l'échange de cavaliers : une configuration est un quadruplet (b1, b2, n1, n2) des positions des deux cavaliers blancs et des deux noirs — correcte seulement si les quatre positions sont différentes ; quatre configurations finales possibles ;
• le saute-mouton : >>>_<<< doit devenir <<<_>>> en avançant ou en faisant sauter les moutons ; le programme se paramètre par une constante TAILLE (plateau impair, au moins 7).

Dans les trois cas, le schéma est identique : implémenter initialNodes et successors, charger en implicite, parcourir en largeur, puis find-path vers la configuration finale et traduire le chemin en suite d'actions.

Le problème d'affectation

Quatre employés A, B, C, D doivent accomplir quatre tâches W, X, Y, Z ; le tableau donne le nombre de jours de chaque employé pour chaque tâche. Comment affecter les tâches pour minimiser le temps total ? La donnée se lit comme la matrice d'adjacence d'un graphe biparti complet valué :

Un graphe biparti est un graphe non orienté dont les sommets sont partitionnés en deux ensembles U et V tels que chaque arête a une extrémité dans U et l'autre dans V. Il est complet quand chaque sommet de U est relié à chaque sommet de V.

Le problème d'affectation à coût minimal demande alors un sous-ensemble d'arêtes F tel que chaque sommet soit extrémité d'exactement une arête de F, avec la somme des poids de F minimale. L'algorithme de référence est celui de Kuhn-Munkres (algorithme hongrois). Une autre voie, vue au TD et au DS d'entraînement : ramener l'affectation à un flot maximal dans un réseau biparti — source vers chaque type de famille (capacité = nombre de familles), arêtes famille-appartement quand le logement est acceptable, chaque type d'appartement vers le puits (capacité = nombre d'appartements). Le DS l'applique aux déchets toxiques de types A à D vers les usines G à K, capacités de traitement comprises.

A retenir

• graphe de configurations : sommets = états, arêtes = actions ; configurations perdantes exclues ;
• graphe implicite : initialNodes() + successors(node) suffisent, seuls les sommets accessibles sont découverts (Grapp load -implicit) ;
• DFS = parcours en largeur avec une pile ; le BFS donne la solution en un nombre minimal d'étapes ; find-path extrait le chemin d'un résultat de parcours ;
• affectation à coût minimal = couplage parfait de poids minimal dans un graphe biparti complet valué (Kuhn-Munkres), ou flot maximal dans le réseau biparti associé.