Algoritmo de busqeuda en profundida

| iTT |
| Unidad Tomas Aquino |

[Algoritmos de Búsqueda] |
|

BUSQUEDA EN PROFUNDIDAD

Equipo #3
* .
* .
* .
* .
* Vázquez Herrera Dario Iván
Sábado, 31 de Octubre de 2009
Materia: Matemáticas Para Computadora
Grupo:
Profesor: Rossana Gutiérrez Montoya

Índice

Algoritmos de Busqueda. 3
Motor de búsqueda 3
Busqueda en Profundidad. 4
Ventajas y Desventajas 4
ComplejidadComputacional 4
Pseudocodigo para Grafos: 5
Busqueda en profundidad (método): 5
Algoritmo BEP: 5
Búsqueda en profundidad iterativa 7
Ventajas y desventajas 7
Complejidad computacional 7
Bibliografia 8

Algoritmos de Búsqueda.
Un algoritmo de búsqueda es aquel que está diseñado para localizar un elemento concreto dentro de una estructura de datos. Consiste en solucionar un problema deexistencia o no de un elemento determinado en un conjunto finito de elementos, es decir, si el elemento en cuestión pertenece o no a dicho conjunto, además de su localización dentro de éste.
Este problema puede reducirse a devolver la existencia de un número en un vector.
Motor de búsqueda
Un motor de búsqueda es un sistema informático que indexa archivos almacenados en servidores web gracias a su«spider» (o Web crawler). Un ejemplo son los buscadores de Internet (algunos buscan sólo en la Web pero otros buscan además en noticias, servicios como Gopher, FTP, etc.) cuando se pide información sobre algún tema. Las búsquedas se hacen con palabras clave o con árboles jerárquicos por temas; el resultado de la búsqueda es un listado de direcciones Web en los que se mencionan temas relacionados con laspalabras clave buscadas.
Como operan en forma automática, los motores de búsqueda contienen generalmente más información que los directorios. Sin embargo, estos últimos también han de construirse a partir de búsquedas ( no automatizadas) o bien a partir de avisos dados por los creadores de páginas (lo cual puede ser muy limitante). Los buenos directorios combinan ambos sistemas. Hoy en día elInternet se ha convertido en una herramienta, para la búsqueda de información, rápida, para ello han surgido los buscadores que son un motor de búsqueda que nos facilita encontrar información rápida de cualquier tema de interés, en cualquier área de las ciencias, y de cualquier parte del mundo.

Búsqueda en Profundidad.

Una Búsqueda en profundidad (en inglés DFS o Depth First Search) es un algoritmoque 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 yaprocesado.
Ventajas y Desventajas
Expandir un camino hasta su máxima profundidad puede ser útil para acotar la solución en problemas de optimización. Esto es, si se ha encontrado una solución posible con determinada valoración, no se admitirá expandir nodos con una valoración peor, y así el algoritmo puede ir eliminando ramas sin la carga de procesamiento de recorrerlas. Además, el requerimiento dememoria es limitado, aun si se garantiza que no cicle, ya que sólo hace falta guardar los datos de la rama actual.
Complejidad Computacional
La cantidad mínima de nodos a ser expandidos para garantizar la mejor solución es la misma que en la búsqueda en anchura, es decir
C = in+1- 1i - 1
La diferencia es que en este caso no tendremos certeza de haber encontrado la mejor solución hasta que se hayanexpandido todas las ramas hasta el nivel de la mejor solución encontrada (siempre hablando de problemas con costo uniforme), y, aunque el problema tenga la mejor solución en un nivel n, el algoritmo podría explorar por otra rama hasta una profundidad mucho mayor, incluso indefinidamente, por lo cual la complejidad computacional en el peor de los casos está determinada por la profundidad a la cual...