1

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)
4

1 に答える 1

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)

この関数にありました。最後の if は "if 4 and pos > n:" だったので、未踏の状態がありました.. "-1" の場合は 2 日

より多くの単体テストを行うことを教えてくれます

于 2016-11-24T22:17:06.390 に答える