Un algoritmo voraz es un algoritmo simple e intuitivo que se utiliza en problemas de optimización. El algoritmo hace la elección óptima en cada paso, ya que intenta encontrar la forma óptima general de resolver todo el problema. Los algoritmos voraces tienen bastante éxito en algunos problemas, como la codificación de Huffman, que se utiliza para comprimir datos, o el algoritmo de Dijkstra, que se utiliza para encontrar el camino más corto a través de un grafo o el algoritmo de Prim o Kruskal.
Los algoritmos voraces tienen las siguientes ventajas y desventajas:
-
Son fáciles de implementar, por lo general las soluciones basadas en algoritmos voraces no exigen una complejidad alta.
-
Son fáciles de analizar, en comparación a técnicas como divide y conquista, donde en esta última técnica es difícil analizar si la técnica ralentiza o incrementa la velocidad del algoritmo.
-
La parte difícil de los algoritmos voraces es entender la correctitud del algoritmo, incluso si se tiene el algoritmo correcto es difícil es comprobar por qué está correcta.
Principio de la optimalidad
Cuando hablamos de optimizar nos referimos a buscar alguna de las mejores soluciones de entre muchas alternativas posibles. Dicho proceso de optimización puede ser visto como una secuencia de decisiones que nos proporcionan la solución correcta. Si, dada una subsecuencia de decisiones, siempre se conoce cuál es la decisión que debe tomarse a continuación para obtener la secuencia óptima, el problema es elemental y se resuelve trivialmente tomando una decisión detrás de otra, lo que se conoce como estrategia voraz.
Ejemplo de un algoritmo voraz: Árbol de expansión mínima
Dado un grafo cuyos nodos están conectados se necesita conocer el camino que conecta todos los nodos de este grafo y la ruta tiene el menor coste.
Algoritmo de Kruskal
El algoritmo de Kruskal se considera un algoritmo voraz debido a que toma la decisión optima en cada paso esperando que la respuesta conjunta sea correcta.
El algoritmo de Kruskal busca calcular el árbol de expansión mínima, bajo los siguientes pasos:
-
Ordenar las aristas en orden ascendente con respecto al peso.
-
Elegir la arista de menor coste/peso (Decisión óptima local).
-
revisar si no se forma un ciclo entre vértices con la solución actual, si se forma un ciclo se descarta la arista seleccionada.
-
Se repite el paso 2 y 3 hasta tener una cantidad de aristas que sean menor a la cantidad de vértices menos uno.
Ejemplo
Vamos a utilizar el siguiente grafo como ejemplo.
Teniendo la lista de aristas como:
Como primer paso se deben de ordenar las aristas en orden ascendente.
Como siguiente paso se tiene que comer la arista con peso 2 y sus vértices.
Se selecciona la arista con peso de 3 que va entre el vértice 1 y el 0, verificando que no se forme un ciclo en el proceso.
Como último paso, debido a que el algoritmo se detiene cuando encuentra V-1 aristas (V siendo la cantidad de vértices) seleccionamos la arista de peso 4 que va entre el vértice 2 y 3.
Este sería el árbol de expansión mínima que resaltando en el grafo original sería el siguiente:
Referencias
Moore K, Khim J, & Ross E. Greedy Algorithms. Recuperado 16 junio 2020, de https://brilliant.org/wiki/greedy-algorithm/
Sharma A. Basics of Greedy Algorithms Tutorials & Notes. Recuperado 15 junio 2020, de https://www.hackerearth.com/practice/algorithms/greedy/basics-of-greedy-algorithms/tutorial/
Kruskal’s Minimum Spanning Tree Algorithm. Recuperado 15 junio 2020, de https://www.geeksforgeeks.org/kruskals-minimum-spanning-tree-algorithm-greedy-algo-2/