# 1ère semaine au LaBRI --- ## Définitions --- $P$ domine $Q$ ssi $$ \forall i \in [\![1, d]\!], P_i \leqslant Q_i $$ --- $P$ $(1+\varepsilon)$-couvre $Q$ ssi $$ \forall i \in [\![1, d]\!], P_i \leqslant (1+\varepsilon)Q_i $$ --- $P$ appartient au Front de Pareto de $PATH_G(u,v)$ ssi $$ \forall Q \in PATH_G(u, v), Q \text{ ne domine pas } P $$ --- ### Représentation du Front de Pareto  --- Un résumé du Front de Pareto est un ensemble de points $P$ tels que $$ \forall Q \in PATH_G(u, v), Q\text{ ne }(1+\varepsilon)\text{-couvre pas }P $$ --- ### Représentation d'un résumé pour $\varepsilon = 0.85$ :  --- ## Mesures d'un bon résumé --- * **$\varepsilon$ à posteriori** La valeur minimale d'$\varepsilon$ tel que les éléments du résumé $\varepsilon$-couvrent le Front de Pareto. --- * **Distance moyenne au Front de Pareto$** $$ D(\Pi^*, \Pi) = \frac{1}{|\Pi^*|} \sum_{\pi^* \in \Pi^*} \underset{\pi \in \Pi}{min} \space d(\pi^*, \pi) $$ --- * **Distance euclidienne** $$ d_c(\pi^*, \pi) = \sqrt{\sum_{i = 0}^d(\pi^*_i - \pi_i)^2} $$ * **Distance de Jaccard** $$ d_j(\pi^*, \pi) = \frac{|(\pi^*\cup\pi)| - |(\pi^*\cap\pi)|}{|(\pi^*\cup\pi)|} $$ --- ## Partitionnement de Graphe En théorie des graphes et en algorithmique, le partitionnement de graphe est la tâche qui consiste à diviser un graphe orienté ou non orienté en plusieurs parties. --- Partitions $$ \cup_{i=1}^k V_i = V\\ \forall i, j \in [\![1, k]\!]^2 \quad i \neq j \quad V_i \cap V_j = \emptyset $$ --- Partitions équilibées $$ \forall i \in [\![1, k]\!], |V_i| \leqslant \frac{1}{k} |V| $$ --- ## Algorithmes multicritères --- * Basés sur Dijkstra(MLS) * Basés sur Bellman-Ford * NAMOA$^*$ * McRAPTOR * CSA * McHL --- ### NAMOA$^*$ Basé sur A$^*$, heuristique sur plusieurs critères. $$ h(u, t) = (C_1(u, t), ..., C_d(u, t)) $$ --- ### Hub Labeling On construit $L(s)$ et $L^{-1}(t)$ de sorte que : * $L(s) \cap L^{-1}(t) \neq \emptyset$ * $L(s) \cap L^{-1}(t)$ contienne un sommet sur un plus court chemin de $s$ à $t$. --- 2 tâches à réaliser : * Extraction de données multi-critères. * Implémentation d'un algo avec préprocess. --- Page confluence du stage * http://confluence/pages/viewpage.action?pageId=35328153 Note complêtes * https://hackmd.io/@eDvq0VarQ8G37x2ngDWUvg/SymwwGbV8