Étude

Le problème que nous voulons résoudre est la création d'un réseau ferré. On reprend les notations utilisées lors de la partie consacrée à la programmation dynamique :

Dans la partie programmation dynamique on s'intéressait à un réseau déjà créé, ici, on va le construire.

Par exemple les 5 villes ci-dessous :

Aucun tronçon n'a été construit et on ne peut voyager de ville en ville.

Dans la figure ci-dessous un réseau ferré a été construit. À gauche toutes les tronçons possibles ont été construites, ce qui est pratique si ont veut voyager vite entre deux villes mais c'est beaucoup trop cher (et dangereux, regardez le nombre de croisements !). À droite seul le nombre minimum de tronçons entre villes voisines pour pouvoir aller de n'importe quelle ville à n'importe quelle autre ville en suivant le réseau ferré ont été construites.

Nuages de points

Nous allons dans les exemples qui suivent utiliser le même jeu de données. Nous avons généré en python 100 points en deux dimensions dont les abscisses et ordonnées sont entre 0 et 1.

import random

villes = dict()

for nom in range(100):
    villes[str(nom)] = (random.random(), random.random())

return villes

import matplotlib.pyplot as plt

TAILLE = 10

x = []
y = []
label = []
for nom, (long, lat) in villes.items():
    x.append(long)
    y.append(lat)

    label.append(nom)

height = max(y) - min(y)
width = max(x) - min(x)

fig, ax = plt.subplots(figsize=(TAILLE, TAILLE * height / width))
ax.set_title("Les villes")

ax.scatter(x, y)
for i in range(len(x)):
    ax.text(x[i], y[i], label[i])

for x, y in segments:
    ax.plot(
        [villes[x][0], villes[y][0]],
        [villes[x][1], villes[y][1]],
        color=mcolors.CSS4_COLORS["brown"],
    )
plt.show()

Pour ce qui va suivre, une hypothèse souvent utilisée est :

Ce n'est pas une contrainte forte puisque la probabilité que ça arrive est nulle (si on tire au hasard des coordonnées réelles aux points), et – même si ça arrivait – il suffirait de déplacer un des trois points d'epsilon pour que ça n'arrive plus.

La raison fondamentale de cette hypothèse est que :

Ceci va simplifier nombre de preuves de ce qui va suivre.

Connexité

Le but final est d'obtenir un réseau ferré où l'on puisse librement aller d'une ville à l'autre. Formalisons ceci en commençant par étudier des réseaux ferrés déjà constitués

On reprend la relation $C$ du deuxième exemple de la partie consacrée à la programmation dynamique :

Le fait que la relation chemin soit une relation d'équivalence montre que le réseau ferré est connexe si et seulement si cette relation n'admet qu'une seule classe d'équivalence ($C(x) = C(y)$ quelques soient les villes $x$ et $y$).

Si un réseau ferré n'est pas connexe, les classes d'équivalences de la relation chemin donnent les composantes connexes du réseau ferré. Le réseau ferré de la figure suivante contient 2 composantes connexes :

Notez que :

Par exemple, en ajoutant le tronçon entre B et P, on obtient un réseau ferré connexe :

La propriété ci-dessus nous permet de créer un algorithme glouton permettant de trouver toutes les parties connexes d'un réseau ferré uniquement à partir de sa relation tronçon.

Algorithme composante connexe :

pour chaque ville v : R(v) = v
pour chaque tronçon (x, y):
    si R(x) ≠ R(y):
        pour chaque gare z telle que R(z) = R(y):
            R(z) = R(x)

pour chaque ville u:
    si R(u) == R(x) alors:
        R(u) = R(y)

à_changer = R(x)
pour chaque ville u:
    si R(u) == à_changer alors:
        R(u) = R(y)

Cet algorithme fonctionne grâce à la marque R qui définit le représentant de chaque ville. Montrons ça sur un exemple en reprenant le réseau ci-après et en affectant une couleur à chaque ville comme représentant :

Et en étudiant les tronçons dans l'ordre $(L, S)$, $(B, M)$, $(P, S)$ et enfin $(L, P)$ on obtient :

Notez que l'étude du tronçon $(L, P)$ ne produit aucun changement dans les représentants car la couleur de $L$ est déjà égale à la couleur de $P$.

Création du réseau ferré

On peut maintenant reformuler notre problème d'optimisation :

L'analyse préliminaire précédente nous permet d'aborder sereinement ce problème d'optimisation. On peut utiliser l'algorithme "composante connexe" en choisissant l'ordre dans lequel examiner les tronçons.

Cet ordre semble évident puisque l'on veut minimiser le coût : on examine les tronçons par coût croissant.

Commençons par écrire cet algorithme, initialement proposé par Kruskal :

pour chaque ville v : R(v) = v
pour chaque tronçon (x, y) examiné par distance croissante:
    si R(x) ≠ R(y):
        on ajoute (x, y) aux tronçons choisis
        pour chaque ville z telle que R(z) = R(y):
            R(z) = R(x)

