Explicar BFS y DFS en términos de dar marcha atrás

Question

Wikipedia primera búsqueda en profundidad:

Profundidad-primera búsqueda (DFS) es un algoritmo para el desplazamiento o la búsqueda un árbol, estructura de árbol, o un gráfico. Uno comienza en la raíz (seleccionando un nodo como la raíz en el caso gráfico) y explora lo más posible a lo largo de cada rama antes de retroceder.

¿Qué es Breadth First Search?

"un algoritmo que elija un nodo de inicio, comprueba todos los nodos Backtracks, elige el camino más corto, eligió vecino nodos Backtracks, eligió el camino más corto, finalmente encuentra el camino óptimo porque de atravesar cada trayectoria debido a la continua backtracking.

RegexPoda de- retroceso?

El término retroceso confunde debido a su variedad de uso. El find de UNIX poda un SO-usuario explicado con retroceso. Regex Buddy usa el término "backtracking catastrófico" si no limita el alcance de sus Regexes. Parece ser un término general demasiado utilizado. Entonces:

1. ¿Cómo se define "retroceder" específicamente para Graph Theory?
2. ¿Qué es "retroceder" en la búsqueda inicial y la primera búsqueda de amplitud?

[Agregado]

buenas definiciones sobre dar marcha atrás y ejemplos

1. The Brute-force method
2. de Stallman (?) Inventado plazo "dependency-directed backtracking"
3. Backtracking y regex ejemplo
4. Depth First Search definition.

Answer 1

La confusión viene en retroceso porque es algo que sucede durante la búsqueda, pero también se refiere a una técnica de resolución de problemas específicos, donde se realiza una gran cantidad de retroceso. Tales programas se llaman backtrackers.

Imagen conduciendo hacia un vecindario, siempre tomando la primera curva que ve (suponiendo que no hay bucles) hasta llegar a un callejón sin salida, en cuyo punto conduce a la intersección de la siguiente calle no visitada. Este es el "primer" tipo de retroceso, y es más o menos equivalente al uso coloquial de la palabra.

El uso más específico se refiere a una estrategia de resolución de problemas que es similar a la búsqueda en profundidad pero retrocede cuando se da cuenta de que no vale la pena continuar descendiendo por algún subárbol.

Dicho de otra manera: un DFS ingenuo visita ciegamente cada nodo hasta que alcanza el objetivo. Sí, "retrocede" en los nodos de las hojas. Pero un backtracker también retrocede en ramas inútiles. Un ejemplo es buscar palabras en un tablero Boggle. Cada azulejo está rodeado por otras 8, por lo que el árbol es enorme, y el DFS ingenuo puede llevar demasiado tiempo. Pero cuando vemos una combinación como "ZZQ", podemos dejar de buscar de forma segura desde este punto, ya que agregar más letras no hará que una palabra.

Me encantan estas conferencias de la Prof. Julie Zelenski. Ella resuelve 8 reinas, un rompecabezas de sudoku y un rompecabezas de sustitución de números utilizando retroceso, y todo está muy animado. Programming Abstractions, Lecture 10 Programming Abstractions, Lecture 11

Un árbol es una gráfica en la que dos vértices sólo tienen un camino entre ellos. Esto elimina la posibilidad de ciclos. Cuando estás buscando un gráfico, normalmente tendrás un poco de lógica para eliminar los ciclos, así que el comportamiento es el mismo. Además, con un gráfico dirigido, no puede seguir los bordes en la dirección "incorrecta".

Por lo que puedo decir, en el artículo de Stallman desarrollaron un sistema lógico que no solo dice "sí" o "no" en una consulta sino que realmente sugiere soluciones para consultas incorrectas haciendo el menor número de cambios. Puede ver dónde podría entrar en juego la primera definición de retroceso.