Pré requis

• Complexité : lien
• Récursivité : lien

On verra dans cette page:

• la programmation dynamique
• les algorithmes gloutons
• un exemple d’algorithme avec recherche locale. Pour la résolution d’un problème de TSP (Traveling salesman problem)
• Les classes de problèmes de decision, P, NP, NP-complet

Programmation dynamique

Principe de la méthode

La programmation dynamique permet de résoudre plus efficacement des problèmes d’optimisation.

La programmation dynamique consiste à résoudre un problème en le décomposant en sous-problèmes, puis à résoudre les sous-problèmes, des plus petits aux plus grands en stockant les résultats intermédiaires, et en suivant une règle d’optimalité. La solution donnée par un algorithme glouton est optimale, mais n’est pas forcement la solution la plus optimale au problème.

Cela diffère des algorithmes de type diviser pour régner par le fait que les sous-problèmes considérés ne sont pas nécessairement indépendants. Pour les algorithmes de type diviser pour régner, on partitionne le problème en sous problèmes indépendants, qui seront résolus recursivement. Puis on combine leurs solutions pour résoudre le problème initial. Mais cela peut revenir à résoudre plusieurs fois le même sous-problème, et peut être parfois inefficace.

Pour la méthode de programmation dynamique, on va se rappeler des sous-problèmes résolus (de leurs solutions), et eviter de les re-calculer.

Cette méthode a été introduite au début des années 1950 par Richard Bellman.

Comment s’y prendre pour mémoriser les solutions?

La méthode demande alors de mémoriser ce résultat intermédiaire dans un dictionnaire ou un tableau afin de le réutiliser au besoin. Sans avoir besoin de les recalculer. La complexité spatiale augmente, mais celle temporelle diminue.

Cette méthode s’appelle : la mémoïzation.

Elle va permettre d’eviter la répétition des calculs que l’on voit dans l’exemple suivant, le triangle de Pascal. Sans cette reduction, la compléxité de l’algorithme est exponentielle (voir l’arbre des calculs, présenté plus bas).

Ce problème de répétitions a été vu avec l’exemple du calcul des termes de la suite de Fibonacci.

Limites de la méthode diviser pour regner : le triangle de Pascal

Principe

En mathématiques, le triangle de Pascal est une présentation des coefficients binomiaux dans un triangle. Il fut nommé ainsi en l’honneur du mathématicien français Blaise Pascal. Il est connu sous l’appellation « triangle de Pascal » en Occident, bien qu’il fût étudié par d’autres mathématiciens, parfois plusieurs siècles avant lui.

$$\begin{matrix}\begin{align}n=2, (x+y)^2 & = x^2+2xy+y^2\\n=3, (x+y)^3 & = x^3+3x^2y+3xy^2+y^3\\n=4, (x+y)^4 & = x^4+4x^3y+6x^2y^2+4xy^3+y^4\end{align}\end{matrix}$$

voir compléments sur la page wikipedia : Lien

Un coefficient quelconque du triangle, situé à la ligne i et à la colonne j est calculé à partir de la formule de récurrence : (i et j superieurs à 1)

$$C\left(\begin{matrix}i\\j\end{matrix}\right)=C\left(\begin{matrix}i-1\\j-1\end{matrix}\right)+C\left(\begin{matrix}i-1\\j\end{matrix}\right)$$

Algorithme récursif non optimisé

Les algorithmes de type diviser pour regner sont souvent exprimés de manière recursive.

def pascal_recur(n,p):
    # calcul d'un coefficient par recursivité
    if p==0:return 1
    if p>n:
        return 0
    else:
        return pascal_recur(n-1,p) + pascal_recur(n-1,p-1)

def pascal(n):
    T = [[0] * (n+1) for p in range(n+1)]
    for n in range(n+1):
        for k in range(n+1):
            T[n][k] = pascal_recur(n,k)
    return T

On peut alors tester le programme:

> pascal(9)