L'étude précédente nous indique d'ores et déjà que :

1. on choisira exactement $n-1$ tronçons
2. le reseau ferré formé des tronçons choisies sera connexe

Pour nos 100 villes, on trouve :

import matplotlib.pyplot as plt
import matplotlib.colors as mcolors

TAILLE = 10

x = []
y = []
label = []
for nom, (long, lat) in villes.items():
    x.append(long)
    y.append(lat)

    label.append(nom)

height = max(y) - min(y)
width = max(x) - min(x)

fig, ax = plt.subplots(figsize=(TAILLE, TAILLE * height / width))
ax.set_title("Les villes")

ax.scatter(x, y)
for i in range(len(x)):
    ax.text(x[i], y[i], label[i])

for x, y in tronçons:
    ax.plot(
        [villes[x][0], villes[y][0]],
        [villes[x][1], villes[y][1]],
        color=mcolors.CSS4_COLORS["brown"],
    )
plt.show()

Avant de montrer que l'algorithme de Kruskal est optimal, commençons par montrer une propriété intéressante de ce réseau :

Montrons que l'algorithme est bien optimal :

Le réseau obtenu par l'algorithme de Kruskal est optimal ! Il a alors la propriété de ne pas contenir de croisements (de segments qui s'intersectent).

Chemins entre villes

Le réseau de coût de construction minimal est connexe et ne contient pas de cycle. Il n'existe donc pour chaque couple de villes qu'un unique chemin.

L'algorithme que l'on va créer dans les exercices suivants et qui permet soit de visiter toutes les villes soit de trouver un chemin entre deux villes est connu sous le nom de parcours en profondeur. Il est très efficace et utilisé dans de nombreuses occasions.

fonction tronçons_rec(précédente, courante):
    affiche à l'écran : courante
    pour chaque tronçon (u, v) du réseau ferré:
        si u == courante et v != précédente:
                tronçons_rec(u, v)

En utilisant le réseau exemple, et en partant de 0, on peut par exemple parcourir (et afficher) les villes dans l'ordre suivant :

[ '0', '28', '93', '31', '88', '68', '20', '30', '43', '61', '36', '18',
  '3', '52', '14',  '5', '80', '66', '85', '87', '25', '60', '90', '16',
  '4', '97', '15', '11', '81', '78', '82', '47', '73', '48', '58', '44',
 '72', '22', '63',  '8', '53', '27', '89', '76', '74', '56', '35', '37',
 '62', '34', '67', '13', '75', '19', '69',  '9', '45', '57', '41', '59',
  '6', '84', '77', '10', '38', '83', '32', '29', '39', '17', '40', '26',
 '71', '49', '23',  '1', '95', '12', '64', '33', '70', '96', '24',  '7',
 '98', '46', '42', '21',  '2', '94', '55', '54', '65', '79', '99', '51',
 '91', '92', '86', '50']

fonction tronçons_rec(précédente, courante, chemin):
    ajoute courante à la fin du chemin
    pour chaque tronçon (u, v) du réseau ferré:
        si u == courante et v != précédente:
                tronçons_rec(u, v, chemin)

chemin = []
tronçons_rec(1, 1, chemin)
affiche à l'écran : chemin

[1, 2, 3, 4, 5, 6]

fonction tronçons_rec(précédente, courante, destination, chemin):
    si courante == destination:
        ajoute courante à la fin de chemin
        retour
    pour chaque tronçon (u, v) du réseau ferré:
        si u == courante et v != précédente:
                tronçons_rec(u, v, destination, chemin)
                si chemin est non vide:
                    ajoute courante à la fin de chemin
                    retour

chemin = []
tronçons_rec(1, 1, 4, chemin)
affiche à l'écran : chemin

[4, 2, 1]

On affiche le chemin entre les villes 0 et 1 de l'exemple :

Cycles

Le réseau ferré de coût de construction minimum est parfait pour relier les villes à moindre coût. En revanche, il n'est pas robuste aux pannes ou aux blocages. Un seul tronçon de bloqué et le réseau n'est plus connexe.

L'idée est alors de chercher un cycle reliant toutes les villes. Pour tout couple de ville, il existe alors deux chemins disjoints permettant de les relier.

Ce problème est cependant souvent vu sous un autre angle, celui d'un voyageur de commerce voulant visiter toutes les villes :

Sous la forme d'un problème d'optimisation on cherche, pour un ensemble de villes $V$ donné, un cycle $v_1 v_2\dots v_1$ passant par toutes les villes 1 fois minimisant la quantité :

$$ \sum_{i=1}^nd(v_i, v_{i+1}) + d(v_n, v_1) $$

Algorithme optimal

Générer tous les cycles prend énormément de temps.

On va de plus considérer des cycles objectivement mauvais car ayant des croisements. Par exemple tous les cycles ayant comme chemin $[\dots, 50, 64, 34, 65, \dots]$ (les 4 coins de la carte) seront plus mauvais que les mêmes cycles ayant $[\dots, 50, 34, 64, 65, \dots]$ :

