BUSQUEDA HEURISTICA

La búsqueda heuristica es un conjunto de métodos, formas o reglas que se usan para obtener la mejor solución posible a cierto problema, en esta clase de búsqueda se van a explicar dos métodos, el primero es  el costo uniforme y el otro es la heuristica pura, ambos se desarrollan bajo la regla de primero mejor.

Algunas características de la búsqueda eucarística son: 

* No garantiza que se encuentre una solución aunque se existan varias

* Si encuentra una solución no se asegura de que esta tenga las mejores propiedades

* En algunas ocasiones encontrara una solución en un tiempo favorable

En la siguiente imagen se muestran de forma gráfica los pasos que realiza un algoritmo de búsqueda heurística para hallar la mejor solución

Imagen tomada de:

https://people.hofstra.edu/geotrans/eng/methods/trafficcostsmin.html

Como puede apreciarse lo primero que el algoritmo hace es estudiar los posibles caminos que se pueden recorrer para llegar del punto A al F; luego, estudia cual es el costo generado de cada camino estudiando, por ultimo especifica cual es el costo mínimo y el costo  

La búsqueda eucarística pura, greddy o avara expande el nodo del menor valor de h, la operación de estimación desde n hasta el nodo solución esta dada por  h(n)

Problema de viaje por Rumania desde n hasta Bucharest

                                 Imagen tomada de:http://agentesprimavera2014.blogspot.com.co/2014/03/algoritmo-de-busquedas.html

Como puede observarse a continuación se expande el nodo con menos valor de h

Entre los algoritmos de heurística podemos encontrar el algoritmo A* creado en 1968 por Peter E Hart y Nils J Nillson, gracias a los avances que realizo Nils Nillson en el 64 del algoritmo DijKstra.

El algoritmo A estrella encuentra la ruta entre dos caminos A y B  de menor coste siempre y cuando cumplan ciertas condiciones usando una técnica de grafos con una función heurística donde la solución se da por la evaluación del progreso conseguido. El coste del algoritmo esta dado por f(x), g(x), y h(x) donde:

* f(x) =  verdadera evaluación de un nodo a determinar

*g(x) = coste del camino que se ha conseguido 

*h(x) = Estimación del punto actual al punto final.

Se dice que un algoritmo es admisible si no sobreestima el valor de la solución óptima, en otras palabras, un algoritmo es admisible siempre que : h(n)<=h(n), siendo h(n) la solución optima.

Un algoritmo es consistente cuando: h(n)<=k(m,n) + h(m)

Monótono cuandos para cada nodo n y cada sucesor n 'de n generada por una acción a, el costo estimado de alcanzar el objetivo de n no es mayor que el coste de paso de llegar al n' más el costo estimado de alcanzar el objetivo de n'.

                     

AMPLITUD ITERATIVA

AMPLITUD ITERATIVA

Como se observo la clase pasada la búsqueda por profundidad iterativa combina la búsqueda en profundidad y en anchura recorriendo el árbol por niveles y ramas, ahora se describirá la amplitud iterativa, la cual realiza una pequeña exploración de cada porción del árbol, lo que genera un ahorro de tiempo. La búsqueda por anchura iterativa propone mejorar la calidad de la búsqueda por profundidad iterativa. 

Su funcionamiento es el siguiente:

Lo primero que el algoritmo realiza es crear un nodo raíz, si no encuentra solución en el nodo raíz, entonces creara un hijo, si no encuentra la solución en el nodo hijo creara dos nuevos sucesores, hasta este momento se encuentran 4 nodos en memoria.  Si la solución no se encontrara en en los 4 nodos generados el algoritmo pedirá que se retorne el camino hasta el primer nodo y este creara otro hijo en, lo que quiere decir que el nodo raíz tendrá dos ramas desde ese momento. Al no encontrar la solución en el primer hijo de la segunda rama creara 2 sucesores, si no encuentra la solución en estos dos sucesores el algoritmo dirá que el camino se retorne hasta los nodos hoja de la primera rama creara un sucesor para cada nodo hoja y otro sucesor para el nodo padre de los nodos hoja, este es el proceso que seguirá el algoritmo hasta que encuentre la solución.

