Programmation dynamique : une approche pour résoudre les problèmes informatiques

Parfois, en informatique, vous rencontrerez des problèmes. Vous pouvez les diviser en sous-problèmes, qui peuvent, à leur tour, être divisés en sous-problèmes plus petits. Si les sous-problèmes plus petits se chevauchent, vous pouvez enregistrer le résultat en mémoire pour référence future. De cette façon, vous n’avez pas besoin de calculer plusieurs fois le même résultat, ce qui augmente considérablement l’efficacité du programme. Cette façon de résoudre ces problèmes est appelée programmation dynamique.

Programmation dynamique – Apprenez à résoudre les problèmes algorithmiques et les défis de codage. | Vidéo : freeCodeCamp.org

Dans cet article, vous apprendrez ce qu’est la programmation dynamique. Je montrerai également comment calculer les nombres de Fibonacci, qui est un problème simple que la programmation dynamique peut résoudre. Je comparerai les solutions de programmation dynamique à la solution naïve qui utilise la récursivité. Ces exemples sont écrits en Python syntaxe. Enfin, je donnerai également quelques indications générales à garder à l’esprit lorsque vous tenterez de résoudre des problèmes à l’aide de la programmation dynamique

programmation dynamique

La programmation dynamique est une méthode efficace pour résoudre des problèmes informatiques en enregistrant des solutions en mémoire pour référence future. Lorsque vous avez des sous-problèmes qui se chevauchent, vous pouvez appliquer une programmation dynamique pour gagner du temps et augmenter l’efficacité du programme.

Plus d’Arturi Jalli: Aide-mémoire Python : un guide pratique de Python

Quels types de problèmes la programmation dynamique peut-elle résoudre ?

La programmation dynamique est généralement un moyen d’optimiser les solutions à certains problèmes qui utilisent la récursivité. Si une solution récursive à un problème doit calculer à plusieurs reprises des solutions pour des sous-problèmes avec les mêmes entrées, vous pouvez l’optimiser grâce à la programmation dynamique. Comme mentionné précédemment, dans ce cas, vous enregistreriez simplement le résultat du calcul pour une utilisation ultérieure si et quand cela est nécessaire. Cette optimisation peut réduire la complexité temporelle d’un algorithme d’un temps exponentiel à un temps polynomial. Cela signifie que le nombre de calculs n échelles comme une expression polynomiale au lieu de mise à l’échelle comme une expression exponentielle comme n augmente. En général, les expressions polynomiales croissent beaucoup plus lentement que les expressions exponentielles.

Deux conditions doivent être remplies pour utiliser la programmation dynamique :

  1. Sous-problèmes qui se chevauchent
  2. Propriété optimale de la sous-structure

Que sont les sous-problèmes qui se chevauchent ?

J’ai fait allusion à la condition des sous-problèmes qui se chevauchent plus tôt. Cela signifie simplement que lors de la résolution du problème en question, les solutions pour les mêmes sous-problèmes sont nécessaires à plusieurs reprises. Dans ce cas, les solutions à ces sous-problèmes peuvent être stockées pour une utilisation ultérieure afin d’éviter le recalcul.

Une autre façon de penser à cette condition est de la renverser. S’il n’y a pas de sous-problèmes qui se chevauchent, il est inutile de sauvegarder les solutions des sous-problèmes et vous ne pouvez pas utiliser la programmation dynamique.

Il existe deux manières différentes de stocker les solutions aux sous-problèmes qui se chevauchent :

  1. Mémoïsation (descendante)
  2. Tabulation (ascendante)

Qu’est-ce que la mémorisation ?

L’approche de mémorisation de la programmation dynamique est très similaire à l’approche de récursivité naïve, avec seulement un petit changement. La différence est que nous utilisons une table de recherche pour stocker les solutions aux sous-problèmes, puis utilisons cette table pour vérifier si cette solution existe déjà.

Si la solution pour un certain sous-problème existe déjà dans la table de recherche, alors cette solution est renvoyée à partir de la table de recherche. Si ce n’est pas le cas, il doit être calculé (par récursivité) et ajouté à la table de recherche.

