Ich fing gerade an, über Prolog zu lernen und ich fragte mich, warum es dfs anstelle von bfs ist und warum es keinen einfachen Weg gibt, es zu ändern.Warum ist Prolog Vereinheitlichung Tiefensuche zuerst statt Breitensuche?
Verlangt ISO Prolog es?
Zunächst ist es ist ziemlich einfach zu ändern. Die meisten Prologtexte erklären, wie man ein Prädikat schreibt, das ein BFS ausführt, und wie man einen Meta-Interpreter erstellt, der es mit beliebigen Termen macht. Die Wahrheit ist, dass Studenten, die einen Vorgeschmack auf Prolog an der Universität bekommen, die ersten ein oder zwei Wochen mit Prolog durchkommen. Dies zu tun ist nicht genau eine grundlegende Prolog Aufgabe, aber es ist keine erweiterte Prolog Technik entweder. Wenn du zwei Monate auf Prolog verbringst, wäre das keine einschüchternde Sache. Das hört sich nach einer Menge Prolog an, aber verglichen mit (sagen wir) Java ist es wirklich nicht viel. Aus irgendeinem Grund werden wir mit Prolog viel schneller ins Ziel kommen als bei Systemen, die eigentlich weniger interessant sind.
Ich glaube, dass die von ISO vorgeschriebene Suchstrategie SLD Resolution genannt wird, und Tiefensuche zuerst ergibt sich aus diesem Auflösungsmechanismus. Ich habe den ISO-Standard nicht gelesen, also wird vielleicht jemand, der besser informiert ist als ich, kommentieren. Ich denke, es wäre schwierig, die Prolog-Standardisierung zu managen, wenn die Auflösungsmethode (und damit die Tiefe zuerst oder Breite zuerst) nicht obligatorisch wäre, da Berechnungen, die in einer Richtung erfolgreich sind, in die andere gehen können. Ein Sprachstandard, der das Verhalten von normalen Programmen nicht spezifiziert, wäre ein ziemlich schlechter Standard. Es gibt jedoch keinen Grund, warum es keine integrierte Möglichkeit zur Angabe einer alternativen Suchstrategie geben könnte.
Ich kenne nicht den Grund für das Mandat DFS im Besonderen. Nachdem ich Prolog eine Weile benutzt habe, scheint mir die Idee des Nicht-DFS offensichtlich ineffizient zu sein. Zum Beispiel, wenn ich etwas Code hinzufüge, um einen Randfall zu behandeln, werde ich es jedes Mal mit BFS bezahlen, aber nur in Fällen, wo es mit DFS notwendig ist. Ich habe das Gefühl, dass DFS mehr Speicher effizient sein wird; Ich werde zum Beispiel nicht einen Haufen möglicherweise nutzloser Codepfade im Auge behalten müssen. Ich habe das Gefühl, dass DFS wahrscheinlich leichter zu kontrollieren ist, weil ich den Suchbaum leicht beschneiden kann. Aber das sind nur Gefühle; Vielleicht ist mein Gefühl für das, was natürlich ist, ein Ergebnis dessen, was ich benutzt habe. Der Mangel an Existenz eines Prolog-Konkurrenten, der BFS-basiert ist, ist eine Art Vorschlag, dass es vielleicht keine großartige Idee ist. Auf der anderen Seite ist das, was 1980 noch ineffizient war, auch heute noch die Prolog-Implementierungen, auch wenn sich die Dinge heute sehr unterscheiden.
Wenn Sie einen Baum "durchsuchen", können Sie aufhören zu suchen, sobald Sie finden, was Sie suchen. Das bedeutet, dass zwischen einer "Tiefensuche" und einer "Breitensuche" unterschieden wird. Aber Prolog macht keine Suche - es macht eine Berechnung. Es gibt keinen Unterschied zu einer "Tiefen-zuerst-Berechnung" und einer "Breiten-zuerst-Berechnung", da Sie eine vollständige Berechnung durchführen müssen, um ein Ergebnis zu erhalten. – Enigmativity
Sprichst du wirklich über die Tiefe - zuerst in * Vereinigung *? Ist es das was du meinst? – false
Könnten Sie ein Beispiel dafür geben, was Sie mit "* Vereinigung * Tiefensuche" beschreiben? Oder meinst du nur Tiefensuche generell, wie beim Suchen einer Baumstruktur? – lurker