Como dice Wikipedia:
Un algoritmo codicioso es un algoritmo que sigue la heurística de resolución de problemas de hacer la elección óptima localmente en cada etapa con la esperanza de encontrar un óptimo global
Cual es nuestro problema Necesitamos encontrar el árbol de expansión mínimo del gráfico dado. Esta es una optimización global que debemos hacer. No nos importan los bordes individuales que forman parte del árbol de soluciones. De hecho, si lo piensa, bien podría suceder que un borde más pesado de un vértice sea parte de la solución, mientras que un borde más ligero no figura en él.
- ¿Deberíamos permitir patentes sobre algoritmos?
- ¿Es adecuado usar un algoritmo de hash perceptual para desarrollar un motor de búsqueda de imágenes?
- ¿Cómo funcionan los algoritmos de YouTube?
- ¿Cuándo debería mirar la solución de algún problema algorítmico?
- Hago segmentación usando el algoritmo de cambio medio en MATLAB, pero obtengo mis objetos segmentados. ¿Cómo puedo fusionar partes segmentadas de mi objeto que son diferentes por color y tamaño?
¿Y cómo resuelve el problema el algoritmo de Kruskal? Simplemente selecciona el borde más pequeño en cada paso y lo agrega al árbol si mantiene intacta la propiedad del árbol. En este momento no nos preocupamos por lo que sucederá cuando agreguemos los bordes más pesados a la mezcla. Esto parecería contradictorio para una persona que no ha visto el análisis del algoritmo debido a la observación anterior de que un borde más pesado podría ser parte de la solución mientras que un borde más ligero no figura en él. Sin embargo, podemos hacer la elección óptima a nivel local de elegir el siguiente borde más ligero porque hemos demostrado que el borde agregado no puede reemplazar un borde existente en una solución óptima. El hecho de que estamos ignorando el efecto de todos los bordes futuros (más pesados) mientras procesamos el borde actual es lo que hace que esto sea codicioso.
Para comprender esto, considere otro problema: dada una matriz que contiene enteros positivos, elija el subconjunto de elementos que proporciona la suma máxima con la restricción de que no se deben seleccionar dos elementos adyacentes.
Si tratamos de resolver esto de la manera de Kruskal, clasificaríamos la matriz en orden decreciente y elegiríamos los elementos y los agregaríamos a la suma siempre que el elemento actual en consideración no sea adyacente a ningún elemento existente en la matriz. Pero si lo aplicamos a la matriz [6,10,6] el algoritmo de Kruskalish devolvería que la solución óptima es 10 mientras que la óptima real es 12.
