Kürzester Pfad zwischen zwei Trie-Knoten
Dies ist eine zweifache Frage, weil ich keine Ideen habe, wie ich dies am effizientesten umsetzen kann.
Ich habe ein Wörterbuch mit 150.000 Wörtern, das in einer Trie-Implementierung gespeichert ist. Hier sieht meine spezielle Implementierung aus: 
Ein Benutzer wird mit zwei Wörtern versehen. Mit dem Ziel, den kürzesten Weg von anderen englischen Wörtern (geändert um jeweils ein Zeichen) vom Anfangswort zum Endwort zu finden.
Zum Beispiel:
Start: Hund
Ende: Katze
Pfad: Hund, Punkt, Kinderbett, Katze
Pfad: Hund, Kogge, Log, Bog, Bot, Kinderbett, Katze
Pfad: Hund, Doe, Joe, Freude, Jot, Kinderbett, Katze
Meine aktuelle Implementierung hat mehrere Iterationen durchlaufen, aber am einfachsten kann ich Pseudocode bereitstellen (da der eigentliche Code mehrere Dateien enthält):
%Vor%Bekannte:
- Ein Startwort und ein Endwort
- Wörter haben die gleiche Länge
- Wörter sind englische Wörter
- Es ist möglich, dass es keinen Pfad gibt
Frage:
Mein Problem ist, dass ich keine effiziente Möglichkeit habe, ein potenzielles Wort zu bestimmen, ohne es zu versuchen - ohne das Alphabet zu erzwingen und jedes neue Wort gegen das Wörterbuch zu prüfen. Ich weiß, dass es eine Möglichkeit für einen effizienteren Weg gibt, Präfixe zu verwenden, aber ich kann keine richtige Implementierung herausfinden, oder eine, die nicht nur die Verarbeitung verdoppelt.
Zweitens, sollte ich einen anderen Suchalgorithmus verwenden, habe ich A * und Best First Search als Möglichkeiten betrachtet, aber diese erfordern Gewichte, die ich nicht habe.
Gedanken?
2 Antworten
Wie in den Kommentaren gefordert, illustriere ich, was ich meine, indem ich verknüpfte Wörter in den Bits von ganzen Zahlen kodiere.
In C ++ sieht es vielleicht so aus ...
%Vor% Nachdem der obige Code ausgeführt wurde, links[x] - wobei x ein Wort ist, dessen Buchstabe durch einen Unterstrich ersetzt wird a la d_g - ruft eine Ganzzahl ab, die die Buchstaben angibt, die den Unterstrich ersetzen können, um bekannte Wörter zu bilden. Wenn das niedrigstwertige Bit eingeschaltet ist, dann ist "dag" ein bekanntes Wort, wenn das Next-from-least-significant-Bit eingeschaltet ist, dann ist "dbg" das bekannte Wort etc ..
Intuitiv würde ich erwarten, ganze Zahlen zu verwenden, um den Gesamtspeicher für Verknüpfungsdaten zu reduzieren, aber wenn die Mehrheit der Wörter nur jeweils ein paar verknüpfte Wörter hat, kann das Speichern eines Indexes oder Zeigers auf diese Wörter tatsächlich weniger Speicher verbrauchen - und sein einfacher, wenn Sie nicht an bitweise Manipulationen gewöhnt sind, zB:
%Vor%Wie auch immer, Sie haben dann ein Diagramm, das jedes Wort mit denen verbindet, in die es sich verwandeln kann, mit Einzelzeichen-Änderungen. Sie können dann die Logik des Dijkstra-Algorithmus anwenden, um den kürzesten Weg zwischen zwei beliebigen Wörtern zu finden.
Tags und Links python javascript algorithm performance sorting