3-2do PA

 Investigar información sobre los métodos de búsqueda (primero en anchura, primero en profundidad). Discutir en grupo los diferentes algoritmos de búsqueda, presentado un reporte con las conclusiones logradas en el salón

Búsqueda en Anchura:

 

La búsqueda general de un nodo de partida A es la siguiente:

1.       Examinar el nodo de partida A

2.      Examinar todos los nodos vecinos de A

3.      Examinar todos los nodos vecinos de los vecinos del nodo A, así sucesivamente.

4.     Garantizar que ningún nodo se procese más de una vez

5.      Utilizar una cola para mantener los nodos en espera de procesamiento, utilizando el campo ESTADO, para que especifique el estado actual de los nodos.

Algoritmo:

Formulación del problema.

Realizar la búsqueda en anchura de un grafo G comenzando con el nodo de partida A

1.       Inicializar todos los nodos al estado de preparado (ESTADO = 1)

2.      Poner el nodo de partida A en la COLA y cambiar el estado a espera (ESTADO = 2)

3.      Repetir los siguientes pasos: 3 y 4, hasta que la COLA, este vacía

4.     Quitar el nodo del principio de la COLA, N. Procesar N y cambiar su estado a procesado (ESTADO=3)

5.      Añadir a la COLA todos los vecinos de N que estén en estado de preparado (ESTADO = 1) y cambiar su estado al de espera (ESTADO = 2)

[Fin de bucle del paso 3]

6.      Salir

Nomenclatura:

      Raíz

      Rama

      Frado

      Nivel

      Altura

Ventajas:

ü  Siempre encuentra solución

ü  Optimo

Desventajas:

o   Nodos inútiles

o   Aplica a problema sencillos

 

Búsqueda en Profundidad:

Busca la solución en profundidad en todos los nodos hasta llegar a ella. Siempre comienza y hace el recorrido por nuestro lado izquierdo.

Es el algoritmo que permite recorrer todos los nodos de un grafo o árbol de manera ordenada, dentro de la teoría de grafos. Su funcionamiento consiste en ir expandiendo todos y cada uno de los nodos que va alcanzando, de forma recurrente, en un camino en concreto, cuando ya no existen más nodos que visitar en el camino, se regresa para iniciar de nuevo con cada uno de los hermanos del nodo ya procesado, a este proceso se le denomina Backtracking.

 

Pseudocódigo 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

        si solucion(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 función

 

Conclusión

Como conclusión se puede decir con certeza que a pesar de ser dos puntos relativamente sencillos como se puede ver, en cuanto a la búsqueda primero en anchura es más de una forma ordenada ya que se recorre nodo por nodo, es decir que si tenemos tres nodos, aunque la solución se encuentre en el tercer nodo, de todas formas este empezará desde el primer nodo hasta llegar al tercero, y cada nodo de tener otros nodos hijos los revisará igualmente en ese orden lo que realmente si se toma a consideración a la hora de hacer un programa que funcione de esta forma, realmente es más tardado en encontrar la solución, pero eso no impide el que la solución más rápida para resolver un problema se encontrará y me refiero a la hora de realizar un programa que nos permita ganar un puzzle de forma rápida, así mismo si tomamos a consideración el orden también se debe hablar de la búsqueda en profundidad; esta pues bien, si bien recorre en orden y como el nombre lo indica a profundidad del nodo que nosotros seleccionamos, pues bien, tiene esa ventaja, que nosotros podemos seleccionar el nodo que se recorrerá a profundidad, más no indica que de forma uniforme debemos recorrer nodos del 1 al 3, dando esa ventaja de poder seleccionar el que nosotros queramos para encontrar una solución, aunque si se toma en cuenta, también esto podría verse como un tipo de azar ya que al no ser ordenado recorremos todo de forma aleatoria refiriéndome al nodo que uno elige.