La fiche avant l'algorithme

Pour qu'un programme trouve seul une solution, il faut d'abord lui décrire le problème sans rien laisser au hasard. Les spécialistes le font avec une « fiche » de quatre lignes. Cette séance apprend à la remplir : c'est l'étape la plus humaine, et celle qui fait le plus souvent échouer les projets.

À la fin de cette séance, vous saurez

  • remplir la fiche : états, actions, but, coût ;
  • compter les états d'un problème simple ;
  • expliquer pourquoi le chemin direct n'est pas toujours le meilleur.

Les quatre lignes de la fiche

Fiche de problème, remplie pour un trajet de livraison
LigneQuestionPour le livreur
ÉtatsQu'est-ce qui décrit complètement la situation ?Le point où se trouve le camion (dépôt, gare, marché, parc, musée).
ActionsQu'a-t-on le droit de faire, depuis un état ?Emprunter un tronçon direct vers un lieu voisin.
ButDans quel état le problème est-il résolu ?Camion arrivé au musée.
CoûtQu'essaie-t-on de réduire ?La durée totale du trajet, en minutes.

Une transition est le passage direct d'un état à un autre par une seule action. Une suite de transitions forme un chemin : c'est lui qu'on cherche.

À essayer : le meilleur trajet

Départ : la Gare. But : le Musée. Voici les tronçons directs et leur durée.

Durée des tronçons
TronçonMinutes
Gare ↔ Musée9
Gare ↔ Marché2
Marché ↔ Parc1
Gare ↔ Parc4
Parc ↔ Musée3
Marché ↔ Musée8

Cherchez le trajet le plus court avant d'ouvrir la réponse.

Voir la réponse

Gare → Marché → Parc → Musée : 2 + 1 + 3 = 6 minutes, contre 9 par le tronçon direct. Sans la ligne « coût », la machine ne pourrait pas comparer les chemins : elle s'arrêterait au premier qui arrive au but.

Combien d'états, au juste ?

Si une situation se décrit par plusieurs éléments indépendants, on multiplie leurs possibilités.

  • Un cadenas à 3 interrupteurs : 2 × 2 × 2 = 8 états.
  • Avec 10 interrupteurs : 210 = 1 024 états.
  • Avec 30 : plus d'un milliard.

Atelier : les deux jerricans

Un jerrican A de 3 litres, un jerrican B de 5 litres, une source d'eau. Objectif : obtenir exactement 4 litres dans l'un des deux, avec le moins de transitions possible.

Séance précédente Séance suivante : cinq repères historiques