from dirmaths import *
import numpy as np
En plus des packages habituels, nous aurons besoin du package math, pour sa représentation de l'infini
from math import inf
inf vérifie les propriétés classiques :
print(inf > 9999)
print(inf + 82 == inf)
print(inf + 1 > inf)
print(inf*(-72) == -inf)
True True False True
Un graphe valué est un graphe auquel on ajoute un poids sur ses arcs/arêtes.
Un graphe valué peut être représenté par sa matrice de poids M définie de la façon suivante :
$M_{i,j}=+\infty$ si il n'y pas d'arcs/arêtes reliant i à j
$M_{i,j}=$ valuation de l'arc/arête {i, j}
Exemple : le graphe valué $GV$ a pour matrice de poids $MV$.
MV = np.array([ [inf,2,4,3,6],
[2,inf,7,inf,inf],
[4,7,inf,2,8],
[3,inf,2,inf,1],
[6,inf,8,1,inf]])
Pour l'affichage, la fonction display possède un paramètre weighted qui prend pour argument un booléen.
Si l'argument vaut False (argument par défaut), la fonction display attend une matrice d'adjacence, et si l'argument vaut True, la fonction display attend une matrice de poids.
display(MV,weighted=True,directed=False,title="GV",dispo='dot')
display(MV2,weighted=True,title="GV2",dispo="dot")
définition de bellman(M) Dist = liste des distances depuis le sommet 0, dont chaque élément est initialisé à l'infini Dist[0] = 0 tant que Dist change pour tout sommet i pour tout sommet j si Dist[i] + M[i,j] < Dist[j] alors Dist[j] = Dist[i] + M[i,j] fin si fin pour fin pour fin tant que retourner Dist
Construire une fonction bellman(M), qui renvoie les distances du plus court chemin du sommet $0$ à tous les autres, dans un graphe orienté de matrice de poids $M$, à l'aide de l'algorithme de Bellman.
Tester bellman avec la matrice $MV2$.
bellman(MV2)
[0, 7.0, 2.0, 8.0, 3.0]
définition de dijkstra(M) Dist = liste des distances depuis le sommet 0, dont chaque élément est initialisé à l'infini Dist[0] = 0 tant que il y a des sommets non marqués choisir un sommet i non marqué, tel que Dist[i] soit minimale marquer i pour tout sommet j non marqué si Dist[i] + M[i,j] < Dist[j] alors Dist[j] = Dist[i] + M[i,j] fin si fin pour tant que retourner Dist
dij(M) et l'algorithme de Dijkstra.Rq : on pourra par exemple créer une liste marquage, avec marquage[i]=True si le sommet i est marqué, False sinon.
Exemple :
dij(MV2)
[0, 7.0, 2.0, 8.0, 3.0]
Que doit-on modifier dans l'algorithme de Bellman et dans une matrice de poids pour traiter un problème de plus long chemin ?
Créer une fonction bellmanlong(M) qui renvoie les distances du plus long chemin du sommet 0 à tous les autres.
Exemple :
bellman_long(MV2)
[0, 8.0, 2.0, 13.0, 3.0]
Soit le problème d'ordonnancement suivant :
| tâches | contraintes | durée (jours) |
|---|---|---|
| (0) | début du projet | 0 |
| (1) | aucune contrainte | 3 |
| (2) | commence au plus tôt après la fin de (3), et 9 jours après la fin de (1) | 6 |
| (3) | commence au plus tôt 5 jours après le début du projet, et 4 jours après la fin de (1) | 4 |
| (4) | fin du projet | 0 |
On associe à ce problème d'ordonnancement un graphe potentiel-tâche :
les sommets sont les tâches, et un arc (i,j) a une valuation k ssi la tâche j commence au plus tôt k jours après le début de la tâche i.
display(A,weighted=True,directed=True,title='potentiel_tâche',dispo='dot')
L'objectif est de trouver les dates de début au plus tôt de chaque tâche, pour terminer le projet le plus rapidement possible. Il suffit alors de calculer les chemins les plus long depuis le sommet 0 à tous les autres.
[0, 0.0, 12.0, 7.0, 18.0]
[0, 0.0, 12.0, 7.0, 18.0]
display(MV,weighted=True,directed=False,title="GV",dispo='dot')
Par exemple, cela couterait 3 millions de relier directement Zérocity à Trois-sur-marne, et 6 millions de relier directement Zérocity à Saint-Quatre.
Le regroupement de communes décide d'autoriser les changements de lignes, et de ne construire que les lignes nécessaires, afin d'assurer un coût total minimal.
Mathématiquement, il s'agit de construire un arbre couvrant de poids minimal, c'est à dire un arbre passant par tous les sommets du graphe, dont la somme des poids des arêtes est minimale. L'algorithme proposé pour résoudre le problème est l'algorithme de Prim.
Dans l'exemple, l'abre couvrant serait :
L'algorithme proposé pour résoudre le problème est l'algorithme de Prim.
définition de prim(M) marquer le sommet 0 arbre = arbre résultat, ne contenant initialement pas d'arêtes. tant qu' il reste des sommets non marqués {x, y} = arête de poids minimal, joignant un sommet marqué x à un sommet non marqué y marquer y ajouter l'arête {x,y} à l'arbre fin tant que retourner arbre
prim(M) qui retourne la matrice de l'arbre couvrant de poids minimum d'une matrice de poids M.prim(MV)
array([[inf, 2., inf, 3., inf],
[ 2., inf, inf, inf, inf],
[inf, inf, inf, 2., inf],
[ 3., inf, 2., inf, 1.],
[inf, inf, inf, 1., inf]])