我正在处理在线 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 []
它对我来说看起来是正确的，但是当我运行 autograder 时，它会输出以下内容:
*** 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 不太熟悉，但在我看来我的代码应该可以通过此测试。我怎样才能修复我的代码以使其通过测试？提前致谢!
请您参考如下方法:
在这一行:
currentTotalCost = currentCost + stepCost + heuristic(currentState, problem)
您正在尝试计算后继节点的成本:这应该是到当前节点的路径加上步长成本，再加上后继节点的启发式预期成本。所以我认为你应该调用 heuristic(successor,problem)，而不是 heuristic(currentState,problem)
