Table des matières

Consignes importantes

• Téléchargez l'archive tp2.zip et dépaquetez-la.
• Toutes les réponses sont à fournir dans le fichier tp2.py de l'archive, et c'est le fichier unique que vous devrez remettre.
• Vous devez fournir vos réponses aux endroits indiqués dans le fichier tp2.py : ne modifiez rien d'autre.
• Les réponses à fournir sont de deux sortes :
  1. code manquant dans une fonction
  2. explications textuelles, insérées dans une chaîne de caractères
• Vos réponses de type "code" peuvent être testées par la commande suivante :

python grader.py -q qn où {$n$} est le numéro de la question à tester. Les réponses textuelles peuvent aussi être testées, mais le résultat du test sera systématiquement 0. L'évaluation réelle sera faite lors de la correction.

• Ne changez pas les signatures des fonctions demandées (noms des fonctions, paramètres des fonctions...): sinon vous risquez de perdre des points.
• N'ajoutez aucun block de code supplémentaire
• N'ajoutez pas de packages supplémentaires
• Vous devez soumettre votre fichier sur Edunao dans le groupe de votre voie. Avant d'envoyer votre travail, vérifiez que la commande suivante s'exécute sans erreur :

python grader.py --all --no-graphics

• Votre travail sera évalué en propre et par rapport à votre groupe.

Merci de respecter toutes ces consignes, sinon votre rendu ne sera pas évalué.

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, comme 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 du 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 quand tous les poids sont positifs. L'algorithme de Bellman-Ford peut fonctionner pour les poids négatifs et permet 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 un 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 résoudre ce problème 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 dans les descentes, tandis que nous consommons de l'énergie dans 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 sa descente inverse.

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 utilisée pour la frontière (liste ou tas binaire). Vous trouverez ci-dessous les implémentations SP_naive et SP_heap avec les structures de données respectives que sont la liste et le tas pour réaliser la file de priorité.

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

def q1():
    return '''
    Insérer votre réponse
    '''

def q2():
    return '''
    Insérer votre réponse
    '''

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 de la fonction 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()

Exécutez la fonction benchmark avec la question 3 et expliquez les résultats en répondant aux questions 3 à 5 ci-dessous.

def q3():
    benchmark()
    return '''
    Insérer votre réponse
    '''

def q4():
    return '''
    Insérer votre réponse
    '''

def q5():
    return '''
    Insérer votre réponse
    '''

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 qui n'a 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 SP 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.

Etant donné un graphe {$G=(V, E)$} avec une fonction de poids {$w$}, on construit un nouveau graphe {$G'=(V', E')$} avec la fonction de poids {$w'$} telle que

-{$V'=V\cup\{s\}$}, et {$s\notin V$}

-{$E'=E\cup\{(s, v) : v\in V\}$}

-{$w'(v, v')=0$} lorsque {$v=s$}, {$w'(v, v')=w(v, v')$} sinon.

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 l'instruction suivante :  

python grader.py -q q6

  La fonction est testée à l'aide sur les données suivantes :  

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

src="source"

sim_graph_src=add_source(sim_graph, src)

assert sim_graph_src == {"A":{"B":4,"C":2,"D":3},
                         "B":{"A":6,"C":-5},
                         "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.  

python grader.py -q q7

  La fonction est testée sur les données suivantes :  

opt_distance=bellman_ford(sim_graph_src, src)

assert opt_distance=={'A': 0, 'B': 0, 'C': -5, 'D': -4, '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 l'instruction suivante :  

python grader.py -q q8

  La fonction est testée sur les données suivantes :  

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

nonneg_graph=rewrite_weights(sim_graph, opt_distance)

assert nonneg_graph=={'A': {'B': 4, 'C': 7, 'D': 7}, 'B': {'A': 6, 'C': 0}, 'C': {'D': 0}, 'D': {}}

  Il y a deux propriétés importantes avec cette réécriture des poids. Répondez aux deux questions suivantes:  

def q9():
    return '''
    Insérer votre réponse
    '''

def q10():
    return '''
    Insérer votre réponse
    '''

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 l'instruction suivante :

python grader.py -q q11

La fonction est testée sur les données ci-dessous :

nonneg_graph={'A': {'B': 4, 'C': 7, 'D': 7}, 'B': {'A': 6, 'C': 0}, 'C': {'D': 0}, 'D': {}}


assert all_distances(nonneg_graph)=={('A', 'A'): 0, ('A', 'B'): 4, ('A', 'C'): 4, ('A', 'D'): 4, 
                                     ('B', 'A'): 6, ('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}

def BF_SP_all_pairs(graph, src="source"):

  ############### TODO : complete code ##################
  d = {(u,v):None for u in graph for v in graph}

  # Return a dictionary of distances for all pairs of nodes

  return d

Testez votre fonction avec l'instruction suivante :

python grader.py -q q12

La fonction est testée sur les données ci-dessous :

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

def q13():
  return '''
  Insérer votre réponse
  '''

Application : 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 sont 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

Le code suivant permet de charger une carte à partir d'un fichier :

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

L'exemple jouet fourni ci-dessous (le dictionnaire toy_village) sera utilisé dans les fonctions de test pour la suite :

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 14). Pour un ensemble de maisons données, le coût d'accès est le coût maximum de cet ensemble (voir Question 15).

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):
    ############### TODO : complete code ##################

Testez votre fonction avec l'instruction suivante :

python grader.py -q q14

La fonction est testée sur les données ci-dessous :

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):
    ############### TODO : complete code ##################

Testez votre fonction à l'aide de l'instruction suivante :

python grader.py -q q15

La fonction est testée sur les données ci-dessous :

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

Le code suivant s'exécute en utilisant la carte d'un village de 20 maisons que vous avez dépaquetée avec l'archive du TP (également disponible ici). Ensuite, attachez-vous à comprendre la fonction {$brute\_force$}. Qu'observez-vous comme résultat de {$BF\_benchmark$} ? Expliquez-le.

def brute_force(map, candidates, k, distance_dict) :
    best_combi = []
    best_dist = math.inf
    for combi in itertools.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)

def BF_benchmark():

    village = read_map('village.map')

    village_distance_dict = BF_SP_all_pairs(village)

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


    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()

def q16():
    BF_benchmark()
    return'''
    Insérer votre explication.
    '''

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.

def greedy_algorithm(map, candidates, k, distance_dict):

    ############### TODO : complete code ##################
    return best_d, set() 

Testez votre fonction avec l'instruction suivante :

python grader.py -q q17

Comparez le résultat avec {$brute\_force$} sur {$village.map$} pour {$k=5$} ? La fonction est testée de la manière suivante :  

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)

Le prochain algorithme que nous concevons est un algorithme de sélection aléatoire de {$k$} maisons parmi les maisons candidates. Cet algorithme essaie aléatoirement un certain nombre de combinaisons de {$k$} maisons candidates et conserve la meilleure solution parmi ces combinaisons.

def random_algorithm(map, candidates, k, distance_dict, trials=100) :
    ############### TODO : complete code ##################

Vous allez maintenant exécuter le benchmark suivant pour toutes les valeurs de k sur le village {$village.map$} en termes de temps d'exécution et de qualité de la solution.

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()

def q19():
    BF_G_R_benchmark()
    return '''
    Insérer vos conclusions.
    '''