Probleme – Le voyageur de commerce, ou la dynamique sur les sous-ensembles

1. Le sous-problème. Pour un sous-ensemble $S\subseteq \{1,\dots ,n-1\}$ et un sommet $k\in S$, on pose

$$D[S][k]=\text{couˆt minimal d’un chemin partant de }0,$$

$$\text{visitant exactement les sommets de }S,\text{et finissant en }k.$$

C'est le point décisif : l'ensemble visité fait partie de l'état. La récurrence devient alors immédiate — le chemin arrive en $k$ depuis un $m\in S\setminus \{k\}$ :

$$D[\{k\}][k]=c_{0k},D[S][k]=\underset{m\in S\setminus \{k\}}{\min }(D[S\setminus \{k\}][m]+c_{mk}),$$

et la réponse est ${\min }_k(D[\{1,\dots ,n-1\}][k]+c_{k0})$.

Pourquoi la sous-structure optimale est ici vraie alors qu'elle était fausse pour le plus long chemin simple : le sous-chemin de $0$ à $m$ visite exactement $S\setminus \{k\}$, et cette contrainte est inscrite dans le sous-problème. Rien n'est laissé à l'extérieur. On a acheté la sous-structure au prix de $2^{n-1}$ états.

2. Le programme. Un sous-ensemble de $\{0,\dots ,n-1\}$ se code par un entier dont le bit $k$ vaut $1$ si $k\in S$ :

/* Cout minimal d'un circuit passant par toutes les villes, depart et arrivee
   en 0. c[u][v] est le cout de u a v.
   Preconditions : 2 <= n <= 20, c[u][v] >= 0.
   Complexite : Theta(2^n * n^2) en temps, Theta(2^n * n) en memoire. */
int voyageur(int c[][N_MAX], int n) {
    assert(2 <= n && n <= 20);
    int taille = 1 << n;
    int (*d)[N_MAX] = malloc((size_t) taille * sizeof *d);   /* PAS sur la pile */
    if (d == NULL) { return -1; }
    for (int S = 0; S < taille; S = S + 1)
        for (int k = 0; k < n; k = k + 1) { d[S][k] = INT_MAX; }
    for (int k = 1; k < n; k = k + 1) { d[1 << k][k] = c[0][k]; }
    /* INVARIANT : quand on traite S, tous les d[T][.] avec T strictement
       inclus dans S sont definitifs -- vrai car T < S comme ENTIERS. */
    for (int S = 1; S < taille; S = S + 1) {
        for (int k = 1; k < n; k = k + 1) {
            if (!(S & (1 << k)) || d[S][k] == INT_MAX) { continue; }
            for (int j = 1; j < n; j = j + 1) {
                if (S & (1 << j)) { continue; }        /* j deja visite */
                int neuf = d[S][k] + c[k][j];
                if (neuf < d[S | (1 << j)][j]) { d[S | (1 << j)][j] = neuf; }
            }
        }
    }
    int tout = taille - 2, meilleur = INT_MAX;        /* toutes les villes sauf 0 */
    for (int k = 1; k < n; k = k + 1) {
        if (d[tout][k] != INT_MAX && d[tout][k] + c[k][0] < meilleur) {
            meilleur = d[tout][k] + c[k][0];
        }
    }
    free(d);                                          /* qui alloue documente qui libere */
    return meilleur;
}

L'ordre de remplissage est ici gratuit, et c'est la plus jolie idée du code : si $T⊊S$, alors l'entier $T$ est strictement plus petit que l'entier $S$ (on lui a retiré des bits). Une simple boucle croissante sur les entiers respecte donc l'ordre d'inclusion. Aucun tri, aucune boucle par cardinal.

Mesure sur quatre villes, avec la matrice

$$c=\left(\begin{array}{cccc}0& 10& 15& 20\\ 10& 0& 35& 25\\ 15& 35& 0& 30\\ 20& 25& 30& 0\end{array}\right):$$

la table rend $80$, et l'énumération des $3!=6$ circuits confirme $80$, réalisé par $0\to 1\to 3\to 2\to 0$.

3. Le gain. L'énumération examine $(n-1)!$ circuits (ou $(n-1)!/2$ si la matrice est symétrique), chacun coûtant $\Theta (n)$ à évaluer. La table examine $2^{n-1}(n-1)$ états, chacun en $\Theta (n)$ :

À $n=20$, le rapport entre les deux colonnes de droite vaut $6,08\cdot 10^{16}/4,19\cdot 10^8\approx 1,45\cdot 10^8$ : l'énumération demanderait des siècles, la table quelques secondes. La mémoire, en revanche, vaut $2^{20}\times 20\times 4$ octets, soit $84$ Mo — et c'est elle, et non le temps, qui arrête l'algorithme vers $n=25$.

4. Non, ce n'est pas polynomial, et il ne faut pas s'y tromper : $\Theta (2^n{n}^2)$ reste exponentiel. Le problème est np-difficile (chapitre chap:decidabilite) et personne ne connaît d'algorithme polynomial.

Ce que le problème enseigne malgré tout : la programmation dynamique ne rend pas facile ce qui est difficile. Elle transforme $\Theta (n!)$ en $\Theta (2^n{n}^2)$ — d'une exponentielle à une autre, mais infiniment plus praticable. Et elle le fait par le même geste que partout ailleurs dans ce chapitre : choisir un état qui rende les sous-problèmes indépendants, ici en y logeant l'ensemble déjà visité. C'est l'étape 2 de la méthode en cinq points, et c'est toujours la seule qui demande de l'invention.