Présentation générale

Cette année encore, la canicule a fait rage sur le campus de l'université. Heureusement, les arbres et espaces verts ont aidé les usagers à supporter la température. Afin d'améliorer la situation, l'université aimerait planter des arbres de sorte que toutes les zones utilisées soient couvertes par leur fraîcheur. Cependant les arbres ne peuvent pas être plantés dans des zones bétonnées et doivent être remplacés par des parasols, moins efficaces. Les zones bétonnées reflètent la chaleur ce qui limite également la propagation de la fraîcheur.

Le projet se déroulera en plusieurs étapes :

  1. modélisation du problème ;
  2. implémentations des algorithmes (force brute, etc...) ;
  3. ajout d'extensions.

Concernant l’organisation :

Problème

On vous propose les problèmes suivant: Comment placer les arbres de sortes que l'ensemble des zones utilisées du campus (trottoirs etc...) soient couvertes par de l'ombre ? Quel est le nombre minimal d'arbres à placer pour couvrir ces zones ?

Dans un second temps vous considérerez des problèmes annexes avec les parasols et la variation de la distance couverte en fonction du terrain.

Vous pourrez également proposer vos propres variantes du problèmes en justifiant pourquoi elles sont pertinentes.

Vous présenterez vos résultats de manière graphique afin de faciliter la compréhension de ce que vous proposez.

Données

Pour réaliser le projet, vous aurez besoins des données cartographique du campus. Celles-ci peuvent-être récupérée via openstreetmap, par exemple en utilisant des requêtes overpass. Vous pouvez également utiliser d'autres sources ouvertes que vous trouveriez. osmnx pourrait également vous être utile si vous choisissez de faire votre projet en python

Pour le 2 Octobre

Chaque groupe préparera mini présentation de la modélisation. Les outils choisis pour la réalisation seront présenté également

Algorithme Branch and Bound

ensemble_dominant(graphe G, dominant partiel S, entier k)
    si k = 0 :
        tester si S est un dominant 
    sinon :
        u <- sommet de degré min parmi les sommets non dominés par S
        pour tout v dans N[u] :
            ensemble_dominant(G, S U {v}, k-1)

Premier rendu - 16/10

  1. Implémentez la modélisation du problème en utilisant Ensemble Dominant (Dominating Set) ou un problème équivalent ;
  2. Implémentez les algorithmes Bruteforce et Branch and Bound pour le problème choisi.

Pensez à commencer un rapport pour les prochains rendus.

Second rendu 06/11

Vous rédigerez un rapport reprenant les éléments suivants: