Tabla de contenido:
Definición: ¿Qué significa el algoritmo codicioso?
Un algoritmo codicioso es una estrategia algorítmica que hace la mejor elección óptima en cada pequeña etapa con el objetivo de que esto finalmente conduzca a una solución óptima a nivel mundial. Esto significa que el algoritmo elige la mejor solución en este momento sin tener en cuenta las consecuencias. Elige el mejor resultado inmediato, pero no considera el panorama general, por lo tanto, se considera codicioso.
Techopedia explica el algoritmo codicioso
Un algoritmo codicioso funciona al elegir la mejor respuesta posible en cada paso y luego pasar al siguiente paso hasta que llegue al final, sin tener en cuenta la solución general. Solo espera que el camino que tome sea el óptimo a nivel mundial, pero como se ha demostrado una y otra vez, este método a menudo no ofrece una solución óptima a nivel mundial. De hecho, es completamente posible que las soluciones a corto plazo más óptimas conduzcan al peor resultado global posible.
Piense en ello como tomar muchos atajos en un negocio de fabricación: a corto plazo, se ahorran grandes cantidades en el costo de fabricación, pero esto eventualmente conduce a una caída ya que la calidad se ve comprometida, lo que resulta en retornos de productos y bajas ventas a medida que los clientes se familiarizan con el Producto "barato". Pero este no es siempre el caso, hay muchas aplicaciones en las que el algoritmo codicioso funciona mejor para encontrar o aproximarse a la solución óptima global, como la construcción de un árbol Huffman o un árbol de aprendizaje de decisiones.
Por ejemplo: tome el camino con la suma más grande en general. Un algoritmo codicioso tomaría el camino azul, como resultado de la miopía, en lugar del camino naranja, que produce la suma más grande.
Componentes:
- Un conjunto de datos candidato que necesita una solución.
- Una función de selección que elige al mejor contribuyente para la solución final
- Una función de viabilidad que ayuda a la función de selección al determinar si un candidato puede contribuir a la solución.
- Una función objetivo que asigna un valor a una solución parcial.
- Una función de solución que indica que se ha descubierto la solución óptima.
