¿Cuál es la diferencia entre el retroceso y la primera búsqueda en profundidad?

¿Cuál es la diferencia entre el retroceso y la primera búsqueda en profundidad?

El retroceso es un algoritmo de propósito más general.

La búsqueda en profundidad es una forma específica de retroceso relacionada con la búsqueda de estructuras de árbol. De Wikipedia:

Uno comienza en la raíz (seleccionando algún nodo como raíz en el caso del gráfico) y explora en la medida de lo posible a lo largo de cada rama antes de retroceder.

Utiliza el retroceso como parte de su forma de trabajar con un árbol, pero se limita a una estructura de árbol.

Sin embargo, el retroceso se puede utilizar en cualquier tipo de estructura en la que se puedan eliminar partes del dominio, ya sea que se trate de un árbol lógico o no. El ejemplo de Wiki usa un tablero de ajedrez y un problema específico: puede mirar un movimiento específico y eliminarlo, luego retroceder al siguiente movimiento posible, eliminarlo, etc.

Creo que esta respuesta a otra pregunta relacionada ofrece más información.

Para mí, la diferencia entre retroceder y DFS es que el retroceso maneja un árbol implícito y DFS se ocupa de uno explícito. Esto parece trivial, pero significa mucho. Cuando el espacio de búsqueda de un problema es visitado por retroceso, el árbol implícito se atraviesa y se poda en el medio. Sin embargo, para DFS, el árbol / gráfico con el que se ocupa está construido explícitamente y los casos inaceptables ya se han descartado, es decir, se han eliminado antes de realizar cualquier búsqueda.

Entonces, retroceder es DFS para árbol implícito, mientras que DFS es retroceder sin podar.

El retroceso generalmente se implementa como DFS más poda de búsqueda. Atraviesa el árbol espacial de búsqueda en profundidad construyendo soluciones parciales a lo largo del camino. El DFS de fuerza bruta puede construir todos los resultados de búsqueda, incluso los que no tienen sentido en la práctica. Esto también puede ser muy ineficiente para construir todas las soluciones (n! O 2 ^ n). Entonces, en realidad, al hacer DFS, también debe podar las soluciones parciales, que no tienen sentido en el contexto de la tarea real, y centrarse en las soluciones parciales, que pueden conducir a soluciones óptimas válidas. Esta es la técnica de retroceso real: descarta las soluciones parciales lo antes posible, da un paso atrás e intenta encontrar el óptimo local nuevamente.

Nada se detiene para atravesar el árbol del espacio de búsqueda usando BFS y ejecutar la estrategia de retroceso en el camino, pero no tiene sentido en la práctica porque necesitaría almacenar el estado de búsqueda capa por capa en la cola, y el ancho del árbol crece exponencialmente hasta la altura, así que desperdiciaríamos mucho espacio muy rápidamente. Es por eso que los árboles generalmente se atraviesan usando DFS. En este caso, el estado de búsqueda se almacena en la pila (pila de llamadas o estructura explícita) y no puede exceder la altura del árbol.

Por lo general, una búsqueda en profundidad es una forma de iterar a través de una estructura de árbol / gráfico real en busca de un valor, mientras que retroceder es iterar a través de un espacio de problemas en busca de una solución. El retroceso es un algoritmo más general que no necesariamente se relaciona con los árboles.

Yo diría que DFS es la forma especial de retroceder; retroceder es la forma general de DFS.

Si ampliamos DFS a problemas generales, podemos llamarlo retroceso. Si usamos el retroceso para problemas relacionados con árboles / gráficos, podemos llamarlo DFS.

Llevan la misma idea en el aspecto algorítmico.

Según Donald Knuth, es lo mismo. Aquí está el enlace en su artículo sobre el algoritmo Dancing Links, que se utiliza para resolver problemas "que no son árboles" como N-reinas y solucionador de Sudoku.

Retroceso, también llamado búsqueda en profundidad primero

En mi humilde opinión, la mayoría de las respuestas son en gran medida imprecisas y / o sin ninguna referencia para verificar. Permítanme compartirles una explicación muy clara con una referencia .

Primero, DFS es un algoritmo general de recorrido (y búsqueda) de gráficos. Por lo que se puede aplicar a cualquier gráfico (o incluso bosque). El árbol es un tipo especial de gráfico, por lo que DFS también funciona para árbol. En esencia, dejemos de decir que solo funciona para un árbol o similares.

Basado en [1], Backtracking es un tipo especial de DFS que se utiliza principalmente para ahorrar espacio (memoria). La distinción que estoy a punto de mencionar puede parecer confusa, ya que en los algoritmos Graph de este tipo estamos tan acostumbrados a tener representaciones de listas de adyacencia y usar un patrón iterativo para visitar a todos los vecinos inmediatos ( para el árbol son los hijos inmediatos ) de un nodo. , a menudo ignoramos que una mala implementación de get_all_immediate_neighbors puede causar una diferencia en los usos de memoria del algoritmo subyacente.

Además, si un nodo gráfico tiene un factor de ramificación by un diámetro h ( para un árbol, esta es la altura del árbol ), si almacenamos todos los vecinos inmediatos en cada paso de visitar un nodo, los requisitos de memoria serán grandes-O (bh) . Sin embargo, si tomamos solo un vecino (inmediato) a la vez y lo expandimos, entonces la complejidad de la memoria se reduce a big-O (h) . Mientras que el primer tipo de implementación se denomina DFS , el segundo tipo se denomina Backtracking .

Ahora verá, si está trabajando con lenguajes de alto nivel, lo más probable es que esté usando Backtracking disfrazado de DFS. Además, realizar un seguimiento de los nodos visitados para un conjunto de problemas muy grande podría consumir mucha memoria; pidiendo un diseño cuidadoso de get_all_immediate_neighbors (o algoritmos que puedan manejar la revisión de un nodo sin entrar en un bucle infinito).

[1] Stuart Russell y Peter Norvig, Inteligencia artificial: un enfoque moderno, 3ª ed.

La profundidad primero es un algoritmo para atravesar o buscar un árbol. Vea aquí . Retroceder es un término mucho más amplio que se usa siempre que se forma una solución candidata y luego se descarta retrocediendo a un estado anterior. Vea aquí . La búsqueda en profundidad primero utiliza el retroceso para buscar una rama primero (candidata a la solución) y, si no tiene éxito, buscar las otras ramas.

DFS describe la forma en que desea explorar o recorrer un gráfico. Se centra en el concepto de ir lo más profundo posible dada la opción.

El retroceso, aunque generalmente se implementa a través de DFS, se centra más en el concepto de podar los subespacios de búsqueda poco prometedores lo antes posible.

En una búsqueda en profundidad primero , comienza en la raíz del árbol y luego explora lo más lejos posible a lo largo de cada rama, luego retrocede a cada nodo principal posterior y atraviesa sus hijos

Retroceder es un término generalizado para comenzar al final de una meta y retroceder gradualmente, construyendo gradualmente una solución.

En mi opinión, en cualquier nodo específico del backtracking, primero intenta profundizar ramificándose en cada uno de sus hijos, pero antes de ramificarse en cualquiera de los nodos secundarios, debe "borrar" el estado del niño anterior (este paso es equivalente a back caminar hasta el nodo principal). En otras palabras, cada estado de hermanos no debe impactarse entre sí.

Por el contrario, durante el algoritmo DFS normal, normalmente no tiene esta restricción, no necesita borrar (retroceder) el estado de hermanos anteriores para construir el siguiente nodo hermano.

Idea: comience desde cualquier punto, verifique si es el punto final deseado, si es así, entonces encontramos una solución; de lo contrario, va a todas las siguientes posiciones posibles y si no podemos ir más allá, regrese a la posición anterior y busque otras alternativas que marquen esa posición actual. camino no nos llevará a la solución.

Ahora retroceso y DFS son 2 nombres diferentes que se le dan a la misma idea aplicada en 2 tipos de datos abstractos diferentes.

Si la idea se aplica a la estructura de datos matriciales, lo llamamos retroceso.

Si se aplica la misma idea en un árbol o en un gráfico, lo llamamos DFS.

El cliché aquí es que una matriz podría convertirse en un gráfico y un gráfico podría transformarse en una matriz. Entonces, realmente aplicamos la idea. Si está en un gráfico, lo llamamos DFS y si está en una matriz, lo llamamos retroceso.

La idea en ambos algoritmos es la misma.

El retroceso es solo una búsqueda en profundidad con condiciones de terminación específicas.

Considere caminar por un laberinto donde por cada paso que tome una decisión, esa decisión es una llamada a la pila de llamadas (que realiza su primera búsqueda profunda) ... si llega al final, puede regresar a su camino. Sin embargo, si llega a un callejón sin salida, querrá regresar de una determinada decisión, en esencia, regresar de una función en su pila de llamadas.

Entonces, cuando pienso en dar marcha atrás, me preocupo por

1. Estado
2. Decisiones
3. Casos base (condiciones de terminación)

Lo explico en mi video sobre dar marcha atrás aquí .

A continuación se muestra un análisis del código de retroceso. En este código de retroceso quiero todas las combinaciones que darán como resultado una determinada suma u objetivo. Por lo tanto, tengo 3 decisiones que hacen llamadas a mi pila de llamadas, en cada decisión puedo elegir un número como parte de mi ruta para alcanzar el número objetivo, omitir ese número o elegirlo y elegirlo nuevamente. Y luego, si llego a una condición de terminación, mi paso hacia atrás es simplemente regresar . Regresar es el paso de retroceso porque sale de esa llamada en la pila de llamadas.

class Solution:    

"""

Approach: Backtracking 

State
    -candidates 
    -index 
    -target 

Decisions
    -pick one --> call func changing state: index + 1, target - candidates[index], path + [candidates[index]]
    -pick one again --> call func changing state: index, target - candidates[index], path + [candidates[index]]
    -skip one --> call func changing state: index + 1, target, path

Base Cases (Termination Conditions)
    -if target == 0 and path not in ret
        append path to ret
    -if target < 0: 
        return # backtrack 

"""

def combinationSum(self, candidates: List[int], target: int) -> List[List[int]]:
    """
    @desc find all unique combos summing to target
    @args
        @arg1 candidates, list of ints
        @arg2 target, an int
    @ret ret, list of lists 
    """
    if not candidates or min(candidates) > target: return []

    ret = []
    self.dfs(candidates, 0, target, [], ret)
    return ret 

def dfs(self, nums, index, target, path, ret):
    if target == 0 and path not in ret: 
        ret.append(path)
        return #backtracking 
    elif target < 0 or index >= len(nums): 
        return #backtracking 


    # for i in range(index, len(nums)): 
    #     self.dfs(nums, i, target-nums[i], path+[nums[i]], ret)

    pick_one = self.dfs(nums, index + 1, target - nums[index], path + [nums[index]], ret)
    pick_one_again = self.dfs(nums, index, target - nums[index], path + [nums[index]], ret)
    skip_one = self.dfs(nums, index + 1, target, path, ret)