Busqueda Heuristica

puntos a trabajar:
I

• Complejidad, costo uniforme, heuristica pura, A*

II. Algoritmo A*

• Que es?
• Como funciona?
• Algoritmo
• Prueba de escritorio para un ejemplo

III Heuristica

• Que es?
• Admisibilidad
• Consistencia
• Monotonía
• Heuristica mas informadas

SOLUCION

I

• Complejidad, costo uniforme, heuristica pura, A*

La complejidad de un algoritmo de búsqueda heuristica esta dada dependiendo de la calidad de la heuristica que se este utilizando, ya que debido a esto, al desarrollar el algoritmo de búsqueda, este puede tomar un camino u otro que puede o no estar mas cerca de la solución dependiendo del tipo de heuristica utilizada, de tal forma que si la heuristica es buena, al recorrer la búsqueda con el fin de encontrar una solución, cada paso que de estará mas cerca de la solución, pero el resultado final, estará ligado a la heuristica programada, haciendo que la complejidad temporal y espacial varié dependiendo de la técnica aplicada.

En el caso de la heuristica pura, lo que dictamina es que al momento de recorrer el camino en busca de la solución, elija el camino que tenga menor coste para recorrerlo y así avanzar en la búsqueda de la solución, el costo de este camino esta dado por el algoritmo heuristico que se plantee al momento de buscar la solución, de esta forma, se tiene una búsqueda un poco mas dirigida y distinta de la búsqueda ciega la cual no tiene una guía para recorrer el camino y encontrar la solución.

En el caso de A* ya utiliza dos tipos de heuristicas, en la cual se tiene en cuenta el costo del camino a recorrer, y una estimación de lo cerca que esta cada camino a recorrer de la solución final, de tal forma que tiene en cuenta dos tipos de heuristicas, y por medio del algoritmo, escoge el camino y así, se acerca en su búsqueda de la solución final.

II. Algoritmo A*

• Que es?

El algoritmo A* es un tipo de búsqueda la cual aplica dos tipos de heuristica para buscar la mejor solución a un problema o búsqueda planteada desde un estado inicial, a un estado objetivo o estado final.

• Como funciona?

El algoritmo evalúa dos factores principales para el recorrido en su búsqueda de la mejor solución, uno de ellos es el coste del camino a recorrer que esta dado por  un tipo de heuristica planteada inicialmente, y otro por una estimación del coste del camino del posible estado a escoger y el estado objetivo o el estado final, de tal manera que suma el coste de las dos heuristicas, y el camino que menor coste tenga, sera el seleccionado para recorrer.

• Algoritmo

A continuación se presenta el algoritmo A* sobre grafos:

1) Open<<-- nodo raiz.

2)Si Open є 0, fallo stop. sino n<<-- estrae_minimo(open).

3)Si n objetivo, exito stop. sino añade n a closed y generar los sucesores de n(expansion de n).

4)para cada sucesor n hacer:

  4.1)si n є open reetiquetar n' con el camino mas corto

  4.2)si n' є closed, ignorar n'.

  4.3)si n' ¢ open y n' ¢ closed, Añadir n' a open

  4.4)ir a paso 2

• Prueba de escritorio para un ejemplo

III Heuristica

• Que es?

la heuristica podríamos definirla como un tipo de reglas, procedimientos, pasos a seguir a la hora de implementar una posible solucion a un problema planteado, te tal forma, que esta heuristica(reglas, procedimientos, pasos) nos ayudan a direccionar nuestra solución en busca de la mas optima o mejor solución.

• Admisibilidad

la admisibilidad consiste básicamente en no sobrestimar el coste de la solución mas optima con la heuristica que se esta planteando, es decir, que el costo real del camino total del nodo escogido hasta la solución deba ser igual o menor al costo estimado de la heuristica planteada, para ello se tiene la siguiente formula:

A*: h admisible 

h(n): estimación de coste mínimo desde n hasta una solución 

h*(n): coste mínimo desde n hasta una solución 

h admisible ssi h(n) ≤ h*(n) ∀n 

Si h admisible, A* encuentra la solución óptima

• Consistencia

la consistencia es básicamente no sobrestimar el coste del camino que se quiere tomar desde el estado o nodo origen hasta el estado o nodo destino que conlleva ese camino, de tal forma que se tiene en cuenta que el coste estimado del camino desde el estado o nodo origen hasta la solución, debe ser menor o igual al costo estimado desde el estado o nodo destino hasta la solución mas el coste del camino a recorrer desde el estado o nodo origen hasta el estado o nodo destino, para ello se tiene la siguiente formula:

h(n): estimación de coste mínimo desde n hasta una solución

h*(n): coste mínimo desde n hasta una solución

h admisible ssi h(n) ≤ h*(n) ∀n

Si h admisible, A* encuentra la solución óptima

• Monotonía

la monotonía trata sobre el costo de los sucesores de un estado, es decir, los posibles caminos que se pueden tomar desde un nodo o estado inicial a un nodo o estado sucesor de tal manera que la heuristica planteada en el algoritmo de solución del nodo o estado origen sea menor que la estimación del coste del estado o nodo sucesor hasta la solución mas el coste del camino de estado o nodo origen hasta el estado o nodo sucesor, esto se explica mediante la formula:

h(n): estimación de coste mínimo desde n hasta una solución

h(n'): coste mínimo desde n' hasta una solución

∀ n, n’∈succ(n)

h monótona ssi h(n) ≤ c(n,n’) + h(n’)

• Heuristica mas informadas

la heuristica mas informada consiste especialmente en el tipo de heuristica que utilicemos, ya que esto, nos da un coste estimado de el coste desde un nodo o estado hasta una solucion, por ende, la heuristica que planteemos podria realizar un coste distinto para cada algoritmo heuristico, de tal forma que nos harian recorrer mas o menos estados o nodos posibles, de esta dforma llegamos a la siguiente conclusion la cual esxpresaremos mediante la formula:

nodos (A*, h): nodos expandidos por A* con h

h1 y h2 admisibles

h2 es más informada que h1 sii h2(n) > h1(n) ∀n 

nodos (A*,h2) ⊂ nodos (A*,h1)

Bibliografia:

• http://www.iiia.csic.es/~pedro/busqueda3-A*.pdf
• https://ccc.inaoep.mx/~jagonzalez/AI/Sesion5_Busquedas2.pdf