Algoritmos voraces (greedy): Dado un problema con n entradas, se pretende obtener un subconjunto de estas, de tal forma que satisfaga una determinada restricción de forma óptima.
💡
Este tipo de algoritmos pretenden resolver un problema tomando la mejor decisión en cada paso, sin tener en cuenta si esa decisión es la mejor para resolver el problema.Ejemplo
🧠
Dado que estos algoritmos toman la mejor decisión en cada momento, esto puede resultar en que una decisión tomada en un mometo determinado donde esta era la mejor, resulta que redirige el problema en una dirección que empeora la solución final. Sin embargo, si hubieramos escogido la segunda mejor opción en vez de la primera, esta habría resulto el problema con una solución más óptima
💡
Ejemplo real
Imagina que tenemos que repartir 6€ en el menor número de monedas posible, y en nuestro país hay monedas de 1€, 3€ y 4€.
En este caso, un algoritmo voráz comprobará en el primer paso que la mejor opcción es escoger una moneda de 4€, luego una de 1€ y finalmente una de 1€. Por lo que su solución se compone de 3 monedas: [4€, 1€, 1€]
Si embargo, la solución óptima sería usar dos monedas de 3€, osea: [3€, 3€]
📖
Características de los algoritmos voraces
🔁 Iterativos → El algoritmo se implementa de forma iterativa
☀️ Decisiones óptimas en cada iteración → El algortimo toma la mejor decisión en cada momento
🏔️ Decisiones inalterables → Una vez se toma una decisión en un paso concreto, no hay vuelta atrás
📖
Estructura de los algoritmos voraces
Se suelen definir la siguiente funciones:
Algoritmo voraz → Esta es la función que implementa el bucle iterativo que buscará la solución óptima y la devuelve
Función de selección → Determina cual es el valor que se evaluará en la siguiente iteración. Esta función seleccionará el siguiente candidato considerando que es el mejor de los disponibles
Función de factibilidad → Determina si el valor actual debe formar parte de la solución o no
Función solución → Esta función determina si se ha alcanzado los requisitos de la solución. Esta función es la encargada de para de parar el bucle
Algoritmos Voraces en Grafos
Árboles de recubrimiento mínimo
📖
Problema
Dado un grafo no dirigido y ponderado, calcular un subgrafo que conecte todos los vértices a traves de las aristas de menor peso. La suma de las aristas de la solución sea la mínima
🧠
Solución
Si el grafo es conexo, la solución será un arbol
ℹ️
Datos relevantes
💡
Se dice que un grafo G está compuesto por un conjunto de vertices V y aristas E. Tambíen cabe recordar que ∣E∣ hace referencia al número de aristas del grafo
Candidatos → Conjunto de aristas de E
Solución → Un árbol con ∣V∣ vértices (mismo número de vértices) y ∣V−1∣ aristas (tantas aristas como vértices, menos una)
Factibilidad → No existe ninºgún ciclo
Objetivo → Que la suma de las aristas incluidas en la solución, sumen el mínimo valor posible
Selección → Depende del algoritmo
Algoritmo de Kruskal
ℹ️
Buscar la en cada iteración la arista de menor peso, si esta reduce en uno la cantidad de componentes conexas, entonces añadimos dicha arista a la solución.
📖
Explicado en profundidad tendríamos que…
Dado un grafo no dirigido y ponderado. Anotaremos todas las aristas (origen, destino y peso)y a continuación creamos un subgrafo con los mismos vertices que el grafo original, pero sin aristas. De este modo, el grafo resultante tiene tantos vertices como componentes conexas. Cada vértice es una componente conexa en sí mismo
🔖
Una componente conexa es un grupo de vertices que están conectados entre sí. Ejemplo
Los siguientes ejemplos muestran las componentes conexas de un grafo de 5 vertices según las aristas que lo forman
Ejm 1: Grafo de 5 componentes conexas (grafo sin aristas)
Ejm 2: Grafo de 4 componentes conexas
Ejm 3: Grafo de 3 componentes conexas
A partir de este punto, tenemos, en cada iteración, que añadir al grafo una nueva arista. Dicha arista debe cumplir
Reduce en 1 el numero de componentes conexas del grafo (evitamos que se creen ciclos)
La nueva arista debe ser la mejor en cada caso, utilizando el peso de la arista como valor determinante, o en su defecto, el vétice de origen (orden lexicográfico)
Habremos terminado cuando el grafo sea totalmente conexo. El resultado será un árbol cuya suma de los pesos de todas las aristas será normalmente el valor de la solución
👉🏻
Proceso de selección
Para reducir la complejidad del algoritmo se recomienda ordenar la lista de aristas respecto del peso. En caso de empate, se deberán ordenar respecto del vértice de origen, y en caso de empate otra vez, respecto del vertice de destino (orden lexicográfico)
🥇
El algoritmo de kruskal encuentra la solución óptima
Algoritmo de Prim
ℹ️
Seleccionar un vértice al azar y construir el árbol a partir de él, añadiendo las aristas de
menor peso que adyacentes al nodo actual
📖
Explicado en profundidad…
Primero, escogemos un nodo al azar, y como candidatos tenemos todas las aristas adyacentes. De las aristas ayacentes, escogeremos cual será la mejor (presumiblemente la de mejor peso)
En la siguiente iteración, ahora los nodos que pertenecen a la componente conexa son, el nodo inicial y el nodo al que nos hemos conectado en el paso anterior. Ahora repetimos el primer paso de anotar como candidatos a las aristas ayacentes que apuntan a nodos que no pertenecen a la componente conexa, tomando como nodo origen cualquiera de los que pertenecen actualmente a la parte conexa. Esto quiere decir que los candidatos serán los adyacente del nodo inicial y los del segundo nodo. A continuación tomamos el mejor candidato (arista) y lo añadimos a la solución y añadimos el nodo de destino a la componente conexa
Repetimos este paso hasta que todos los nodos pertenezcan a la misma componente conexa
