Uniform Kosten Graph Such Öffnung zu viele Knoten

Question

ich von einem archivierten AI Kurs ab 2014

Der Parameter „Problem“ arbeitet an einem Auftrag bezieht sich auf ein Objekt, das verschiedene Kostenfunktionen gewählt zur Lauf (manchmal hat es ist 1 Kosten pro Zug, manchmal sind Züge teurer je nachdem, auf welcher Seite des Pacman Boards die Züge ausgeführt werden.

Wie unten geschrieben, bekomme ich das richtige Verhalten, aber ich öffne mehr Suchknoten als erwartet (etwa 2x was die Aufgabe erwartet).

Wenn ich die Kostenvariable auf negativ setze, bekomme ich das richtige Verhalten im 1-Unit-Kostenfall UND bekomme eine wirklich niedrige Anzahl von Knoten. Aber das Verhalten ist für die Fälle von höheren Kosten für eine gegebene Seite des Brettes entgegengesetzt.

Also grundsätzlich Frage ist: Scheint es, als ob ich im Rahmen einer einheitlichen Kostensuche irgendwelche Knoten unnötig öffne?

def uniformCostSearch(problem): 
    """Search the node of least total cost first.""" 
    def UCS(problem, start): 


      q = util.PriorityQueue() 
      for node in problem.getSuccessors(start): ## Comes a tuple ((x,y), 'North', 1) 
       q.push([node], node[2]) ##Push nodes onto queue one a time (so they are paths) 

      while not q.isEmpty(): 
       pathToCheck = q.pop() ##Pops off the lowest priorty path on the queue? 
       #if pathToCheck in q.heap: 
       # continue 
       lastNode = pathToCheck[-1][0] ## Gets the coordinates of that last node in that path 
       if problem.isGoalState(lastNode): ##Checks if those coordinates are goal 
        return pathToCheck ## If goal, returns that path that was checked 
       else: ## Else, need to get successors of that node and put them on queue 
        for successor in problem.getSuccessors(lastNode): ##Gets those successors the popped path's last node and iterates over them 
         nodesVisited = [edge[0] for edge in pathToCheck] ##Looks at all the edges (the node plus its next legal move and cost) and grabs just the coords visited (nodes) 
         if successor[0] not in nodesVisited: ## ##Checks to see if those visited were in THIS particular path (to avoid cyclces) 
          newPath = pathToCheck + [successor] ## If ONE successor was not in path, adds it to the growing path (will do the next one in next part of loop) 
          cost = problem.getCostOfActions([x[1] for x in newPath]) 
          q.update(newPath, cost) #Pushes that validated new path onto the back of the queue for retrieval later 
      return None 

    start = problem.getStartState()#Starting point of stack 
    successorList = UCS(problem, start) 
    directions = [] 
    for i in range(len(successorList)): 
     directions += successorList[i] 
    return directions[1::3] 

Answer 1

Ich fand es heraus.

Während ich überprüfe, dass ich Knoten innerhalb eines bestimmten Pfades nicht erneut besuche, überprüfe ich nicht, ob ich Knoten in anderen Pfaden in der Warteschlange besuche. Ich kann das überprüfen, indem ich eine nodesVisited-Liste hinzufüge, die nur alle Knoten anfügt, die ich je besucht habe, und das für doppelte Besuche überprüfe.