Algorithmus

Un vieux projet me tenait à coeur depuis très longtemps (environ depuis la troisième), et je viens enfin d'en venir à bout. Je vous explique le contexte, il existe en natation (mais ça doit être transposable à plein d'autres problèmes) des compétitions par équipe, pour schématiser N nageurs sur N épreuves (avec donc un nageur par épreuve). La natation n'étant pas comme l'athlétisme, on peut sortir de sa spécialité et on considère donc a priori que les N nageurs peuvent concourir sur les N épreuves. Chacun fait un certain nombre de point sur chacune d'elles, déterminé par son temps (mais nous ne conserverons ici que la notion de points). La question est donc : comment faire l'équipe la plus optimisée possible ? (en théorie seulement bien entendu, car nul ne peut prédire avec exactitude les performances le jour J). Donnée importante : un nageur ne peut faire qu'une seule épreuve.

À l'âge de Pierre

On observe rapidement que le problème n'est pas simple, N nageurs sur N épreuves ça fait du factoriel N combinaisons. Et donc beaucoup de calculs. La méthode la plus simple pour se représenter le problème (et un peu naïve) est une bonne vielle matrice NxN. Ça donne par exemple à petite échelle :

Exemple de matrice 4x4

100Nl 100 Brasse 100 Dos 100 Papillon
Nageur1 856 756 942 600
Nageur2 745 340 511 442
Nageur3 900 570 560 222
Nageur4 540 530 550 530

