Algorithme de Kadane : une approche efficace du problème de sous-réseau maximum, expliquée avec des photos

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 du sous-réseau maximum.

Qu’est-ce que le problème du 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 contigu. En termes simples, la tâche que présente ce problème est de trouver le sous-tableau contigu maximum dans un tableau, arr[], de taille N. Autrement dit, trouvez la somme maximale possible de l’ajout 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, soit 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 que l’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 façon, 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 continuer 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 ensembles de données plus volumineux. 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 plus é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 sont alors accessibles lorsque nous résolvons le même type de problème, ce qui évite d’avoir à les résoudre à nouveau et accélère les calculs globaux.

Ce serait vraiment bénéfique si nous pouvions appliquer les principes de la programmation dynamique à notre problème de sous-réseau maximum. Heureusement, nous le pouvons, et c’est exactement ce que l’algorithme de Kadane se propose de faire. Alors, allons-y.

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

Prenons le tableau [4, -1, 2, 1] encore. 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]UN[n-2] jusqu’à ce que nous les ayons tous terminés.

En regardant les deux derniers éléments, A[3] et un[4], nous pouvons voir que le local_maximum est respectivement de 5 et 6. 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]qui est 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 à la base de 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’indice i-1.

Il suffit donc de trouver le maximum de A[i] et un[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-tableau maximum.

• L’algorithme ne nécessitera qu’une seule boucle, itérant de i[0[ to 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

Premièrement, 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 la 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 varie et est initialement défini sur 0.

« for » fait référence à une boucle, qui est utilisée 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 localMaxSum précédent.

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 maximal 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-réseau contigu maximum a une somme de 11.

Emballer

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…

Algorithme de Kadane : une approche efficace du problème de sous-réseau maximum, expliquée avec des photos FAQ (Foire aux questions)

Qu’est-ce qu’un sous-réseau ?

Un sous-tableau fait partie d’un tableau qui est ininterrompu, c’est-à-dire sans rupture entre les entiers. Ceci est décrit comme contigu. Un sous-réseau peut être composé d’un seul é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 permettant de résoudre des 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.

Quel est le problème de sous-tableau maximum ?

Il s’agit d’un problème de programmation classique qui consiste à trouver le plus grand 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.

Quel est 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, alors le sous-tableau contigu maximum est connu et égal au global_maximum.

Quelle est l’approche de la force brute pour résoudre le problème du sous-réseau maximum ?

L’approche par force brute consiste à itérer sur tous les sous-tableaux possibles dans 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, si l’algorithme est 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 des 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 renverra le sous-tableau avec la somme la moins négative dans ce cas.