A*搜索不在python中工作

Question

我正在进行在线AI课程作业.作为赋值的一部分,我必须在python中实现A*搜索.我的代码:

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 []

它对我来说是正确的,但是当我运行自动编程器时,它会输出以下内容:

*** FAIL: test_cases/q4/astar_1_graph_heuristic.test
***     graph:
***              2     3     2
***           S --- A --- C ---> G
***           | \       /       ^
***         3 |  \ 5   / 1     / 
***           |   \   /       / 
***           B --- D -------/
***              4         5  
***         
***         S is the start state, G is the goal.  Arrows mark possible state 
***         transitions.  The number next to the arrow is the cost of that transition.
***         
***         The heuristic value of each state is:
***             S 6.0
***             A 2.5
***             B 5.25
***             C 1.125
***             D 1.0625
***             G 0
***     student solution:       ['0', '0', '2']
***     student expanded_states:    ['S', 'A', 'C', 'D']
*** 
***     correct solution:       ['0', '0', '2']
***     correct expanded_states:    ['S', 'A', 'D', 'C']
***     correct rev_solution:       ['0', '0', '2']
***     correct rev_expanded_states:    ['S', 'A', 'D', 'C']

我对python不太熟悉,但在我看来我的代码应该通过这个测试.如何修复我的代码以便通过测试？提前致谢!

Answer 1

在这一行:

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

您试图计算后继节点的成本:应该是当前节点的路径,加上步骤成本加上后继节点的启发式预期成本.所以我认为你应该打电话heuristic(successor,problem),而不是heuristic(currentState,problem)