Einen Weg durch ein Wörterbuch finden

Question

Ich habe ein Wörterbuch, das Zeichenketten Mengen von Zeichenketten zuordnet. Als Spielzeug Beispiel:

d = {'a': {'b', 'c', 'd'}, 
'b': {'c', 'x'}, 
'c': {'d', 'z'}} 

Die Idee ist, dass jeder String Karten auf einen Satz von Saiten, die jeweils wieder Karten zu seinem eigenen Satz von Saiten usw.

mag ich eine Funktion f(start, d, pathLength) das wird Nehmen Sie eine Startzeichenfolge, das Wörterbuch und eine Pfadlänge, und geben Sie den ersten Pfad durch das gefundene Wörterbuch mit der Länge pathLength zurück. Eine Invariante ist, dass ein Pfad nicht fortgesetzt werden kann, wenn sein letztes Element einem Wert entspricht, der bereits im Pfad vorhanden ist.

Ich schrieb Code, der den gesamten Baum rekursiv konstruiert, aber das ist ziemlich rechenintensiv und scheint unnötig. Um die benötigte Zeit zu reduzieren, ließ ich Knoten mit einer gewissen Wahrscheinlichkeit aufbauen. Ich möchte das stochastische Feature beibehalten, so dass jedes Mal, wenn die Funktion ausgeführt wird, ein anderer Pfad zurückgegeben wird. Ich denke, es gibt eine Möglichkeit, dies mit einem Stack und einer Schleife ohne Rekursion zu tun, aber ich war nicht erfolgreich.

Answer 1

Dies ist ein klassischer Algorithmus in der Graphentheorie; Bitte suchen Sie nach einem Weg durch einen gerichteten Graphen. Dijktra's algorithm ist der Standard für den kürzesten Weg. Wenn Sie jedoch genau die angegebene Pfadlänge möchten, müssen Sie es ein wenig ändern.

Im Allgemeinen sollten Sie eine Liste mit den Schritten führen, die Sie benötigen, um zu jedem Knoten zu gelangen: Behalten Sie alle Möglichkeiten, anstatt nur die kürzesten. Die allgemeine Gliederung lautet:

**search list** <- start node 
**found list** <- [] 
While the **search list** is not empty: 
    Pop the next node (call it **here**) from the search list. 
    If the current path length < desired path length: 
     For each node **next** reachable from **here**: 
     If **next** is already on the **found list**, 
      Add the present path to its entry on the found list. 
      Follow the downstream paths from **here** and update their paths with the new path to **here** (alternate solutions). 
     Else 
      Add **next** and the present path to the **found list**. 
      Add **next** to the search list.