Table des matières

Consignes importantes

• Ne changez pas les signatures des fonctions demandées (noms des fonctions, paramètres des fonctions...): sinon vous risquez de perdre des points.
• Vous devez répondre clairement aux questions posées dans votre fichier python sous forme de commentaires.
• Votre fichier à soumettre doit avoir le nom votreNom_votrePrenom_votreNumEtu.py (votre numero étudiant commence par 23 avec 7 chiffres)
• Vous devez soumettre votre fichier à votre propre groupe sur Edunao
• Nous allons évaluer votre travail fait par vous-même et dans la salle de votre groupe!

Merci de respecter toutes ces consignes, sinon votre rendu ne serait pas évalué (correctement).

Objectifs du TP2

Les algorithmes du plus court chemin sont une famille d'algorithmes conçus pour résoudre le problème du plus court chemin. Le problème du plus court chemin peut être défini pour des graphes non orientés ou orientés. Les algorithmes du plus court chemin ont de nombreuses applications dans notre monde réel, telles que les systèmes GPS, les protocoles de routage Internet, les réseaux de distribution d'énergie, la navigation de l'IA ennemie dans les jeux vidéo, la recherche de contacts et la prédiction de la propagation des maladies, etc.

Dans les cours et TDs, vous avez vu que l'algorithme plus court chemin / SP (Dijkstra) est utilisé pour trouver les chemins les plus courts entre un sommet donné et tous les autres dans un graphe avec seulement des poids positifs. L'algorithme de Bellman-Ford peut fonctionner pour les poids négatifs ainsi que pour la détection des circuits absorbants, mais avec une complexité plus élevée. Dans cette séance de TP (3h), nous examinerons un nouveau problème : nous voulons calculer le chemin le plus court pour toutes les paires de sommets dans le graphe avec des poids positifs et négatifs. Une méthode naïve consiste à exécuter l'algorithme de Bellman-Ford |V| fois (|V| est le nombre de sommets). Cependant, nous verrons qu'un autre algorithme, combinant SP et Bellman-Ford, peut accomplir cette tâche avec une meilleure complexité.

Définition du problème

Nous avons construit un village de montagne avec N maisons reliées par des chemins forestiers, présentant des élévations variables. Les élévations sont représentées positivement ou négativement selon la direction, le coût de la montée étant au moins aussi important que la valeur absolue du "coût négatif" de la descente. Cela signifie que nous rechargeons les batteries de nos véhicules pendant les descentes, tandis que la consommation d'énergie est nécessaire pendant les montées. Voici un exemple de descente de la maison A vers la maison B et de montée de B vers A.

Exemple : A --(-2)--> B et B --(+7)--> A

La mairie dispose d'un budget pour acheter des fours à pain K, qui peuvent être installés dans une maison de village (les fours ne peuvent pas être placés à l'extérieur des maisons car ils doivent être alimentés en électricité). La question est la suivante : comment placer les K fours pour minimiser le coût pour le villageois le plus éloigné d'un four ?

Nous avons donc des poids négatifs et, en outre, nous devons calculer tous les chemins entre deux maisons pour déterminer où placer les fours.

Le village est représenté sous la forme d'un graphe pondéré avec des coûts positifs ou négatifs. Il convient de noter qu'il ne peut y avoir de circuits absorbants dans le village, car toute montée est plus coûteuse que l'inverse de toute descente.

Pour résoudre ce problème de placement, nous allons d'abord réviser l'algorithme SP, puis mettre en œuvre le nouvel algorithme combinant les algorithmes SP et Bellman-Ford pour calculer tous les chemins les plus courts entre deux maisons quelconques.

Analyse de la complexité de l'algorithme SP

Vous avez vu, dans Cours 2, la complexité de l'algorithme SP, en fonction de la structure de données pour la frontière (liste ou tas binaire). Vous trouverez ci-dessous l'implémentation avec deux structures de données (SP_naive et SP_heap).

def SP_naive (graph, s):
    frontier = [s]
    dist = {s:0}

    while len(frontier) > 0:

        x = min(frontier, key = lambda k: dist[k])
        frontier.remove(x)

        for y, dxy in graph[x].items():
            dy = dist[x] + dxy

            if y not in dist:
                frontier.append(y)
                dist[y] = dy

            elif dist[y] > dy:
                dist[y] = dy

    return dist

