我正在从事在线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不太了解,但是在我看来我的代码应该可以通过此测试。如何修复我的代码,使其能够通过测试?提前致谢!
在这行上:
currentTotalCost = currentCost + stepCost + heuristic(currentState, problem)
您试图找出后继节点上的成本:这应该是到当前节点的路径,加上步骤成本,再加上后继节点上的启发式预期成本。所以我认为你应该打电话heuristic(successor,problem)
,而不是heuristic(currentState,problem)
本文收集自互联网,转载请注明来源。
如有侵权,请联系[email protected] 删除。
我来说两句