Cette constatation nous incite à utiliser le principe de la programmation dynamique pour résoudre notre problème. Le principe de création d'algorithmes utilisant la programmation dynamique est toujours le même : on essaie de créer des solutions optimales avec des solutions partielles elles-même optimales. Ceci se concrétise souvent par une équation récurrente à vérifier.

Dans le cas de notre problème du voyageur de commerce à $n$ villes $(v_i)_{1\leq i \leq n}$, on peut construire un algorithme de programmation dynamique en remarquant que :

L'équation ci-dessous nous donne un moyen de construire itérativement des chemins minimaux jusqu'à arriver au calcul final :

Qui est le coût minimal du voyageur de commerce.

    pour chaque I de E:
        pour chaque l de [1..n] qui n'est pas dans I:
            pour chaque j de [1..n] qui n'est pas dans I et qui n'est pas l:
                m = C(I, l) + c(v_l, v_j)
                si C(I + {l}, j) n'existe pas:
                    C(I + {l}, j) = m
                sinon:
                    C(I + {l}, j) = min(C(I + {l}, j), m)

Cette complexité est importante, mais tout de même plus petite que l'énumération de tous les cycles ($2^n$ est très petit devant $n!$) puisque l'on ne garde qu'une solution pour un sous-ensemble donné et pas tous les cycles possibles.

Algorithme glouton

Le nombre astronomique de solutions possibles nous empêche de toutes les essayer. De plus, on peut montrer (nous ne le ferons pas ici) qu'il est illusoire de trouver une solution exacte (du moins pendant une séance de code) car le problème du voyageur de commerce est NP-complet (plus précisément NP-difficile, mais ne chipotons pas).

Couramment, l'algorithme glouton utilisé pour approximer ce problème est :

1. choisir une ville de départ qui constitue le départ du cycle
2. tant que toutes les villes n'ont pas été ajoutée au cycle : on ajoute la ville la plus proche du dernier élément de celui-ci.

Pour notre exemple, on trouve, en partant de la ville $0$ (la dernière ville traversée est la $17$):

On obtient, pour K =1, un coût de construction de : 10.475838825929351

On voit bien que l'algorithme n'est pas vraiment optimal...

Optimisation

La représentation graphique de la solution montre de nombreux croisements, ce qui prouve que notre solution est bien améliorable :

C'est l'idée sous-jacente de la méthode d'optimisation 2-opt :

1. trouver un cycle potentiel
2. chercher un croisement et le supprimer
3. retour en 2

On peut itérativement chercher les croisements jusqu'à leurs disparitions complète, ou prendre un certain nombre de couples de segments et le décroiser si nécessaire. C'est cette dernière façon de faire qui est privilégiée pour de grands cycles.

Par exemple ci-dessous, on a décroisé les segment $(0, 17)$ et $(37, 50)$ :

Notre cycle étant très petit, on peut se permettre de faire tous les cas. La figure suivante montre le résultat de 100 itérations de tous les cas possibles (on exécute 100 fois un test de tous les décroisements possibles) :

On obtient, pour K =1, un coût de construction de : 8.606090557637186

C'est bien mieux, et il n'y a plus de croisements.

Algorithmes à performances garanties

L'algorithme glouton précédant ainsi que son optimisation ne garantissent rien sur la solution. Il existe cependant des algorithmes heuristiques dont on peut garantir la performance.

On peut commencer par donner une borne min du coût du voyageur de commerce :

Du réseau au cycle

L'idée est de reprendre le réseau optimal et de le parcourir entièrement en suivant ses tronçons. Par exemple, en considérant le réseau ci-dessous :

On peut le parcourir en suivant ses tronçons de cette façon par exemple :

Ce qui donne le cycle :

$$ [1, 2, 3, 2, 4, 2, 1, 5, 1, 6] $$

Il parcours 2 fois le réseau son coût est donc de deux fois le coût du réseau connexe optimal.

En supprimant les sommets déjà parcourus, on obtient le cycle :

$$ [1, 2, 3, 4, 5, 6] $$

Remarquez que c'est l'algorithme du parcours en profondeur qui ajoute dans chemin toutes les villes parcouru permet de trouver ce cycle.

Le coût de ce parcours est plus faible que le parcours précédent (on a une distance, donc elle respecte l'inégalité triangulaire). On en conclut que :

Le parcours donne, sur nos 100 villes :

On obtient, pour K =1, un coût de construction de : 10.608836994373258

Ce qui après optimisation (100 passes) devient :

On obtient, pour K =1, un coût de construction de : 8.596669623756684

Algorithme de Christofides

L'algorithme de Christofides est une amélioration de l'algorithme précédent. On peut montrer qu'il est au pire 1.5 fos plus mauvais que le cycle optimal.

C'est de plus la meilleure approximation connue. Son étude nécessite cependant des connaissance en théorie des graphes que nous n'avons (pour l'instant) pas.

Autre parcours

cycle bitonique exo 9 https://wkerl.me/cours/ouv_td.pdf