Projet d’Algorithmique appliquée (2022-2023)

An english version of the project is available here!

Présentation générale

Dans ce projet, l’objectif est de sauver les villes d'une région d'un incendie. Le but est donc de placer astucieusement des points d'intervention de pompiers pour empêcher le feu d'atteindre les villes. Ce projet se déroulera en plusieurs étapes :

  1. Modélisation du problème ;
  2. Implémentation d’algorithmes résolvant le problème : brute force, algorithmes progressifs, d’approximation, etc... ;
  3. Test de vos algorithmes sur différentes instances ;
  4. Extensions possibles.

Concernant l’organisation :

Problème

On part d'une image simplifiée de la région avec peu de couleurs, représentant les zones habitées (à protéger, mais les pompiers ne peuvent pas intervenir dans une ville sans causer de dégâts), les zones d'eau, inaccessibles pour le feu et pour les pompiers, et les zones agricoles ou forestières, accessible aux deux.

Des pixels rouges sont ajoutés, représentant des départ de feu. Pour simplifier le problème, on suppose que le feu ne se propage qu'en ligne droite et donc ne peut pas contourner un obstacle. De plus, on peut supposer que les flammes empêchent les pompiers de s'approcher trop près du départ de feu. Un pompier peut ignifuger une zone d'un rayon fixe autour de sa position.

Le but est de sauver toutes les villes avec le moins de pompier possible. Il faudra renvoyer l'image sur laquelle sont modifiés les pixels correspondants aux positions d'intervention des pompiers.

Les fichiers à manipuler

Les images d'entrée et de sortie sont au format PPM et accompagnées d'un fichier texte.

Le format PPM

Le format PPM (pour Portable Pixmap) est un moyen très simple de décrire une image sous forme textuelle. Dans notre cas, il s’agira de fichiers ASCII de ce format (voir Wikipedia) avec un stockage correspondant à un row-major order (voir Wikipedia) :

P3 # fichier PPM ASCII sous format RGB
# Created by GIMP... #on travaillera avec des images créées sous GIMP qui met ce commentaire
3 2 # l'image contient 3 colonnes et 2 lignes
255 # chaque composante R, G et B est représentée par un entier entre 0 et 255
255 255  0
0    0   0
0    0  255 # fin première ligne
255 255  0
0    0  255
255  0   0  # fin deuxième ligne

Le fichier de configuration associé

En plus du fichier au format PPM, un fichier de configuration config.txt permet d’indiquer :

Le nombre d'angles est un entier qui permet de discrétiser les angles, on considère na direction partant de chaque départ de feu. À vous de choisir une valeur adaptée.

