Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Búsqueda Primero el Mejor

No description
by

paola Rodriguez

on 27 March 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of Búsqueda Primero el Mejor

Búsqueda Primero el Mejor
Paola Andrea Cuervo Rodriguez
Búsqueda Primero el Mejor
Esta búsqueda combina los algoritmos primero en profundidad y primero en amplitud.
Es decir, que puede empezar por un camino y cambiarse a otro que parece mejor.


Se tienen en cuenta 2 casos especiales para la búsqueda de primero el mejor:
• Búsqueda voraz primero el mejor
• Búsqueda A*


Búsqueda voraz primero el mejor
Toma en cuenta el nodo más cercano al objetivo, asumiendo llegar a una solución.
La función evaluación o heurística es f(n):
f (n) = h(n)
Donde h(n) = costo estimado del camino más barato.
Desde el nodo n hasta el objetivo.


La minimización de h(n) puede llevarnos a ventajas falsas como:
Puede hacernos difundir nodos que no son necesarios.
Se puede llegar a callejones sin salida, si no se tiene cuidado con los nodos repetidos.
No es óptima y es incompleta.


Ejemplo
Tenido en cuenta una serie de países, se quiere hallar la distancia en linea recta desde n hasta bucharest.
Donde h(n) = Distancia en Línea Recta desde la ciudad n hasta Bucharest


Características
inicio
meta
y empieza seleccionando de la lista ABIERTOS, el nodo con el menor valor de f(n).
Y es así como la solución de la Búsqueda voraz primero el mejor es:
Arad – Sibiu – Fagaras – Bucharest
Costo total: (140+99+211) = 450
Aunque:
Arad– Sibiu– Rimmicu– Pitesti- Bucharest
Costo total: (140+80+97+101) = 418
Por lo cual la solución no es óptima ya que no toma el camino por Rimnicu Vilcea y
Pitesti, que es 32 Km más corta.
Búsqueda A*
Tiene como objetivo "minimizar el costo estimado total de la solución".
donde:
g(n): costo de haber alcanzado n.
h(n): costo para llegar desde n hasta el objetivo.


costo más barato estimado de la solución a través de n
Características:
La solución es óptima siempre y cuando la
función heurística h(n) "sea una heurística admisible".
Son funciones optimistas
Es un método completo de búsqueda, es decir que termina encontrando la solución.


Teniendo en cuenta el ejemplo anterior.
Se empieza por arad, el cual tiene g(n)-> costo de haber alcanzado n que es 0.

Y h(n)-> costo para llegar desde n hasta el objetivo que es 366.

118=g(n)costo de haber alcanzado n.
329=h(n)costo para llegar desde n hasta el objetivo.
Ciber-grafía:

https://es.scribd.com/doc/102866003/Tema-6-Busqueda-Heuristica#download
pag 9-28
http://webdiis.unizar.es/~jangelb/IA-30223/3.leccion4_B%FAsquedaInformadaImp.pdf
pag 19,20,21,22





Búsqueda con memoria acotada
Búsqueda A* con profundidad iterativa (A*PI)
Ejemplo 2:
Conclusión:
En este caso se llega al destino y después se devuelve, para tomar el otro camino que parece mas "óptimo" , y vuelve a tomar el menor valor.
Luego llega al objetivo con un recorrido de menor valor a diferencia de la primera busqueda "the first best"


Mas Ejemplos...
Los fantasmas persiguen a pacman buscando el camino mas corto, en lugar de aparecer de forma aleatoria en el juego.
Es decir que:
Total Recorrido =
140 + 80 + 97 + 101 = 418
y es óptimo!

Cada iteración es una búsqueda primero en profundidad, pero modifica el limite de costo que puede utilizar f(n) .

Búsqueda Primero Mejor Recursiva (BPMR)
En este caso mantiene el f-valor del mejor camino disponible desde cualquier antecesor del nodo actual.
Y en caso de que el nodo actual exceda ese límite, vuelve al camino alternativo con mejor f-valor.
También esta actualiza los nodos hacia atrás, y no descarta volver a pasar por otro camino abandonado si el f-valor vuelve a ser mejor.

Ejemplo:
Camino hasta Rumnicu Vilcea.
El camino llega hasta Pitesti tiene un valor que debe tener en cuenta si es mayor a >415.
Y se tiene en cuenta los 2 caminos.
Búsqueda A* con memoria acotada simplificada (A*MS)


*Inteligencia artificial: modelos, técnicas y áreas de aplicación
Escrito por Maria Isabel Alfonso Galipienso,Miguel Angel Cazorla Quevedo,Otto Colomina Pardo,Francisco Escolano Ruiz,Miguel Angel Lozano Ortega
pag. 17-19
*Inteligencia Artificial e Ingenierıa
del Conocimiento autor Felix Gomez Marmol
pag 9-15
Bibliografía:
Siguiendo con el mismo ejemplo
Guarda el mejor valor f de la
hoja Pitesti 417.
Y ahora el mejor camino es fagaras
Guarda el mejor f de la hoja Fagaras que es 450 , y ahora el mejor camino es Rimnicu Viclea. donde 447 > 417
La búsqueda heurística se enfoca en encontrar algoritmos con tiempos mínimos de ejecución y óptimas soluciones.
Se puede entender como heurística como "un proceso que puede resolver un problema, aunque no ofrece ninguna garantía de solución "
Búsqueda Heurística
Se tiene en cuenta el mismo procedimiento el algoritmo A* , pero si la memoria se termina antes de encontrar la solución, se da paso a eliminar el peor nodo de acuerdo a su función heurística y se introduce el nuevo nodo.

Este juego se trata de la caída del imperio romano, y así mismo la reconstrucción, lo cual conlleva a explorar el lugar y enfrentarse a otras civilizaciones por medio de campañas.
En las campañas la planificación de caminos se utiliza para mover mecanismos de combate por todo el terreno, evadiendo obstáculos.
La búsqueda de caminos es algo fundamental a la hora de programar juegos , ya que se tiene que tener en cuenta varios métodos de búsqueda para el desarrollo de estos.
Se pueden encontrar varios ejemplos de juegos como lo es "pacman" y "age of empires" , el cual tiene como objetivo conquistar al mundo.


Sin lugar a dudas la estrategia de búsqueda de pacman toma en cuenta la busqueda de "the first best" y age of empires la Busqueda A*.
Cada estrategia que se platea es diferente aunque tienen el mismo objetivo, hallar la solución.
Full transcript