from heapq import *

def SP_heap (graph, s):
    frontier = []
    heappush(frontier, (0, s))
    done = set()
    dist = {s: 0}

    while len(frontier) > 0:

        dx, x = heappop(frontier)
        if x in done:
            continue

        done.add(x)

        for y, dxy in graph[x].items():
            dy = dx + dxy

            if y not in dist or dist[y] > dy:
                heappush(frontier,(dy, y))
                dist[y] = dy

    return dist

Vous disposez maintenant de fonctions qui génèrent aléatoirement des graphes peu denses {$|E|\approx|V|$} et des graphes denses {$|E|\approx|V|^2$} ainsi que benchmark.

import random

def random_sparse_graph (n, step):
    graph = {f'{i}_{j}': {} for i in range(1, n+1) for j in range(1, n+1)}

    for i in range(1, n+1):
        for j in range(1, n):
            d = random.randint(step+1, 2*step)
            graph[f'{i}_{j}'][f'{i}_{j+1}'] = d
            graph[f'{i}_{j+1}'][f'{i}_{j}'] = d

    for i in range(1, n):
        for j in range(1, n+1):
            d = random.randint(step+1, 2*step)
            graph[f'{i}_{j}'][f'{i+1}_{j}'] = d
            graph[f'{i+1}_{j}'][f'{i}_{j}'] = d

    return graph

def random_dense_graph (n, d_max):
    graph = {f'{i}':{} for i in range(n)}

    for n1 in graph:
        for n2 in graph:
            if n2!= n1 and n2 not in graph[n1]:
                d = random.randint(1, d_max)
                graph[n1][n2] = d
                graph[n2][n1] = d

    return graph

import matplotlib.pyplot as plt
from timeit import timeit

def benchmark():
    Time_heap_sparse = []
    Time_naive_sparse = []
    Time_heap_dense = []
    Time_naive_dense = []

    n_list = []

    for N in range(10, 30):
        n = N*N
        n_list.append(n)

        # on compare sur des cartes non-denses: grille de côté N contient N*N villes
        graph_sparse = random_sparse_graph(n = N, step = 100)

        # on calcule une moyenne sur N lancements en tirant aléatoirement une ville de départ à chaque fois
        Time_naive_sparse.append(timeit(lambda: SP_naive(graph_sparse, random.choice(list(graph_sparse))), number=N) / N)
        Time_heap_sparse.append(timeit(lambda: SP_heap(graph_sparse, random.choice(list(graph_sparse))), number=N) / N)

        # on compare sur des cartes denses
        graph_dense = random_dense_graph(n = N*N, d_max = 10000)

        Time_naive_dense.append(timeit(lambda: SP_naive(graph_dense, random.choice(list(graph_dense))), number=N) / N)
        Time_heap_dense.append(timeit(lambda: SP_heap(graph_dense, random.choice(list(graph_dense))), number=N) / N)

    plt.xlabel('N')
    plt.ylabel('T')
    plt.plot(n_list, Time_naive_sparse, 'r^', label="naive sparse")
    plt.plot(n_list, Time_heap_sparse, 'b^', label="heap sparse")
    plt.plot(n_list, Time_naive_dense, 'r*', label="naive dense")
    plt.plot(n_list, Time_heap_dense, 'b*', label="heap dense")

    plt.legend()
    plt.show()

Technique de réécriture pour de nouveaux poids non négatifs tout en préservant les plus courts chemins

Étant donné un graphe avec une fonction de poids {$w$} qui peut avoir une arête de poids négatif mais pas de circuits absorbants, l'idée de la technique de réécriture est de calculer un nouvel ensemble de poids non négatifs en préservant les plus courts chemins de telle sorte que l'algorithme de Dijkstra puisse être directement appliqué. Plus précisément, il faut trouver une nouvelle fonction de poids {$\hat{w}$} telle que les deux propriétés suivantes soient respectées :

