· web viewprimero se le establece un orden al grafo bajo un esquema de árbol en el cual se...
TRANSCRIPT
“UNIVERSIDAD MAYOR DE SAN SIMON”
FACULTAD DE CIENCIAS Y TECNOLOGIA
CARRERA: LIC. ING. SISTEMAS
BUSQUEDAS EN ANCHURA Y EN PROFUNDIDAD
NOMBRES:
CLAROS ORELLANA SERGIO ALVARO
COAGUILA PATIÑO IMER VLADIMIR
HERRERA ROJAS DENIS DAVID
PACO GAMARRA KAREN PATRICIA
MATERIA:
INTELIGENCIA ARTIFICIAL
DOCENTE:
LIC. GARCIA PEREZ CARMEN ROSA
FECHA:
11/SEPTIEMBRE/2019
COCHABAMBA-BOLIVIA
P á g i n a 1 | 39
ÍNDICE1.- Introducción Primero en anchura 2
2.- Cómo funciona la búsqueda Primero en anchura 2
3.- Algoritmo de búsqueda Primero en anchura 3
4.- Criterios de búsqueda Primero en anchura 4
5.- Ejemplo de cómo funciona el algoritmo Primero en anchura 5
6.- Introducción Primero en profundidad 24
7.- Cómo funciona la búsqueda Primero en profundidad 24
8.- Algoritmo de búsqueda Primero en profundidad 26
9.- Criterios de búsqueda Primero en profundidad 27
10.- Ejemplo de cómo funciona el algoritmo Primero
en profundidad 28
11.- Conclusiones 38
12.- Bibliografía 38
P á g i n a 2 | 39
1.- Introducción Primero en anchuraEn Ciencias de la Computación, búsqueda en anchura (en inglés BFS - Breadth First Search) es un algoritmo de búsqueda no informada utilizado para recorrer o buscar elementos en un grafo (usado frecuentemente sobre árboles). Intuitivamente, se comienza en la raíz (eligiendo algún nodo como elemento raíz en el caso de un grafo) y se exploran todos los vecinos de este nodo. A continuación, para cada uno de los vecinos se exploran sus respectivos vecinos adyacentes, y así hasta que se recorra todo el árbol.
Formalmente, BFS es un algoritmo de búsqueda sin información, que expande y examina todos los nodos de un árbol sistemáticamente para buscar una solución.
2.- Como funciona la búsqueda Primero en anchura Primero se le establece un orden al grafo bajo un esquema de árbol en el cual se ordenan los nodos por niveles partiendo de izquierda a derecha respectivamente (de menor a mayor), luego su recorrido parte desde la raíz y baja nivel por nivel recorriendo los valores de izquierda a derecha respectivamente hasta llegar al último nodo del último nivel.
P á g i n a 3 | 39
3.- Algoritmo Búsqueda Primero en anchura Función buscar (Nodo origen)Lista FIFO
iniciosi solución(origen) retornar origen
sinoMarcar(origen)
si tieneHijos(origen)Añadir a la lista hijos del(origen)
origen = leer primer hijo de(lista)
Eliminar primer dato (lista)
Función buscar (origen)
sinoorigen =leer primer hijo de(lista)
Eliminar primer dato (lista)
Función buscar (origen)
Fin
P á g i n a 4 | 39
4.- Criterios de búsqueda Primero en anchura
● Completo
Podemos ver que es completa porque si existe la solución que estamos buscando, la encontrará.
● Óptimo
Es óptima porque la solución encontrada es la más superficial, por lo tanto, la que usa menos recursos (coste) suponiendo que el costo de las acciones es el mismo y no son negativos.
● Complejidad Temporal
La complejidad en tiempo del algoritmo es exponencial O(b^d) = b^d+...+b^3+b^2+b^1+b^0
b^d+...+b^3+b^2+b+1
En esta función polinómica “b” es el número de ramificaciones (la media de los descendientes de un nodo) y “d” es la variable o tamaño del
problema (maxima profundidad del espacio de estados)
● Complejidad Espacial
La complejidad espacial en este algoritmo también es exponencial, ya que debe almacenar todo el árbol o grafo completo.
P á g i n a 5 | 39
5.- Ejemplo búsqueda Primero en anchuraEncontrar la palabra “pueblo” en la siguiente estrofa
Brilla el sol de septiembre radiante reflejando la gloria inmortal del gran pueblo que firme y constante.
Primeramente, pasamos el texto de la estrofa que se nos dio a un árbol binario.
1. Brilla2. El 3. Sol 4. De5. Septiembre6. Radiante7. Reflejando8. La9. Gloria10. Inmortal11.Del12.Gran13.Pueblo14.Que15.Firme16.Y 17.Constante
P á g i n a 6 | 39
Para almacenar los elementos del árbol utilizaremos una LISTA FIFO.
Agarramos el nodo raíz, lo añadimos a la lista
La lista tiene los nodos {1}
Sacamos el primer elemento de la lista, en este caso es el nodo 1.
Preguntamos ¿El elemento que contiene el nodo 1 es igual a “Pueblo”?
P á g i n a 7 | 39
La palabra que contiene el nodo 1 es “Brilla” y como esta no es igual a “Pueblo” entonces marcamos como visitado el nodo 1.
Preguntamos. ¿El nodo 1 tiene hijos?
Como el nodo 1 tiene dos hijos los añadimos a la lista de izquierda a derecha.
P á g i n a 8 | 39
La lista tiene los nodos {2,3}
Sacamos el primer elemento de la lista, en este caso es el nodo 2.
Preguntamos ¿El elemento que contiene el nodo 2 es igual a “Pueblo”?
La palabra que contiene el nodo 2 es “El” y como esta no es igual a “Pueblo” entonces marcamos como visitado el nodo 2.
P á g i n a 9 | 39
Preguntamos. ¿El nodo 2 tiene hijos?
Como el nodo 2 tiene dos hijos los añadimos a la lista de izquierda a derecha.
La lista tiene los nodos {3,4,5}
Sacamos el primer elemento de la lista, en este caso es el nodo 3.
Preguntamos ¿El elemento que contiene el nodo 3 es igual a “Pueblo”?
P á g i n a 10 | 39
La palabra que contiene el nodo 3 es “Sol” y como esta no es igual a "Pueblo" entonces marcamos como visitado el nodo 3.
Preguntamos. ¿El nodo 3 tiene hijos?
Como el nodo 3 tiene dos hijos los añadimos a la lista de izquierda a derecha.
P á g i n a 11 | 39
La lista tiene los nodos {4,5,6,7}
Sacamos el primer elemento de la lista, en este caso es el nodo 4.
Preguntamos ¿El elemento que contiene el nodo 4 es igual a “Pueblo”?
La palabra que contiene el nodo 4 es “De” y como esta no es igual a "Pueblo" entonces marcamos como visitado el nodo 4.
P á g i n a 12 | 39
Preguntamos. ¿El nodo 4 tiene hijos?
Como el nodo 4 tiene dos hijos los añadimos a la lista de izquierda a derecha.
La lista tiene los nodos {5,6,7,8,9}
Sacamos el primer elemento de la lista, en este caso es el nodo 5.
Preguntamos ¿El elemento que contiene el nodo 5 es igual a “Pueblo”?
P á g i n a 13 | 39
La palabra que contiene el nodo 5 es “Septiembre” y como esta no es igual a "Pueblo" entonces marcamos como visitado el nodo 5.
Preguntamos. ¿El nodo 5 tiene hijos?
Como el nodo 5 tiene dos hijos los añadimos a la lista de izquierda a derecha.
P á g i n a 14 | 39
La lista tiene los nodos {6,7,8,9,10,11}
Sacamos el primer elemento de la lista, en este caso es el nodo 6.
Preguntamos ¿El elemento que contiene el nodo 6 es igual a “Pueblo”?
La palabra que contiene el nodo 6 es “Radiante” y como esta no es igual a "Pueblo" entonces marcamos como visitado el nodo 6.
P á g i n a 15 | 39
Preguntamos. ¿El nodo 6 tiene hijos?
Como el nodo 6 tiene dos hijos los añadimos a la lista de izquierda a derecha.
La lista tiene los nodos {7,8,9,10,11,12,13}
Sacamos el primer elemento de la lista, en este caso es el nodo 7.
Preguntamos ¿El elemento que contiene el nodo 7 es igual a “Pueblo”?
P á g i n a 16 | 39
La palabra que contiene el nodo 7 es “Reflejando” y como esta no es igual a "Pueblo" entonces marcamos como visitado el nodo 7.
Preguntamos. ¿El nodo 7 tiene hijos?
Como el nodo 7 tiene dos hijos los añadimos a la lista de izquierda a derecha.
P á g i n a 17 | 39
La lista tiene los nodos {8,9,10,11,12,13,14,15}
Sacamos el primer elemento de la lista, en este caso es el nodo 8.
Preguntamos ¿El elemento que contiene el nodo 8 es igual a “Pueblo”?
La palabra que contiene el nodo 8 es “La” y como esta no es igual a "Pueblo" entonces marcamos como visitado el nodo 8.
P á g i n a 18 | 39
Preguntamos. ¿El nodo 8 tiene hijos?
Como el nodo 8 tiene dos hijos los añadimos a la lista de izquierda a derecha.
La lista tiene los nodos {9,10,11,12,13,14,15,16,17}
Sacamos el primer elemento de la lista, en este caso es el nodo 9.
Preguntamos ¿El elemento que contiene el nodo 9 es igual a “Pueblo”?
P á g i n a 19 | 39
La palabra que contiene el nodo 9 es “Gloria” y como esta no es igual a "Pueblo" entonces marcamos como visitado el nodo 9.
Preguntamos. ¿El nodo 9 tiene hijos?
Como el nodo 9 no tiene hijos no añadimos nada a la lista.
La lista tiene los nodos {10,11,12,13,14,15,16,17}
Sacamos el primer elemento de la lista, en este caso es el nodo 10.
Preguntamos ¿El elemento que contiene el nodo 10 es igual a “Pueblo”?
P á g i n a 20 | 39
La palabra que contiene el nodo 10 es “Inmortal” y como esta no es igual a "Pueblo" entonces marcamos como visitado el nodo 10.
Preguntamos. ¿El nodo 10 tiene hijos?
Como el nodo 10 no tiene hijos no añadimos nada a la lista.
La lista tiene los nodos {11,12,13,14,15,16,17}
Sacamos el primer elemento de la lista, en este caso es el nodo 11.
Preguntamos ¿El elemento que contiene el nodo 11 es igual a “Pueblo”?
P á g i n a 21 | 39
La palabra que contiene el nodo 11 es “Del” y como esta no es igual a "Pueblo" entonces marcamos como visitado el nodo 11.
Preguntamos. ¿El nodo 11 tiene hijos?
Como el nodo 11 no tiene hijos no añadimos nada a la lista.
La lista tiene los nodos {12 ,13,14,15,16,17}
Sacamos el primer elemento de la lista, en este caso es el nodo 12.
Preguntamos ¿El elemento que contiene el nodo 12 es igual a “Pueblo”?
P á g i n a 22 | 39
La palabra que contiene el nodo 12 es “Gran” y como esta no es igual a "Pueblo" entonces marcamos como visitado el nodo 12.
Preguntamos. ¿El nodo 12 tiene hijos?
Como el nodo 12 no tiene hijos no añadimos nada a la lista.
La lista tiene los nodos {13,14,15,16,17}
Sacamos el primer elemento de la lista, en este caso es el nodo 13.
Preguntamos ¿El elemento que contiene el nodo 13 es igual a “Pueblo”?
P á g i n a 23 | 39
La palabra que contiene el nodo 1 es “Pueblo” y como esta es igual a "Pueblo" encontramos la solución.
P á g i n a 24 | 39
6.- Introducción Primero en profundidadLa búsqueda en profundidad es un algoritmo que está dentro del grupo de algoritmos de búsqueda ciega o no informada.
Las búsquedas a ciegas o no informadas se realiza cuando no existe información específica sobre el problema que nos ayude a determinar cuál es el mejor operador que se debería aplicar en cada momento o el mejor nodo por el cual continuar la búsqueda.
No dependen de información propia del problema a la hora de resolverlo, sino que proporcionan métodos generales para recorrer los árboles de búsqueda asociados a la representación del problema, por lo que se pueden aplicar en cualquier circunstancia. Se basan en la estructura del espacio de estados y determinan estrategias sistemáticas para su exploración, es decir, que siguen una estrategia fija a la hora de visitar los nodos que representan los estados del problema. Se trata también de algoritmos exhaustivos, de manera que, en el peor de los casos, pueden acabar recorriendo todos los nodos del problema para hallar la solución.
Una búsqueda en profundidad (en inglés DFS o Depth First Search) es un algoritmo utilizado para recorrer todos los nodos de un grafo o árbol de manera ordenada, pero no uniforme.
7.- Cómo funciona la búsqueda Primero en profundidad 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, de modo que repite el mismo proceso con cada uno de los hermanos del nodo ya procesado.
Si el nodo que estamos examinando en un momento dado tiene descendientes, el siguiente nodo a examinar será uno de esos descendientes para poder avanzar en profundidad.
Sólo cuando lleguemos a un nodo sin descendientes deberemos ir hacia atrás para localizar otro nodo a expandir.
Está búsqueda no funcionará si nuestro árbol puede tener ramas de profundidad infinita, dado que el algoritmo no se detendría nunca si localiza una de esas ramas.
En este caso habría que hacer una provisión para detener el algoritmo (y considerar la búsqueda fallida) si se sobrepasa una determinada profundidad que se considere excesiva.
La búsqueda en profundidad se aplica tanto para árboles como para grafos, podemos observar que la aplicación para ambos es similar, pero los grafos a
P á g i n a 25 | 39
diferencia de los árboles pueden contener ciclos por lo que podemos volver al mismo nodo.
Búsqueda en grafo no dirigido Se parte de un nodo dado y sirven para visitar los vértices y arcos de manera sistemática. El recorrido puede ser para grafos dirigidos y no dirigidos.
Es lo mismo que el recorrido de un árbol, se elige un nodo de partida. Se marca como visitado y se recorren los nodos no visitados adyacentes a este nodo marcado, usando recursivamente primero la búsqueda en profundidad.
P á g i n a 26 | 39
8.- Algoritmo búsqueda Primero en profundidadFunción buscar (Nodo origen)Pila de adyacentes
Iniciosi solución(origen) retornar origen
sinomarcar visitado(origen)
si tiene adyacentes no marcados (origen) Añadir a pila adyacentes no marcados del (origen)
Origen =leer primer dato de(pila)
Eliminar primer dato (pila)
Función buscar(Nodo origen)
sino mientras (pila!=null)
Origen =leer primer dato de(pila)
Eliminar primer dato (pila)
Función buscar(Nodo origen)
Fin
9.- Criterios de búsqueda Primero en profundidadP á g i n a 27 | 39
● Completo
La búsqueda en profundidad no es completa.
El algoritmo de búsqueda en profundidad llega a ser completo si usamos búsqueda basadas en árboles y grafos en espacios de estado finitos (ya que todo los nodos serán expandidos) y también si se evitan caminos redundantes (ciclos).
● Complejidad Temporal
La complejidad en tiempo del algoritmo es exponencial
O(b^m) = b^m+...+b^2+b^1+b^0
b^m+...+b^2+b+1
en esta función polinómica “b” es el número de ramificaciones (la media de los descendientes de un nodo) y “m” es el nivel donde se encuentra la solución que no siempre es la solución más óptima.
● Complejidad Espacial
Complejidad para almacenamiento vendría a ser lineal O(b*m) ya que solo almacena el camino y los nodos hijos de los nodos intermedios.
● Óptimo
Este algoritmo no nos asegura darnos la solución más óptima porque si existe más de una solución, podría encontrar la primera que está a un nivel de profundidad mayor que otra en otra rama que todavía no a sido expandida.
10.- Ejemplo de cómo funciona el algoritmo Primero en profundidad
P á g i n a 28 | 39
El siguiente grado es la representación de cómo llegar a una tienda de la ciudad.
La posición inicial es “I” y se requiere llegar a “F”.
Solución paso a paso
1.- Seleccionamos el nodo inicial. Lo añadimos a nuestra pila que tiene los elementos {I}.
Preguntamos si su valor es igual a “F”. ¿I es igual a F?
Como el valor de este nodo no es “F”. entonces marcamos como visitado.
P á g i n a 29 | 39
Ahora le preguntamos al nodo “I”. ¿Tienes nodos adyacentes?
Como “I” tiene nodos adyacentes, añadimos todos sus nodos a nuestra pila que tiene los elementos {D,H,A}.
En este caso nuestro recorrido será en sentido horario.
Vamos al siguiente nodo que es el nodo “D”.
Preguntamos. ¿D es igual a F?
Como D no es igual a F entonces marcamos D como nodo visitado.
P á g i n a 30 | 39
Ahora preguntamos. ¿D tiene nodos adyacentes?
Como D tiene nodos adyacentes, los añadimos a la pila que tiene los elementos {B,H,A}.
Vamos al siguiente nodo que es B
Preguntamos. ¿B es igual a F?
Como B no es igual a F entonces marcamos B como nodo visitado.
P á g i n a 31 | 39
Ahora preguntamos. ¿B tiene nodos adyacentes?
Como B tiene nodos adyacentes los añadimos a la pila que tiene los elementos {G,H,A}.
Vamos al siguiente nodo que es G
Preguntamos. ¿G es igual a F?
Como G no es igual a F entonces marcamos G como nodo visitado.
P á g i n a 32 | 39
Ahora preguntamos. ¿G tiene nodos adyacentes?
G no tiene nodos adyacentes. La pila tiene los siguientes elementos {H,A}
Vamos al siguiente nodo que es H
Preguntamos. ¿H es igual a F?
Como H no es igual a F entonces marcamos H como nodo visitado.
Ahora preguntamos. ¿H tiene nodos adyacentes?
P á g i n a 33 | 39
H tiene dos nodos adyacentes G y D pero como G y D ya fueron visitados. Continuamos la búsqueda. La pila tiene los siguientes elementos {A}
Vamos al siguiente nodo que es A
Preguntamos. ¿A es igual a F?
Como A no es igual a F entonces marcamos A como nodo visitado.
P á g i n a 34 | 39
Ahora preguntamos. ¿A tiene nodos adyacentes?
Como A tiene nodos adyacentes los añadimos a la pila y los nodos ya visitados los ignoramos.
La pila tiene los siguientes elementos {C}
Vamos al siguiente nodo que es C.
Preguntamos. ¿C es igual a F?
Como C no es igual a F entonces marcamos C como nodo visitado.
P á g i n a 35 | 39
Ahora preguntamos. ¿C tiene nodos adyacentes?
Como C tiene nodos adyacentes los añadimos a la pila. Y los nodos ya visitados los ignoramos
La pila tiene los siguientes elementos {J}
Vamos al siguiente nodo que es J.
Preguntamos. ¿J es igual a F?
Como J no es igual a F entonces marcamos J como nodo visitado.
P á g i n a 36 | 39
Ahora preguntamos. ¿J tiene nodos adyacentes?
Como J tiene nodos adyacentes los añadimos a la pila que tiene los siguientes elementos {K}.
Vamos al siguiente nodo que es K.
Preguntamos. ¿K es igual a F?
Como K no es igual a F entonces marcamos K como nodo visitado.P á g i n a 37 | 39
Ahora preguntamos. ¿J tiene nodos adyacentes?
Como J tiene nodos adyacentes los añadimos a la pila. Y los nodos ya visitados los ignoramos.
La pila tiene los siguientes elementos {F}
Vamos al siguiente nodo que es F.
Preguntamos. ¿F es igual a F?
Como F es igual F encontramos la solución.P á g i n a 38 | 39
El camino para llegar a f es: I,A,C,J,K,F.
6.- ConclusionesDespués del análisis de ambas búsquedas, pudimos concretar que la búsqueda en Amplitud es más completa y óptima en comparación a la búsqueda en Profundidad, ya que, si una rama del árbol es más extensa que las otras, la búsqueda será más difícil, y más extenuante que la búsqueda en amplitud, además de tener probabilidad de enciclarse si esta no se marca correctamente. Con la búsqueda en Amplitud podemos acelerar el encuentro del nodo deseado ya que este está enfocado en los niveles.
7.- Bibliografía
● Stuart J Russell y Peter Norvig. Inteligencia Artificial un enfoque moderno (segunda edición).
● https://www.youtube.com/watch? v=Q3SYN8K0v1I&feature=youtu.be
● https://www.youtube.com/watch?v=HdZbPqYKafU
P á g i n a 39 | 39