下面的代码
for k in list(g_score.keys()):
print(g_score[k])
返回 KeyError对我来说:
Traceback (most recent call last):
File "./np.py", line 134, in <module>
main()
File "./np.py", line 131, in main
NPuzzle(n).solve()
File "./np.py", line 116, in solve
print(g_score[k])
KeyError: 3
我不明白这怎么可能 print(list(g_score.keys()))是[4, 3, 7] . 3字典里写的很清楚。
对于上下文,我正在尝试对 N-Puzzle 问题实现 A* 搜索(我什至不确定 A* 是否正确实现,因为我无法克服这个错误),并且以下State类和 solve功能:
class State:
def __init__(self, blank_idx, puzzle, g=0, h=0):
self.blank_idx = blank_idx
self.puzzle = puzzle
self.f = g + h
def __eq__(self, other):
return self.puzzle == other.puzzle
def __hash__(self):
return self.f + self.blank_idx
def __lt__(self, other):
return self.f < other.f
def __repr__(self):
return str(self.f)
...
class NPuzzle:
# ...other stuff
def solve(self):
start_state = State(
self.puzzle.index(' '),
self.puzzle,
0,
self.cost(self.puzzle)
)
g_score = {start_state: 0}
open_set = [start_state]
path = {}
while open_set:
state = open_set[0]
if state.puzzle == self.goal_state:
break
heappop(open_set)
for next_state in self.neighbors(state):
g = g_score[state] + 1
if next_state in g_score and g >= g_score[next_state]:
continue
path[next_state] = state
g_score[next_state] = g
next_state.f = g + self.cost(next_state.puzzle)
heappush(open_set, next_state)
我第一次遇到错误是在我所在的行上:
g = g_score[state] + 1
我不确定为什么这个 KeyError正在发生,但我假设这可能与我的习惯有关 __hash()__功能。
请您参考如下方法:
好吧,原来问题是我立即更改了哈希函数所依赖的 State 实例的属性...糟糕:
State 的__hash()__ 函数是:
return self.f + self.blank_idx
我在 g_score 中存储 State 的方式如下:
g_score[next_state] = g
next_state.f = g + self.cost(next_state.puzzle)
原来上面的代码破坏了一切,因为它使用 next_state.f 将 next_state 放入 g_score,但紧接着在下一行我变异 next_state.f
像这样切换两个语句的顺序:
next_state.f = g + self.cost(next_state.puzzle)
g_score[next_state] = g
解决了我的问题。
