A*搜索在python中不起作用

Question

我正在做一个在线人工智能课堂作业。作为作业的一部分，我必须在python中实现一个*搜索。我的代码：

def aStarSearch(problem, heuristic=nullHeuristic):
"""Search the node that has the lowest combined cost and heuristic first."""
"*** YOUR CODE HERE ***"

    fringe = util.PriorityQueue()
    visited = {} # Visited nodes

    if problem.isGoalState(problem.getStartState()):
        return []

    fringe.push((problem.getStartState(),[]),0)

    while not fringe.isEmpty():
        currentState, pathToCurrent = fringe.pop()
        currentCost = problem.getCostOfActions(pathToCurrent)

        if problem.isGoalState(currentState):
            return pathToCurrent

        if currentState not in visited or currentCost<visited[currentState]:
            visited[currentState]=currentCost
            for successor,action,stepCost in problem.getSuccessors(currentState):
                currentTotalCost = currentCost + stepCost + heuristic(currentState, problem)
                fringe.push((successor, pathToCurrent+[action]),currentTotalCost)
    return []

在我看来，它是正确的，但当我运行自动签名机时，它会输出以下内容：

^{pr2}$

我对python不是太有经验，但我觉得我的代码应该通过这个测试。我怎样才能修正我的代码使它通过测试？提前谢谢！在

Answer 1

在这条线上：

currentTotalCost = currentCost + stepCost + heuristic(currentState, problem)

您正试图计算出后继节点的成本：这应该是到当前节点的路径，加上步骤成本，再加上后续节点的启发式预期成本。所以我认为您应该调用heuristic(successor,problem)，而不是{}