Algoritmos voraces

Algoritmo voraz
El esquema algorítmico conocido como algoritmos voraces (también Ávidos; (greedy en ingles) es el que menos dificultades plantea a la hora de diseñar y comprobar su funcionamiento. Normalmente, este esquema se aplica a los problemas de optimización.
Una aproximación voraz consiste en que cada elemento a considerar se evalúa una Única vez, siendo descartado o seleccionado, detal forma que si es seleccionado forma parte de la solución, y si es descartado, no forma parte de la solución ni volverá a ser considerado para la misma. Una forma de ver los algoritmos voraces es considerar la estrategia de vuelta atrás , en la cual se vuelve recursivamente a decisiones anteriormente tomadas para variar la elección entonces tomada, pero eliminando esa recursión y eligiendo lamejor opción.
El término voraz se deriva de la forma en que los datos de entrada se van tratando, realizando la elección de desechar o seleccionar un determinado elemento una sola vez.
Al contrario que con otros métodos algorítmicos, no siempre es posible dar una solución a un problema empleando un algoritmo voraz. No todos los problemas son resolubles con algoritmos voraces.
* Esquema
Dadoun conjunto finito de entradas C, un algoritmo voraz devuelve un conjunto S (seleccionados) tal que y que además cumple con las restricciones del problema inicial. Cada conjunto C que satisfaga las restricciones se le suele denominar prometedor, y si además logra que la función objetivo se minimice o maximice (según corresponda) diremos que S es una solución Óptima.

* Elementos de los queconsta la técnica
* El conjunto C de candidatos, entradas del problema.
* Función de selección. Informa cuál es el elemento más prometedor para completar la solución. Este elemento no puede haber sido rechazado o escogido con anterioridad. Luego, pertenecería.
* Función de factibilidad. Informa si a partir de un conjunto se puede llegar a una solución. Lo aplicaremos al conjuntode seleccionados unido con el elemento más prometedor.
* Función objetivo. Devuelve la bondad de la solución hallada. Normalmente se desea que su valor sea máximo o mínimo.
* Función solución. Comprueba si el subconjunto de candidatos forma una solución (no importa si es Óptima o no lo es).

* Funcionamiento
El algoritmo escoge en cada paso al mejor elemento posible. Actoseguido comprueba si puede ser una solución factible; elimina x y vuelve a seleccionar otro; si es factible incluye al elemento prometedor en S y comprueba si es solución. Si no lo es el proceso continúa, y si lo es, el algoritmo termina.
El algoritmo se muestra a continuación:

Esquema general de un algoritmo voraz |
función /*C es el conjunto de candidatos*/mientras y no hacer si entonces sientonces devolver /*S es una solución*/si no devolver /*No hay soluciones*/ |

Los algoritmos voraces tienden a ser bastante eficientes y pueden implementarse de forma relativamente sencilla. Su eficiencia se deriva de la forma en que trata los datos, llegando a alcanzar muchas veces una complejidad de orden lineal. Sin embargo, la mayoría de los intentos de crear un algoritmo voraz correctofallan a menos que exista previamente una prueba precisa que demuestre la correctitud del algoritmo. Cuando una estrategia voraz falla al producir resultados Óptimos en todas las entradas, en lugar de algoritmo suele denominarse heurística Las heurísticas resultan Útiles cuando la velocidad es más importante que los resultados exactos (por ejemplo, cuando resultados "bastante buenos" son suficientes).Algunos Algoritmos de ejemplo
* Problema de planificación de tareas
* Problema de la mochila
* Enunciado: "Se tiene una mochila que es capaz de soportar un peso máximo P, así como un conjunto de objetos, cada uno de ellos con un peso y un beneficio. La solución pasa por conseguir introducir el máximo beneficio en la mochila, eligiendo los objetos adecuados. Cada objeto puede...