Ich habe also ein Problem, das ich mithilfe der Tiefensuche lösen möchte, um den ersten Pfad zurückzugeben, den DFS findet. Hier ist meine (unvollständige) DFS-Funktion:
start = problem.getStartState()
stack = Stack()
visited = []
stack.push(start)
if problem.isGoalState(problem.getStartState):
return something
while stack:
parent = stack.pop()
if parent in visited: continue
if problem.isGoalState(parent):
return something
visited.append(parent)
children = problem.getSuccessors(parent)
for child in children:
stack.push(child[0])
Die Variablen startState und targetState sind einfach ein Tupel von x, y-Koordinaten. Problem ist eine Klasse mit einer Vielzahl von Methoden. Die wichtigsten hier sind getSuccessors (die die untergeordneten Elemente eines bestimmten Status in Form einer Liste mit 3 Elementtupeln zurückgeben. Für diesen Teil des Problems jedoch nur das erste Element des Tupels (child [0]), das Gibt den Status des Kindes in x, y-Koordinaten zurück, ist wichtig) und isGoalState (der die x, y-Koordinaten des Zielstatus bereitstellt).
Ich denke also (an diesem Punkt schwer zu testen), dass diese Funktion bei ordnungsgemäßer Implementierung von allem anderen zurückkehren wird, sobald sie einen Zielzustand erreicht hat. Bitte lassen Sie mich wissen, wenn mir etwas fehlt. Mein größtes Problem ist jedoch, WAS ich zurückgeben soll. Ich möchte, dass es eine Liste aller Zustände ausgibt, die erforderlich sind, um zum Zielzustand zu gelangen, und zwar in der Reihenfolge von Anfang bis Ende. Es scheint nicht so, als würde die einfache Rückgabe meines Stapels den Trick tun, da der Stapel viele nicht besuchte Kinder enthält. Meine besuchte Liste wird auch nichts Nützliches liefern, da es denkbar ist, dass ich Sackgassen erreichen, zurückverfolgen muss, aber immer noch die Sackgassen-Tupel in der besuchten Liste habe. Wie würde ich vorgehen, um die gewünschte Liste zu erhalten?
4 Antworten
Sie haben Recht - Sie können den Stapel nicht einfach zurückgeben, er enthält tatsächlich viele nicht besuchte Knoten.
Wenn Sie jedoch eine Karte (ein Wörterbuch) pflegen: map:Vertex->Vertex
, sodass parentMap[v] = the vertex we used to discover v
Sie Ihren Pfad ermitteln können.
Die Änderung, die Sie vornehmen müssen, befindet sich so ziemlich in der for-Schleife:
for child in children:
stack.push(child[0])
parentMap[child] = parent #this line was added
Wenn Sie später Ihr Ziel gefunden haben, können Sie den Pfad von der Quelle zum Ziel abrufen (Pseudocode):
curr = target
while (curr != None):
print curr
curr = parentMap[curr]
Beachten Sie, dass die Reihenfolge umgekehrt wird. Sie kann gelöst werden, indem Sie alle Elemente auf einen Stapel legen und dann drucken.
Ich habe einmal eine ähnliche (wenn auch nicht identische IMO) Frage zum Auffinden des tatsächlichen Pfads in BFS in diesem Thread beantwortet
Eine andere Lösung besteht darin, eine rekursive Version von DFS anstelle von iterativem + Stapel zu verwenden. Sobald ein Ziel gefunden wurde, werden alle current
Knoten in der Rekursionssicherung gedruckt. Diese Lösung erfordert jedoch eine Neugestaltung des Algorithmus zu einem rekursiven .
P.S. Beachten Sie, dass DFS möglicherweise keinen Pfad zum Ziel findet (selbst wenn ein visited
-Satz beibehalten wird), wenn das Diagramm einen unendlichen Zweig enthält.
Wenn Sie einen vollständigen (findet immer eine Lösung, wenn eine existiert) und optimalen (findet den kürzesten Weg) Algorithmus möchten, möchten Sie möglicherweise BFS oder Iterative Deepening DFS oder sogar A * -Algorithmus, wenn Sie eine heuristische Funktion haben
Ich habe gerade etwas Ähnliches in PHP
implementiert.
Die Grundidee dahinter lautet wie folgt: Warum sollte ich einen anderen Stapel verwalten, wenn es den Aufrufstapel gibt, der an jedem Punkt der Ausführung den Pfad vom Einstiegspunkt widerspiegelt? Wenn der Algorithmus das Ziel erreicht, müssen Sie lediglich auf dem aktuellen Aufrufstapel zurückfahren, wodurch der zurückgelegte Pfad gelesen wird. Hier ist der modifizierte Algorithmus. Beachten Sie die Abschnitte return immediately
.
/**
* Depth-first path
*
* @param Node $node Currently evaluated node of the graph
* @param Node $goal The node we want to find
*
* @return The path as an array of Nodes, or false if there was no mach.
*/
function depthFirstPath (Node $node, Node $goal)
{
// mark node as visited
$node->visited = true;
// If the goal is found, return immediately
if ($node == $goal) {
return array($node);
}
foreach ($node->outgoing as $edge) {
// We inspect the neighbours which are not yet visited
if (!$edge->outgoing->visited) {
$result = $this->depthFirstPath($edge->outgoing, $goal);
// If the goal is found, return immediately
if ($result) {
// Insert the current node to the beginning of the result set
array_unshift($result, $node);
return $result;
}
}
}
return false;
}
Nicht spezifisch für Ihr Problem, aber Sie können diesen Code optimieren und auf verschiedene Szenarien anwenden. Tatsächlich können Sie dafür sorgen, dass der Stapel auch den Pfad enthält.
Beispiel:
A
/ \
C B
\ / \
\ D E
\ /
F
graph = {'A': set(['B', 'C']),
'B': set(['A', 'D', 'E']),
'C': set(['A', 'F']),
'D': set(['B']),
'E': set(['B', 'F']),
'F': set(['C', 'E'])}
def dfs_paths(graph, start, goal):
stack = [(start, [start])]
visited = set()
while stack:
(vertex, path) = stack.pop()
if vertex not in visited:
if vertex == goal:
return path
visited.add(vertex)
for neighbor in graph[vertex]:
stack.append((neighbor, path + [neighbor]))
print (dfs_paths(graph, 'A', 'F')) #['A', 'B', 'E', 'F']
Dieser Link sollte Ihnen sehr helfen ... Es ist ein langer Artikel, der ausführlich über eine DFS-Suche spricht, die einen Pfad zurückgibt ... und ich denke, es ist besser als jede Antwort, die ich oder jemand anderes posten kann
http://www.python.org/doc/essays/graphs/
Verwandte Fragen
Neue Fragen
python
Python ist eine dynamisch typisierte Mehrzweck-Programmiersprache mit mehreren Paradigmen. Es wurde entwickelt, um schnell zu lernen, zu verstehen, zu verwenden und eine saubere und einheitliche Syntax durchzusetzen. Bitte beachten Sie, dass Python 2 ab dem 01.01.2020 offiziell nicht mehr unterstützt wird. Fügen Sie für versionenspezifische Python-Fragen das Tag [python-2.7] oder [python-3.x] hinzu. Wenn Sie eine Python-Variante (z. B. Jython, PyPy) oder eine Bibliothek (z. B. Pandas und NumPy) verwenden, fügen Sie diese bitte in die Tags ein.