DEPTH FIRST SEARCH

Primera búsqueda en profundidad (DFS) es un algoritmo para recorrer o buscar un árbol, estructura de árbol, o gráfico. Uno empieza en la raíz (la selección de algún nodo como raíz en el caso gráfico), y analiza la medida de lo posible a lo largo de cada rama antes de dar marcha atrás.

El tiempo y el espacio de análisis de la DFS es diferente de acuerdo a su área de aplicación. En ciencias de la computación teórica, DFS se utiliza normalmente para recorrer todo un gráfico, y toma tiempo O (| V | + | E |) , lineal en el tamaño del gráfico. En estas aplicaciones, también utiliza el espacio O (| V |) en el peor de los casos para almacenar la pila de los vértices de la ruta de búsqueda actual, así como el conjunto de vértices ya visitados. Por lo tanto, en este escenario, el tiempo y el espacio los límites son los mismos que para el primer manga de la búsqueda y la elección de cuál de los dos algoritmos para el uso no depende tanto de su complejidad y más en las diferentes propiedades de los ordenamientos vértice de los dos algoritmos de producir .

Para las aplicaciones de la DFS para buscar problemas en la inteligencia artificial , sin embargo, el gráfico que se debe buscar es a menudo demasiado grandes para visitar en su totalidad o incluso infinito, y DFS pueden sufrir de no terminación cuando la longitud de una ruta en el árbol de búsqueda es infinito. Por lo tanto, la búsqueda sólo se realiza a una profundidad limitada, y debido a una limitada disponibilidad de memoria normalmente no utiliza estructuras de datos que no perder de vista el conjunto de todos los vértices visitados anteriormente. En este caso, el tiempo sigue siendo lineal en el número de vértices y aristas ampliado (aunque este número no es lo mismo que el tamaño de todo el gráfico debido a que algunos vértices se pueden buscar más de una vez y otros no en todos), pero el espacio complejidad de esta variante de la DFS sólo es proporcional al límite de profundidad, mucho menor que el espacio necesario para buscar a la misma profundidad usando la búsqueda primero en amplitud.

Para tales aplicaciones, DFS también se presta mucho mejor a la heurística métodos de elegir una rama de futuro probable. Cuando un límite de profundidad adecuada, no se conoce a priori, iterativo en profundidad de la búsqueda profundización DFS se aplica en varias ocasiones con una secuencia de aumento de los límites, en el modo de la inteligencia artificial de análisis, con un factor de ramificación más de uno, iterativo aumenta la profundización del tiempo de funcionamiento por sólo un factor constante en el caso en que el límite de la profundidad correcta es conocido por el crecimiento geométrico del número de nodos por nivel.

Ejemplo

Para el siguiente gráfico:

una búsqueda en profundidad a partir de A, suponiendo que el borde izquierdo de la gráfica que se muestra son elegidos antes de los bordes derecho, y asumiendo la búsqueda recuerda nodos previamente visitados y no los repita (ya que es un pequeño gráfico), visitará la nodos en el siguiente orden: A, B, D, F, E, C, G. Los bordes recorrido de esta forma buscar un árbol Tremaux , una estructura con importantes aplicaciones en la teoría de grafos .

Realizar la misma búsqueda sin recordar visitado resultados nodos en visitar los nodos en el orden A, B, D, F, E, A, B, D, F, E, etc para siempre, atrapada en la F A, B, D, , el ciclo de E y nunca llegar a C o G.

Profundización iterativa es una técnica para evitar este bucle infinito, y que llegar a todos los nodos.

La producción de una primera búsqueda en profundidad-

Los cuatro tipos de bordes definidos por un árbol de expansión

