Stub-Warnung: Dieser Artikel ist sehr kurz und behandelt nur die grundlegendsten Aspekte des Themas.
Der Artikel zu Proof-Number Search enthält Erläuterungen für einige der Begriffe und Konzepte, die auch für diesen Artikel relevant sind. Zur besseren Klarheit empfiehlt es sich deswegen, den Artikel zu PNS zuerst zu lesen.
Depth-First Proof-Number (kurz df-pn oder dfpn) ist ein Algorithmus zur Traversierung von UND-/ODER-Bäumen (Spielbäumen). Er wurde von A. Nagai als, wie der Name bereits suggeriert, depth-first Alternative zum best-first-Algorithmus Proof-Number Search (PNS) entwickelt[1] , und kombiniert wie dieser die Konzepte von Proof- und Disproof-Zahl.
Dieser Artikel basiert auf den in diesem [2] Paper vorgestellten Untersuchungen.
Während PNS ein best-first-Verfahren ist, ist df-pn als Tiefensuchalgorithmus konzipiert. Die Kernidee besteht darin, das Verhalten von PNS beizubehalten, und gleichzeitig Vorteile der Tiefensuche, wie geringeren Speicherverbrauch und leichtere Erweiterbarkeit, zu nutzen.
Dies wird durch die Verwendung von zwei Schwellenwerten (thresholds) für jeden Knoten erreicht:
Die Suche unterhalb eines Knotens wird fortgesetzt, bis dessen Proof-Zahl oder Disproof-Zahl den entsprechenden Schwellenwert erreicht.
Ähnlich wie bei PNS wählt dfpn den zu expandierenden vielversprechendsten Knoten (engl: most-proving node) anhand spezifischer Kriterien aus:
Dazu verwendet dfpn eine Technik namens Multiple Iterative Deepening. Dabei werden die Schwellenwerte für die Kindknoten dynamisch angepasst. Beispielsweise wird der Proof-Zahl-Schwellenwert für den ausgewählten Kindknoten an einem ODER-Knoten unter Berücksichtigung der zweitbesten Proof-Zahl unter den Geschwisterknoten gesetzt.
Das Paper beweist, dass dfpn durch diesen Mechanismus stets denselben vielversprechendsten Knoten zur Expansion auswählt wie PNS. Die beiden Algorithmen sind in diesem Sinne äquivalent, was bedeutet, dass dfpn ebenso effizient sucht wie PNS, aber die praktischen Vorteile eines Tiefensuchealgorithmus bietet.
Nagai, A. (2002). Df-pn algorithm for searching AND/OR trees and its applications. Ph. D. thesis, Department of Information Science, University of Tokyo. ↩︎
Nagai, A., & Imai, H. (2002). Proof for the equivalence between some best-first algorithms and depth-first algorithms for AND/OR trees. IEICE TRANSACTIONS on Information and Systems, 85(10), 1645-1653. ↩︎