avara

Estrategia de métodos de búsqueda Informada (Heurística)
Consiste en como una búsqueda informada (en la que se utiliza el conocimiento específico del problemas, fuera de la definición del mismo) puede hallar soluciones de una forma más eficiente que una estrategia no informada.
Búsqueda primero el mejor.
A su forma general se le llama búsqueda primero el mejor. Este tipo de búsqueda es uncaso particular del algoritmo general de búsqueda en árboles o grafos, en la cual se selecciona un nodo para la expansión basada en una función de evaluación.
Este tipo de búsqueda es respetable pero inexacto. Dado que si nosotros supiéramos exactamente cual nodo expandir primero como el mejor de ellos, dejaría de ser una búsqueda y se convertiría en un camino hacia la meta. Lo único que sepuede hacer es escoger el nodo que aparenta ser el mejor según la función de evaluación. Por ende dependemos mucho de cuan bien definida esta dicha función.
Existe un grupo de algoritmos de búsqueda primero el mejor con funciones de evaluación diferentes. La diferencia radica en que estos emplean en sus algoritmos una función heurística h(n).
h(n)= coste estimado del camino más barato desde el nodon hacia el objetivo
Las funciones heurísticas son la manera más usada de transmitir el conocimiento adicional del problema al algoritmo de búsqueda
Búsqueda Avara o búsqueda voraz, primero el mejor (greedy search)
Esta búsqueda trata de expandir el nodo más cercano al objetivo, suponiendo que probablemente conducirá rápidamente a una posible solución. Es así como se evalúa los nodos utilizandola función heurística: fn=h(n).
Ejemplo:
Supongamos que un turista llega a México y está decidido a tener la mejor experiencia de su vida pues es la primera vez que llega a un país extranjero. Sin embargo, nuestro amigo a quien llamaremos NATEL no le gusta gastar y prefiere ahorrar lo más que pueda pero quiere llegar a su objetivo de todas maneras.
Evaluaremos los casos en los que se quieraahorrar tiempo, luego dinero y finalmente ambos y veremos cómo le iría a nuestro amigo NATEL en su viaje a México.
Se muestra a continuación el cuadro con las DLR a Chiapas que será nuestro destino objetivo.
DISTANCIA EN LINEA RECTA DESDE CHIAPAS
Distancia en Línea Recta
DLR
desde Chiapas a :
Sonora 970.95
Chihuahua 920.19
Coahuila 896.75
Durango 864.66
Nuevo León 850.99
Sinaloa 901.86Nayarit 645.24
Jalisco 564.87
Michoacán 370.66
Oaxaca 124.15
Tabasco 98.56
Chiapas 0
Hidalgo 494.31
San Luis Potosí 639.35
Veracruz 227.79
(En Km.)

Primer escenario (Ahorrar tiempo, la ruta más corta)

Usaremos el método de búsqueda avara para solucionar este problema.
Partiremos desde la ciudad de Coahuila y tenemos como destino la ciudad de Chiapas, entonces:
ExpandimosCoahuila:
Vemos que la distancia más corta es hacia Nueva León, con una distancia de 850.99km.
Expandimos Nueva León:
Vemos que la distancia en este caso es San Luis Potosí, con una distancia de 639.35 km. Adicionalmente se puede mencionar que es preferible no permitir el retroceso al momento de la búsqueda.
Expandimos San Luis Potosí:
Vemos que en esta ciudad (nodo) que la ciudad más próxima anuestro destino será Hidalgo, con una distancia de 494.31 km. Por lo tanto tomaremos esta ciudad.
Expandimos Hidalgo:
En este punto se observa que la ciudad más próxima a nuestro destino es Veracruz, con una distancia de 227.79km. Entonces, esta será nuestra siguiente ciudad a tomar.
Expandimos Veracruz:
Al expandir Nagoya, observamos que la ciudad con distancia menor hacia nuestro destino esTabasco, con una distancia de 98.56km.
Expandimos Tabasco, observamos que la distancia menor a nuestra ciudad es Chiapas.
Con todos estos pasos podemos apreciar que encontramos una solución hacia nuestro objetivo, sin embargo, no se puede asegurar que esta solución será óptima.
La ruta escogida para este tipo de búsqueda seria:
Coahuila → Nuevo León → San Luis Potosí → Hidalgo → Veracruz →...