PA2_U3.- Métodos de búsqueda (primero en anchura, primero en profundidad).

 

                            Búsquedas en Anchura y Profundidad

                    Algoritmo de Búsqueda en Anchura (BFS).

Búsqueda en anchura. Es equivalente a recorrer un árbol por niveles. Dado un nodo v, se visitan primero todos los nodos adyacentes a v, luego todos los que están a distancia 2 (y no visitados), a distancia 3, y así sucesivamente hasta recorrer todos los nodos.

la Búsqueda en anchura es un algoritmo para recorrer o buscar elementos de un grafo(usado frecuentemente en arboles). Se comienza por la raíz y se explora todos los hijos de este nodo. A continuación se explora cada unos de los hijos de los hermanos y así sucesivamente hasta encontrar la solución.

1. Implementación: La búsqueda primero en anchura se puede implementar con la Búsqueda de Árboles con una frontera vacía que sea una cola (FIFO). La cola FIFO pone todos los nuevos sucesores generados al final de la cola, lo que significa que los nodos más superficiales se expanden antes que los nodos más profundos.
2.  Evaluación de la Búsqueda Primero en Anchura Completa: Si el nodo objetivo más superficial está en una cierta profundidad finita d, se lo encontrará luego de expandir los nodos más superficiales, siempre que el factor de ramificación b sea finito. Óptima: Es óptimo si el coste del camino es una función no decreciente de la profundidad del nodo.

Pseudocogido Algoritmo:

Establecer nodo origen 

Evaluar primer hijo 

          si cumple, establecer como origen y salir

          si valido, repetir búsqueda a partir del nuevo estado 

          sino valido, repetir búsqueda para todos los hermanos  

          si encuentra , establecer como origen y salir

          si no encuentra, marcar al padre como no valido 

          establecer origen como abuelo y seguir buscando.

1. 
   

                                Algoritmo de Búsqueda en Profundidad (DFS)

Una Búsqueda en profundidad es un algoritmo que permite recorrer todos los nodos de un grafo o árbol (teoría de grafos) de manera ordenada, pero no uniforme. Su funcionamiento consiste en ir expandiendo todos y cada uno de los nodos que va localizando, de forma recurrente, en un camino concreto. Cuando ya no quedan más nodos que visitar en dicho camino, regresa (Backtracking), de modo que repite el mismo proceso con cada uno de los hermanos del nodo ya procesado

La forma más intuitiva de hacer este algoritmo es de forma recursiva, de lo contrario tendríamos que usar en lugar de una cola una pila, pero con la recursión nos ahorramos la necesidad de utilizar esta estructura explícitamente y en lugar de ello nos valemos de la pila de recursión. En este caso pasaremos por parámetro el nodo a buscar y el nodo actual (El nodo que está siendo visitado en cada ambiente de recursión), que en la primera llamada será el nodo raíz

El orden en que se eligen las ramas en un recorrido DFS está determinado por el tipo de recorrido de procesamiento de árbol que se haya elegido, estos pueden ser:

·      Pre-orden: Se procesa primero la raíz, luego la rama izquierda y luego las ramas siguientes hasta llegar a la que se encuentra más a la derecha.

·     Post-orden: Se procesa el árbol desde las ramas izquierdas hasta la que se encuentra más a la derecha. Finalmente se procesa el nodo raíz

·    Simétrico o In-orden: Se procesa la rama de la izquierda, luego el nodo raíz y luego la rama derecha.

Pseudocodigo algoritmo búsqueda en profundidad

funcion buscar_en_hijos(Nodo:n)

variable encontrado=boolean

inicio

    si solucion(n->hijo)

    retornar n->hijo

    

    sino

    n1=n->hijo

    encontrado=falso    

        mientras no (encontrado)

        n1=n1->hermano

        sisolucion(n1)

        retornar n1

        

        sino

            n1=null

            romper ciclo

    

            buscar_en_hijos(n->hijo)

            n2->n->hijo

    

                mientras(n2->hermano!=null)

                n2=n2->hermano

                buscar_en_hijos(n2)

        fin si

    fin mientras

fin funcion

     conclusión: los métodos de búsqueda dentro de la inteligencia artificial, en la investigación que se realizo se pudo notar como estos métodos ya sea Primero en profundidad o en anchura, tiene como objetivo el llegar a un resultado solicitado. derivado a que los dos poseen características diferentes al momento de realizar la búsqueda, es muy conveniente saber cual de las dos se adapta mejor a lo que se necesitara dentro de nuestros proyectos, ya sea por el costo en memoria o el tiempo de respuesta y eficiencia de dicho método de búsqueda.  

referencias:

•             Universidad Tecnológica de Pereira. (2015, 20 enero). - Algoritmo búsqueda en anchura - Inteligencia Artificial. Recuperado de https://sites.google.com/a/utp.edu.co/inteligencia-artificial/algoritmo-busqueda-en-anchura
•             M. (2010, 18 enero). BúSqueda Primero En Anchura. Recuperado de https://es.slideshare.net/mapaz91/bsqueda-primero-en-anchura
•             Universidad tecnológica de Pereira. (2015, 20 enero). - Algoritmo búsqueda en profundidad - Inteligencia Artificial. Recuperado de https://sites.google.com/a/utp.edu.co/inteligencia-artificial/algoritmo-busqueda-en-profundidad
•             Z. (2016, 7 febrero). Practica 6. Busqueda en profundidad. Recuperado de http://www.uco.es/%7Ei42crjij/aplicada/mem6_1.htm#:%7E:text=En%20la%20b%C3%BAsqueda%20primero%20en,estado%20final%20o%20estado%20meta).