Première profondeur de recherche de base

Question

Je suis en train d'améliorer mon algorithme actuel pour le 8 Queens problème, ce qui est la première fois que je suis vraiment affaire avec l'algorithme de conception / algorithmes. Je veux mettre en œuvre une recherche en profondeur d'abord associée à une permutation des différentes valeurs Y décrites ici: http://en.wikipedia.org/wiki/Eight_queens_puzzle#The_eight_queens_puzzle_as_an_exercise_in_algorithm_design

Je l'ai mis en œuvre la partie de permutation pour résoudre le problème, mais je vais avoir un peu de mal envelopper mon esprit autour de la recherche en profondeur d'abord. Il est décrit comme un moyen de traverser un arbre / graphique, mais est-il générer le graphique d'arbre? Il semble que la seule façon que cette méthode serait plus efficace que si la recherche en profondeur d'abord génère la structure de l'arbre à parcourir, en mettant en œuvre une logique seulement générer certaines parties de l'arbre.

Donc, essentiellement, je dois créer un algorithme qui a généré un arbre élagué des permutations lexigraphic. Je sais comment mettre en œuvre la logique de la taille, mais je ne suis pas sûr de savoir comment l'attacher avec le générateur de permutation depuis que je suis en utilisant next_permutation.

Y at-il des ressources qui pourraient me aider avec les bases de recherche d'abord en profondeur ou en créant des permutations lexigraphic sous forme d'arbre?

Answer 1

En général, oui, l'idée de la recherche en profondeur d'abord est que vous n'aurez pas à générer (ou « visite » ou « développer ») chaque nœud.

Dans le cas des huit Queens problème, si vous placez une reine de telle sorte qu'il peut attaquer une autre reine, vous pouvez abandonner cette branche; il ne peut pas conduire à une solution.

Si vous résolvez une variante de huit Queens tel que votre objectif était de trouver un solution, pas tout 92, vous pourriez alors quitter dès que vous avez trouvé un.

Plus généralement, si vous résolvez un problème moins discret, comme trouver le « meilleur » arrangement des reines selon une certaine mesure, alors vous pourriez abandonner une branche dès que vous saviez qu'il ne pouvait pas conduire à un état final mieux que un état final que vous auriez déjà trouvé sur une autre branche. Ceci est lié à la algorithme A * recherche .

Plus généralement encore, si vous attaquez vraiment un gros problème (comme les échecs), vous pouvez être satisfait avec une solution qui n'est pas exacte, vous pouvez abandonner une branche probablement ne peut pas conduire à une solution que vous avez déjà trouvé.

Answer 2

L'algorithme DFS lui-même ne génère pas l'arbre / graphique. Si vous voulez construire l'arbre et le graphique, il est aussi simple construire que vous effectuez la recherche. Si vous ne souhaitez que trouver une soution, une structure de données LIFO plat comme une liste chaînée suffit pour cela: lorsque vous visitez un nouveau nœud, ajoutez à la liste. Lorsque vous quittez un nœud de revenir en arrière dans la recherche, le nœud pop off.

Answer 3

Un livre intitulé « Introduction aux algorithmes » par Anany Levitan a une bonne explication pour votre compréhension. Il a également fourni la solution à 8 reines problème juste la façon dont vous desctribed il. Il sera helpyou sûr.

Je crois comprendre, pour trouver une solution que vous ne avez pas besoin toute permutation tout ce que vous avez besoin est dfs.That SUFFIT seul en solution trouver