A* 搜索在 python 中不起作用

Question

我正在处理在线 AI class 作业。作为作业的一部分，我必须在 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)

A* 搜索在 python 中不起作用

A* search not working in python

python

a-star