Algoritmo ganancioso (Greedy Algorithm) em Java: explicado com exemplos

O Algoritmo Ganancioso é uma técnica de otimização em Java programação caracterizada por selecionar a melhor solução em cada etapa sem revisitar ou considerar o futuro. Em vez de examinar todo o espaço de estados, este algoritmo escolhe a melhor opção atual e espera que isso leve a uma solução global ótima.

Como funciona o algoritmo ganancioso

1. Etapa 1: comece do estado inicial.

2. Passo 2: A cada passo, o algoritmo seleciona a melhor opção entre as opções disponíveis com base em uma função de avaliação.

3. Etapa 3: O algoritmo passa para um novo estado escolhendo a melhor opção.

4. Passo 4: O processo continua até que uma condição de encerramento seja atendida ou não haja mais opções para escolher.

5. Etapa 5: Devolva a solução encontrada.

Vantagens e desvantagens do algoritmo ganancioso

Vantagens:

• Simplicidade: Fácil de entender e implementar.
• Eficiência: Muitas vezes requer menos tempo de computação e memória em comparação com alguns outros algoritmos de otimização.
• Ideal para problemas abaixo do ideal: Adequado para problemas onde considerar todas as possibilidades é muito complexo.

Desvantagens:

• Nenhuma garantia de ótimo global: O algoritmo pode parar em uma solução ótima local sem encontrar a solução ótima global.
• Falta de previsão: o algoritmo muitas vezes não considera as consequências de decisões anteriores.

Exemplo e explicação

Um exemplo comum do Algoritmo Ganancioso é encontrar o problema do "Kº Maior Elemento". Vamos ver como esse algoritmo funciona:

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);  
    }  
}  

No exemplo acima, usamos o algoritmo Greedy para encontrar o segundo maior elemento em uma matriz de inteiros. Este algoritmo simplesmente classifica o array e retorna o k-ésimo maior elemento. Embora não seja garantido que seja o ideal global, é uma solução relativamente boa para este problema.