6. TP de C++ n°6 Utilisation des tas

6.1. Les tas en STL

Les tas sont représentés par la classe priority_queue dans la STL. Cette classe est caractérisée par les éléments suivants :

En tant que spécialisation d'une classe de base, on doit fournir la classe conteneur de base en paramètre template. Comme l'indexation est requise, ce devra être soit un tableau, soit une file à double accès (deque). L'utilisation d'une deque fournit habituellement un résultat plus rapide au détriment d'une plus grande occupation mémoire.
En tant que collection ordonnée, il faudra passer un prédicat au constructeur à moins que votre compilateur C++ favori n'accepte les arguments template avec valeur par défaut.

6.2 Une application sympa : les séquences de Bean

6.2.1 Les séquences de Bean

Les séquences de Bean offrent un codage particulièrement efficace pour la résolution par algorithme génétique du problème du voyageur de commerce (TSP).

Rappelons brièvement que le principe des algorithmes génétiques consiste à disposer d'une population de chromosomes codant différentes solution d'un problème. A chaque itération, ces chromosomes sont croisés par paires pour donner une nouvelle génération.

La plus commune des techniques de croisement imite le processus naturel du cross over. Les deux chromosomes sont coupés en un certain nombre d'endroits et leurs différentes parties sont recopiées. La figure suivante illustres des cross overs à 1 et 2 points.

Utiliser des séquences de villes pour coder un TSP ne convient pas car l'application des cross overs ne donne pas toujours des solutions réalisables (c'est à dire correspondant à une solution du problème). L'exemple suivant illustre ce problème pour un TSP à 6 villes sur un cross over à 1 point.

Bean a eu l'idée d'utiliser un générateur de nombres aléatoires pour pallier cette difficulté. Le principe des séquences de Bean consiste à associer un nombre aléatoire à chaque ville en fonction de sa position dans la tournée.

Algorithme de codage

Voici l'algorithme de codage d'une séquence de villes vers une séquence de Bean.

Générer une séquence de nombres aléatoires de même taille que la tournée
Trier ces nombres
Associer chaque nombre a une ville de la tournée dans l'ordre croissant des positions (i.e. le plus petit nombre correspond à la première ville, le second plus petit nombre à la seconde ville, etc.)
On obtient ainsi une séquence de couples (nombre aléatoire, numéro de ville)
Trier cette séquence de couples par ordre croissant du numéro de ville
On obtient alors une séquence de Bean

Lorsque vous effectuez un cross over sur de telles séquences, vous êtes sur d'obtenir une solution réalisable car chaque ville sera représentée une et une seule fois.

Algorithme de décodage

Voici l'algorithme de décodage de la séquence de Bean en une séquence de villes :

Triez la séquence par ordre croissant des nombres aléatoires
La séquence des villes s'obtient alors par simple lecture de la séquence

Exemple d'utilisation

Séquence de villes n°1

Nombres aléatoires associés

0.13

0.36

0.56

0.58

0.91

Séquence de Bean après tri par ordre de ville :

1	2	3	4	5
0.13	0.56	0.36	0.91	0.58

Séquence de villes n°2

Nombres aléatoires associés

0.27

0.41

0.63

0.66

0.88

Séquence de Bean après tri par ordre de ville :

1	2	3	4	5
0.41	0.66	0.27	0.63	0.88

Après application d'un cross over entre les villes 3 et 4

Fils 1

1	2	3	4	5
0.13	0.56	0.36	0.63	0.88

Fils 2

1	2	3	4	5
0.41	0.66	0.27	0.91	0.58

Décodage du Fils 1

0.13	0.36	0.56	0.63	0.88
1	3	2	4	5

Décodage du Fils 2

0.27	0.41	0.58	0.66	0.91
3	1	5	2	4

On obtient donc les 2 solutions :

1	3	2	4	5
3	1	5	2	4

6.3 Travail demandé

On vous demande d'utiliser la STL pour réaliser le codage et le décodage d'une séquence de villes vers une séquence de Bean.

6.4 Solution

Elle est axée sur les trois fichiers sources suivants :

Bean.hxx contient le code de déclaration de la classe Bean ainsi que de nombreuses instanciations de conteneurs de la STL
Bean.cc ne contient que le code d'opérateurs d'entrées sorties divers et l'implémentation d'une méthode d'initialisation de la classe Bean
MainBean.cc propose un exemple d'utilisation de ces classes en conjonction avec le fichier d'exemples sequences. Notez l'extrème concision du code obtenu à la fin !

Je vous concède que le code n'est pas simple à suivre. En effet, il utilise des template de tous les côtés ainsi que des astuces propres à l'utilisation de la STL.

Les deux premières classes définissent des foncteurs pour comparer des objets dérivant des classes paires en fonction de leur premier ou de leur second membre.
Les méthodes de la classe Bean sont elles mêmes des template qui leur permettent d'utiliser n'importe quelle classe itérateur en entrée !

6.5 Pour aller plus loin

Codez un algorithme génétique minimal pour chercher la solution d'un problème de voyageur de commerce. Pour cela, il faut disposer des coordonnées géographiques des villes pour calculer la longueur d'une tournée. Les opérateurs de XOvers peuvent aussi être codés sous la forme de classes foncteurs.