パスの発見：AからBまでの距離がAからBまでではない

Question

私は8つのパズルのマンハッタン距離でAスターアルゴリズムを実装しています。 BからAへ行くような工程の数が同じになりませんBに行くから、いくつかのケースで

1 2 3 
8 0 4 
7 6 5 

[ソリューションは、らせん状である]

私はそれがないので、これがあると思います同じコストを持っているので、同じノードを展開していないオープンリストで同じ状態を選択しないでください。両方がマンハッタン距離を使用して同じ値を持つ

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) 

Answer 1

の関連する部分です。

def get_next_states(self, mtx, direction): 
    n = self.n 
    pos = mtx.index(0) 
    if direction != 1 and pos < self.length and (pos + 1) % n: 
     yield (self.swap(pos, pos + 1, mtx),pos, 3) 
    if direction != 2 and pos < self.length - self.n: 
     yield (self.swap(pos, pos + n, mtx),pos, 4) 
    if direction != 3 and pos > 0 and pos % n: 
    yield (self.swap(pos, pos - 1, mtx),pos, 1) 
    if direction != 4 and pos > n - 1: 
    yield (self.swap(pos, pos - n, mtx),pos, 2) 

これはこの機能に含まれていました。 「-1」

のためにそれは私が「より多くのユニットテスト