A continuación se muestran gráficos que harán mas fácil el entendimiento del funcionamiento del algoritmo búsqueda en anchura iterativa.

Imagen tomada de : https://intartificialblog.wordpress.com/2016/09/05/amplitud-iterativa/

Imagen tomada de:http://www.iiia.csic.es/~pedro/busqueda1-ciega

En resumidas palabra podemos decir que el algoritmo de búsqueda por anchura iterativa aumenta en 1 la cantidad de nodos hijos que tiene. es decir, d(b-1)+1

.

BUSQUEDA POR AMPLITUD, PROFUNDIDAD

BÚSQUEDA POR AMPLITUD Y PROFUNDIDAD (BEP, DEF)

La búsqueda ciega es un tipo de búsqueda no informada, por esta razón alcanzar el objetivo obliga al algoritmo a revisar estado por estado hasta hallar la correcta. Para la búsqueda ciega encontramos los algoritmos búsqueda por profundidad y búsqueda en anchura, los que se explicaran a continuación. 

BEP:

En la búsqueda breath first search se empieza con el nodo de menor valor, para la imagen al lado por orden alfabético. El funcionamiento del algoritmo se realiza evaluación de niveles hasta hallar la respuesta.

Un algoritmo de árbol cuenta con una profundidad B, un   factor de ramificación D, y un nodo o nodos hoja.

Imagen tomada de:
https://www.coursehero.com/file/p5vihbn/frontier-is-a-first-in-first-out-FIFO-queue-ie-new-successors-go-at-end-of-the/

En una búsqueda ciega de amplitud cuando las soluciones son varias, entonces la solución que está más cerca de la raíz es la mejor.

En cuanto  la complejidad podemos ubicar dos factores:

*El tiempo: mejor caso = (B^D)

                                                                                        *Caso medio = (B^D)

                                                                                        *Peor caso = (B^D), donde podemos concluir que el tiempo es exponencial.

*El espacio: mejor caso = (B^D)

                     caso medio = (B^D)

                    peor caso = (B^D)              

                                                           

Imagen tomada de:
http://ia-israel.blogspot.com.co/2014/04/tecnica-de-busqueda-ciega.html

Se dice que un algoritmo debe ser optimo y completo, esto quiere decir:

*Optimo: si encuentra la solución, genera menos nodos  y menos espacio

*Completo:Si hay solución la encuentra.

La búsqueda BEF es un algoritmo completo, pero no optimo.

DEF:

La busqueda ciega por profundidad  o  depth first search  funciona evaluando cada nodo hasta b, osea hasta su profundidad, se dice que esta búsqueda es lineal:

*Complejidad espacial mejor caso = (d(b-1))

*Complejidad espacial peor caso = (d(b-1))

*Tiempo peor caso = (b^d)

*Tiempo mejor caso = (bd)

En la búsqueda DEF se concluye que el algoritmo no es optimo y en arboles muy grandes no es completo.

Para el siguiente juego se pide solucionarlo con el sistema DEF

Formalización:

Estado inicial:

Imagen tomada de:

http://enexcel.blogspot.com.co/2013/05/juegos-en-excel-el-salto-de-la-rana.html

Estado final  

Imagen tomada de:

http://www.taringa.net/comunidades/sigycre/4477622/Juego-6-ranas.html

      

      

En el juego de las ranas cada movimiento se evaluó hasta que no hubiera solución y luego se examinaba la siguiente rama hasta que no se encontrara solución posible, así se desarrolla el algoritmo hasta que encuentre solución. DEF no es el tipo de búsqueda mas optimo para este juego pues el tiempo para encontrar la respuesta es extenso, a riesgo de quedarse en un ciclo infinito.