Le rayon de fournaise (distance minimale à laquelle on peut s'approcher du départ de feu) rf et le rayon d'action d'un pompier rp sont deux flottants supérieurs ou égaux à 1, en pixels.

Enfin, on définit des indices pour chaque type de zone dont l'interprétation est fixée ci-dessous, et pour chaque indice, on lui associe une couleur de l'image.

Voici un exemple de fichier de configuration config.txt:

700             # nombre d'angles
4.5             #rayon de fournaise
1.6             #rayon d'action d'un pompier
0 255  0   0    # rouge: Feu
1  0  255  0    # vert: Pompier
2  0   0   0    # noir: Ville
3  0   0  255   # bleu: Inaccessible
4 255 255  0    # jaune: Libre

On notera que les pixels verts (indice 1) ne concernent que l'image solution.

Un exemple concret

Voici un exemple concret de plan d'une zone en gironde.

Cette image a été largement simplifiée (les étapes de création d'images seront explicitées plus tard) pour obtenir une image plus petite au format PPM, à télécharger ici.

Si on ouvre ce fichier, on s’aperçoit notamment que l’image est de taille 100*100 : les 100 premiers triplets représentent la première ligne, les triplets 100 à 200 la deuxième ligne et ainsi de suite. Cette image contient 4 couleurs différentes :

  1. (255,0,0) : rouge ;
  2. (0,0,0) : noir ;
  3. (0,0,255) : bleu ;
  4. (255,255,0) : jaune ;

On peut ainsi remarquer que la couleur bleue représente les zones d’eau, la couleur noire les zones de ville et le jaune les zones forestières et agricoles. Il y a deux départs de feu: les pixels rouges.

On peut lui associer le fichier de configuration proposé en exemple précédemment, téléchargeable ici.

Création d’autres images PPM

Vous pouvez facilement créer d’autres instances de votre choix. Voici une aide pour créer ce genre d'image sous GIMP.

!!! Attention, GIMP introduit une ligne de commentaire en 2eme ligne, et par défaut on suppose la présence de cette ligne. Si vous créez des images ppm autrement, faite attention au possible décalage.

  1. Aller sur uMap puis cliquer sur “Créer une carte” ;
  2. Changer le fond de carte (menu vertical à droite) et choisir un fond sur lequel les zones à identifier ont des couleurs assez contrastées (par exemple OSM-Hydra);
  3. Faire une capture d’écran de la zone souhaitée dans un fichier file.png.

À partir de cette image, on va en créer une simplifiée sous GIMP, donc pour commencer, ouvrir file.png avec GIMP ;

Il vous faudra ensuite certainement diminuer le nombre de pixels dans l'image. Pour cela

  1. Image > Échelle et taille de l'image
  2. choisir une valeur pour la Largeur ou la Hauteur, par exemple 100;
  3. Mise à l'échelle;
  4. Affichage > Zoom > choisir une valeur de zoom appropiée parmi celles proposés.

Il vous faudra ensuite diminuer le nombre de couleurs pour arriver aux 3 de base (Ville/Inaccessible/Libre) :

  1. Image > Mode > Couleurs indexées ;
  2. Générer une palette optimale et choisir le nombre maximal de couleurs. Comme il y a beaucoup d'éléments sur l'image, il est quasiment impossible de prendre directement 3 couleurs et d'avoir quelque chose s'approchant du résultat voulu. Il est donc préférable de procéder par étapes, commencer par réduire à 5 couleurs (par exemple).
  3. Il est possible de modifier les valeurs RGB de chacune des couleurs restantes, ce qui permet de regrouper des couleurs (par exemple mettre les routes de la même couleur que les forêts), et de choisir les couleurs souhaitées pour chaque type de zone dans l'image finale pour cela :
  4. Image > Mode > RVB ;
  5. Image > Mode > Couleurs indexées ; cette fois choisir 3 comme nombre maximal de couleurs. Vous pouvez à nouveau modifier les valeurs RGV des couleurs à votre convenance.

Enfin, pour exporter l’image en PPM :

  1. Fichier > Exporter sous > file.ppm > Exporter ;
  2. choisir ASCII.

Il vous faudra ensuite lancer la commande suivante depuis un terminal :

foo@bar:~$ awk '{ ++x; if(x<=4) print $0; else { l1=$0; getline; l2=$0; getline; print l1 " " l2 " " $0; }}' file.ppm > res.ppm

Ceci permet de récupérer le fichier PPM final dans un fichier res.ppm. Ici, le x<=4 signifie que la couleur du pixel de coordonnées (0,0) est sur la ligne 5 du fichier file.ppm.

Premier rendu

On vous demande un petit rapport (fichier texte ou PDF) expliquant :

Date limite : vendredi 30 septembre

Deuxième rendu

On vous demande un rapport (fichier texte ou PDF) expliquant :

Date limite : vendredi 28 octobre

Rapport final et Soutenances

Il vous est demandé d’envoyer votre rapport final (format PDF) d’ici le 16 janvier . Les soutenances auront lieu le 19 janvier (CREMI, salle 201) et dureront 20 minutes par groupe. Les soutenances et questions/réponses pourront être au choix en Français ou Anglais. Les horraires de passage sont :

Nous vous demandons d’entrer discrètement dans la salle 10 minutes avant votre horaire et de vous installer sur un ordinateur afin d’éviter toute perte de temps. Vous devrez présenter rapidement ce que vous avez fait, puis nous vous poserons des questions à propos de votre projet. Vous pouvez utiliser des slides, mais ce n’est pas obligatoire.