close

Algoritmo codicioso (Greedy Algorithm) en Java: explicado con ejemplos

El Algoritmo Codicioso es una técnica de optimización en Java programación que se caracteriza por seleccionar la mejor solución en cada paso sin revisar ni considerar el futuro. En lugar de examinar todo el espacio de estados, este algoritmo elige la mejor opción actual y espera que esto conduzca a una solución óptima global.

Cómo funciona el algoritmo codicioso

  1. Paso 1: comience desde el estado inicial.

  2. Paso 2: En cada paso, el algoritmo selecciona la mejor opción entre las opciones disponibles en función de una función de evaluación.

  3. Paso 3: El algoritmo pasa a un nuevo estado eligiendo la mejor opción.

  4. Paso 4: El proceso continúa hasta que se cumple una condición de terminación o no hay más opciones para elegir.

  5. Paso 5: devolver la solución encontrada.

Ventajas y desventajas del algoritmo codicioso

Ventajas:

  • Simplicidad: Fácil de entender e implementar.
  • Eficiencia: a menudo requiere menos tiempo de cálculo y memoria en comparación con otros algoritmos de optimización.
  • Ideal para problemas subóptimos: Adecuado para problemas en los que considerar todas las posibilidades es demasiado complejo.

Desventajas:

  • Sin garantía de óptimo global: el algoritmo puede detenerse en una solución óptima local sin encontrar la solución óptima global.
  • Falta de previsión: el algoritmo muchas veces no considera las consecuencias de decisiones anteriores.

Ejemplo y explicación

Un ejemplo común del algoritmo codicioso es encontrar el problema del "K-ésimo elemento más grande". Veamos cómo funciona este algoritmo:

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

En el ejemplo anterior, utilizamos el algoritmo codicioso para encontrar el segundo elemento más grande en una matriz de números enteros. Este algoritmo simplemente ordena la matriz y devuelve el késimo elemento más grande. Aunque no se garantiza que sea el óptimo global, es una solución relativamente buena para este problema.