Sous-structure optimale - Optimal substructure

Graphique 1 . Trouver le chemin le plus court en utilisant une sous-structure optimale. Les nombres représentent la longueur du chemin; les lignes droites indiquent des arêtes simples , les lignes ondulées indiquent les chemins les plus courts , c'est-à-dire qu'il peut y avoir d'autres sommets qui ne sont pas représentés ici.

En informatique , on dit qu'un problème a une sous - structure optimale si une solution optimale peut être construite à partir de solutions optimales de ses sous-problèmes. Cette propriété est utilisée pour déterminer l'utilité de la programmation dynamique et des algorithmes gourmands pour un problème.

En règle générale, un algorithme glouton est utilisé pour résoudre un problème avec une sous-structure optimale s'il peut être prouvé par induction que celle-ci est optimale à chaque étape. Sinon, à condition que le problème présente également des sous- problèmes qui se chevauchent , la programmation dynamique est utilisée. S'il n'y a pas d'algorithmes gloutons appropriés et que le problème ne présente pas de sous-problèmes qui se chevauchent, une recherche longue mais directe de l'espace de solution est souvent la meilleure alternative.

Dans l'application de la programmation dynamique à l'optimisation mathématique , le principe d'optimalité de Richard Bellman est basé sur l'idée que pour résoudre un problème d'optimisation dynamique d'une période de départ t à une période de fin T , il faut implicitement résoudre des sous-problèmes à partir de dates ultérieures s , où t <s <T . Ceci est un exemple de sous-structure optimale. Le principe d'optimalité est utilisé pour dériver l' équation de Bellman , qui montre comment la valeur du problème à partir de t est liée à la valeur du problème à partir de s .

Exemple

Envisagez de trouver le chemin le plus court pour voyager entre deux villes en voiture, comme illustré à la figure 1. Un tel exemple est susceptible de présenter une sous-structure optimale. Autrement dit, si la route la plus courte de Seattle à Los Angeles passe par Portland puis Sacramento, la route la plus courte de Portland à Los Angeles doit également passer par Sacramento. Autrement dit, le problème de la façon de se rendre de Portland à Los Angeles est imbriqué dans le problème de savoir comment se rendre de Seattle à Los Angeles. (Les lignes ondulées du graphique représentent des solutions aux sous-problèmes.)

À titre d'exemple d'un problème peu susceptible de présenter une sous-structure optimale, considérons le problème de trouver le billet d'avion le moins cher de Buenos Aires à Moscou. Même si ce billet implique des escales à Miami puis à Londres, nous ne pouvons pas conclure que le billet le moins cher de Miami à Moscou s'arrête à Londres, car le prix auquel une compagnie aérienne vend un voyage multi-vols n'est généralement pas la somme des prix. auquel il vendrait les vols individuels du voyage.

Définition

Une définition légèrement plus formelle de la sous-structure optimale peut être donnée. Soit un «problème» une collection «d'alternatives», et que chaque alternative ait un coût associé, c (a) . La tâche est de trouver un ensemble d'alternatives qui minimise c (a) . Supposons que les alternatives peuvent être partitionnées en sous-ensembles, c'est-à-dire que chaque alternative n'appartient qu'à un seul sous-ensemble. Supposons que chaque sous-ensemble a sa propre fonction de coût. Les minima de chacune de ces fonctions de coût peuvent être trouvés, de même que les minima de la fonction de coût global, limités aux mêmes sous-ensembles . Si ces minima correspondent à chaque sous-ensemble, alors il est presque évident qu'un minimum global peut être choisi non pas dans l'ensemble complet des alternatives, mais uniquement dans l'ensemble qui comprend les minima des fonctions de coût locales plus petites que nous avons définies. Si minimiser les fonctions locales est un problème "d'ordre inférieur", et (spécifiquement) si, après un nombre fini de ces réductions, le problème devient trivial, alors le problème a une sous-structure optimale.

Problèmes avec une sous-structure optimale

Problèmes sans sous-structure optimale

  • Problème de chemin le plus long
  • Exponentiation de la chaîne d'addition
  • Tarif aérien le moins cher. (En utilisant la recherche de vols en ligne, nous trouverons fréquemment que le vol le moins cher de l'aéroport A à l'aéroport B implique une seule connexion via l'aéroport C, mais le vol le moins cher de l'aéroport A à l'aéroport C implique une connexion via un autre aéroport D.) Cependant, si le problème prend comme paramètre le nombre maximum d'escales, alors le problème a une sous-structure optimale: le vol le moins cher de A à B impliquant une seule connexion est soit le vol direct; ou un vol de A vers une destination C, plus le vol direct optimal de C à B.

Voir également

Les références

  1. ^ un b Cormen, Thomas H .; Leiserson, Charles E .; Rivest, Ronald L .; Stein, Clifford (2009). Introduction aux algorithmes (3e éd.). MIT Press . ISBN   978-0-262-03384-8 .