El resultado más natural de una primera búsqueda en profundidad de un gráfico (si se considera como una función en lugar de un procedimiento ) es un árbol de expansión de las cimas alcanzadas durante la búsqueda. Sobre la base de este árbol de expansión, los bordes de la gráfica original se puede dividir en tres clases: los bordes hacia adelante, que apuntan de un nodo del árbol de uno de sus descendientes, de nuevo los bordes, que apuntan de un nodo a uno de sus antepasados, y los bordes de cruz, que no hacen ninguna. A veces los bordes de árboles, bordes que pertenecen al árbol de expansión en sí, se clasifican por separado de los bordes hacia adelante. Se puede demostrar que si la gráfica original es no dirigida entonces todos sus bordes son bordes de árboles o bordes posteriores.

Ordenamientos Vertex

También es posible utilizar la búsqueda en profundidad para ordenar linealmente los vértices de la gráfica original (o árbol). Hay tres formas comunes de hacerlo:

• Un preorden es una lista de los vértices en el orden en que fueron visitados por primera vez por el primer algoritmo de búsqueda exhaustiva. Esta es una forma compacta y natural de describir el progreso de la búsqueda, como se hizo anteriormente en este artículo.

Un preorden de un árbol de expresión es la expresión en notación polaca .

• Un postordering es una lista de los vértices en el orden en que fueron visitados por última vez por el algoritmo. Un postordering de un árbol de expresión es la expresión en notación polaca inversa .

• Un postordering inversa es el reverso de un postordering, es decir, una lista de los vértices en el orden inverso de su última visita. Al buscar un árbol, postordering inversa es lo mismo que preorden, pero en general son diferentes cuando se busca un gráfico. Por ejemplo, al buscar la grafo dirigido

Comenzando en el nodo A, una visita a los nodos en orden, ya sea para producir listas ABDBACA o ACDCABA (dependiendo de si el algoritmo elige para visitar B o C primero). Tenga en cuenta que las visitas repetidas en la forma de dar marcha atrás a un nodo, para comprobar si tiene aún sin visitar los vecinos, se incluyen aquí (incluso si se encuentra que no tiene ninguno). Así, el preorderings posibles ABCD y ACDB (orden por la ocurrencia más a la izquierda del nodo en la lista de arriba), mientras que la inversa postorderings posibles ACBD y ABCD (orden por la ocurrencia más a la derecha del nodo en la lista de arriba). Invertir postordering produce una ordenación topológica de un grafo acíclico dirigido . Este orden también es útil para análisis de flujo de control , ya que a menudo representa una linealización natural del flujo de control.

La gráfica anterior podría representar el flujo de control en un fragmento de código como
si (A) entonces {
B
Else {}
C
}
D
y es natural considerar el código siguiente en el orden ABCD o ACBD, pero no natural de usar el orden ABDC o B. ACD

Pseudocódigo

Entrada: Un grafo G y un vértice v de G
Salida: Un etiquetado de los bordes de la componente conexa de v como bordes descubrimiento y bordes posteriores
Un procedimiento DFS (G, v):
2 etiqueta v como se analiza
3 para todos los correos en los bordes G.incidentEdges (v) hacer
4 si arista e es entonces inexplorada
5 w ← G.opposite (V, E)
6 si w vértice está sin explorar a continuación,
7 etiqueta e como un borde descubrimiento
8 llamada recursiva DFS (G, w)
9 más
10 etiqueta de correo como un borde posterior

Aplicaciones

Los algoritmo aleatorio similar a la búsqueda en profundidad utilizada en la generación de un laberinto.

Los algoritmos que utilizan la búsqueda primero en profundidad como un bloque de construcción incluyen:

• Encontrar los componentes conectados .
• clasificación topológica .
• Resultado 2 - (lado o vértice) conectado a los componentes.
• Encontrar los componentes fuertemente conectados .
• Prueba de planaridad
• Resolviendo puzzles con una sola solución, tales como laberintos . (DFS se puede adaptar a encontrar todas las soluciones a un laberinto al incluir únicamente los nodos de la ruta actual en el conjunto visitó.)
• generación Laberinto puede utilizar una profundidad de sesiones de la búsqueda al azar.
• Encontrar biconnectivity en los gráficos .