[[1, 0, 0, 0, 0, 0, 0, 0, 0, 0],
 [1, 1, 0, 0, 0, 0, 0, 0, 0, 0],
 [1, 2, 1, 0, 0, 0, 0, 0, 0, 0],
 [1, 3, 3, 1, 0, 0, 0, 0, 0, 0],
 [1, 4, 6, 4, 1, 0, 0, 0, 0, 0],
 [1, 5, 10, 10, 5, 1, 0, 0, 0, 0],
 [1, 6, 15, 20, 15, 6, 1, 0, 0, 0],
 [1, 7, 21, 35, 35, 21, 7, 1, 0, 0],
 [1, 8, 28, 56, 70, 56, 28, 8, 1, 0],
 [1, 9, 36, 84, 126, 126, 84, 36, 9, 1]]

On remarque que l’on calcule souvent les mêmes coefficients binomiaux :

On voit que certains termes, comme celui (n=2, p=1) est calculé plusieurs fois. Dans les branches (n=3, p=1) et (n=3, p=2). Cela est du au fait que les 2 branches de l’arbre sont indépendantes.

La mémoïzation consistera alors à stocker dans un tableau les solutions pour les sous-problèmes afin de ne pas les recalculer…

Algorithme avec mémoïzation

Chaque valeur du triangle n’est calculée qu’une seule fois.

def trianglePascal(n):
    T = [[0] * (n+1) for p in range(n+1)]
    for n in range(n+1):
        for k in range(n+1):
            if k == 0:
                T[n][0] = 1
            else:
                T[n][k] = T[n-1][k-1] + T[n-1][k]
    return T

L’algorithme non recursif, avec mémoïzation est plus efficace.

Problèmes de décision et algorithmes gloutons

Le problème du rendu de monnaie

Le problème du rendu de monnaie est un problème d’algorithmique. Il s’énonce de la façon suivante : étant donné un système de monnaie (pièces et billets), comment rendre une somme donnée de façon optimale, c’est-à-dire avec le nombre minimal de pièces et billets ?

Par exemple, la meilleure façon de rendre 7 euros est de rendre un billet de cinq et une pièce de deux, même si d’autres façons existent (rendre 7 pièces de un euro, par exemple).

algorithme naif

Ce problème est traité d’une manière différente de ce que l’on a vu en 1ere NSI. Supposons que l’on dispose d’une fonction recursive, qui pour chaque piece de la caisse fait le choix suivant:

• soit la piece est inférieure à la monnaie à rendre: alors on soustrait la piece à la somme à rendre et on appelle la fonction de manière récursive avec cette même caisse, et la nouvelle somme à rendre.
• soit la piece est supérieure à la somme à rendre. on retire la piece de la caisse. Et on appelle de manière récursive la fonction avec la nouvelle caisse, et la même somme.

La condition de base sera: la liste de pieces est vide.

On utilisera une liste rendu pour placer les pieces rendues.

def rendre_monnaie(somme,pieces,rendu):
    if pieces == []:
        return rendu
    if pieces[-1]<=somme:
        rendu.append(pieces[-1])
        return rendre_monnaie(somme-pieces[-1],pieces,rendu)
    else:
        pieces.pop()
        return rendre_monnaie(somme,pieces,rendu)

rendre_monnaie(49,[1,2,5,10,20,50,100],[])
# affiche 
# [20, 20, 5, 2, 2]

Un système monétaire non canonique:

1. Que renvoie la fonction pour rendre 53 pences avec le système imperial où pieces = [240,60,30,24,12,6,3,1] ?
2. Le rendu est-il optimal avec cette méthode? Ou bien existe t-il une autre façon de rendre la monnaie, avec moins de pieces?

3. Représenter une partie de l’arbre des combinaisons possibles pour rendre un montant égal à 15, en choisissant une à une chaque piece de la caisse [1, 7, 9]. Quel est le choix optimal?

