Embed Size (px)
Citation preview
BUSQUEDA EN ANCHURA Y PROFUNDIDAD
Por:
Juan Carlos Echeverri Cadavid
Análisis de Algoritmos
Profesor: Ricardo Botero
PARA LA COMPRENSIÓN Y DETERMINACIÓN DE LOS ALGORITMOS DE BÚSQUEDA EN PROFUNDIDAD Y ANCHURA, ES NECESARIO TENER CONOCIMIENTO DE ALGUNOS CONCEPTOS BÁSICOS DE LA TEORÍA DE GRAFOS
Grafo Camino Componente conexa Grafo conexo
QUE ES UN GRAFO
Es un conjunto de objetos llamados vértices o nodos unidos por enlaces llamados aristas o arcos, que permiten representar relaciones binarias entre elementos de un conjunto.
Típicamente, un grafo se representa gráficamente como un conjunto de puntos (vértices o nodos) unidos por líneas (aristas).
Tipos de grafos dirigidos (aristas) no dirigidos (arcos)
TIPOS DE GRAFOS
Grafo etiquetado: Cada arista y/o vértice tiene asociada una
etiqueta/valor. Grafo ponderado = Grafo con pesos: Grafo etiquetado en el que existe un valor
numérico asociado a cada arista o arco. Multigrafo: Grafo en el que se permite que entre dos
vérticesexista más de una arista o arco.
CAMINO (TEORÍA DE GRAFOS)
Un camino es una sucesión de vértices tal que de cada uno de sus vértices existe una arista hacia el vértice sucesor. Un camino simple es aquel que no repite vértices en su recorrido. Dos caminos son ajenos o independientes si no tienen ningún vértice en común excepto el primero y el último.
Sucesión de arcos adyacentes tal que el vértice final de cada arco coincide con el inicial del siguiente.
COMPONENTE CONEXA
Es un grafo tal que para cada par de vértices, existe un camino de uno hacia el otro, y viceversa.
GRAFO CONEXO
Si es posible formar un camino desde cualquier vértice a cualquier otro en el grafo, decimos que el grafo es conexo.
Un grafo no dirigido es un grafo conexo
BUSQUEDA EN ANCHURA BFS -Breadth First Search) es un algoritmo para recorrer
o buscar elementos en un grafo. Usado frecuentemente sobre arboles. 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. Y agotar la grafica.
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. El algoritmo no usa ninguna estrategia heurística.
Si las aristas tienen pesos negativos aplicaremos el algoritmo de Bellman-Ford en alguna de sus dos versiones.
ORDEN EN QUE SE RECORRE UN GRAFO EN UNA BÚSQUEDA EN ANCHURA
ALGORITMO PARA LA BÚSQUEDA EN ANCHURA:
Este algoritmo realiza la búsqueda en anchura en un grafo G comenzando en un nodo de partida A.
1. Inicializar todos los nodos al estado de preparados (ESTADO=1).
2. Poner el nodo de partida A en la COLA y cambiar su estado a espera (ESTADO=2).
3. Repetir pasos 4 y 5 hasta que COLA esté vacía.estado a procesado (ESTADO=3).
4. Quitar el nodo del principio de la cola, N. Procesar N y cambiar supreparados (ESTADO=1) y cambiar su estado al de espera(ESTADO=2).[ fin del bucle del paso 3 ]
5. Añadir a COLA todos los vecinos de N que estén en estado de
6. Salir.
PSEUDOCÓDIGO
BUSQUEDA EN PROFUNDIDAD
DFS o Depth First Search) es un algoritmo que permite recorrer todos los nodos de un grafo o árbol , 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.
ORDEN EN QUE SE RECORRE UN GRAFO EN UNA BÚSQUEDA EN PROFUNDIDAD.
ALGORITMO PARA LA BÚSQUEDA EN PROFUNDIDAD: Este algoritmo realiza la búsqueda en profundidad el
grafo G comenzando en un nodo A.
1. Inicializar todos los nodos al estado de preparado (ESTADO=1)
2. Meter el nodo inicial A en la pila y cambiar su estado a estado de espera (ESTADO=2).
3. Repetir los pasos 4 y 5 hasta que la pila este vacia.estado al de procesado (ESTADO=3).
4. Sacar el nodo N en la cima de la pila. Procesar el nodo N y cambiar supreparados (ESTADO=1) y cambiar su estado a estado de espera
(ESTADO=2).
[ fin de bucle del paso 3 ]
5. Meter en la pila todos los vecinos de N que estén en estado de
6. Salir.
PSEUDOCÓDIGO PARA GRAFOS
CONCLUSION
Los algoritmos de búsqueda BFS y DFS son una de las herramientas básicas a la hora de trabajar con grafos. No sólo podremos usarlos para recorrer grafos o buscar elementos, sino que también podemos adaptarlos y mejorarlos para resolver de manera eficiente cualquier tipo de situaciones que podamos moldear como un grafo o un árbol.
PREGUNTAS
¿Qué es un grafo? ¿Cómo funciona la búsqueda en profundidad
en un grafo?
BUSQUEDA EXTERNA EN ARCHIVOS SECUENCIALES
Por: Jhonathan Monsalve Velásquez
Análisis de Algoritmos.
Profesor: Ricardo Botero
QUE ES LA BÚSQUEDA ?
• La búsqueda es una de las operaciones más importantes en el procesamiento de la información, y permite la recuperación de datos previamente almacenados.
• La búsqueda de información esta relacionada con las diferentes tablas de búsqueda, llamadas “lookup”, las cuales contienen una gran cantidad de información, que es distribuida y almacenada en forma de listas de datos.
TIPOS DE BÚSQUEDA
• El tipo de búsqueda puede ser clasificada en varias formas, como interna o externa. Esto varia según el lugar de destino en el que esté almacenada la información (en memoria o en dispositivos externos).
BÚSQUEDA EXTERNA
BÚSQUEDA INTERNA
• Es aquella donde se evidencia grandes volúmenes de registros, que puede ser necesario almacenarlos en archivos de disco o cinta, este proceso es externo a la memoria del equipo.
• La búsqueda interna es aquella donde se almacenan por completo todos los registros en memoria de la computadora.
Buscar_elemento “N”
Existe N el conjunto de información ?.
Identificar la posición de N
en el conjunto.
No Existe
Determinar que N no existe en
el conjunto
FINALIDAD DE LA BUSQUEDA• Existen diferentes algoritmos de búsqueda, por lo
que su elección depende directamente de la forma en que se encuentren organizados sus datos. Su objetivo principal es la detección de el dato buscado, es por eso que la búsqueda de un elemento N se puede determinar de la siguiente forma:
DISPOSITIVOS DE ALMACENAMIENTO SECUENCIAL
Unidades de cinta
magnéticas
Unidades de
Disquetes
Discos ópticos
Cintas magnét
icas
Cartuchos de
memoria
Digitalización de imágen
es
• Estos son algunos de medios de almacenamiento secuencial para la información.
QUE SON ARCHIVOS ?
• Los archivos también denominados ficheros son una colección de datos relacionados entre sí, localizados o almacenados como una unidad en alguna parte de la computadora. Dichos elementos sirven para dar la entrada y salida a un ordenador normalmente son manejados con programas y pueden ser contrastados con arrays y registros.
Características de los archivos
• Independencia de la información respecto de los programas
• La información almacenada es permanente.• Un archivo puede ser accedido por distintos
programas en distintos momentos.• Gran capacidad de almacenamiento
ARCHIVOS SECUENCIALES
• Es la forma básica de organizar e un conjunto de registros, que forman un archivo, permiten indicar a la computadora mediante la programación que el ordenador lea o escriba una entrada. Estos archivos se almacenan uno tras otro, el primer registro almacenado se coloca al principio del archivo y el segundo se almacena inmediatamente después (no existen posiciones sin uso) y así sucesivamente.
Posición1• Registro1
Posición2• Registro2
Posición3• Registro3
Posición N• Registro
N
Para leer un archivo secuencial, el sistema siempre comienza al principio del arreglo de izquierda a derecha y lee un registro a la vez hasta llegar al registro deseado.
El proceso concluye cuando el elemento es encontrado o cuando el intervalo de búsqueda se anula o es nulo lo primero que suceda.
Normalmente si la búsqueda concluye con éxito, es de
interés conocer la posición en que fue hallado el elemento.
METODO DE BÚSQUEDA SECUENCIAL EN ARCHIVOS SECUENCIALES.
Consiste en revisar la estructura de datos elemento por elemento hasta encontrar el dato que estamos buscando, o hasta llegar al final de la estructura de datos.
EJEMPLO BÚSQUEDA SECUENCIAL•DATO A BUSCAR: X=45
•TAMAÑO DEL ARREGLO: N=5
30 45 30 70 40
•P = APUNTADOR DEL PRIMER NODO
•Q = VARIABLE DE TIPO APUNTADOR
A1 A2 A3 A4 A5
p qq<>null Si
q.info<>x
Si
EJEMPLO BÚSQUEDA SECUENCIAL•DATO A BUSCAR: X=45
•TAMAÑO DEL ARREGLO: N=5
30 45 30 70 40
•P = APUNTADOR DEL PRIMER NODO
•Q = VARIABLE DE TIPO APUNTADOR
A1 A2 A3 A4 A5
p qq<>null Si
q.info<>x
No
q<-q.liga
Hemos encontrado el valor buscado en
Posición A1 Valor = 45
PREGUNTAS
¿Cuáles son los tipos de busqueda? ¿Qué son archivos secuenciales?
GRACIAS….
