Busquedas IA
Páginas: 8 (1822 palabras)
Publicado: 23 de octubre de 2013
Algoritmo de Búsqueda A*
A grandes rasgos la exploración A* es un algoritmo de búsqueda por grafos, este algoritmo encuentra el camino de menor coste entre un nodo origen y un nodo objetivo, esto siempre y cuando se cumplan ciertas condiciones.
Propiedades
Como todo algoritmo de búsqueda en amplitud, A* es un algoritmo completo: en caso de existir una solución, siempre dará con ella.
Sipara todo nodo n del grafo se cumple g(n) = 0, nos encontramos ante una búsqueda voraz. Si para todo nodo n del grafo se cumple h(n) = 0, A* pasa a ser una búsqueda de coste uniforme no informada.
Para garantizar que el algoritmo sea optimo, la función h(n) debe ser heurística admisible, esto es, que no sobrestime el coste real de alcanzar el nodo objetivo.
De no cumplirse dicha condición, elalgoritmo pasa a denominarse simplemente A, y a pesar de seguir siendo completo, no se asegura que el resultado obtenido sea el camino de coste mínimo. Asimismo, si garantizamos que h(n) es consistente (o monótona), es decir, que para cualquier nodo n y cualquiera de sus sucesores, el coste estimado de alcanzar el objetivo desde n no es mayor que el de alcanzar el sucesor más el coste de alcanzar elobjetivo desde el sucesor.
Por ejemplo se tiene un laberinto:
El cuadro azul es el inicio, y el cuadro rojo es la meta/objetivo, los cuadros blancos son alcanzables y los negros son restricciones.
El laberinto con valores en una matriz. Donde los ceros representan las casillas que no son alcanzables, la I representa el inicio y la F el final.
I c c c c 0 0 c c c c
0 c 0 0 c 0 c c 0 0 c
0c 0 c 0 c 0 c 0 c c
0 c 0 c c c 0 c 0 c 0
c c 0 c 0 c c c 0 c c
c 0 0 c c 0 0 0 c 0 c
c c c c 0 c c c c c c
c c 0 c 0 c 0 c 0 0 0
0 c c c 0 c c 0 c c c
0 c 0 c 0 c c c c 0 F
Valores a texto plano
Ahora, para utilizar el método A* es necesario incluir elementos heurísticos como listas de posibles movimientos aceptables y no aceptables, y calcular el objetivo utilizando " G " y " H”.G es el costo del movimiento para ir desde el punto inicial A hasta cierto punto designado, tomando en cuenta todos los puntos que cruzan para llegar hacia el punto designado.
H es el costo aproximado para llegar al objetivo final desde el punto en el que se en cuenta. Es designado H por que en teoría es una hipótesis del costo, la idea es analizar el problema para tener una medición lo másacertada posible para encontrar una buena solución.
Algoritmo Simulated Annealing
Hill-Climbing es un algoritmo incompleto porque puede estancarse en óptimos locales y no alcanzar el óptimo global pero eficiente, dado el tamaño del espacio de soluciones.
Por contra, un algoritmo que se moviese hacia un sucesor elegido de forma uniformemente aleatoria de entre un conjunto desucesores sería completo pero muy ineficiente.
El algoritmo SIMULATED ANNEALING (temple simulado) está a medio camino entre estos extremos: combina el HillClimbing con el seguimiento de un camino aleatorio de modo que se pueda conseguir tanto eficiencia como completitud.
El Modelo
El modelo de funcionamiento del algoritmo procede del proceso físico del templado de metales. Para conseguir quela estructura molecular del metal tenga las propiedades deseadas de resistencia o flexibilidad, es necesario controlar la velocidad del proceso de templado (enfriamiento). Si se hace adecuadamente, el estado final del metal es un estado de mínima energía.
El Algoritmo
El algoritmo consta de 2 elementos clave:
1. [Bucle interno] Un método que permite obtener nuevas configuraciones(estados) a partir de la actual => esquema de exploración del espacio de configuraciones.
2. [Bucle externo] Un esquema de descenso de temperatura, enfriamiento, que garantiza la convergencia a óptimos globales => mínima energía.
Bucle interno
Objetivo: encontrar la mejor configuración para la temperatura fijada.
Explora caminos de, como mucho, longitud=tope.
En lugar de elegir el ‘mejor...
A grandes rasgos la exploración A* es un algoritmo de búsqueda por grafos, este algoritmo encuentra el camino de menor coste entre un nodo origen y un nodo objetivo, esto siempre y cuando se cumplan ciertas condiciones.
Propiedades
Como todo algoritmo de búsqueda en amplitud, A* es un algoritmo completo: en caso de existir una solución, siempre dará con ella.
Sipara todo nodo n del grafo se cumple g(n) = 0, nos encontramos ante una búsqueda voraz. Si para todo nodo n del grafo se cumple h(n) = 0, A* pasa a ser una búsqueda de coste uniforme no informada.
Para garantizar que el algoritmo sea optimo, la función h(n) debe ser heurística admisible, esto es, que no sobrestime el coste real de alcanzar el nodo objetivo.
De no cumplirse dicha condición, elalgoritmo pasa a denominarse simplemente A, y a pesar de seguir siendo completo, no se asegura que el resultado obtenido sea el camino de coste mínimo. Asimismo, si garantizamos que h(n) es consistente (o monótona), es decir, que para cualquier nodo n y cualquiera de sus sucesores, el coste estimado de alcanzar el objetivo desde n no es mayor que el de alcanzar el sucesor más el coste de alcanzar elobjetivo desde el sucesor.
Por ejemplo se tiene un laberinto:
El cuadro azul es el inicio, y el cuadro rojo es la meta/objetivo, los cuadros blancos son alcanzables y los negros son restricciones.
El laberinto con valores en una matriz. Donde los ceros representan las casillas que no son alcanzables, la I representa el inicio y la F el final.
I c c c c 0 0 c c c c
0 c 0 0 c 0 c c 0 0 c
0c 0 c 0 c 0 c 0 c c
0 c 0 c c c 0 c 0 c 0
c c 0 c 0 c c c 0 c c
c 0 0 c c 0 0 0 c 0 c
c c c c 0 c c c c c c
c c 0 c 0 c 0 c 0 0 0
0 c c c 0 c c 0 c c c
0 c 0 c 0 c c c c 0 F
Valores a texto plano
Ahora, para utilizar el método A* es necesario incluir elementos heurísticos como listas de posibles movimientos aceptables y no aceptables, y calcular el objetivo utilizando " G " y " H”.G es el costo del movimiento para ir desde el punto inicial A hasta cierto punto designado, tomando en cuenta todos los puntos que cruzan para llegar hacia el punto designado.
H es el costo aproximado para llegar al objetivo final desde el punto en el que se en cuenta. Es designado H por que en teoría es una hipótesis del costo, la idea es analizar el problema para tener una medición lo másacertada posible para encontrar una buena solución.
Algoritmo Simulated Annealing
Hill-Climbing es un algoritmo incompleto porque puede estancarse en óptimos locales y no alcanzar el óptimo global pero eficiente, dado el tamaño del espacio de soluciones.
Por contra, un algoritmo que se moviese hacia un sucesor elegido de forma uniformemente aleatoria de entre un conjunto desucesores sería completo pero muy ineficiente.
El algoritmo SIMULATED ANNEALING (temple simulado) está a medio camino entre estos extremos: combina el HillClimbing con el seguimiento de un camino aleatorio de modo que se pueda conseguir tanto eficiencia como completitud.
El Modelo
El modelo de funcionamiento del algoritmo procede del proceso físico del templado de metales. Para conseguir quela estructura molecular del metal tenga las propiedades deseadas de resistencia o flexibilidad, es necesario controlar la velocidad del proceso de templado (enfriamiento). Si se hace adecuadamente, el estado final del metal es un estado de mínima energía.
El Algoritmo
El algoritmo consta de 2 elementos clave:
1. [Bucle interno] Un método que permite obtener nuevas configuraciones(estados) a partir de la actual => esquema de exploración del espacio de configuraciones.
2. [Bucle externo] Un esquema de descenso de temperatura, enfriamiento, que garantiza la convergencia a óptimos globales => mínima energía.
Bucle interno
Objetivo: encontrar la mejor configuración para la temperatura fijada.
Explora caminos de, como mucho, longitud=tope.
En lugar de elegir el ‘mejor...
Leer documento completo
Regístrate para leer el documento completo.