• préservation du plus court chemin : si {$p=\langle v_0, v_1, ..., v_k \rangle$} est un chemin quelconque de {$v_0$} à {$v_k$}, alors {$w(p)$} est le plus court chemin de {$v_0$} à {$v_k$} si {$\hat{w}(p)$} est le plus court chemin de {$v_0$} à {$v_k$}.
• poids non négatifs : pour toutes les arêtes {$(u, v)$}, le nouveau poids {$\hat{w}(u, v)$} est non négatif.

Ces deux propriétés peuvent être obtenues de manière élégante en utilisant l'algorithme de Bellman-Ford. Nous allons procéder étape par étape dans ce qui suit.  

def add_source(graph, src):

  if src in graph:
    return "error: the source vertex is already in the graph"

  graph_src=graph.copy()

  ############TODO : complete code#########

  return graph_src

Testez votre fonction avec le code suivant:

sim_graph = {"A":{"B":-5,"C":2,"D":3},
             "B":{"A":6,"C":4},
             "C":{"D":1},
             "D":{}}

src="source"

sim_graph_src=add_source(sim_graph, src)

assert sim_graph_src == {"A":{"B":-5,"C":2,"D":3},
                         "B":{"A":6,"C":4},
                         "C":{"D":1},
                         "D":{},
                         "source":{"A":0, "B":0, "C":0, "D":0}}

import math

def bellman_ford(graph, src):

    dist={}


    ############TODO : complete code#############


    return dist

Testez votre fonction avec le code suivant.

opt_distance=bellman_ford(sim_graph_src, src)

assert opt_distance=={'A': 0, 'B': -5, 'C': -1, 'D': 0, 'source': 0}

neg_cycle_graph = {"A":{"B":-5,"C":2,"D":3},
             "B":{"A":3,"C":4},
             "C":{"D":1},
             "D":{}}

assert bellman_ford(neg_cycle_graph, "A")==None

import copy

def rewrite_weights(graph, dist):

    # use deepcopy
    altered_graph = copy.deepcopy(graph)

    # Recalculate the new nonnegative weights
    ############### TODO : complete code ##################


    return altered_graph

Testez votre fonction avec le code suivant.

opt_distance={'A': 0, 'B': -5, 'C': -1, 'D': 0, 'source': 0}

nonneg_graph=rewrite_weights(sim_graph, opt_distance)

assert nonneg_graph=={'A': {'B': 0, 'C': 3, 'D': 3}, 'B': {'A': 1, 'C': 0}, 'C': {'D': 0}, 'D': {}}

Calcul des plus courts chemins pour toutes les paires

def all_distances(graph):

  d = {(u,v):None for u in graph for v in graph}

  ############### TODO : complete code ##################

  return d

Testez votre fonction avec le code suivant.

nonneg_graph={'A': {'B': 0, 'C': 3, 'D': 3}, 'B': {'A': 1, 'C': 0}, 'C': {'D': 0}, 'D': {}}

assert all_distances(nonneg_graph)=={
 ('A', 'A'): 0, ('A', 'B'): 0, ('A', 'C'): 0, ('A', 'D'): 0,
 ('B', 'A'): 1, ('B', 'B'): 0, ('B', 'C'): 0, ('B', 'D'): 0,
 ('C', 'A'): None, ('C', 'B'): None, ('C', 'C'): 0, ('C', 'D'): 0,
 ('D', 'A'): None, ('D', 'B'): None, ('D', 'C'): None, ('D', 'D'): 0
 }

Testez votre fonction avec le code suivant.

assert BF_SP_all_pairs(sim_graph)== {('A', 'A'): 0, ('A', 'B'): -5, ('A', 'C'): -1, ('A', 'D'): 0,
                                      ('B', 'A'): 6, ('B', 'B'): 0, ('B', 'C'): 4, ('B', 'D'): 5,
                                      ('C', 'A'): None, ('C', 'B'): None, ('C', 'C'): 0, ('C', 'D'): 1,
                                      ('D', 'A'): None, ('D', 'B'): None, ('D', 'C'): None, ('D', 'D'): 0}

Application (bonus) : Problème de placement

Revenons maintenant à notre problème de placement, où il s'agit de calculer les plus courts chemins pour toutes les paires d'un ensemble donné de maisons. Précisément, il faut écrire un programme qui permette à la mairie de choisir les maisons dans lesquelles on peut installer les fours à pain pour minimiser le coût d'accès des villageois à un four.

