[Algoritmos y Computabilidad] Algoritmos voraces

 El post de hoy está dedicado a un tipo de algoritmo llamado algoritmo voraz, se ven de manera práctica en la asignatura de Algoritmos y Computabilidad perteneciente a la rama de Computación del Grado en Ingeniería Informática.

  La principal característica de los algoritmos voraces es que toman la mejor decisión en el punto actual de la resolución del problema, sin tener en cuenta los futuros pasos. Por esto su estructura es muy sencilla y se construye de la siguiente forma:

  1. Inicialización de la estructura de datos que se va a utilizar que contiene todos los posibles candidatos a elegir.
  2.  Inicialización a "vacío" de la estructura de datos que representará al final la solución.
  3. Si el conjunto de candidatos contiene un candidato elegible, entramos en el bucle voraz. Si no se va directamente al paso 6.
  4. Seleccionamos el mejor candidato en este momento y lo añadimos al conjunto solución, además de quitarlo del conjunto de candidatos.
  5. Si el conjunto solución cumple la función solución se sale del bucle. De lo contrario se vuelve al paso 3. 
  6. Se devuelve el conjunto solución.
Sabiendo esto recalcamos los miembros que aparecen en todos los algoritmos voraces:
  • Conjunto de candidatos: es la estructura de datos del problema actual.
  • Conjunto solución: es la estructura de datos que contiene la solución.
  • Función de eligibilidad: comprueba si el conjunto de candidatos puede dar una solución.
  • Función de elección: saca el mejor candidato del conjunto de candidatos.
  • Función solución: comprueba si el conjunto solución ya es una solución definitiva.
  • Función objetivo: (es implícita) es lo que se pretende conseguir con el algoritmo completo.
 Por si me he explicado mal, o me he dejado algo en el tintero os dejo un video explicando que es un algoritmo voraz:

Uno de los ejemplo más comunes de algoritmo voraz es el árbol de expansión mínimo en el que se pretende unir a un conjunto de nodos por los caminos de mínimo coste, esto tiene su aplicación práctica en la construcción de redes de ordenadores. Os dejo un vídeo que os lo explicará muy bien, así como la práctica del algoritmo de Kruskal para este árbol de expansión mínimo.

 
Práctica del algoritmo de Kruskal en Java

0 comentarios: