BFS- und UCS-Algorithmen. Meine BFS-Implementierung funktioniert, mein UCS jedoch nicht. Kann nicht herausfinden, warum

Question

Solange ich mich nicht irre, ist UCS das gleiche wie BFS mit dem einzigen Unterschied, dass, anstatt den flachsten Knoten zu erweitern, es den Knoten mit den niedrigsten Pfadkosten erweitert. (Dazu verwende ich PriorityQueue anstelle von Queue.) Also kopierte ich meinen BFS-Code, erstellte eine zusätzliche Map, um die Pfadkosten jedes Knotens zu verfolgen und änderte nur die Art und Weise, wie die Elemente in der Queue/Priority-Queue verschoben werden.

Hinweis: getSuccessors (state) gibt eine Liste der Tripel (Zustand, Aktion, Kosten)

Dies sind meine beiden Implementierungen:

BFS:

def breadthFirstSearch(problem): 
    """Search the shallowest nodes in the search tree first.""" 
    queue=Queue() 
    objectQueue=Queue() 
    visited=set() 
    actions=[] 
    flag=0 
    objectMap={} 
    actionMap={} 
    start=problem.getStartState() 
    objectMap[start]=start 
    queue.push(start) 
    objectQueue.push(start) 
    if problem.isGoalState(start): 
     return actions 
    while queue: 
     parent=queue.pop() 
     object=objectQueue.pop() 
     if parent in visited: continue 
     visited.add(parent) 
     if problem.isGoalState(parent): 
       while object!=start: 
         action=actionMap[object] 
         actions.append(action) 
         object=objectMap[object] 
       return actions[::-1] 
     children=problem.getSuccessors(parent) 
     for child in children: 
       queue.push(child[0]) 
       objectQueue.push(child) 
       objectMap[child]=object 
       actionMap[child]=child[1] 
     flag=1 
    util.raiseNotDefined() 

UCS:

Nach dem Autograder bin ich mit BFS funktioniert funktioniert perfekt, aber mein UCS schlägt fehl. Hier ist der Test, dass es und seine Ergebnisse nicht:

 B1   E1 
    ^\  ^\ 
    / V / V 
    *A --> C --> D --> F --> [G] 
     \ ^ \ ^
     V/  V/
     B2   E2 

    A is the start state, G is the goal. Arrows mark 
    possible state transitions. This graph has multiple 
    paths to the goal, where nodes with the same state 
    are added to the fringe multiple times before they 
    are expanded. 

The following section specifies the search problem and the solution. 
The graph is specified by first the set of start states, followed by 
the set of goal states, and lastly by the state transitions which are 
of the form: 

<start state> <actions> <end state> <cost> 


start_state: A 
goal_states: G 
A 0:A->B1 B1 1.0 
A 1:A->C C 2.0 
A 2:A->B2 B2 4.0 
B1 0:B1->C C 8.0 
B2 0:B2->C C 16.0 
C 0:C->D D 32.0 
D 0:D->E1 E1 64.0 
D 1:D->F F 128.0 
D 2:D->E2 E2 256.0 
E1 0:E1->F F 512.0 
E2 0:E2->F F 1024.0 
F 0:F->G G 2048.0 

student solution:  ['1:A->C', '0:C->D', '0:E1->F'] 
student expanded_states: ['A', 'B1', 'C', 'B2', 'D', 'E1', 'F', 'E2'] 

correct solution:  ['1:A->C', '0:C->D', '1:D->F', '0:F->G'] 
correct expanded_states: ['A', 'B1', 'C', 'B2', 'D', 'E1', 'F', 'E2'] 

Answer 1

Sie aktualisieren costMap unabhängig von den aktuellen Werten. So erhöhen Sie wiederholt die Kosten für den noch nicht besuchten gemeinsamen Nachfolger des zuvor besuchten und aktuellen Kindes.

Betrachten Sie dieses Beispiel: Start von A, Ende in C. Es gibt Knoten Kette mit Kosten 1 für jeden Übergang: A-> A1-> A2-> A3-> A4-> A5-> A6-> A7- > A8-> A9-> A10. Jeder von A Knoten führt zu B mit Kosten 3. Und B führt zu C. Ihre aktuelle Implementierung wird die Kosten von B mehrmals von mindestens 3 Knoten (A, A1, A2) aktualisieren, obwohl die tatsächlichen Kosten 3 sind (A-> B).

Sie sollten prüfen, ob Kind in costMap ist, aktuellen costMap-Wert mit neuem vergleichen und nur in Warteschlange schieben, wenn der neue Wert besser ist. Wenn costMap kein untergeordnetes Element enthält, fügen Sie es zu costMap und Warteschlangen hinzu.

Answer 2

es sieht aus wie Sie nicht Ihre Nachfolger richtig zu konstruieren. du bist irgendwie zu e1 gekommen, ohne von da her zu kommen. ich nehme an, du benutzt dicts oder listen. Versuchen Sie, dass Ihr Code nur Tupel verwendet. Auf diese Weise werden Sie keine Referenzen weitergeben und Ihren Code muddeln.

Ich würde mit Daten gehen, die wie folgt aussehen. erstens ist die Priorität, zweitens ist die Liste der Knoten, die wir gereist sind und drittens der nächste Knoten zu erweitern.

queue.push((2, (A, C), D))