Tiefensuche Basics

Question

Ich versuche, meinen aktuellen Algorithmus für das 8 Queens Problem zu verbessern, und dies ist das erste Mal, dass ich wirklich bin mit der Entwicklung von Algorithmen / Algorithmen zu tun. Ich mag eine Tiefensuche mit einer Permutation der verschiedenen Y-Werte kombiniert implementieren hier beschrieben: http://en.wikipedia.org/wiki/Eight_queens_puzzle#The_eight_queens_puzzle_as_an_exercise_in_algorithm_design

habe ich die Permutationsteil implementiert, das Problem zu lösen, aber ich bin mit einer wenig Mühe schlingt meine Gedanken um die Tiefensuche. Es wird als eine Möglichkeit beschrieben, einen Baum / Graph zu überqueren, aber ist es, den Baum Graph erzeugen? Es scheint die einzige Möglichkeit, dass diese Methode nur effizienter wäre, wenn die Tiefensuche die Baumstruktur erzeugt durchlaufen werden, um eine gewisse Logik Umsetzung nur auf bestimmte Teile des Baumes erzeugen.

So im Wesentlichen, würde ich einen Algorithmus erstellen, die einen beschnittenen Baum von lexigraphic Permutationen erzeugt. Ich weiß, wie die Beschneidung Logik zu implementieren, aber ich bin einfach nicht sicher, wie es in der Permutation Generator zu binden, da ich next_permutation war verwenden.

Gibt es irgendwelche Ressourcen, die mir mit den Grundlagen der Tiefen Suche helfen könnten oder lexigraphic Permutationen in Baumform erstellen?

Answer 1

In der Regel ja, die Idee der Tiefensuche ist, dass Sie nicht erzeugen müssen (oder „Besuch“ oder „erweitern“) jeden Knoten.

Im Falle des Acht-Damen Problem, wenn Sie eine Königin platzieren, so dass es eine andere Königin angreifen können, können Sie diesen Zweig abbrechen; es kann nicht zu einer Lösung führen.

Wenn Sie waren eine Variante der Acht-Damen lösen, so dass Ihr Ziel zu finden war eine Lösung, die nicht alle 92, dann könnte man, sobald man einen gefunden beenden.

Generell, wenn Sie ein weniger diskretes Problem waren zu lösen, wie die „beste“ Anordnung von Königinnen zu finden, bis zu einem gewissen Maße nach, dann könnte man einen Zweig so bald abbrechen, wie Sie es wussten nicht besser zu einem Endzustand führen könnte als ein Endzustand Sie würden bereits auf einem anderen Zweig gefunden. Dies bezieht sich auf die A * -Algorithmus .

allgemeiner Auch, wenn Sie ein wirklich großes Problem angreifen (wie Schach), können Sie mit einer Lösung zufrieden sein, die nicht exakt ist, so dass Sie einen Zweig abbrechen können, dass wahrscheinlich kann nicht führen zu einer Lösung haben Sie bereits gefunden.

Answer 2

Der DFS-Algorithmus selbst erzeugt nicht den Baum / Diagramm. Wenn Sie den Baum und Grafik aufbauen wollen, dann ist es so einfach, den Aufbau, wie Sie die Suche durchführen. Wenn Sie nur eine soution finden wollen, eine flache LIFO-Datenstruktur wie eine verknüpfte Liste wird hierfür genügen: Wenn Sie einen neuen Knoten besuchen, um es in die Liste anhängen. Wenn Sie einen Knoten zurückverfolgen bei der Suche verlassen, knallt die Knoten aus.

Answer 3

Ein Buch mit dem Titel „Einführung in den Algorithmen“ von Anany levitan hat eine richtige Erklärung für Ihr Verständnis. Er stellte auch die Lösung auf 8 Damen-Problem, so wie Sie es desctribed. Es wird helpyou sicher.

Als mein Verständnis, für die Suche nach einer Lösung, die Sie brauchen nicht jede Permutation alles, was Sie brauchen, ist dfs.That wird einsam suffice in Lösung zu finden