Definición - ¿Qué significa 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 eventualmente conduzca a una solución globalmente óptima. Esto significa que el algoritmo elige la mejor solución en este momento sin tener en cuenta las consecuencias. Selecciona la mejor salida inmediata, pero no considera el panorama general, por lo que se considera codicioso.
Techinfo explica el algoritmo codicioso
Un algoritmo codicioso funciona eligiendo la mejor respuesta posible en cada paso y luego pasando al siguiente paso hasta llegar 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 no suele ofrecer una solución óptima a nivel mundial. De hecho, es muy 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 costos de fabricación, pero esto eventualmente conduce a la caída ya que la calidad se ve comprometida, lo que resulta en devoluciones 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 al construir un árbol de Huffman o un árbol de aprendizaje de decisiones.
Por ejemplo: tome la ruta con la mayor suma total. Un algoritmo codicioso tomaría el camino azul, como resultado de la miopía, en lugar del camino naranja, que produce la mayor suma.
Componentes:
- Un conjunto de datos candidato que necesita una solución
- Una función de selección que elige al mejor contribuyente a 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.