Fundamentos primera búsqueda en profundidad

Question

Estoy tratando de mejorar mi actual algoritmo para el problema 8 Queens, y esta es la primera vez que realmente estoy tratando con el algoritmo de diseño / algoritmos. Quiero poner en práctica una búsqueda en profundidad combinada con una permutación de los diferentes valores de Y descritas aquí: http://en.wikipedia.org/wiki/Eight_queens_puzzle#The_eight_queens_puzzle_as_an_exercise_in_algorithm_design

He implementado la parte de permutación para resolver el problema, pero estoy teniendo un poco de problemas para envolver mi mente alrededor de la búsqueda en profundidad. Se describe como una forma de recorrer un árbol / gráfica, pero tampoco genera el gráfico árbol? Parece que la única forma en que este método sería más eficiente sólo si la búsqueda en profundidad genera la estructura de árbol para ser atravesado, mediante la aplicación de una lógica que sólo generan ciertas partes del árbol.

Así que, esencialmente, lo habría hecho para crear un algoritmo que genera un árbol podado de permutaciones lexigraphic. Sé cómo implementar la lógica de la poda, pero no estoy seguro de cómo atar adentro con el generador de permutación desde que estoy usando next_permutation.

¿Hay algún recurso que me podrían ayudar con los fundamentos de la profundidad primeras búsquedas o la creación de permutaciones lexigraphic en forma de árbol?

Answer 1

En general, sí, la idea de la búsqueda en profundidad es que usted no tendrá que generar (o "visita" o "expandir") cada nodo.

En el caso del problema de las ocho reinas, si coloca una reina tal que puede atacar a otra reina, se puede abortar esa rama; no puede llevar a una solución.

Si estuviera resolviendo una variante de ocho reinas de tal manera que su objetivo era encontrar un solución, no todos los 92, entonces usted podría dejar de fumar tan pronto como lo encontró uno.

De forma más general, si estuviera resolviendo un problema menos discreta, como encontrar el "mejor" disposición de las reinas de acuerdo con alguna medida, a continuación, se puede abortar a una rama tan pronto como se supo que no podría llevar a un estado final mejor que un estado final que ya habías encontrado en otra rama. Esto se relaciona con la * Un algoritmo de búsqueda .

Incluso de manera más general, si usted está atacando un problema muy grande (como el ajedrez), puede ser satisfecha con una solución que no es exacta, por lo que puede abortar una rama que probablemente no puede conducir a una solución ya has encontrado.

Answer 2

El propio algoritmo DFS no genera el árbol / gráfico. Si usted quiere construir el árbol y el gráfico, es tan simple como la construcción de realizar la búsqueda. Si sólo desea encontrar uno soution, una estructura de datos LIFO plana como una lista enlazada será suficiente para esto: cuando se visita un nuevo nodo, añádelo a la lista. Al salir de un nodo que dar marcha atrás en la búsqueda, aparecerá el nodo fuera.

Answer 3

Un libro titulado "Introducción a los algoritmos" por levitan anany tiene una explicación adecuada para su comprensión. También proporcionó la solución a 8 reinas problema de la manera que se desctribed. Será helpyou con seguridad.

Como mi entendimiento, para encontrar una solución que no necesita cualquier permutación todo lo que necesita es dfs.That bastará solo en la búsqueda de solución