Par souci de clarté, définissons une solution pour qu’un sous-problème de notre problème de programmation dynamique soit DP[X]., avec DP[N] étant la solution souhaitée et DP[0] étant la solution de base. Dans l’approche de mémorisation, le programme commence à partir de DP[N] et demande les solutions à partir desquelles DP[N] peut être atteint (il doit s’agir de sous-problèmes d’ordre inférieur DP[n. Puis, à partir de ces états, le même processus est répété récursivement, jusqu’à ce que la solution de base soit atteinte DP[0].

Si cela vous semble un peu trop abstrait, ne vous inquiétez pas. Les exemples présentés plus loin dans cet article devraient clarifier ce que je veux dire.

La mémorisation est connue comme une approche descendante de la programmation dynamique puisque le programme commencera à partir du dernier état (supérieur) souhaité et progressera de manière récursive.

Qu’est-ce que la tabulation ?

L’approche de tabulation de la programmation dynamique fonctionne de manière inverse par rapport à l’approche de mémorisation. Le programme commencera à partir de la solution de base (ou inférieure) pour le sous-problème et remontera, résolvant les sous-problèmes un par un jusqu’à ce que la solution souhaitée soit atteinte.

En termes de solutions aux sous-problèmes, l’approche de tabulation part de la solution de base DP[0] puis calcule DP[1]DP[2]… D.P.[N] jusqu’à atteindre la solution souhaitée pour le sous-problème DP[N]. Puisque nous sommes partis de la solution de base DP[0] et travaillé vers la solution souhaitée DP[N]l’approche tabulaire est également connue sous le nom d’approche ascendante.

Encore une fois, les exemples ci-dessous devraient faciliter la compréhension.

Qu’est-ce que la propriété optimale de la sous-structure ?

Si la solution optimale d’un problème peut être obtenue en utilisant la solution optimale de ses sous-problèmes, alors on dit que le problème a propriété optimale de la sous-structure.

A titre d’exemple, considérons le problème de trouver le chemin le plus court entre les nœuds ‘Start’ et ‘Goal’ dans le graphique ci-dessous. Les nœuds sont connectés à d’autres nœuds via des arêtes, et la distance entre deux nœuds connectés est marquée par un nombre à côté de l’arête.

Graphique des nœuds ‘Start’ et ‘Goal’. | Image: Arturi Jalli

Le chemin le plus court entre le nœud Start et le nœud Goal passe par les nœuds trois et quatre.

Ce problème a clairement une propriété de sous-structure optimale. Étant donné que le chemin le plus court du nœud de départ au nœud d’arrivée passe par le nœud quatre, il s’ensuit clairement que ce chemin est une combinaison du chemin le plus court du nœud de départ au nœud quatre et du chemin le plus court du nœud quatre au nœud d’arrivée.

De nombreux problèmes n’ont pas de propriété de sous-structure optimale. Par exemple, le problème de trouver le chemin le plus long (sans cycle) entre le nœud Start et le nœud Goal dans le graphique ci-dessus ne fonctionne pas. Voici comment vous pouvez voir ceci :

Le chemin le plus long est : Start – Node Three – Node Two – Node One – Node Four – Goal. Cependant, cela n’implique pas que le chemin le plus long entre le nœud de départ et le nœud deux soit Démarrer – nœud trois – nœud deux. Le chemin le plus long du nœud Start au nœud Two est en fait Start – Node One – Node Four – Node Three – Node Two (et Start – Node One – Node Four – Goal – Node Two, qui a la même longueur que le premier).

Exemple de programmation dynamique : calcul des nombres de Fibonacci

L’un des exemples les plus simples de programmation dynamique est le calcul des nombres de Fibonacci, qui sont des nombres de la suite de Fibonacci. Le premier nombre de Fibonacci est zéro, le second est un et les nombres suivants sont la somme des deux nombres de Fibonacci précédents. Les 10 premiers nombres de Fibonacci sont zéro, un, un, deux, trois, cinq, huit, 13, 21 et 34.

Commençons d’abord par la solution naïve et récursive. Voici une fonction Python pour calculer le nième nombre de Fibonacci (l’indexation commence à zéro) :

def fib_recursive(n):
	if n <= 1:
		return n
	else:
		return fib_recursive(n-1) + fib_recursive(n-2)

À partir de cet exemple, il est facile de voir que ce problème satisfait la condition de sous-problèmes qui se chevauchent puisque la fonction doit clairement calculer les nombres de Fibonacci précédents plusieurs fois (lorsque n > trois). Les plus petits nombres de Fibonacci sont calculés le plus souvent, lorsque cette fonction est appelée pour un grand n.

Ce problème a également clairement une sous-structure optimale puisqu'il n'y a qu'une seule solution pour les sous-problèmes, qui sont utilisés pour calculer la solution au problème souhaité.

En raison de la récursivité, cette fonction s'exécute en temps exponentiel.

Voyons ensuite comment cela pourrait être résolu en utilisant la programmation dynamique. Commençons par une solution descendante utilisant la mémorisation. Voici une fonction Python qui calcule le nième nombre de Fibonacci qui implémente la programmation dynamique par mémorisation :

def fib_DP_memoization(n):

	# Define a lookup table
	lookup_table = [None] * (n+1)

	# Define an inner function for the recursive part
	def _inner(n, lookup):
		# If the n:th Fibonacci number has not been
		# calculated previously, calculate it
		if lookup[n] is None:

			if n <= 1:	# Base case
				lookup[n] = n
			else:
				lookup[n] = _inner(n-1, lookup) 
						+ _inner(n-2, lookup)

		return lookup[n]

	_inner(n, lookup_table)

	# Return n:th Fibonacci number
	return lookup_table[n]

Cette approche est assez similaire à l'approche récursive puisqu'elle part du calcul du nième nombre de Fibonacci et, pour le calculer, passe au calcul des n-1er et n-2ème nombres de Fibonacci. La différence réside dans la table de recherche, où les plus petits nombres de Fibonacci seront enregistrés au fur et à mesure qu'ils sont calculés, de sorte qu'ils n'ont pas besoin d'être calculés encore et encore.

Cela rend cette fonction réellement exécutée en temps linéaire au lieu d'un temps exponentiel.

À titre d'exemple, examinons également une fonction Python qui résout le même problème de manière ascendante avec une programmation dynamique utilisant la tabulation :

def fib_DP_tabulation(n):
	# Define an array and base case(s)
	f = [0] * (n+1)
	if n > 0:
		f[1] = 1

	# Calculate Fibonacci numbers bottom-up
	for i in range(2, n+1):
		f[i] = f[i-1] + f[i-2]

	return f[n]

Dans cette solution, le nième nombre de Fibonacci est calculé de manière ascendante, en commençant par calculer le premier nombre de Fibonacci, puis le deuxième, le troisième et ainsi de suite jusqu'à atteindre le nième nombre de Fibonacci. Cette fonction s'exécute également en temps linéaire.

Plus en génie logiciel : Module Glob en Python : expliqué

Comment résoudre des problèmes à l'aide de la programmation dynamique

La première étape pour résoudre un problème à l'aide de la programmation dynamique consiste à l'identifier comme un problème de programmation dynamique. Si vous pouvez valider que le problème a des sous-problèmes qui se chevauchent et qu'il satisfait la propriété de sous-structure optimale, vous pouvez être sûr que vous pouvez le résoudre avec la programmation dynamique.

La deuxième étape consiste à décider d'une expression d'état. Cet état est l'ensemble de paramètres qui identifie de manière unique les différents sous-problèmes.

Dans l'exemple des nombres de Fibonacci, le paramètre identifiant l'état serait simplement le numéro de série d'un certain nombre de Fibonacci.

Il peut y avoir plus d'un paramètre identifiant un état. Cependant, vous devez toujours utiliser le moins de paramètres possible.

La troisième étape - et probablement la plus difficile - dans la résolution de problèmes à l'aide de la programmation dynamique consiste à formuler la relation entre les différents états.

Dans le cas du nombre de Fibonacci, c'est simple, cependant, puisque le nième nombre de Fibonacci est la somme des n-1er et n-2e nombres de Fibonacci. Alors F[n] =F[n-1] + F[n-2].

La quatrième étape consiste à implémenter la mémorisation ou la tabulation pour les états que vous avez choisis, en utilisant la relation que vous avez découverte entre les états. Cela signifie simplement enregistrer l'état (ou en d'autres termes la solution à un certain sous-problème) afin qu'il puisse être récupéré de la mémoire sans recalcul lorsqu'il est à nouveau nécessaire. Cela devrait être assez simple, si vous avez bien fait une à trois étapes

.

Leave a Comment

Your email address will not be published. Required fields are marked *