Ch. 3 — Bellman et ordonnancement

Des chemins optimaux au-delà du plus court

Le plus court chemin n'est qu'un cas de chemin optimal. On peut aussi chercher :

• un plus long chemin (à poids maximal) : il existe toujours si les poids sont négatifs ou si le nombre de chemins entre les deux sommets est fini ;
• un chemin produit minimal ou maximal, où l'on optimise le produit des poids au lieu de leur somme — c'est ainsi qu'on combine des probabilités : la probabilité de survivre à un trajet est le produit des probabilités de survivre à chaque route.

Plus long chemin et poids négatifs : Dijkstra ne convient plus. Il faut un algorithme adapté aux graphes sans cycles.

Graphe acyclique et ordre topologique

Un graphe acyclique (DAG) est un graphe orienté sans cycles. Tout graphe acyclique peut être aligné en un ordre topologique : toutes les arêtes vont de gauche à droite, le sommet le plus à gauche n'a pas de prédécesseur, celui le plus à droite pas de successeur. On l'obtient par numérotation :

1. chercher un sommet dont tous les prédécesseurs sont déjà numérotés (ou qui n'a aucun prédécesseur) — un tel sommet existe toujours si le graphe est acyclique ;
2. lui donner le numéro courant, incrémenter ;
3. recommencer tant qu'il reste des sommets non numérotés.

L'algorithme de Bellman

Entrées : un graphe valué acyclique G et un sommet s0. Résultats : l'arbre des chemins optimaux (ici, à poids maximal) depuis s0, et le poids optimal de chaque sommet.

soit Pred(y) = indéfini pour tout y
soit Optim(y) = -∞ pour tout y      // poids des chemins maximaux
soit P = { s0 }                     // sommets permanents
Optim(s0) = 0
répéter
  soit s un sommet dont tous les prédécesseurs sont dans P
        et qui a au moins un prédécesseur
  si un tel sommet n'existe pas
    retourner l'arbre défini par Pred et la table Optim
  sinon
    soit x le prédécesseur de s t.q. Optim(x) + p((x,s)) est maximal
    Optim(s) = Optim(x) + p((x,s))
    Pred(s) = x
    ajouter s à P

Le principe suit l'ordre topologique : quand on traite un sommet, la valeur optimale de tous ses prédécesseurs est déjà connue — il suffit d'inspecter leurs valeurs et les poids des arêtes entrantes. Pour des plus courts chemins au lieu de plus longs, on change le signe de tout : Optim(y) = +∞ à l'initialisation, et le prédécesseur x choisi est celui qui minimise Optim(x) + p((x, s)).

La méthode potentiel-tâches

Un problème d'ordonnancement détermine les dates d'exécution des tâches d'un projet pour optimiser l'usage de ressources limitées — ici une seule ressource, le temps, avec un objectif : minimiser la durée totale. Le vocabulaire :

• la tâche A est antérieure à B si B ne peut démarrer avant la fin de A ; antérieure directe si aucune tâche ne s'exécute entre les deux ;
• la date au plus tôt d'une tâche : la date à partir de laquelle elle peut démarrer, ses antérieures pouvant être finies ;
• la date au plus tard : la dernière date à laquelle elle peut démarrer sans remettre en cause la durée minimale du projet.

La méthode construit le graphe potentiel-tâches, orienté et valué : les sommets sont les tâches, plus α (début du projet) et ω (fin) ; une arête de A vers B si A est antérieure directe de B — les antécédences indirectes sont éliminées ; une arête de α vers chaque tâche sans antérieure, de chaque tâche sans successeure vers ω ; les arêtes sortant de α ont un poids 0, toutes les autres ont pour poids la durée de la tâche d'origine. Si le graphe n'est pas acyclique, le projet n'est pas réalisable (dépendances cycliques). Sinon, Bellman calcule les plus longs chemins depuis α :

• la durée minimale d du projet = poids du plus long chemin de α à ω ;
• la date au plus tôt d'une tâche = poids du plus long chemin de α à cette tâche ;
• la date au plus tard = d − poids du plus long chemin de ω à la tâche dans le graphe où le sens des arêtes est inversé ;
• un chemin critique est un chemin de α à ω dont toutes les tâches ont date au plus tôt égale à date au plus tard — ces tâches ne peuvent pas être retardées sans retarder le projet.

Le diagramme de Gantt, construit à partir des deux dates, montre un planning possible et les marges de chaque tâche — et permet de lire l'effectif minimal : en supposant que toutes les tâches commencent à leur date au plus tôt, on compte les tâches en cours à chaque instant (deux couleurs, deux personnes sur l'exemple du cours).

Grapp : optimal-path

La commande optimal-path calcule un chemin optimal avec Bellman : -algorithm Bellman, -on (graphe), -from (source), -optimize Min ou Max, et -operation Add (défaut) ou Mult pour optimiser le produit des poids. La commande gen-yaml génère une trame de graphe (Grapp gen-yaml -graphType diwgraph -to trame.yaml a b c d …) bien commode pour les grands graphes, comme celui de l'interro sur l'ordonnancement. Avec -operation Mult -optimize Max sur un réseau dont les poids sont des probabilités de réussite, on obtient la route que Michel Strogoff aurait choisie en connaissant le calcul des probabilités — plutôt qu'en maximisant naïvement la somme des chances.

A retenir

• chemin optimal : plus court, plus long, produit minimal ou maximal — le critère se choisit ;
• graphe acyclique = ordre topologique possible ; Bellman ne fonctionne que sur ces graphes ;
• Bellman traite les sommets dans l'ordre topologique : quand un sommet arrive, tous ses prédécesseurs sont déjà optimisés ;
• potentiel-tâches : dates au plus tôt = plus longs chemins depuis α ; durée minimale = plus long chemin α → ω ; dates au plus tard = durée minimale − plus long chemin depuis ω à arêtes inversées ;
• chemin critique : tâches où tôt = tard ; le Gantt donne les marges et l'effectif minimal.