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.