---
# System prepended metadata

title: APPERO

---

# APPERO


## Résolution du problème : 


### Pour le rapport/video : 
Avoir des stats stylés - genre on parcourt 5% d'arrêtes en trop.

### Comment parcourir tout le graph ? 
- Cas des impasses -> aller sur le noeud et faire demi tour
- Lorsque l'on est sur un noeud impair (3 ou +) -> faire un allé retour sur une arrete au hasard 

0. Premier parcours pour faire une liste des sommets de degré impair


### I. Survol de la ville 

*Consigne :* Le drone doit survoler **TOUT** le graph voir 1. dans la consigne. On supprime du graph toutes les routes que l'on a pas besoin de deneiger car pas trop de neige. 


Dans les trucs à faire partie théorie c'est montrer comment un chemin eulérien ammène au résultat et dans le cas d'un graphe non eulérien, on pourrait trouver un cycle eulérien mm s'il couvre pas tout le graphe

### II. Trajet minimal d'une machine dans une partie de la ville
*Consigne :* Déterminer le trajet **minimal** d’un appareil de déblaiement d’une zone de la ville, celui-ci ne parcourt **que dans un sens** les routes à double sens.

- Séparation d'un quartier de la ville du reste du graphe
- Parcours eulérien de toute le graph en cherchant la méthode la plus courte

On ne va pas passer dans les petites rues qui cassent les couilles. Avantage deneigement de la ville plus rapide mais on risque de decevoir les habitants des rues laissés de coté. Dans ce cas on propose une deneigeuse de jour dont l'objetif sera de déneiger les rues mises de coté dans la nuit. 

On est très efficace et on permet aux rues les plus importantes d'être toutes libre dès avant le matin

### III. Modèle de coût pour les opérations déblaiement sur l’ensemble de la ville en fonction du nombre de véhicules à disposition
*Consigne :* Proposer un **modèle de coût** pour les opérations de déblaiement sur l’ensemble de la ville en fonction du **nombre de véhicules** à disposition.

On sépare le graphe de la ville en sous-graphes de taille a peu près égale. 
- On propose plusieurs hangars a deneigeuse pour gagner du temps dans le déploiement et éviter les déplacements inutiles ? 
- Les deneigeuses déblaient sur leur route vers leur zone atitrée (plus court chemin) et on retire le chemin qu'elles ont pris du graph (pour être sur que la prochaine déneigeuse qui partira ne passera pas à un endroit déjà fait)

**Coût** : 
Salaire des conducteurs 
Entretien machines
Paiement machine
Hangar
Plus de machine = moins de temps
Plus de machine = plus d'employés
Plus de machine = plus grand hangar



## CODE

- Rendre un graphe non-eulérien eulérien
- Parcours complet de graphe eulérien ()
- Division d'un graphe eulérien en sous-graphes eulérien (ville en quartier)



## Script vidéo :
Suite à la tempête Joël du 31 décembre, la ville de Montréal est en prise à la panique sous 5 mètres 50 de neige ! Du jamais vu jusqu'alors. Démunis comme jaja, il faut s'empresser de déblayer toute cette neige qui empêche les honnêtes citoyens de faire le métro boulôt dodo pour payer son loyer et ses impôts.
L'heure est grave et le temps où la ville faisait les guignols avec leurs déneigeuses est révolu, cette fois, il faut des pros, des mecs malins qui utilisent les maths avec un gros cerveau



*Truc au départ très sérieux puis part dans un truc plus drôle mais on garde un bon contenu.*

masterclass : https://www.youtube.com/watch?v=hj8NZwFl-5s


ceci est un graphe eulérien ^^
.__.
| /|
|/ |
²--²










---

## Vieilles idées 

#### Pas possible car trop de noeud impair dans les villes
Chemin eulérien - 0 ou 2 sommets ayant des sommets impairs
Objectifs : Parcourir les noeuds et casser le edge le plus cours des noeuds ayant un nombre de lien impair. 

0. Premier parcours pour faire une liste des sommets de degré impair
1. On parcours la liste de nos noeuds impairs 
- On supprime le edges le plus court du noeud (on le garde en mémoire pour plus tard)
-  On va sur le noeud qui était lié par le lien et on regarde s'il est devenu impair. (Si c'est le cas retour à l'étape 4)
2. Et bim normalement on obtient un graphe eulerien


On doit deblayer les rues restantes. 

1. Prendre l'edge gardé en mémoire le plus proche (rue mise de coté). Algo A* présent dans NetworkX
2. Utilisé le plus court chemin pour y aller et le traverser
3. Le supprimer de la liste 
4. Revenir à l'étape 1 tant que la liste d'edge n'est pas vide
