© Jirsak/Shutterstock.com
Lorsque vous avez affaire à des ensembles de données, ils se présenteront probablement sous la forme d’un tableau. Et ces tableaux sont souvent contigus. Cela signifie qu’il n’y a pas de”pauses”entre les valeurs de données-elles sont stockées dans un seul bloc de mémoire. Ce type de tableau occupe une place centrale lorsqu’il s’agit du problème classique de sous-tableau maximum. Bien qu’il existe plusieurs façons d’aborder ce problème, l’une des meilleures façons de le résoudre consiste à utiliser l’algorithme de Kadane. Si vous vous demandez comment utiliser cet algorithme, et comment il s’intègre dans le domaine de la programmation dynamique, vous êtes au bon endroit. Venez avec nous alors que nous explorons l’algorithme de Kadane et comment il est utilisé pour résoudre le problème de sous-réseau maximum.
Qu’est-ce que le problème de sous-réseau maximum ?
Le problème de sous-réseau maximum est également connu sous le nom de problème de sous-réseau maximum. Problème de sous-réseaux contigus. En termes simples, la tâche que ce problème présente est de trouver le sous-tableau contigu maximum dans un tableau, arr[], de taille N. Autrement dit, trouver la somme maximale possible d’addition d’entiers dans le tableau sans rupture entre eux. Par exemple, si nous prenons un tableau [4,-1, 2, 1], la somme maximale serait simplement la somme de tous les entiers, ou 6.
Pour les petits ensembles de données, cela peut être une tâche relativement simple, et peut être résolu assez facilement en utilisant ce qu’on appelle «l’approche de la force brute». Cela signifie essentiellement utiliser les calculs les plus simples au détriment de l’efficacité globale. De cette manière, nous pouvons partir du 0ème indice et calculer la somme de tous les sous-tableaux possibles, en commençant par l’élément A[0]. Nous pouvons calculer ces sommes de sous-tableaux en commençant par A[1] et en continuant jusqu’à A[n-1], où n est la taille du tableau. Si nous appelons la somme maximale d’un sous-tableau le local_maximum à l’indice i, nous pouvons calculer tous ces éléments, puis terminer en trouvant le maximum des local_maximums. Cela nous donnera la plus grande somme possible, qui peut être décrite comme le global_maximum.
Comme vous pouvez vous y attendre, cela peut fonctionner assez bien pour les très petits tableaux mais est plutôt inefficace pour les grands ensembles de données. La complexité temporelle est quadratique, ou O(n2), ce qui signifie que la complexité augmente assez rapidement avec l’augmentation de la taille de l’entrée. Par conséquent, nous allons avoir besoin d’un processus plus efficace et élégant. C’est là qu’intervient la programmation dynamique.
Comment la programmation dynamique peut-elle aider ?
La programmation dynamique est une approche pour résoudre des problèmes complexes en les réduisant à un ensemble de problèmes plus simples. Ces problèmes plus faciles sont résolus et leurs solutions sont stockées dans une structure de données telle qu’un tableau. Ces solutions peuvent ensuite être consultées lorsque nous résolvons le même type de problème, évitant ainsi d’avoir à les résoudre à nouveau et accélérant les calculs globaux.
Ce serait vraiment bénéfique si nous pouvions appliquer les principes de la programmation dynamique à notre problème de sous-tableau maximum. Heureusement, nous le pouvons, et c’est exactement ce que l’algorithme de Kadane se propose de faire. Alors, allons-y.
La programmation dynamique est une approche pour résoudre des problèmes complexes en les réduisant à un ensemble de problèmes plus simples.
©hafakot/Shutterstock.com
Algorithme de Kadane
Comme brièvement mentionné, l’algorithme de Kadane utilise la programmation dynamique pour calculer une solution efficace au problème du sous-réseau maximum. L’algorithme fonctionne en stockant la somme maximale du sous-tableau contigu à l’index actuel. Ceci est ensuite comparé à la somme maximale trouvée jusqu’à présent. Si elle est supérieure à la somme maximale trouvée jusqu’à présent, elle est mise à jour avec la nouvelle valeur.
Un avantage majeur de l’algorithme de Kadane est sa rapidité, illustrée par sa complexité temporelle de O(n). Cela signifie que la complexité temporelle augmente de manière linéaire avec l’augmentation de la taille de l’entrée, ce qui est bien meilleur que la complexité temporelle quadratique de l’approche par force brute. La complexité spatiale est également bonne, car l’algorithme est stable-cela signifie qu’une quantité constante de mémoire est requise pendant le processus, car seules deux variables doivent être stockées (ce sont le global_maximum et le local_maximum).
L’algorithme de Kadane en action
Reprenons le tableau [4,-1, 2, 1]. Si nous inversons l’approche de la force brute et commençons par l’élément A[n] (dans ce cas, 1), nous pouvons calculer la somme de chaque sous-tableau possible, puis continuer avec A[n-1], A[n-2] jusqu’à ce que nous les ayons tous complétés.
En regardant les deux derniers éléments, A[3] et A[4], nous pouvons voir que le local_maximum est 5 et 6 respectivement. Mais, si nous connaissons local_maximum[3], nous n’avons pas besoin de calculer toutes les sommes des sous-tableaux pour A[4]. C’est parce que nous connaissons déjà les résultats de A[3] et le local_maximum[3]. Il suffit de vérifier deux sous-tableaux, celui contenant A[4] seul et la somme de A[4] et local_maximum[3]. Dans ce cas, ce serait A[4} + local_maximum[3], soit 6. C’est la même réponse que nous obtenons si nous calculons toutes les sommes des sous-tableaux pour A[4].
Ce principe est ce qui sous-tend l’algorithme de Kadane, et peut être décrit comme suit :
local_maximum[i]=max(A[i], A[i] + local_maximum[i-1])
Ou, en d’autres termes, le local_maximum à l’index i est le maximum de A[i] et la somme de A[i] et local_maximum à l’index i-1.
Donc, nous n’avons qu’à trouver le maximum de A[i] et A[i] + local_maximum[i-1] pour trouver le maximum à chaque indice i. Par conséquent, nous n’avons qu’à trouver chaque local_maximum pour trouver le sous-tableau maximum. C’est un moyen beaucoup plus efficace de résoudre le problème du sous-réseau maximum.
Le fonctionnement de l’algorithme de Kadane
Passons en revue les étapes que l’algorithme de Kadane utilise pour calculer le sous-réseau maximum.
L’algorithme ne nécessitera qu’une seule boucle, itérant de i[0[ à i[n-1].Le local_maximum[i] sera calculé pour chaque élément, qui dépend de local_maximum[i-1].Le local_maxium est comparé au global_maximum. S’il est supérieur, alors global_maximum sera mis à jour. Ceci est répété pour chaque index jusqu’à ce que la plus grande somme d’un sous-tableau contigu soit trouvée.
Implémentation de l’algorithme de Kadane
Pour montrer comment l’algorithme de Kadane peut être implémenté, nous allons utiliser Python dans l’environnement Spyder. Voyons comment le code fonctionne en pratique.
from sys import maxsize def solveMaxSubArrayProblem(input): n=len(input) globalMaxSum=-maxsize-1 localMaxSum=0 for i in range(0, n): localMaxSum=max(input[i], input[i] + localMaxSum) if(localMaxSum>globalMaxSum): globalMaxSum=localMaxSum return globalMaxSum if_name_==”_main_”input=[1,-2, 5,-3, 4,-1, 6] result=solveMaxSubArrayProblem(input) print(result) 11
Tout d’abord, la bonne indentation en Python est essentielle pour exécuter correctement le code. Pour commencer, nous importons la fonction”maxsize”, qui est utilisée pour trouver la valeur maximale.
Ensuite, nous définissons”solveMaxSubArrayProblem”en fonction du tableau”input”de longueur n , avec globalMaxSum initialisé comme valeur entière minimale. Ceci est fait pour s’assurer que toute somme de sous-tableau calculée sera supérieure à cette valeur.
Le local_maximum variera et est initialement défini sur 0.
“for”fait référence à une boucle, qui est utilisé pour parcourir chaque élément du tableau.
Pour chaque itération,”localMaxSum”est mis à jour soit avec le localMaxSum de l’élément actuel, soit avec l’élément plus le précédent localMaxSum.
Si localMaxSum est supérieur au globalMaxSum actuel, ce dernier est mis à jour pour refléter ce changement.
Une fois le processus itératif terminé, globalMaxSum est égal au sous-tableau contigu maximum, et ce résultat est renvoyé.
Enfin,”if __name__==””__main__””teste la fonction en créant le tableau qui suit et en utilisant la fonction définie dessus, puis imprime le résultat.
Pour le tableau [1 ,-2, 5,-3, 4,-1, 6], le sous-tableau contigu maximum a une somme de 11.
©”TNGD”.com
Conclusion
Nous avons couvert le principe de la programmation dynamique. Nous avons également montré comment l’algorithme de Kadane l’utilise pour résoudre le problème du sous-réseau maximum. Les avantages de ceci ont été décrits. L’algorithme de Kadane est relativement simple à comprendre et à utiliser, avec une complexité temporelle et spatiale efficace. Lorsqu’il s’agit de résoudre le problème du sous-réseau maximum, l’algorithme de Kadane est l’un des moyens les plus rapides de le faire.
Suivant…
L’algorithme de Kadane : une approche efficace du problème du sous-réseau maximum , Expliqué avec la FAQ Photos (Foire aux questions)
Qu’est-ce qu’un sous-tableau ?
Un sous-tableau fait partie d’un tableau qui est ininterrompu, c’est-à-dire sans interruption entre entiers. Ceci est décrit comme contigu. Un sous-réseau peut être constitué d’un élément. Ils sont principalement utilisés lorsque vous travaillez avec des ensembles de données, pour faire des choses comme trouver le sous-tableau contigu maximum.
Qu’est-ce que la programmation dynamique ?
La programmation dynamique fait référence à une technique de résolution de problèmes complexes en les décomposant en problèmes plus simples. Chaque sous-solution n’a besoin d’être calculée qu’une seule fois et est stockée dans un cache temporaire. Ainsi, les calculs redondants sont évités, les processus sont donc considérablement accélérés. La programmation dynamique est souvent utilisée pour optimiser les solutions et concevoir des algorithmes, tels que l’algorithme de Bellman-Ford pour trouver le chemin le plus court dans un graphe. Habituellement, les sous-problèmes sont résolus de bas en haut, ce qui signifie que les problèmes les plus simples sont résolus en premier. Ces solutions sont ensuite combinées pour résoudre le problème initial.
Qu’est-ce que le problème de sous-tableau maximum ?
Il s’agit d’un problème de programmation classique qui consiste à trouver la plus grande somme sous-tableau contigu dans un tableau d’entiers. La solution à ce problème a de nombreuses applications, dans des domaines tels que la finance, l’analyse de données et le traitement du signal. L’algorithme le plus efficace pour résoudre ce problème est l’algorithme de Kadane.
Qu’est-ce que l’algorithme de Kadane ?
L’algorithme de Kadane est une approche efficace pour résoudre le problème du sous-réseau contigu maximal. L’algorithme fonctionne en calculant le local_maximum et le global_maximum. En itérant sur le tableau en commençant par la gauche, ces variables sont mises à jour à chaque étape, le maximum local_maximum remplaçant jusqu’à présent le global_maximum si sa valeur est supérieure. Une fois que tous les local_maximums ont été calculés, le sous-tableau contigu maximal est connu et égal au global_maximum.
Quelle est l’approche par force brute pour résoudre le problème du sous-tableau maximal ?
L’approche par force brute consiste à parcourir tous les sous-tableaux possibles d’un tableau et à calculer les sommes des sous-tableaux. Le sous-réseau contigu maximum peut alors être trouvé, mais le processus n’est pas très efficace puisque chaque sous-réseau doit être calculé.
Quels sont les inconvénients à utiliser l’algorithme de Kadane ?
Bien que l’algorithme de Kadane soit simple et efficace, il ne peut vraiment être utilisé que pour résoudre le problème du sous-réseau maximum. La sortie qu’il produit est également limitée, car il ne contient que la somme du sous-tableau maximum. Aucune information n’est fournie sur la matrice elle-même, ce qui peut être nécessaire pour certaines applications. Enfin, bien que l’algorithme soit rapide, la solution n’est pas optimale dans tous les cas.
Quelle est la complexité temporelle de l’algorithme de Kadane ?
La complexité temporelle de L’algorithme de Kadane est O(n).
L’algorithme de Kadane peut-il être utilisé avec des tableaux non contigus ?
Non, l’algorithme ne peut pas être utilisé avec tableaux non contigus.
Comment modifier l’algorithme de Kadane pour trouver le sous-tableau avec la somme minimale ?
Nous pouvons simplement remplacer la fonction maxsize par minsize , et initialiser les variables à l’infini au lieu de zéro.
L’algorithme de Kadane peut-il être utilisé avec un tableau avec tous les entiers négatifs ?
Oui, l’algorithme renvoie le sous-tableau avec la somme la moins négative dans ce cas.