Les données d'entrée sont donc :

• un ensemble de maisons reliées par des chemins forestiers dont le poids peut être positif ou négatif ;
• un sous-ensemble de maisons candidates pour accueillir un four à pain (il se peut que certaines maisons ne puissent pas accueillir un four).

Le programme produit un sous-ensemble de maisons candidates de telle sorte que chaque maison du village dispose d'un four ou a accès au four d'une autre maison. L'idée est de prendre en compte le coût d'accès d'une maison à la maison équipée d'un four la plus proche.

Représentation des données

Pour représenter la carte des maisons du village, nous utiliserons un dictionnaire de Python.

Chaque maison sera représentée par une entrée du dictionnaire dont la clé est le nom de la maison (une chaîne de caractères) et la valeur étant un dictionnaire dont les clés sont les noms des maisons voisines et les valeurs sont les coûts d'accès à ces voisines :

Par conséquent, une carte peut être présentée comme suit :

village = {
       'Birchwood':{'Corner':15, 'Fairview':-6, 'Gables':8},
       'Corner':{...},
       ...
}

Nous observons deux dictionnaires imbriqués. L'utilisation de dictionnaires permet un temps d'accès optimal en $O(1)$.

Les informations relatives au village vous seront fournies dans un fichier composé de deux parties séparées par une ligne contenant deux tirets : --. La première partie contient la liste des maisons. La deuxième partie contient la liste des routes entre les maisons et les coûts d'accès entre elles, par exemple :

Birchwood
Corner
Fairview
Gables
--
Birchwood:Corner:15
Birchwood:Fairview:-6
Corner:Fairview:8

Pour charger une carte à partir d'un fichier, vous pouvez utiliser le code suivant :

def read_map(filename):
    f = open(file=filename, mode='r', encoding='utf-8')

    map = {}
    while True:  # reading list of cities from file
        ligne = f.readline().rstrip()
        if (ligne == '--'):
            break
        info = ligne.split(':')
        map[info[0]] = {}

    while True:  # reading list of distances from file
        ligne = f.readline().rstrip()
        if (ligne == ''):
            break
        info = ligne.split(':')
        map[info[0]][info[1]] = int(info[2])

    return map

Copiez l'exemple de jouet fourni ci-dessous (le dictionnaire toy_village) dans votre fichier python :

toy_village = {'A': {'B': -3, 'E': 20, 'F': 30},
           'B': {'A': 6, 'C': 9, 'F': 39},
           'C': {'B': 9, 'D': 8},
           'D': {'C': 8, 'F': 50},
           'E': {'A': -10, 'F': 6},
           'F': {'A': -20, 'B': -25, 'D': -15, 'E': 6} }

Précision du problème

Rappelons que la mairie dispose d'un financement permettant d'équiper {$k$} maisons pour le four à pain. Le nombre {$k$} est donné dans l'instance du problème.

Pour chaque maison, on calcule le coût d'accès à la maison équipée la plus proche (voir Question 10). Pour un ensemble de maisons données, le coût d'accès est le coût maximum de cet ensemble (voir Question 11).

Le but est, pour un village et un nombre {$k$} de fours à pain, de choisir l'emplacement de {$k$} maisons parmi les maisons candidates de manière à minimiser le coût d'accès global. Notez que le nombre de maisons candidates ne doit pas être inférieur à {$k$}.

def closest_oven(house, oven_houses, distance_dict):
    ...

Testez votre fonction avec le code suivant :

toy_distance_dict = BF_SP_all_pairs(toy_village)

assert closest_oven('A', ['B','E','D'], toy_distance_dict) == (-3, 'B')
assert closest_oven('B', ['B','E','D'], toy_distance_dict) == (0, 'B')
assert closest_oven('C', ['B','E','D'], toy_distance_dict) == (8, 'D')
assert closest_oven('D', ['B','E','D'], toy_distance_dict) == (0, 'D')
assert closest_oven('E', ['B','E','D'], toy_distance_dict) == (-19, 'B')
assert closest_oven('F', ['B','E','D'], toy_distance_dict) == (-25, 'B')

