Bonjour,
quelqu'un aura la gentillesse de m'aider à montrer sur un exemple simple que l’algorithme qui consiste à prendre toujours l’objet restant avec la valeur la plus élevée ne garantit pas un résultat optimal ?
Et également montrer sur un exemple simple que l’algorithme qui consiste à choisir toujours la ville non visitée la plus proche ne garantit pas un résultat optimal ?
Merci beaucoup d'avance
question algo exemple
Re: question algo exemple
Vos questions manquent de précision mais je vais essayer quand même d'y répondre, en espérant ne pas me méprendre.
• Je pense que votre première question fait référence au problème du sac à dos : étant donnés $n$ objets de valeurs $c_1,\ldots,c_n$ et de poids respectifs $w_1,\ldots,w_n$, comment remplir un sac à dos de valeur la plus élevée possible sans dépasser le poids total autorisé $W$.
Une stratégie gloutonne consiste à placer dans le sac l'objet de plus grande valeur possible sans dépasser le poids total autorisé et à recommencer tant que c'est possible. Par exemple, avec quatre objets de valeurs $1, 3, 4, 5$ et de poids respectifs $1, 2, 3, 4$ et un poids total ne devant pas dépasser $W=5$, la stratégie gloutonne consiste à placer d'abord l'objet de valeur $5$ et de poids $4$ puis l'objet de valeur $1$ et de poids $1$ pour une valeur totale égale à $6$, mais ce n'est pas optimal car il vaut mieux remplir le sac avec les deux autres objets pour un poids toujours égal à $5$ mais une valeur égale à $7$.
• Votre seconde question fait je pense référence au problème du voyageur de commerce : trouver un chemin reliant $n$ villes puis revenant à la ville de départ en un minimum de distance. Une stratégie possible consiste à partir d'une ville arbitraire puis à se rendre jusqu'à la ville non visitée la plus proche, et à recommencer jusqu'à avoir visité toutes les villes, avant de revenir au point de départ.
Cette stratégie n'est pas optimale, comme vous pouvez le constater en reportant sur un dessin les points suivants : $A(0,0)$, $B(3,0)$, $C(1,1)$, $D(-2,1)$ (ces quatre points forment un parallélogramme).
Partant de $A$, l'algorithme du plus proche voisin consiste à suivre le trajet : $A\to C\to B\to D\to A$ ; il a pour longueur $\sqrt2+\sqrt5+\sqrt{26}+\sqrt5$, mais il n'est pas optimal car le trajet $A\to B\to C\to D\to A$ a pour longueur $3+\sqrt5+3+\sqrt5$, qui est plus court.
Ces deux situations sont des exemples classiques pour lesquels une heuristique gloutonne conduit à une solution non nécessairement optimale.
• Je pense que votre première question fait référence au problème du sac à dos : étant donnés $n$ objets de valeurs $c_1,\ldots,c_n$ et de poids respectifs $w_1,\ldots,w_n$, comment remplir un sac à dos de valeur la plus élevée possible sans dépasser le poids total autorisé $W$.
Une stratégie gloutonne consiste à placer dans le sac l'objet de plus grande valeur possible sans dépasser le poids total autorisé et à recommencer tant que c'est possible. Par exemple, avec quatre objets de valeurs $1, 3, 4, 5$ et de poids respectifs $1, 2, 3, 4$ et un poids total ne devant pas dépasser $W=5$, la stratégie gloutonne consiste à placer d'abord l'objet de valeur $5$ et de poids $4$ puis l'objet de valeur $1$ et de poids $1$ pour une valeur totale égale à $6$, mais ce n'est pas optimal car il vaut mieux remplir le sac avec les deux autres objets pour un poids toujours égal à $5$ mais une valeur égale à $7$.
• Votre seconde question fait je pense référence au problème du voyageur de commerce : trouver un chemin reliant $n$ villes puis revenant à la ville de départ en un minimum de distance. Une stratégie possible consiste à partir d'une ville arbitraire puis à se rendre jusqu'à la ville non visitée la plus proche, et à recommencer jusqu'à avoir visité toutes les villes, avant de revenir au point de départ.
Cette stratégie n'est pas optimale, comme vous pouvez le constater en reportant sur un dessin les points suivants : $A(0,0)$, $B(3,0)$, $C(1,1)$, $D(-2,1)$ (ces quatre points forment un parallélogramme).
Partant de $A$, l'algorithme du plus proche voisin consiste à suivre le trajet : $A\to C\to B\to D\to A$ ; il a pour longueur $\sqrt2+\sqrt5+\sqrt{26}+\sqrt5$, mais il n'est pas optimal car le trajet $A\to B\to C\to D\to A$ a pour longueur $3+\sqrt5+3+\sqrt5$, qui est plus court.
Ces deux situations sont des exemples classiques pour lesquels une heuristique gloutonne conduit à une solution non nécessairement optimale.