ich von einem archivierten AI Kurs ab 2014Uniform Kosten Graph Such Öffnung zu viele Knoten
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]