Busqueda Avara.docx 2s4b2m

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 un caso 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 se puede 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 . = coste estimado del camino más barato desde el nodo n 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 utilizando la función heurística: . 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 quiera ahorrar 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.86 Nayarit 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: 1. Expandimos Coahuila: Vemos que la distancia más corta es hacia Nueva León, con una distancia de 850.99km. 2. 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. 3. Expandimos San Luis Potosí: Vemos que en esta ciudad (nodo) que la ciudad más próxima a nuestro destino será Hidalgo, con una distancia de 494.31 km. Por lo tanto tomaremos esta ciudad. 4. 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. 5. Expandimos Veracruz: Al expandir Nagoya, observamos que la ciudad con distancia menor hacia nuestro destino es Tabasco, con una distancia de 98.56km.

6. 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

Tabasco

Chiapas

El costo de esta ruta será de: s/. 86 + s/. 110 + s/. 90 + s/. 100 + s/. 80 + s/. 50 = s/.516

ESQUEMA DE LA BUSQUEDA VORAZ, EL MEJOR PRIMERO.

Segundo escenario (Disminuir costos, la ruta más económica)

En este escenario se puede presentar que conozcamos exactamente cuáles son las rutas que nos encaminan hacia el destino y además tenemos los costos de las mismas, entonces para llegar a nuestro objetivo por el método de búsqueda avara, tomando como iniciativa ahorrar ahora la variable dinero, en cada nodo se elegirá el menor costo entre los posibles caminos que tenemos. De igual manera que el escenario de búsqueda avara anterior, se puede llegar a alcanzar una solución, sin embargo, no necesariamente esta sea óptima. De igual manera se tomara como partida la ciudad de Coahuila, y el destino será la ciudad de Chiapas, entonces: 1. Expandimos Coahuila, tenemos tres rutas posibles: Durango con un costo de S/. 120 y Nueva León con s/. 86 y Sinaloa con un costo de s/. 175, elegiremos la ruta menos costosa, es decir nos dirigimos hacia Nueva León. 2. Expandimos Nueva León, en este punto al expandir el nodo, la única ruta posible hacia nuestro objetivo es ir hacia San Luis Potosí, con un costo de s/. 110 3. Expandimos San Luis Potosí, expandimos este nodo y se nos presenta dos destinos: Nayarit, con un costo s/105 e Hidalgo con un costo de s/. 90. Escogeremos la ruta menos costosa, la cual es Hidalgo. 4. En Hidalgo expandimos este nodo y se nos presenta cuatro destinos: Nayarit, con un costo s/105, Jalisco con un costo de s/. 84, Michoacán con un costo de s/.50 y Veracruz con un costo de 100. Escogeremos la ruta menos costosa, la cual es Michoacán.

5. En Michoacán tenemos la ruta Oaxaca con un costo de s/. 120. 6. En Oaxaca elegimos la ruta a Chiapas (nuestro objetivo) con un costo de s./ 70. Con todos estos pasos podemos apreciar que no hemos encontrado una solución hacia nuestro objetivo lo que nos diría que el turista por querer ahorrar dinero termina no llegando a su destino. La ruta escogida para este tipo de búsqueda seria: Coahuila

Nueva León

San Luis Potosí

Hidalgo

Michoacán

El costo de esta ruta será de: s/. 86 + s/. 110 + s/. 90 + s/. 50 + s/. 120 + s/. 70 = s/.526

Oaxaca

Chiapas

Búsqueda A*: Minimizar el costo estimado total de la solución. Esta es la forma de búsqueda más ampliamente conocida de la búsqueda de primero el mejor, conocida como Búsqueda A-estrella. Consiste en evaluar los nodos combinando , el costo para alcanzar el nodo y , el costo de ir al nodo objetivo, quedando:

Dado que la nos da el costo del camino desde el nodo inicio al nodo camino más barato desde al objetivo, tenemos:

, y la

el costo estimado del

Resulta que esta estrategia es más que razonable, siempre y cuando que la función heurística ciertas condiciones (heurística isible), la búsqueda A*, es tanto completa como óptima.

satisfaga

Al hablar de heurística isible, es decir, con tal que nunca sobrestime el costo para alcanzar a nuestro objetivo. Las heurísticas isibles son por naturaleza optimistas, dado que piensan que el costo de resolver los problemas es menor que el que es en la realidad. Ya que es el costo exacto para alcanzar a , tenemos como consecuencia inmediata que nunca sobrestima el costo verdadero de una solución a través de . En la búsqueda avara, se reduce el el cual es el costo hacia la meta, pero no es del todo óptimo ni tampoco es completo. La búsqueda de costo uniforme, reduce el , el costo de ruta, siendo así optimo y completo, sin embargo no es eficiente. Si empleamos este tipo de búsqueda, al caso anterior entonces obtendríamos: 1. Partimos de Coahuila con , expandimos los posibles destinos, siendo: Nueva León Durango Tomamos el mínimo, entonces elegimos el destino Nueva León. 2. Al expandir Nueva León, tenemos los siguientes destinos: San Luis Potosí Tomamos el mínimo, entonces elegimos el destino Tottori. 3. Expandimos San Luis Potosí, tendremos los siguientes destinos: Nayarit Hidalgo Tomamos el mínimo, entonces elegimos el destino Hidalgo. 4. Expandimos Hidalgo, tendremos los siguientes destinos: Jalisco Michoacán 50 + 370.66 = 420.66 Veracruz Tomamos el mínimo, entonces elegimos el destino Veracruz. 5. Expandimos Veracruz, tendremos los siguientes destinos:

Oaxaca Tabasco Tomamos el

mínimo, entonces elegimos el destino Tabasco.

6. Expandiendo Tabasco, vemos el último posible viaje que es a nuestro objetivo “Chiapas”. Chiapas = 0 + 50 = 50