Substructure optimale

Question

J'essaie d'obtenir une image plus complète de l'utilisation de la propriété de sous-structure optimale dans la programmation dynamique, mais je suis devenu aveugle pourquoi nous devons prouver que toute solution optimale au problème Contient à l'intérieur des solutions optimales aux sous-problèmes.

ne suffirait-il pas à montrer que une solution optimale au problème a cette propriété, puis utilisez-le pour affirmer que puisque la solution construite par notre algorithme récursif est au moins aussi bonne que possible. une solution optimale, elle sera elle-même optimale? En d'autres termes, je ne parviens pas à repérer où dans l'argument de l'exactitude de notre algorithme, nous avons besoin que toutes les solutions optimales contiennent des solutions optimales aux sous-problèmes.

clarifier:

La définition des CLRS de la sous-structure optimale indique que "un problème présente une sous-structure optimale si toute solution optimale au problème contient des solutions optimales sur les sous-émérides".

Pourquoi ne suffirait-il pas suffire de dire que "un problème présente une sous-structure optimale si une solution optimale au problème contient dans les solutions optimales aux sous-émérides"?

Answer 1

J'ai été dérangé un peu à ce sujet dans mes recherches sur des algorithmes d'approximation, qui impliquent des programmes dynamiques qui trouvent des solutions approximativement optimales. La bonne façon de penser à l'exactitude des programmes dynamiques, je crois, est une réduction (dans le sens de la théorie de la complexité) d'un problème à un subproblème. Cette réduction est souvent appliquée de manière récursive et avec mémoisation, mais ce sont des détails en ce moment.

Soit A être le problème et B soit le sous-programme. Il n'y a qu'un seul sous-émérule, car nous pouvons combiner plusieurs sous-programmes indépendants en une via un produit cartésien généralisé. La réduction consiste en deux fonctions: F, d'une instance A à une instance B et H, d'une solution B à une solution A. La propriété de justice dont nous avons besoin est que, pour chaque fonction G de chaque instance B à une solution B optimale correspondante (l'oracle), la composition h. g . F est une fonction de chaque instance A à une solution optimale correspondante. (Si H a besoin d'accéder à l'instance A, puis étendez B de manière à ce que ses instances contiennent une instance A devez être copiée Verbatim dans la solution B correspondante.)

Pour faire votre point, pour une instance a-instance particulière et une solution A optimale, il n'est pas nécessaire d'exister un Oracle G tel que le pipeline h. g . F produit cette solution de l'instance donnée. (En d'autres termes, il n'a pas besoin d'être surjectif.) D'autre part, H doit pouvoir gérer chaque solution B optimale possible de G pour l'instance B construite par F.

Une stratégie commune pour veiller à ce que H soit correct, c'est de trouver une fonction "sous-structure" K des solutions A à B et un moyen de "épisser" la sous-structure, c'est-à-dire une preuve que, étant donné une solution A-Solution x et une solution B non pire que k (x), il existe une solution a-solution x 'non pire que x tel que k (x')= y. Ensuite, H peut optimiser sur tout dans l'image inverse sous K de son entrée. Il n'est pas nécessaire que l'épissage s'applique à toutes les solutions X, une seule optimale.

Answer 2

Dans la programmation dynamique, nous divisons le problème à des sous-problèmes plus petits, faisons de la manipulation et fournissez une réponse à une réponse plus grande - très similaire à celle de la récursion (et par aucune coïncidence).

Maintenant, lorsque nous viendrons formellement prouver l'exactitude de cet algorithme, cela se fait par induction. Nous prouvons que notre «clause de base» est correcte (généralement très facile), puis nous supposons que tout problème plus petit que celui actuel - est également optimal. Nous utilisons ensuite cette hypothèse pour prouver l'exactitude du problème plus large.

Si nous ne savions pas que toutes les solutions sont optimales - nous ne serions pas en mesure de prouver que l'utilisation de l'étape supplémentaire que nous avons pu modifier une solution optimale à un problème plus faible à une solution optimale à un problème plus important - il n'y aurait tout simplement pas de assez d'informations pour prouver cette réclamation.

Si nous savions que certains des sous-périllons sont une solution optimale - il ne suffirait pas de veiller à ce que l'utilisation de ce subproblème, que nous avons une solution optimale à - en effet est celle dont nous avons besoin pour obtenir la solution optimale au plus grand problème. .

---

Jetez un coup d'œil sur le bon de sac, par exemple et jetons un coup d'œil sur son étape DP:

f(x,i) = max(f(x-weight[i],i-1) +val[i], f(x,i-1))

Si nous ne savions que l'un d'entre eux est optimal - nous n'avons pas pu prouver que l'algorithme est correct, car nous aurions peut-être besoin de l'affaire "Autre", où nous n'avons pas de solution optimale.

Si nous avons choisi f(x,i-1) dans le max() - cela aurait pu être le mauvais choix. En veillant à ce que nous ayons une solution optimale à tous les sous-émérules, nous nous assurons que cela ne peut pas arriver.