Breite erste Suche Implementierung in Python

Question

Ich versuche, BFS in Python zu implementieren, ich verstehe, wie der Algorithmus funktioniert, aber ich habe nicht viel Programmiererfahrung. Ich habe stundenlang darüber nachgedacht, wie man alles am besten darstellen und so effizient wie möglich sein kann. Ich konnte nicht herausfinden, wie ich den Pfad von meinem Startknoten zum Zielknoten abrufen kann.

Ich habe ewig googeln und andere Leute Umsetzung des Algorithmus suchen, aber meine Anwendung ist etwas anders und das verwirrt mich. Wenn Leute BFS implementieren, gehen sie davon aus, dass ihnen ein Graph zugewiesen wurde (wie auch der Wikipedia-Artikel über BFS). In meinem Problem habe ich einen Anfangszustand und einen Zielzustand, den ich erreichen möchte, aber keinen Graphen oder Baum, also erzeuge ich die Knoten, wie ich gehe.

Zum Beispiel:

def BFS(initial, goal): 

    q = [initial] 
    visited = [] 

    while q: 
     n = q.pop() 
     states = generate_states(n) 

     for state in states: 
      if state == goal: 
       pass #placeholder 
      q.append(state) 
      visited.append(state) 

Es ist nicht richtig konkretisiert, weil ich mit etwas Mühe, bin, ich bin nicht sicher, was es speziell ist entweder ... Wenn Anfangs- und Ziel sind Knoten, und ich schreibe eine struct type Klasse woanders in meinen Code wie zum Beispiel:

class node: 
    state = None 
    parent = None 

Ich denke das ist ein geeigneter Weg um einen Knoten darzustellen. Wenn ich also ein Knotenobjekt aus meiner Warteschlange lösche, hat es Informationen darüber, woher es stammt, das durch die Funktion generate_states initialisiert wird. Dann wird die for-Schleife jeden dieser neuen Knoten an die Warteschlange anhängen, und die besuchte Warteschlange, und sie wird unter einem der erzeugten Knoten wiederholt, hat einen Zustand, der mit meinem Zielzustand übereinstimmt.

Jetzt, da ich den Zielknoten gefunden habe, habe ich eine Liste der besuchten Knoten, aber wenn ich den Pfad den Pfad rückwärts vom Zielknoten verfolgen, verlangsame ich den Algorithmus nicht? Sobald ein Ziel gefunden wurde, würde ich nach seinem Elternelement suchen, sein Elternelement in der besuchten Liste suchen, dann auf das Elternelement des Elternteils usw. schauen, bis ich einen Pfad = [Knotenobjekt, Knotenobjekt, ... hatte. ] vom Anfangsknoten zum Zielknoten.

Dies bringt mich zu einem anderen Problem, wenn ich ein Knotenobjekt erstellen dauert es nur für eine Iteration der While-Schleife. Wie soll ich die Objekte in einem Array speichern, sie benötigen jeweils einen eindeutigen Namen und es gibt keinen offensichtlichen Weg (zu mir), dies zu tun. Dies war das Problem, von dem ich bereits erwähnte, dass ich mir nicht sicher war. Es sieht also so aus, als ob ich Knoten erstelle, aber nur den node.state in der Warteschlange speichere, was sinnlos ist, da ich das Knotenobjekt brauche, um auf node.parent zuzugreifen ...

Warum finde ich das so schwierig, vermisse ich etwas Offensichtliches oder mache ich das zu kompliziert?

Danke fürs Lesen.

Answer 1

Ich kann das meiste davon nicht kommentieren, da ich nicht ganz verstehe, was Sie zu tun versuchen - wie Sie sagen, normalerweise würde ein BFS den Graphen dort bereits haben, also bin ich mir nicht sicher wie Sie schlagen vor, es so zu konstruieren, wie Sie gehen. Aber ich muss dieses Bit antworten:

Wie bin ich die Objekte in einem Array speichern soll, werden sie jeweils benötigen Sie einen eindeutigen Namen

Dies ist definitiv falsch ist. Es gibt absolut keine Notwendigkeit, etwas zu benennen, wenn Sie es nur in einer Liste speichern möchten - Sie können es einfach anhängen. Wenn Sie besorgt sind, dass Sie es später finden können, dann ist es normal, wenn Sie Graphen verwenden, dass Sie jedem Knoten eine Nummer geben, und zwar über einen einzelnen Zähler, den Sie jedes Mal erhöhen, wenn Sie einen definieren. Wenn Sie die Knoten nur in einer Liste speichern, erhalten sie automatisch eine eindeutige Nummer: ihre Position in der Liste.

Answer 2

Ihr Ansatz sieht gut aus für mich.

Um den Discovery-Pfad zu erhalten, können Sie jeden übergeordneten Knoten, z. Geben Sie ihm ein Attribut, das auf den Knoten festgelegt ist, der es entdeckt hat. Auf diese Weise haben Sie eine verknüpfte Liste, die den Erkennungspfad zurückverfolgt. Für Fuß zurück, wenn Sie das Ziel erreicht können Sie

def get_parents(node): 
    if node.parent is None: 
     return [] 

    yield node.parent 
    get_parents(node) 

tun für Spur des erzeugten Knoten (Variable n) zu halten, nur die Knoten setzen Sie in den Listen zu entdecken, nicht nur die Staaten.

n = q.pop() 
    states = generate_states(n) 

    for state in states: 
     m = node() 
     m.state = state 
     m.parent = n 
     if state == goal: 
      pass #placeholder 
     q.append(m) 
     visited.append(m) 

Answer 3

im Allgemeinen, was Sie haben, ist in Ordnung.

aber es gibt ein paar Verwirrungen, die ich versuchen werde zu erklären. Zuerst speichern Sie den Knoten in der Warteschlange, nicht den Status. und da der Knoten ein Elternteil hat, können Sie zu den vorherigen Knoten gelangen, so dass Sie sie nicht verloren haben. Zweitens, die Rückverfolgung durch die Eltern ist nicht etwas, um das Sie sich keine Gedanken machen müssen - Sie tun es nur, wenn Sie erfolgreich sind (auch keine Notwendigkeit für Namen - klingt wie verwirrende Listen mit Karten?).

Das einzige, was in Ihrem Code wirklich fehlt, ist, dass Sie Ihre Knoten nicht erstellen. Wenn Sie einen Status erhalten, erstellen Sie einen Knoten und speichern Sie den Knoten, nicht den Status. dann wird alles funktionieren.