Algoritmos voraces

Los algoritmos voraces tratan de mejorar mediante una búsqueda local, el resultado actual. Esta búsqueda se hace mediante pequeños pasos sobre un resultado inicial a través de iteraciones, manteniendo las restricciones/limites del problema.

Haré nuevos post, explicando algoritmos voraces en concreto, pero este no será el caso en el que entremos en implementaciones.

ALGORITMO BASADO EN RESULTADOS

En este tipo de algoritmos donde nos centramos en los resultados, el “viaje” es indiferente, por lo tanto no necesitamos guardar todo el árbol de estados. En este tipo de búsquedas locales, trabajamos sobre un estado al cual mejoramos acercándonos o hallando la solución, tras aplicar el cambio al estado del cual partimos llegamos al estado vecino.

HALLANDO RESULTADOS

Si miramos la gráfica del principio del post, y realmente nos hallamos en el punto “current state” y el algoritmo decide ir hacia la derecha ira encontrando estados vecinos mejorando el estado actual, hasta que llegue al máximo local, el algoritmo podría interpretar que esta en el máximo de la función, en cualquier caso, como he dicho antes, estará en un máximo local.

HEURISTICA CONSTRUCTIVA / CONSTRUCTIVOS VORACES

Si queremos utilizar algoritmos voraces, podriamos empezar por una busqueda aleatoria de un resultado que respete las limitaciones de nuestro problema.

Pero si aplicamos heuristica constructiva, para hallar una solución inicial pseudo optima, y nos acerque al máximo local, mejorará las condiciones en nuestro vorzas, para hallar la mejor solución posible.

Obviamente en los algoritmos constructivos voraces, requiere una buena definición heurística, para que esto se cumpla

Deja una respuesta

A %d blogueros les gusta esto: