algorithm - grafos - busqueda en profundidad inteligencia artificial
¿Cuál es la diferencia entre el retroceso y la búsqueda en profundidad? (9)
Creo que esta respuesta a otra pregunta relacionada ofrece más ideas.
Para mí, la diferencia entre el retroceso y el DFS es que el retroceso maneja un árbol implícito y el DFS trata con uno explícito. Esto parece trivial, pero significa mucho. Cuando el espacio de búsqueda de un problema es visitado por backtracking, el árbol implícito se recorre y se poda en medio de él. Sin embargo, para DFS, el árbol / gráfico con el que trata se construye explícitamente y los casos inaceptables ya se han desechado, es decir, se han eliminado antes de realizar cualquier búsqueda.
Por lo tanto, el retroceso es DFS para el árbol implícito, mientras que el DFS es un retroceso sin poda.
¿Cuál es la diferencia entre el retroceso y la búsqueda en profundidad?
En una búsqueda en profundidad , comienzas en la raíz del árbol y luego exploras a lo largo de cada rama, luego retrocedes hacia cada nodo padre subsiguiente y cruzas sus hijos
Retroceder es un término generalizado para comenzar al final de un objetivo, y retroceder gradualmente, construyendo gradualmente una solución.
Idea: comience desde cualquier punto, verifique si es el punto final deseado, si es así, entonces encontramos una solución, las demás posiciones posibles y si no podemos ir más allá, vuelva a la posición anterior y busque otras alternativas que marquen esa corriente El camino no nos llevará a la solución.
Ahora el retroceso y el 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, la llamamos backtracking.
Si la misma idea se aplica en un árbol o gráfico, lo llamamos DFS.
El cliché aquí es que una matriz se podría convertir en un gráfico y una gráfica se podría transformar en una matriz. Entonces, en realidad 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.
La profundidad primero es un algoritmo para atravesar o buscar un árbol. Ver aqui Retroceder es un término mucho más amplio que se usa cuando se forma una solución candidata y luego se descartan al retroceder a un estado anterior. Ver Backtracking La primera búsqueda en profundidad utiliza el retroceso para buscar primero en una rama (candidato a la solución) y, si no tiene éxito, buscar en las otras ramas.
Por lo general, el retroceso se implementa como DFS más poda de búsqueda. Recorrerás la profundidad del árbol de búsqueda, primero construyendo soluciones parciales en el 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 igual que lo hace DFS, también necesita eliminar 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 soluciones parciales lo antes posible, da un paso atrás e intenta encontrar el óptimo local de nuevo.
Nada se detiene para atravesar el árbol del espacio de búsqueda usando BFS y ejecutar la estrategia de seguimiento 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 a la altura, así que desperdiciaríamos mucho espacio muy rápidamente. Es por eso que los árboles usualmente se recorren 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 el retroceso se está repitiendo en un espacio problemático en busca de una solución. Backtracking es un algoritmo más general que no necesariamente se relaciona con los árboles.
Yo diría, DFS es la forma especial de retroceso; Retroceder es la forma general de DFS.
Si extendemos DFS a problemas generales, podemos llamarlo backtracking. Si utilizamos el retroceso para resolver problemas relacionados con el árbol / gráfico, podemos llamarlo DFS.
Llevan la misma idea en aspecto algorítmico.
Backtracking es un algoritmo de propósito más general.
La búsqueda en profundidad es una forma específica de retroceso relacionado con la búsqueda de estructuras de árboles. De Wikipedia:
Uno comienza en la raíz (seleccionando algún nodo como la raíz en el caso del gráfico) y explora en la medida de lo posible a lo largo de cada rama antes de volver atrás.
Utiliza el retroceso como parte de sus medios para trabajar con un árbol, pero se limita a una estructura de árbol.
Sin embargo, el retroceso se puede usar en cualquier tipo de estructura donde se puedan eliminar partes del dominio, ya sea un árbol lógico o no. El ejemplo de Wiki utiliza un tablero de ajedrez y un problema específico: puede observar un movimiento específico y eliminarlo, luego retroceder al siguiente movimiento posible, eliminarlo, etc.
OMI, en cualquier nodo específico del retroceso, intenta profundizar primero ramificándose en cada uno de sus hijos, pero antes de ramificarse en cualquiera de los nodos secundarios, debe "borrar" el estado anterior del niño (este paso es equivalente a retroceder caminar hasta el nodo padre). En otras palabras, el estado de cada hermano no debe impactar entre sí.
Por el contrario, durante el algoritmo DFS normal, normalmente no tiene esta restricción, no necesita borrar (volver atrás) el estado de los hermanos anteriores para construir el siguiente nodo hermano.