Memoisierung ohne Array

In der Einführung in Algorithmen von Cormen et al. Wird in Abschnitt 15.3 Elemente der dynamischen Programmierung das Speichern wie folgt erläutert:

Ein gespeicherter rekursiver Algorithmus verwaltet einen Eintrag in einer Tabelle zur Lösung jedes Teilproblems. Jeder Tabelleneintrag enthält anfangs einen speziellen Wert, der angibt, dass der Eintrag noch ausgefüllt werden muss. Wenn das Unterproblem zum ersten Mal auftritt, während sich der rekursive Algorithmus entfaltet, wird seine Lösung berechnet und dann in der Tabelle gespeichert. Bei jedem weiteren Auftreten dieses Unterproblems wird einfach der in der Tabelle gespeicherte Wert nachgeschlagen und zurückgegeben.

Und es fügt als Fußnote hinzu:

Dieser Ansatz setzt voraus, dass wir die Menge aller möglichen Unterproblemparameter kennen und die Beziehung zwischen Tabellenpositionen und Unterproblemen hergestellt haben. Ein anderer, allgemeinerer Ansatz besteht darin, sich zu merken, indem Hashing mit den Unterproblemparametern als Schlüssel verwendet wird.

Gibt es bekannte DP-Probleme, bei denen es erforderlich ist (oder einfacher ist), gespeicherte Werte in einem Wörterbuch statt in einem (mehrdimensionalen) Array zu speichern?

Hintergrund: Wenn dies von Nutzen ist, liegt der Grund für diese Frage darin, dass ich versuche, die Vorstellung von (selbstausgeglichenen) binären Suchbäumen für Personen zu motivieren, die gerade dynamische Programmierung erlebt haben.

Es gibt wahrscheinlich bessere Beispiele, aber hier ist eines, das mir auf den Kopf gestellt ist:

$S,T$$\le d$$>d$

Ich möchte 2 Beispiele nennen.

0-1 Rucksackproblem

Im Fall des 0-1-Rucksackproblems (wobei W die Kapazität des Rucksacks und N die Anzahl der Elemente ist) ist es manchmal besser, die dynamische Top-Down-Programmierung mit Memoisierung anstelle der systematischen Bottom-Up-Aufzählung zu verwenden des gesamten 2D-Arrays der Größe WxN (insbesondere in einem Fall, in dem die Kapazität des Rucksacks W groß ist, die Kardinalität des Satzes der zulässigen Kombinationen von Gegenstandsgewichten jedoch viel kleiner als W ist ).

In diesem Fall kann man aus Gründen der Speicherersparnis das Wörterbuch anstelle des 2D-Arrays zum Speichern verwenden.

Earley-Parsing-Algorithmus

Der Earley-Parsing-Algorithmus kann zum Parsen von Anweisungen verwendet werden, die zu einer kontextfreien Grammatik gehören. Im Gegensatz zum CYK-Algorithmus (der auf dem Bottom-Up-DP-Ansatz basiert und eine 2D-Tabelle zum Speichern verwendet) verwendet der Earley-Parser den Top-Down-Ansatz in Kombination mit dem Analysediagramm zum Speichern.

Das Parsing-Diagramm enthält die teilweise geparsten grammatikalischen Produktionen (z. B. bei gegebener Produktion X → AB und nach erfolgreicher Zuordnung des A- Teils dieser Produktion speichern wir die teilweise angepasste Produktion innerhalb des Parsing-Diagramms: X → A • B , wobei der Punkt zeigt zum bereits abgeglichenen Teil).

Die Anzahl der Spalten im Analysediagramm entspricht der Anzahl der Token. Im Allgemeinen kann es jedoch sehr schwierig sein, die Anzahl der teilweise analysierten Grammatikproduktionen pro Spalte zu schätzen (dies hängt von der Grammatik und der jeweiligen Reihenfolge der Token ab).

Daher ist es bequemer, das Analysediagramm basierend auf der Wörterbuchdatenstruktur zu implementieren.

Im Bereich der Verarbeitung natürlicher Sprache ist normalerweise der Earley-Pareser die bequemere Wahl, da für die Grammatik keine Chomsky-Normalform erforderlich ist (und CYK hat eine solche Anforderung).

Nach meiner Erfahrung in der kompetitiven Programmierung ist die Verwendung einer Hash-Tabelle (Python dictoder ähnliches) oft praktischer als die Verwendung eines Arrays, da jeder Hash-Datentyp als Schlüssel verwendet werden kann, z. B. Zeichenfolgen, Mengen ( frozensetin Python) oder Tupel wie (string, int)usw. Wenn Sie ein Array verwenden, müssen Sie alle Schlüssel manuell in ganze Zahlen (beginnend bei 0) übersetzen, was zusätzlichen Aufwand bedeutet und möglicherweise nicht möglich ist, wenn Sie den Speicherplatz der Schlüssel im Voraus nicht kennen. Wörterbücher sind also eher allgemeiner als Arrays.

Wenn Sie mit der Verwendung von Arrays durchkommen können, ist dies wahrscheinlich schneller, da das wiederholte Berechnen von Hashes vermieden wird (auf der anderen Seite muss zuerst das gesamte Array initialisiert werden, was Zeit und Speicher beansprucht). Das Schreiben des Codes kann jedoch länger dauern weil Sie die zusätzliche Arbeit machen müssen, alle Schlüssel in ganze Zahlen zu übersetzen.