algorithm - generadores - busqueda profundidad iterativa java

¿Por qué se afirma que la búsqueda en profundidad es eficiente en el espacio?

Question

En un curso de algoritmos que estoy tomando, se dice que la búsqueda en profundidad (DFS) es mucho más eficiente en espacio que la búsqueda en primer lugar (BFS).

¿Porqué es eso?

Aunque básicamente están haciendo lo mismo, en DFS estamos apilando los sucesores del nodo actual, mientras que en BFS estamos en la cola de los sucesores.

Answer 1

En DFS, el espacio utilizado es O (h) donde h es la altura del árbol.

En BFS, el espacio utilizado es O (w) donde w es el ''ancho'' del árbol.

En árboles binarios típicos (es decir, árboles binarios aleatorios), w = Omega (n) y h = O (sqrt (n)).

En árboles equilibrados, w = Omega (n) y h = O (log n).

Answer 2

En DFS, solo necesita espacio para lineal a la profundidad O(log(n)) en un árbol completamente equilibrado, mientras que BFS (búsqueda por amplitud) necesita O(n) (la parte más ancha del árbol es la profundidad más baja que tiene un árbol binario n / 2 nodos).

Ejemplo:

               1
              / /  
             /   /  
            /     / 
           /       /
          /         /  
         /           /  
        /             / 
       /               /
       2               2 
      / /             / / 
     /   /           /   /  
    /     /         /     /  
   /       /       /       /  
   3       3       3       3
  / /     / /     / /     / / 
 /   /   /   /   /   /   /   /  
 4   4   4   4   4   4   4   4
/ / / / / / / / / / / / / / / / 
5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 5 

DFS necesita espacio: 4
BFS necesita en la segunda última fila de espacio 8

Y empeora si el factor de ramificación es mayor.

Answer 3

Su confusión se deriva del hecho de que aparentemente asume que el algoritmo DFS se puede obtener del algoritmo BFS al reemplazar la cola FIFO con una pila LIFO.

Este es un error popular, simplemente no es cierto. El algoritmo DFS clásico no se puede obtener reemplazando la cola BFS con una pila. La diferencia entre estos algoritmos es mucho más significativa.

Si toma un algoritmo BFS y simplemente reemplaza la cola FIFO con una pila LIFO, obtendrá algo que puede llamarse un algoritmo pseudo-DFS . Este algoritmo pseudo-DFS reproducirá correctamente la secuencia de desplazamiento hacia delante del vértice DFS, pero no tendrá eficiencia de espacio DFS y no admitirá el desplazamiento hacia atrás DFS (retroceso).

Mientras tanto, el verdadero DFS clásico no se puede obtener de BFS mediante un reemplazo tan ingenuo de cola a pila. El DFS clásico es un algoritmo completamente diferente con una estructura central significativamente diferente. True DFS es un algoritmo genuinamente recursivo que usa la pila para propósitos de seguimiento , no para almacenar el "frente" del descubrimiento de vértice (como es el caso en BFS). La consecuencia más inmediata de esto es que, en el algoritmo DFS, la profundidad máxima de pila es igual a la distancia máxima desde el vértice de origen en el recorrido DFS. En el algoritmo BFS (como en el pseudo-DFS mencionado anteriormente) el tamaño máximo de la cola es igual al ancho del frente de descubrimiento de vértices más grande.

El ejemplo más prominente y extremo que ilustra la diferencia en el consumo máximo de memoria entre DFS y BFS (así como pseudo-DFS) es un gráfico de estrellas: un solo vértice central rodeado por un gran número (por ejemplo, 1000 ) de vértices periféricos, con cada vértice periférico conectado al vértice central por un borde. Si ejecuta BFS en este gráfico utilizando el vértice central como origen, el tamaño de la cola saltará inmediatamente a 1000 . Obviamente, ocurrirá lo mismo si usa pseudo-DFS (es decir, si simplemente reemplaza la cola por una pila). Pero el algoritmo DFS clásico necesitará una profundidad de pila de solo 1 (!) Para atravesar todo este gráfico. ¿Ver la diferencia? 1000 contra 1 . Esto es lo que se entiende por una mejor eficiencia de espacio de DFS.

Básicamente, tome cualquier libro sobre algoritmos, encuentre una descripción del DFS clásico y vea cómo funciona. Notará que la diferencia entre BFS y DFS es mucho más extensa que una simple cola en comparación con una pila.

También se debe decir que se puede crear un ejemplo de un gráfico que tendrá un consumo máximo de memoria más bajo en BFS. Por lo tanto, la afirmación sobre una mejor eficiencia de espacio de DFS debe verse como algo que podría aplicarse "en promedio" a alguna clase implícita de gráficos "agradables".