En informatique, on dit qu'un problème a des sous-problèmes qui se chevauchent si le problème peut être décomposé en sous-problèmes qui sont réutilisés plusieurs fois ou si un algorithme récursif pour le problème résout le même sous-problème encore et encore plutôt que de toujours en générer de nouveaux sous-problèmes.
Qu'est-ce que la sous-structure optimale et les sous-problèmes qui se chevauchent dans la programmation dynamique ?
Un problème a une propriété de sous-structure optimale si une solution optimale du problème donné peut être obtenue en utilisant la solution optimale de ses sous-problèmes. La programmation dynamique profite de cette propriété pour trouver une solution.
Qu'est-ce que le sous-problème de chevauchement dans la programmation dynamique ?
1) Sous-problèmes qui se chevauchent:
La programmation dynamique est principalement utilisée lorsque des solutions aux mêmes sous-problèmes sont nécessaires encore et encore. En programmation dynamique, les solutions calculées aux sous-problèmes sont stockées dans une table afin qu'elles n'aient pas à être recalculées.
Quelle est la différence entre une sous-structure optimale et des sous-problèmes qui se chevauchent ?
Je comprends l'approche cible pour les deux méthodes où la sous-structure optimale calcule la solution optimale basée sur une entrée n tandis que les sous-problèmes de chevauchement ciblent toutes les solutions pour la plage d'entrée, disons de 1 à n. Pour un problème comme le problème de coupe de tige.
Laquelle de ces techniques utilise le chevauchement de sous-problèmes ?
La programmation dynamique est une technique de résolution de problèmes avec des sous-problèmes qui se chevauchent. En cela, nous stockons le résultat du sous-problème qui est résolu une fois pour une réutilisation future. La technique de stockage des solutions de sous-problèmes s'appelle la mémorisation.