La question est ici un peu simple ( 4! = 24 seulement), mais dès qu'on augmente un peu N le calcul devient affreux. L'idée pour résoudre cela autrement que par le bon sens humain est de permuter les lignes matricielles de toutes les combinaisons possibles et de calculer la somme de la diagonale (sur l'exemple 856 + 340 + 560 + 530). C'était ce que je faisais en troisième avec ma TI-89, qui trouvait ainsi des solutions pour 6 nageurs sur 6 épreuves en un peu moins de deux minutes (et de la vraie permutation de lignes de matrice, autrement dit le processeur devait s'amuser). En extrapolant pour résoudre des problèmes à 13 nageurs dans le meilleur des cas la calculette aurait résolue le problème en 13!/6! * 2 min = 17297280 min = 288288 heures = 33 ans environ. C'était pas terrible, j'ai donc abandonné l'idée et j'en suis resté là. Cela permettait déjà d'aider à vérifier des équipes des interclubs par catégorie d'âge.

J'y suis revenu récemment complètement par hasard, en programmation OCaml cette fois, et sur mon ordinateur plutôt qu'un processeur de calculette (même si vu le problème, améliorer le processeur ne pourra pas suffire. On ne passe pas en conservant le même algorithme de 33 ans à quelques secondes). Je suis reparti tout d'abord sur la même idée qu'en troisième, une matrice N*N dont on déplace les lignes. Plutôt que de les déplacer au sens propre, j'ai suffisamment grandi (et j'ai d'autres outils que la programmation ti-89 sous la main) pour utiliser un petit vecteur qui contient les positions fictives, ce qui suffit amplement (et simplifie le calcul). Je l'ai fait pour une matrice 6x6, résolu dans l'ordre de la seconde. Mais bon ce n'est ni sympathique à programmer (une suite de boucles for pas belles) ni efficace. Sans compter que j'ai pas trouvé de manière simple pour varier le nombre de nageur, ma seule solution était d'écrire une fonction pour chaque taille (j'ai pas beaucoup cherché non plus). On oublie donc l'idée, et on passe à la suivante.

Un petit arbre perdu dans la forêt

L'idée suivante est de bâtir un arbre des équipes possibles. Comme je pense qu'une image est meilleure qu'un long discours j'ai sorti mon graphviz préféré pour faire quelque chose d'affreux (mais de manière simple et rapide, au passage empaqueté dans Debian par KiBi).

On a ainsi le chemin en rouge qui correspond à "nageur 3" en Nage Libre, "nageur 4" en brasse, "nageur 1" en dos et enfin "nageur 2" en papillon. Le tout pour 2814 points, c'est raisonnable. Avec cette représentation, il n'y a plus qu'à parcourir l'arbre et calculer la meilleure somme, ce n'est pas trop complexe. Gros avantage par rapport à la représentation matricielle on peut "tuer" une branche assez facilement. Imaginons que le sélectionneur décide "Nageur 4 je refuse de le voir nager du Crawl c'est vraiment trop moche, nageur 2 ne sait pas nager la brasse et se ferait disqualifier, nageur 3 ne finira jamais la course en papillon". Il met un 0 pointé à chacun, et le programme supprime les noeuds inutiles. On obtient quelque chose comme :

On y voit déjà beaucoup plus clair, seulement 11 solutions sont encore viables. La réduction du temps de parcours est conséquente, et permet un grand gain de temps par de simples choix du sélectionneur (et qui sont très naturels en natation, on sait parfois qu'il n'est pas la peine d'aligner certains nageurs en dehors de leur spécialité). En résumé on obtient donc un algorithme avec les avantages suivant :

  • Très facile à mettre en place, le parcours d'un arbre est très simple à programmer. De plus on est en vérité pas obligé de le construire (et heureusement car il y a bien plus de N! noeuds à mettre en mémoire, ça tuerait le pauvre ordinateur).
  • Cette solution est très flexible, si on hésite à intégrer un autre nageur on peut l'ajouter et construire les branches supplémentaires correspondantes (très pratique plutôt que de calculer un à un les remplacements).
  • La méthode de suppression de branche permet un gain énorme de temps (cf. juste en dessous), on peut donc envisager de calculer des grosses équipes.
  • On peut se permettre de limiter les calculs en conservant la valeur de chaque noeud, par exemple le noeud 3-4 a une valeur de 1430, il est inutile de le recalculer pour toutes les branches filles. On diminue ainsi fortement le nombre d'opérations (ce que je n'ai pas fait dans le code plus bas).
Il reste cependant des désavantages :
  • On ne sait pas a priori si la branche sera "tuée" par un zéro avant d'atteindre le bas ou pas. Du coup un zéro sur une des premières nages à une importance beaucoup plus grande qu'un zéro sur les dernières (on peut envisager de trier selon le nombre de zéro mais ça simplifie pas vraiment) (ou alors de placer les nages "dures" qui traditionnellement sont réservés à quelques nageurs en premier, ce qui exclu une optimisation dans tout les cas rencontrés).
  • La complexité réelle du problème n'a pas variée par rapport à la méthode matricielle, on a toujours N! feuilles en bout d'arbre, soit beaucoup trop.

J'ai tout de même programmé de quoi mettre en oeuvre cet algorithme, pour tester le temps d'exécution et sa faisabilité dans le monde réel (selon le nombre de zéro, conscient de l'impasse sans cela). J'ai utilisé pour les calculs mon portable avec son "Intel(R) Core(TM)2 Duo CPU T7100 1.80GHz" (oui c'est un copié/collé de /proc/cpuinfo), cet ordinateur avait l'avantage de ne rien faire (pas de cron et de machin comme ça) et d'au pire avoir un second processeur pour le faire (le binaire produit par OCaml n'était absolument pas fait pour paralléliser, 100% d'un CPU mais rien du tout sur l'autre).

J'ai obtenu quelque chose de relativement raisonnable pour N=10, en quasi temps réel aux alentours de 15% de zéros (ils sont placés de manière aléatoire). Cela correspond à une nage et demi supprimée par nageur, c'est tout à fait correct. Cependant le fait que l'on puisse déjà arriver à des temps supérieurs à la seconde m'inquiétait pour des valeurs plus grandes de N.

Et en effet pour N=13 ça commence à être moins joyeux. Il faut environ 60% de zéros pour descendre sous les dix secondes d'utilisation de processeur. C'est énorme, il faut vraiment faire un travail de pré-sélection qui limite immédiatement l'intérêt de la chose (une équipe de ce type l'entraîneur y aura pensé, l'idée est justement de calculer des solutions plus complexes). Et toute extension comme permettre plusieurs nageurs supplémentaires sans modifier les nages augmenterait encore fortement le temps de calcul. De plus le temps de calcul est très fortement lié au nombre de zéro, il est totalement inenvisageable d'utiliser cet algorithme pour des valeurs inférieures à 30% (la dérivée seconde est clairement positive, ça grimpe à une vitesse folle).

Pour ne pas trop dégrader le graphique je n'ai pas été plus loin, mais pour 30% de zéro on arrive au delà des neufs minutes (et je n'ai pas testé plus loin, c'est pas tout ça mais bon faut en lancer plusieurs pour avoir une moyenne qui ressemble à quelque chose et mon processeur aime autant faire la sieste que moi).

Voici la fonction principale utilisée, qui ne prend en argument qu'une matrice contenant les points de chaque nageur pour chaque nage, et les nombres de nages/nageurs associés. Pour le code complet va falloir aller

(* Parcourt d'un arbre, fonction tres proche du fonctionnement de construit_arbre *)
let parcourt_arbre mat n_nageurs n_epreuves =
let solution_liste = ref [] in (* La meilleure combinaison *)
let solution_somme = ref 0 in (* Le score de la meilleure combinaison *)
let rec parcours l1 l2 somme niveau liste =
match (l1,l2) with
(*on arrive à une feuille, donc on test la valeure de cette solution *)
|([],[]) -> if (somme > (!solution_somme)) then
(* Si c'est la meilleure on conserve *)
begin
solution_somme := somme ;
solution_liste := liste
end
(* Effet de bord d'un arbre sans feuille autre qu'une liste vide *)
|([],_) -> ()
|(t::q,_) -> (* Si le noeud est nul, on évite de créer un chemin à partir de lui. *)
if mat.(niveau|>).(t|>) = 0 then
parcours q (t::l2) somme niveau liste
(* Dans le cas ou le n_nageurs > n_epreuves,
inutile/provoquera des erreurs si l'on va trop bas
dans la matrice *)

else if (niveau = n_epreuves) then
parcours [] [] (somme+mat.(niveau|>).(t|>)) niveau liste
(*situation normale, on créé un chemin depuis le noeud, puis
on continue la création de la liste des arbres *)

else begin
parcours (q@l2) [] (somme+mat.(niveau|>).(t|>)) (niveau +1) (liste@[t]) ;
parcours q (t::l2) somme niveau liste end
;
in
(*lancement de la récurrence*)
parcours (construit_liste n_nageurs) [] 0 0 [] ;
(*On renvoie le meilleur résultat*)
((!solution_somme)::(!solution_liste))

La solution à trois côtés

J'ai donc repris mon crayon et mes papiers (des feuilles petits carreaux car les allemands connaissent pas les grands) pour tenter d'améliorer la chose. En observant les arbres plus haut on se rend compte que c'est souvent très bête, on passe son temps à calculer la même chose. Par exemple prenons le chemin 1-2 et 2-1, inutile de calculer 1-2-3-4 et 2-1-3-4, il suffit de savoir en premier lieu qui est le plus favorable entre 1-2 et 2-1 et poursuivre le calcul avec seulement ce maximum. D'où cette conclusion très simple : on s'en moque de l'ordre des prédécesseurs, l'essentiel est de connaître les nageurs déjà sélectionné et les points qu'ils fournissent. On obtient un nouveau graphe, bien plus simple.

D'accord ici le gain de simplicité n'est pas évident, mais à un peu plus grande échelle beaucoup plus. On passe en effet d'un soucis de complexité en N! feuilles à seulement 2 puissance N noeuds. Et mine de rien 13! = 6 227 020 800 alors que 2^13=8192, on change complètement de planète. Mon problème le plus complexe était de déterminé les liens entre les noeuds, pour cela il fallait que j'arrive de manière simple à les numéroter et à savoir surtout quels seront les successeurs de ces jolis tas, et cela pour tout N. Ça n'a pas été gagné d'avance jusqu'au moment ou j'ai fait le simple lien sur un exemple que 1-4-6-4-1 (le nombre de noeuds par ligne sur le graphe) sont tout simplement une suite d'une des lignes du triangle de Pascal. Il ne restait plus qu'à calculer la N-ième ligne du triangle de Pascal, et on savait pour une ligne donnée combien de noeuds étaient "plus haut". Pour l'algorithme complet il fallait encore compter sur la ligne, et ça je dois avouer que je ne sais toujours pas trop bien comment ça marche (mais ça marche, n'est-ce pas l'essentiel ?), en bidouillant ça a fini par le faire (et hélas de la vraie bidouille, "oh tiens ça marche presque, et si je mettais un +1 là ?)

À partir de là le problème était devenu très simple. Plus de questions de zéro à gérer (le temps de calcul étant devenu négligeable, on ne gagne vraiment rien à réfléchir à ça). Pour "tuer" une branche il faut énormément de zéro et c'est totalement improbable que cela puisse arriver. Voici les deux grosses fonctions utiles du programme :

let position_absolue triangle l taille vecteur_somme =
(* le tri et la taille de la liste *)
let (l_taille,l_tri) = evalue_liste l in
(* Fonction un peu étrange, donne la position horizontale
d'un noeud. Cela permet de retrouver le prochain noeud
du chemin. "liste" contient la liste des noeuds
parcourus, triée plus tôt. *)

(* glossaire :
la position relative est la position sur la ligne considérée
la position absolue est la position relative sommée avec
le nombre de noeuds plus haut dans le graphe *)

(* Cette fonction est complète en "position_absolue" *)
let rec calcul_relatif liste n1 n2 =
match liste with
|[] -> 0
(* Ça ça marche, mais on sait pas trop pourquoi...*)
|t::q -> ((position_vert_pascal triangle (taille-n2) (l_taille-n1) t)
+ calcul_relatif (q--(t+1)) (n1+1) (n2+1+t)) (* Ça ça marche, mais on sait pas trop pourquoi...*)
in
(*calcul de la position absolue *)
(calcul_relatif l_tri 1 1) + vecteur_somme.(l_taille|>-1)
 
 
(* La fonction principale de résolution. Ne prend en argumant
que le nombre de nageurs, le nombre d'épreuve,
et enfin une matrice des points selon la nage *)

let calcul_chemin n_nageurs n_epreuves tableau_points =
(* Mon beau triangle *)
let triangle = triangle_pascal n_nageurs in
(* la somme de Nième ligne du triangle *)
let vecteur_somme = somme_ligne_pascal triangle n_nageurs in
(* La liste de départ *)
let l_initiale = construit_liste n_nageurs in
(*Le plus important, conserve tout ce qui est déjà calculé *)
let cache_chemin = Array.make (power 2 n_nageurs) (0,[]) in
(* juste de la commodité pour réduire le nombre de caractères *)
let calcul_absolu l = (position_absolue triangle l n_nageurs vecteur_somme) in
 
(* l1 = liste des nageurs non exploré ( == restant) *)
(* l2 = chemin déjà effectué trié (==parcourue) *)
(* l3 = simple tampon de parcours recursif (suite de l1)*)
(* l4 = mémoire des nageurs sélectionnés *)
(* n = nombre d'éléments de l2 (==niveau dans le graphe) *)
(* calcul_unique : donne le maximum d'un noeud *)
(* calcul_liste : renvoie la liste des chemins du noeud *)
let rec
calcul_liste l1 l2 l3 niveau l4 =
match l1 with
| [] -> []
| t::q ->(*on calcule la valeur d'un noeud puis on continue
le parcours de la liste *)

let (c,parc) = calcul_unique (q@l3) (t::l2) (niveau+1) l4 in
((tableau_points.(niveau|>).(t|>) + c,[t]@parc)::
(calcul_liste q l2 (t::l3) niveau l4))
and
calcul_unique l1 l2 niveau l4 =
(* si dans le cache inutile de recalculer *)
if fst cache_chemin.(calcul_absolu|> l2) <> 0 then
cache_chemin.(calcul_absolu|> l2)
(* sinon prenons le maximum pour ce noeud
et sauvegardons dans le cache *)

else
let c = max_liste (calcul_liste l1 l2 [] niveau l4) in
cache_chemin.(calcul_absolu|> l2) <- c ;
c
in
cache_chemin.(|>0) <- max_liste (calcul_liste l_initiale [] [] 0 []) ;
(fst cache_chemin.(|>0))::(snd cache_chemin.(|>0))

Pour le code complet voir ici. Ce qui est merveilleux c'est que cela résout un problème N=13 en une seconde environ. Objectif atteint. Il est possible qu'il reste encore des optimisations possibles, mais je suis suffisamment content que cela fonctionne pour ne pas avoir le courage de chercher de nouveau.

En conclusion il est quasi certain que je n'ai fais que ré-inventer la roue, mais je n'avais pas trouvé le manuel de construction pour résoudre ce problème. Si quelqu'un a de la documentation ou connaît des problèmes similaires je suis pas contre du tout (ça a peut-être un nom tout bête qui m'empêchait de trouver sur mon moteur de recherche préféré). Il reste encore quelques points pour que tout cela soit véritablement utile :

  • Faire une interface pour taper l'équipe, par exemple une simple page web avec un formulaire, propulsé par ocsigen afin de rester dans le thème. C'est suffisamment peu gourmand pour envisager que mon petit serveur remplisse la fonction.
  • Si pour optimiser une équipe on raisonne en terme de points, un entraîneur raisonne en terme de temps (tient si lui progressait d'une seconde ça ferait quoi ?). L'idéal serait donc d'incorporer la table de cotation officielle pour faire la correspondance entre temps <=> points.
  • Réfléchir à comment gérer l'ajout de nageur dans un nombre supérieur à N. Si c'était très simple avec l'algorithme précédent, là cela peut remettre fortement en cause l'algorithme.
  • Pour boucler la boucle, implémenter le tout sur une ti-89...

Commentaires

1. Le mardi 5 août 2008, 12:05 par Chtiki pardi

T'as pris en compte que trois nageurs font 2 nages?

2. Le mardi 5 août 2008, 12:09 par flo

Bah oui sinon j'aurais visé 10 nages :)
En fait la solution actuelle est moche, et copie/colle le nageur pour en faire un nouveau tout beau (il est en double quoi). Comme je le vois le "sélectionneur" pourra choisir qui peut doubler ou pas (minimum trois, forcément...).

3. Le mardi 5 août 2008, 17:38 par roux par nature

Moi je dis le principe est chouette! Je comprends rien au codage, dommage ! Vive flo et les bubulles (dont Dresde est envahi maintenant!!!) ! Oubli pas les news ! :)

4. Le jeudi 7 août 2008, 15:57 par Arkéla

Tu me dira si c'est bien Ocsigen? Par bien j'entend vraiment correct au niveau du W3C, intuitif (pas genre je met trois heures et trente quatre essais à faire un pauvre formulaire de quatre ligne...) et qui tourne sur un bébé PC qui fait plein d'autres trucs en même temps (le mien quoi...)

5. Le jeudi 7 août 2008, 16:26 par flo

Ocsigen c'est un serveur web, tout comme apache, il ne fait que fournir des pages.

La comparaison pour faire un formulaire dynamique serait Eliom, et là c'est pas gagné, je crois pas que ce soit si intuitif que ça :)

Pour tourner sur un bébé pc oui sans problème ça tourne sur floolf. Pour correct au niveau w3c c'est automatique et fiable (Ocaml tout ça, ça ne peut pas foirer :p) J'émets donc juste des doutes sur l'intuitivité.

Cf là : linuxfr.org/2008/04/09/23...


6. Le samedi 18 octobre 2008, 11:00 par Sprinteur

Si on repart de la matrice, la somme des termes de la diagonale ça s'appelle la trace du tenseur en physique; dans mes études il y a longtemps le tenseur des contraintes se décomposait en une partie de déformation sphérique et une partie de dilatation déviatorique.

Donc si on part du théorème de décomposition du tenseur, il suffit (!) de s'intéresser à son déviateur, ce qui devrait creuser la matrice (intuition non démontrée mais ça marche sur les exemples que j'ai vus) puisque faire le meilleur temps total de l'équipe c'est pareil que d'obtenir le volume maximal dans l'espace à n dimensions en permutant les dimensions de l'hypervolume.

Peut-être même qu'il y aurait des méthodes toutes faites pour ça dans la littérature? En data mining par exemple ça doit servir ce genre de chose?

7. Le samedi 18 octobre 2008, 17:56 par flo

Oulà, une piste intéressante, c'est vrai que la physique et moi... Je vais chercher dans cette direction, ça m'intéresserait fortement de trouver une solution à ce sujet :)

Ajouter un commentaire

Le code HTML est affiché comme du texte et les adresses web sont automatiquement transformées.

La discussion continue ailleurs

URL de rétrolien : http://flo.fourcot.fr/index.php?trackback/33

Fil des commentaires de ce billet