def kcentre_value(village, oven_houses, distance_dict):
     ...

Testez votre fonction à l'aide du code suivant :

assert kcentre_value(toy_village, ['B','E','D'], toy_distance_dict) == 8

from itertools import *

def brute_force(map, candidates, k, distance_dict) :
    best_combi = []
    best_dist = math.inf
    for combi in combinations(candidates, k):
        dist= kcentre_value(map, list(combi), distance_dict)
        if  dist<best_dist:
            best_combi= list(combi)
            best_dist= dist
    return  best_dist, set(best_combi)

assert brute_force(toy_village, list(toy_village), 3, toy_distance_dict) == (0, {'C', 'D', 'B'})
assert brute_force(toy_village, list(toy_village), 2, toy_distance_dict) == (8, {'C', 'A'})

import matplotlib.pyplot as plt
from timeit import timeit

village = read_map('village.map')

village_distance_dict = BF_SP_all_pairs(village)


def BF_benchmark():
    Time_brute_force = []

    k_list = []

    for k in range(1, 20):
        Time_brute_force.append(timeit(lambda: brute_force(village, list(village), k, village_distance_dict), number=1))
        k_list.append(k)

    #print N_list, time_list
    plt.xlabel('k')
    plt.ylabel('T')
    plt.plot(k_list, Time_brute_force, 'r^')
    plt.xticks(k_list)
    plt.show()

Aller plus loin : d'autres algorithmes

Nous nous intéressons maintenant à un algorithme glouton qui serait à la fois rapide et suffisamment intelligent pour produire des solutions qui ne soient pas très éloignées de la solution optimale.

Pour l'implémenter, on construit une liste de {$k$} maisons sélectionnées pour accueillir un four à pain. Au départ, cette liste est vide. A chaque étape, on ajoute à cette liste une nouvelle maison. La maison choisie est celle qui, en plus des maisons précédemment sélectionnées, minimise le coût d'accès sur l'ensemble du village.

Testez votre fonction avec le code suivant : comparez le résultat avec {$brute\_force$} sur {$village.map$} pour {$k=5$} ?

force_d, force_h = brute_force(village, list(village), 5, village_distance_dict)
greed_d, greed_h = greedy_algorithm(village, list(village), 5, village_distance_dict)  
assert greed_d >= force_d
assert brute_force(village, list(village), 1, village_distance_dict) == (14, {'CL5'})
assert brute_force(village, list(village), 5, village_distance_dict) == (2, {'CL4', 'CL7', 'CL6', 'CL5', 'CL2'})
print(greed_d, force_d)

def random_algorithm(map, candidates, k, distance_dict, trials=100) :
    ...

def BF_G_R_benchmark(max_k, random_trials = 100):

    # compare on lite
    time_bruteforce_lite = []
    time_random_lite = []
    time_greedy_lite = []


    d_bruteforce_lite = []
    d_random_lite = []
    d_greedy_lite = []


    k_list = []


    for k in range(2, max_k):
        k_list.append(k)


        time_bruteforce_lite.append(timeit(lambda: d_bruteforce_lite.append(brute_force(village, list(village), k, village_distance_dict)[0]), number=1))

        time_greedy_lite.append(timeit(lambda: d_greedy_lite.append(greedy_algorithm(village, list(village), k, village_distance_dict)[0]), number=1))
        time_random_lite.append(timeit(lambda: d_random_lite.append(random_algorithm(village, list(village), k, village_distance_dict, random_trials)[0]), number=1))


    plt.subplot(2, 1, 1)
    plt.xlabel('k')
    plt.ylabel('T')
    plt.xticks(k_list)
    plt.plot(k_list, time_bruteforce_lite, 'r*')
    plt.plot(k_list, time_greedy_lite, 'b*')
    plt.plot(k_list, time_random_lite, 'y*')

    plt.subplot(2, 1, 2)
    plt.xlabel('k')
    plt.ylabel('d')
    plt.xticks(k_list)
    plt.plot(k_list, d_bruteforce_lite, 'r-')
    plt.plot(k_list, d_greedy_lite, 'b-')
    plt.plot(k_list, d_random_lite, 'y-')
    plt.show()