Voir l’animation sur le site mpechaud.fr

Sur l’animation, l’algorithme traite TOUTES les combinaisons de rendu de monnaie. L’arbre des appels recursifs montre que la complexité de cette méthode croit exponentiellement avec la taille des paramètres d’entrée.

Contrairement aux problèmes étudiés précédement (tri d’un tableau, calcul de xn…), où il y avait toujours une unique solution, dans les problèmes d’optimisation, il peut y avoir des solutions valides (satisfaisant les contraintes) non optimales, une ou plusieurs solutions (valides), optimales (minimisant/maximisant une certaine mesure), voire pas du tout de solution valide.

Si la taille du ou des paramètres en entrée est importante, il n’y a pas d’algorithme déterministe efficace. (on ne peut pas trouver LA solution au problème en parcourant toutes les solutions possibles car la complexité est trop grande). Voir paragraphe suivant sur la recherche exhaustive.

On utilise alors d’autres stratégies, qui donneront parfois une solution, parfois une solution optimale. C’est ce que l’on réalise avec l’utilisation d’un algorithme glouton.

Le problème du rendu de monnaie est NP-difficile relativement au nombre de pièce et billet du système monétaire considéré. (voir annexe).

Algorithme exhaustif

Une autre méthode pourrait être d’envisager TOUTES les combinaisons. On pourrait alors imaginer que l’on commence par rendre la monnaie avec une des pieces de la caisse (pas forcément la plus haute), puis on choisit une autre piece possible (egale ou moins haute), … Jusqu’à ce que la somme à rendre soit nulle. On envisage ainsi toutes les combinaisons possibles, ce qui, avec une valeur élevée de la somme à rendre, et un grand nombre de pieces dans la caisse, va donner un très grand nombre de combinaisons. On selectionne enfin la meilleure des solutions (celle optimale).

Par exemple, pour rendre 7 euros, voici toutes les combinaisons possibles (la solution optimale étant la première):

• 5 + 2
• 5 + 1 + 1
• 2 + 2 + 2 + 1
• 2 + 2 + 1 + 1 + 1
• 2 + 1 + 1 + 1 + 1 + 1
• 1 + 1 + 1 + 1 + 1 + 1 + 1

Un programme python exprimerait le rendu sous forme de liste:

> rendu(7,[5,2,1])
# 6 solutions
[[5, 2],
 [5, 1, 1],
 [2, 2, 2, 1],
 [2, 2, 1, 1, 1],
 [2, 1, 1, 1, 1, 1],
 [1, 1, 1, 1, 1, 1, 1]]
