我正在为 8 谜题实现具有曼哈顿距离的 A 星算法。[解决方案是螺旋形式]
1 2 3
8 0 4
7 6 5
在某些情况下,从 A 到 B 的步数与从 B 到 A 的步数不同。
我认为这是因为当它们具有相同的成本时,它不会在打开列表中选择相同的状态,因此不会扩展相同的节点。
从
7 6 4
1 0 8
2 3 5
(A -> B)
7 6 4
1 8 0
2 3 5
(B -> A)
7 6 4
1 3 8
2 0 5
两者使用曼哈顿距离具有相同的值。我应该探索所有具有相同价值的路径吗?还是我应该改变启发式以进行某种决胜局?
这是代码的相关部分
def solve(self):
cost = 0
priority = 0
self.parents[str(self.start)] = (None, 0, 0)
open = p.pr() #priority queue
open.add(0, self.start, cost)
while open:
current = open.get()
if current == self.goal:
return self.print_solution(current)
parent = self.parents[str(current)]
cost = self.parents[str(current)][2] + 1
for new_state in self.get_next_states(current):
if str(new_state[0]) not in self.parents or cost < self.parents[str(new_state[0])][2]:
priority = self.f(new_state) + cost
open.add(priority, new_state[0], cost)
self.parents[str(new_state[0])] = (current, priority, cost)