close

Algorithme gourmand (Greedy Algorithm) dans Java  : expliqué avec des exemples

L'algorithme gourmand est une technique d'optimisation en Java programmation caractérisée par la sélection de la meilleure solution à chaque étape sans revisiter ni considérer l'avenir. Au lieu d’examiner l’ensemble de l’espace d’états, cet algorithme choisit la meilleure option actuelle et espère que cela conduira à une solution optimale globale.

Comment fonctionne l'algorithme gourmand

  1. Étape 1 :  Partez de l'état initial.

  2. Étape 2: A chaque étape, l'algorithme sélectionne la meilleure option parmi les options disponibles en fonction d'une fonction d'évaluation.

  3. Étape 3: L'algorithme passe à un nouvel état en choisissant la meilleure option.

  4. Étape 4 : Le processus se poursuit jusqu'à ce qu'une condition de résiliation soit remplie ou qu'il n'y ait plus d'options parmi lesquelles choisir.

  5. Étape 5 : Renvoyez la solution trouvée.

Avantages et inconvénients de l'algorithme gourmand

Avantages:

  • Simplicité : Facile à comprendre et à mettre en œuvre.
  • Efficacité : nécessite souvent moins de temps de calcul et de mémoire par rapport à certains autres algorithmes d'optimisation.
  • Idéal pour les problèmes sous-optimaux : convient aux problèmes pour lesquels la prise en compte de toutes les possibilités est trop complexe.

Désavantages:

  • Aucune garantie optimale globale : l'algorithme peut s'arrêter à une solution optimale locale sans trouver la solution optimale globale.
  • Manque de prévoyance : l’algorithme ne prend souvent pas en compte les conséquences des décisions antérieures.

Exemple et explication

Un exemple courant de l’algorithme gourmand est la recherche du problème du « Kème élément le plus grand ». Voyons comment fonctionne cet algorithme :

import java.util.Arrays;  
  
public class GreedyAlgorithmExample {  
    static int findKthLargest(int[] nums, int k) {  
        Arrays.sort(nums); // Sort the array  
        return nums[nums.length- k]; // Return the kth largest element  
    }  
  
    public static void main(String[] args) {  
        int[] nums = {3, 1, 2, 4, 5};  
        int k = 2;  
        int result = findKthLargest(nums, k);  
        System.out.println("The " + k + "th largest element is: " + result);  
    }  
}

Dans l'exemple ci-dessus, nous utilisons l'algorithme gourmand pour trouver le deuxième plus grand élément dans un tableau d'entiers. Cet algorithme trie simplement le tableau et renvoie le kième plus grand élément. Bien qu'il ne soit pas garanti qu'il s'agisse de l'optimum global, il s'agit d'une solution relativement bonne à ce problème.