> rendu(14,[10,5,2,1])
# 19 solutions
[[10, 2, 2],
 [10, 2, 1, 1],
 [10, 1, 1, 1, 1],
 [5, 5, 2, 2],
 [5, 5, 2, 1, 1],
 [5, 5, 1, 1, 1, 1],
 [5, 2, 2, 2, 2, 1],
 [5, 2, 2, 2, 1, 1, 1],
 [5, 2, 2, 1, 1, 1, 1, 1],
 [5, 2, 1, 1, 1, 1, 1, 1, 1],
 [5, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [2, 2, 2, 2, 2, 2, 2],
 [2, 2, 2, 2, 2, 2, 1, 1],
 [2, 2, 2, 2, 2, 1, 1, 1, 1],
 [2, 2, 2, 2, 1, 1, 1, 1, 1, 1],
 [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1],
 [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]
rendu(21,[20,10,5,2,1])
# 44 solutions
[[20, 1],
 [10, 10, 1],
 [10, 5, 5, 1],
 [10, 5, 2, 2, 2],
 [10, 5, 2, 2, 1, 1],
 [10, 5, 2, 1, 1, 1, 1],
 [10, 5, 1, 1, 1, 1, 1, 1],
 [10, 2, 2, 2, 2, 2, 1],
 [10, 2, 2, 2, 2, 1, 1, 1],
 [10, 2, 2, 2, 1, 1, 1, 1, 1],
 [10, 2, 2, 1, 1, 1, 1, 1, 1, 1],
 [10, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [10, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [5, 5, 5, 5, 1],
 [5, 5, 5, 2, 2, 2],
 [5, 5, 5, 2, 2, 1, 1],
 [5, 5, 5, 2, 1, 1, 1, 1],
 [5, 5, 5, 1, 1, 1, 1, 1, 1],
 [5, 5, 2, 2, 2, 2, 2, 1],
 [5, 5, 2, 2, 2, 2, 1, 1, 1],
 [5, 5, 2, 2, 2, 1, 1, 1, 1, 1],
 [5, 5, 2, 2, 1, 1, 1, 1, 1, 1, 1],
 [5, 5, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [5, 5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [5, 2, 2, 2, 2, 2, 2, 2, 2],
 [5, 2, 2, 2, 2, 2, 2, 2, 1, 1],
 [5, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1],
 [5, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1],
 [5, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1],
 [5, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [5, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [5, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [5, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [2, 2, 2, 2, 2, 2, 2, 2, 2, 2, 1],
 [2, 2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1],
 [2, 2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1],
 [2, 2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1],
 [2, 2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [2, 2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [2, 2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [2, 2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [2, 2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [2, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1],
 [1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]]

algorithme de type glouton

On cherche à créer une liste de rendu de monnaie pour chaque montant de 0 à x. On aura une approche ASCENDANTE: on commence par déterminer la manière de rendre la somme la plus petite somme à rendre, puis une somme juste supérieure, etc… Chaque fois, la somme rendu le sera de manière optimale.

Pour rendre x, il faut au moins une pièce, à prendre parmi n pieces possibles. Une fois choisie cette pièce, la somme restante inférieure strictement à x, donc on sait la rendre de façon optimale. Il suffit donc d’essayer les n possibilités. Et de faire un choix parmi les solutions trouvées: celle qui rend le moins de pieces.

Exemple: Rendre 15 avec des pieces de {1, 7, 9}. Ce type de caisse ne donnerait pas le résultat optimum avec le précédent algorithme. Ici, cela peut-être réalisé avec un algorithme glouton, comme le montre le tableau ci-dessous:

L’algorithme remplit le tableau depuis la valeur 1 jusqu’à 15.

Le tableau montre les choix que réalise l’algorithme.

Comment cet algorithme parvient-il à reduire le nombre de combinaisons pour rendre la monnaie?

Remarques:

• Ce problème est NP-complet dans le cas général, c’est-à-dire difficile à résoudre. Cependant pour certains systèmes de monnaie dits canoniques, l'algorithme glouton est optimal.
• Regarder aussi: le probleme de l’allocation des ressources pour un systeme d’exploitation: l’algorithme du banquier

Le problème du sac à dos

Un problème très similaire est celui du sac-à-dos. Supposons que vous découvriez la caverne d’Ali Baba (et des 40 voleurs), il y a une infinité d’objets de valeur v1, v2, · · · , vn mais chaque objet de valeur vi a un poids de pi. Comment remplir votre sac-à-dos avec le contenu qui rapportera le plus, sachant que votre sac ne supporte qu’un poids W?

Voir l’article et l’animation sur Interstices

Algorithme de type glouton

Nous allons chercher à adapter l’algorithme du rendu de monnaie:

Structure de données:

Algorithme:

Question:

Déterminer le choix idéal pour un sac à dos de capacité 32kg, avec les objets suivants, proposés en nombre infini: `[{“valeur”: 7, “poids”:13},{“valeur”: 4, “poids”:11},{“valeur”: 3.1, “poids”:9},{“valeur”: 1, “poids”:3.5}]

Le problème du voyageur du commerce

énoncé du problème

le problème du voyageur de commerce, est un problème d’optimisation qui, étant donné une liste de villes, et des distances entre toutes les paires de villes, détermine un plus court circuit qui visite chaque ville une et une seule fois.

Malgré la simplicité de son énoncé, il s’agit d’un problème d’optimisation pour lequel on ne connait pas d’algorithme permettant de trouver une solution exacte rapidement dans tous les cas. Plus précisément, on ne connait pas d’algorithme en temps polynomial, et sa version décisionnelle (pour une distance D, existe-t-il un chemin plus court que D passant par toutes les villes et qui termine dans la ville de départ ?) est un problème NP-complet. Voir annexe pour précisions.

Pour résoudre ce problème, une heuristique gloutonne construit une seule solution, par une suite de décisions définitives sans retour arrière, parmi ces méthodes on cite le plus proche voisin, la plus proche insertion, la plus lointaine insertion et la meilleure insertion. Il n’est pas certain que la méthode donne la meilleure solution.

La figure suivante aide à la resolution. La solution optimale est celle qui va joindre tous les noeuds du graphe, une seule fois. (Cycle hamiltonien) Des solutions possibles, mais non optimales sont celles qui permettent de visiter tous les noeuds une seule fois, mais dont la distance parcourue cumulée n’est peut-être pas la plus courte.

Exemple

Un voyageur cherche un itinéraire passant par toutes les villes du tableau, et qui minimise la distance totale parcourue. Les villes peuvent être visitées dans n’importe quel ordre mais aucune ne doit être négligée, et le visiteur doit revenir à la fin à sa ville de départ.

Le voyageur part de Nancy et souhaite visiter Metz, Paris, Reims et Troyes, avant de retourner à Nancy.

Voici un tableau donnant les distances kilométriques entre chacune des ces villes.

1. Quelle est la stratégie gloutonne à mettre en oeuvre ?
2. Mettez en oeuvre cette stratégie et donnez la solution.
3. Calculez la distance totale pour le parcours Metz - Reims - Paris - Troyes (départ et arrivée à Nancy sous-entendus)
4. Que dire de la solution gloutonne ?

algorithme de recherche locale k-opt

L’algorithme k-opt est un algorithme de recherche locale proposé par Georges A. Croes en 19581 pour résoudre le problème du voyageur de commerce en améliorant une solution initiale. On représente le tour par un graphe connexe.

à chaque étape, on supprime deux arêtes de la solution courante et on reconnecte les deux tours ainsi formés. Cette méthode permet, entre autres, d’améliorer le coût des solutions en supprimant les arêtes sécantes lorsque l’inégalité triangulaire est respectée (voir figure ci-contre). Sur le schéma de droite, la route {a, b, e, d, c, f, g} est changée en {a, b, c, d, e, f, g} en inversant l’ordre de visite des villes e et c. Il n’est toutefois pas certain que la solution trouvée soit également optimale lorsque l’on additionne ces morceaux de tours.. source: wikipedia: 2-opt.

Plus généralement, lorsqu’on inverse l’ordre de parcours de deux villes, il faut aussi inverser l’ordre de parcours de toutes les villes entre ces deux villes.

Résumé. L’essentiel à retenir

Programmation dynamique

L’idée de la programmation dynamique, c’est de gagner en efficacité. On cherche à reduire la complexité temporelle et spatiale.

Les problèmes à resoudre:

• peuvent être décomposés en sous-problèmes
• présentent un chevauchement des sous-problèmes.

Par exemple, pour la suite de Fibonacci, ou le triangle de Pascal, les coefficients de la suite ou du triangle sont calculés à partir des précédents, ceux de rang inférieur(sous problèmes). En stockant ces valeurs dans une liste, on peut les réutiliser sans les calculer à nouveau.

Algorithmes gloutons

Un algorithme glouton dépend du problème que l’on cherche à resoudre. Il n’y a pas d’algorithme glouton universel. Il permet de trouver une solution à un problème d’optimalité. Il part du principe que l’on peut trouver une solution approchante pour un problème NP-complet, en utilisant une stratégie et en faisant des choix. Chacun de ces choix semble être le meilleur sur le moment.

Cette stratégie peut être par exemple:

• pour le rendu de monnaie: de commencer par résoudre le problème d’optimalité pour rendre de plus petites sommes. Puis, on utilise cette solution pour rendre une partie des sommes plus importantes.

• pour le problème du sac à dos: de commencer par remplir un sac de plus petite contenance. Puis, on utilise ce résultat pour compléter de plus gros sacs.

On fait des choix à chaque étape, mais selon une stratégie bien définie, et qui ne change plus, en esperant que la somme des solutions intermédiaires va donner finalement une solution optimale. Mais on n’en est pas sûr. Et on ne revient pas en arrière.

Algorithme avec recherche locale

Pour le problème du TSP (Traveling salesman problem, ou problème du voyageur du commerce), on peut utiliser un algorithme de recherche locale, comme le k-opt. Celui-ci va cette fois remettre en doute les choix précédents.

Les étapes et leurs liens peuvent être représentés par un graphe connexe.

L’un des algorithmes existant pour la resolution, le 2-opt, va rechercher un minimum local pour un morceau de tour constitué de quelques noeuds. L’algorithme procède par permutation des arêtes entre noeuds. Et il conserve le morceau de tour de plus courte distance.

Il s’agit d’une succession de choix qui determine la solution. Là aussi, il s’agit d’un algorithme glouton.

Complexité

Rappels

Complexité temporelle d’un algorithme. Il s’agit du nombre d’opérations élémentaires executées par l’algorithme dans un pire cas (une instance en entrée qui demande le plus de calculs). Cette complexité est exprimée en fonction de la “taille de l’entrée”. Par exemple, nous avons vu des algorithmes de tri avec des complexité en O(n2) ou en O(nlogn) avec n la longueur du tableau en entrée.

Pour l’exemple du voyageur du commerce: Le nombre de solutions possibles, où les villes sont toutes parcourues une fois, il y a un nombre TRES élevé d’alternatives:

Supposons un graphe à 50 sommets qui représente la carte de ces villes. Il y a 49! possibiltés. Ce qui fait 6,08.1062 solutions.

Si l’ordinateur évalue une solution en 0,1 ms, cela fait 6,08.1058s, soit 1,9.1049 siecles de calculs !! (L’Univers a 14 milliards d’années).

Les algorithmes des problèmes de décision sont classés selon leur complexité:

Problèmes P: probleme faciles à trouver

Un problème est dit polynomial si il existe un algorithme pour le résoudre dont la complexité peut s’exprimer comme un polynôme de la taille de l’entrée. L’ensemble des problèmes polynomiaux est noté P et est considéré comme un ensemble de problèmes “faciles” (ils peuvent être résolus relativement efficacement).

Un exemple de problème polynomial est celui de la connexité dans un graphe. Étant donné un graphe à n sommets (on considère que la taille de la donnée, donc du graphe, est son nombre de sommets), il s’agit de savoir si toutes les paires de sommets sont reliées par un chemin. Un algorithme de parcours en profondeur construit un arbre couvrant du graphe à partir d’un sommet. Si cet arbre contient tous les sommets du graphe, alors le graphe est connexe.(wikipedia)

Problèmes NP: problèmes faciles à vérifier

Une autre classe de problèmes importante est celle des problèmes dont on peut tester en temps polynomial si une solution est valide (par exemple, je vous donne un tableau et vous devez non pas le trier mais me dire si il est déjà trié ou non). Cette classe s’appelle NP pour Non déterministe Polynomial.

Supposons que vous soyez chargé de loger un groupe de quatre cents étudiants. Le nombre de places est limité, seuls cent étudiants se verront attribuer une place dans la résidence universitaire. Pour compliquer les choses le doyen vous a fourni une liste de paires d’étudiants incompatibles, et demande que deux étudiants d’une même paire ne puissent jamais apparaître dans votre choix final. wikipedia.

Produire une telle liste à partir de zéro paraît tellement difficile qu’elle en est même impraticable, car le nombre de façons de regrouper cent étudiants parmi quatre cents dépasse le nombre d’atomes de l’univers !. Par contre, une fois que l’on vous fournit une solution, il est facile de montrer que celle-ci est juste ou fausse.

Si un problème est connu comme étant NP et si une solution au problème est connue, la démonstration de l’exactitude de la solution peut toujours être réduite à une vérification P (temps polynomial). Les algorithmes de cette classe sont non déterministes.

Existe t-il pour les problèmes connus de la classe NP un algorithme susceptible de trouver une solution et de complexité polynomiale. On n’en est pas sûr. Peut-être que cette apparente difficulté ne fait que refléter le manque d’ingéniosité de nos programmeurs.

Le problème de savoir si P = NP est un des problèmes du millénaire de l’institut de mathématiques Clay. Informellement, il s’agit de savoir si vérifier efficacement qu’une “solution à un problème est bien une solution valide” revient à “pouvoir trouver efficacement une solution valide au problème.”

Problèmes NP-complets

Les problèmes dits NP-complets sont des problèmes au moins aussi difficiles que les plus difficiles de la classe NP.

Exemples: le voyageur du commerce, le calcul de solutions optimales en économie (enoncé semblable mais à une echelle plus grande que celui du sac à dos), ou dans les processus de fabrication ou de transport…

Tous les algorithmes connus pour résoudre des problèmes NP-complets ont un temps d’exécution exponentiel en la taille des données d’entrée dans le pire des cas, et sont donc inexploitables en pratique même pour des instances de taille modérée.

Les classes P, NP, NP-complet ne concernent stricto sensus que les problèmes de décision. Donc quand on dit que le problème du voyageur de commerce est NP-complet, il faut l’entendre : dans sa version « décisionnelle », qui est : est-il possible de trouver un chemin qui passe par toute les villes et qui soit de longueur inférieure à L? De manière générale, tous les problèmes d’optimisation sous contrainte, comme ceux vus plus haut, sont aussi des problèmes de décision.

Trouver un algorithme qui résout un problème NP-complet, comme le problème du voyageur de commerce, en temps polynomial, suffirait à démontrer que P = NP, ce serait alors toute une série de problèmes très importants qui se trouveraient résolus. Sans exhiber un algorithme, une preuve pourrait donner des indices précieux pour construire un tel algorithme. wikipedia.

Annexes

Programmes python du rendu de monnaie

algo naîf vu en classe de 1ere

def estvide(ensemble):
    """
    fonction qui teste si un ensemble est vide
    retourne True si vide
    False sinon
    """
    vide = True
    for i in ensemble:
        vide = False
    return vide

def rendre(cost,caisse):
    """
    fonction qui rend la monnaie sur une somme cost (int) selon le 
    contenu de la caisse (une variable de type set)
    en commençant par la plus grande des pieces.
    caisse : la caisse du commerçant (set)
    rendu : ce que rend le commerçant (dict)
    à chaque itération de la boucle, on retire la piece de l'ensemble caisse 
    qui est utilisée jusqu'à ce que caisse soit vide
    """
    ### initialisation ###
    rendu = {}
    for i in caisse : 
        rendu[i] = 0
    
    while not estvide(caisse):
        piece = max(caisse)
        n = cost//piece
        cost = cost - n*piece
        rendu[piece] = n
        caisse.remove(piece)       
    return rendu

essais

>>> caisse = {1,2,5,10,20,50}
>>> rendre(93,caisse) # OK optimal
{1: 1, 2: 1, 5: 0, 10: 0, 20: 2, 50: 1}
>>> caisse = {1,10,15}
>>> rendre(21,caisse) # non optimal
{1: 6, 10: 0, 15: 1}

algo naïf recursif

(non donné)

algorithme glouton

import copy
def renduMonnaieProgDyn(x,c) :
    """
    c : caisse avec les genres de pieces à rendre par ex [1,2,5,10]
    x : montant à rendre
    res : tableau contenant : [nbe pieces rendues,[nb pieces de pieces de A, nb de B, nb de C]]
    temp : nombre de pieces rendues
    """
    n = len(c)
    res = [[x, [0 for j in range(n)]] for i in range(x + 1)]  # initialisation de la table avec des x 
    # x pieces rendues correspond à la plus mauvaise des reponses (par ex que des pieces de 1)
    res[0][0] = 0
    for i in range(1,x+1) :  # valeur du montant à rendre : recherche pour TOUT montant
        for j in range(n) : # parcours de la caisse
            if i >= c[j] : # rendre de la monnaie avec cette piece
                temp = 1 + res[i - c[j]][0] # rend une piece du type de celle de rang j
                # le nbe de piece au total est egal à 1 + le nbe de piece pour rendre le reste (deja calc)
                
                if res[i][0]>=temp:
                    res[i][0] = temp   # nombre de pieces rendues
                    res[i][1] = copy.deepcopy(res[i-c[j]][1])   # copier le nb de pieces de A , de B, de C pour le rendu de monnaie
                    # monnaie du montant i-c[j]
                    # ici il faudra copy.deepcopy pour faire une copie par valeur
                    res[i][1][j] += 1 # ajouter 1 au nombre de pieces de c[j] utilisées
                    print(f'i: {i:2}, j: {j:2}, res[{i}]: {res[i]}, temp: {temp}' )
    return res[x]

Algorithme exhaustif

Programme utilisé pour determiner toutes les combinaisons possibles de rendu de monnaie. Complexité exponentielle…

def rendu_expo(somme,caisse,rendu=[]):
    if somme==0:
        solutions.append(sorted(rendu, reverse=True))
    for i in range(len(caisse)):
        if caisse[i]<=somme:
            rendu_expo(somme-caisse[i],caisse[i:],rendu+[caisse[i]])
        else:
            rendu_expo(somme,caisse[1:],rendu)
def unique(L):
    # pour eliminer les doublons de la liste
    T = []
    T.append(L[0])
    for sol in L:
        if sol not in T:
            T.append(sol)
    return T

solutions=[]
rendu_expo(53,[30,24,12,6,3,1])
solution_min = unique(solutions)
print(len(solution_min))
solution_min

Le problème du sac à dos

Résolution

import copy

def sacADosRemise(W, s) :
    n = len(s)
    res = [[0, [0 for j in range(n)]] for i in range(W + 1)] # format [valeur totale,[nb_o1, nb_o2, nb_o3, nb_o4]]]
    for i in range(1,W +1) :
        j=0
        while (j < n) and (i-s[j][1]>=0) :
            if res[i - s[j][1]][0] + s[j][0] > res[i][0] :
                res[i][0] = res[i - s[j][1]][0] + s[j][0]
                res[i][1] = copy.deepcopy(res[i - s[j][1]][1])
                res[i][1][j] += 1
            j+=1
    return res[W]

essais:

> W = 15
> s = [(1,2),(2,3),(4,5),(6,8)] # ensemble de couples (valeur, poids)
> sacADosRemise(W,s)
[12, [0, 0, 3, 0]]

Liens

• page de cours NSI sur les algorithmes de complexité exponentielle, et la programmation dynamique cours de qkzk
• wikipedia: la programmation dynamique
• wikipedia: le problème du rendu de monnaie
• wikipedia: le problème du sac à dos
• wikipedia: le problème du voyageur du commerce
• programmation dynamique: site Pixees.fr, David Roche
• calcul de complexité de Fibonacci recursif et definition de la programmation dynamique: univ-mlv.fr
• algorithme glouton pour la compression des fichiers: code de Huffman
• les problèmes de décision: sciencesetonantes.com