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?

35
user1427661 12 Okt. 2012 im 21:13

4 Antworten

Beste Antwort

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

40
Community 23 Mai 2017 im 11:54

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;
}
1
raam86 6 Juli 2013 im 00:05

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']
14
XueYu 7 Sept. 2016 im 17:40

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/

4
Joran Beasley 12 Okt. 2012 im 17:17