1

によって生成されたタイルを追跡するのに苦労していgetAdjacentTiles(..)ます。getAdjacentTiles以下の A* 実装のパフォーマンスの問題は、以前に見たタイルを追跡していないNodeことopenSetですclosedSet。これまでに作成されたすべてのタイルとして Node オブジェクトのリストを使用し、それを に渡して、getAdjacentTiles生成されたタイルが既にアクセスされているかどうかを判断することにしました。

私の問題は、これらのタイルを適切に追跡できないように見えることです。私のA *がその場所に到達するために約4回以上の動きをする必要があるときはいつでも、endそれは失敗します. これは、私がどのようにタイルを追跡しようとしているかに関係していると確信しています(これもまたNode、訪問されたものです)問題はpythonの知識にあると思わなければなり.apped(tile)ません。セットgetAdjacentTiles(...)をループするときallTiles

ここに私をこれに導いた質問へのリンクがあります

エラーが発生しました (場合によっては、A* パスが約 3 ステップよりも長い場合のみ..)

File "P3.py", line 67, in aStar
 openSet.remove(curNode) 
KeyError: <__main__.Node instance at 0xa39edcc>

ソース

  #Perform an A* search to find the best path to the dirt
  def aStar(self, current, end):
    openSet = set()
    openHeap = []
    closedSet = set()
    allTiles = set()
    curNode = Node(0, current, self.manHatDist(current, end))
    openSet.add(curNode)
    allTiles.add(curNode)
    openHeap.append((curNode.cost,curNode))
    while openSet:
      curNode = heapq.heappop(openHeap)[1]
      if curNode.pos == end:
          return self.getDirections(curNode)
      openSet.remove(curNode)
      closedSet.add(curNode)
      adjNodes = self.getAdjacentNodes(curNode.pos, allTiles)
      for tile in adjNodes:
        t = tile
        if t not in closedSet:
          cost = (curNode.cost - self.manHatDist(curNode.pos, end) 
                  + self.euclidDist(curNode.pos, current)
                  + self.manHatDist(t.pos, end))
          if t not in openSet or cost < t.cost:
            t.parent = curNode
            t.cost = cost
            openSet.add(t)
            heapq.heappush(openHeap, (cost,t))
        allTiles.add(t)
    return []

  #Get the moves made to get to this endNode
  def getDirections(self, endNode):
    moves = []
    tmpNode = endNode
    while tmpNode.parent is not None:
      moves.append(tmpNode.value)
      tmpNode = tmpNode.parent
    moves.reverse()
    return moves

  #Return all possible moves from given tile as Node objects
  def getAdjacentNodes(self, curPos, allTiles):
    allMoves = ['North','South','East','West']
    posMoves = []
    for direction in allMoves:
      if(self.canMove(direction, curPos)):
        posMoves.append(Node(direction, self.getLocIfMove(curPos, direction)))
    retNodes = []
    for posLocNode in posMoves:
      set = False
      for tile in allTiles:
        if(posLocNode.pos == tile.pos):
          set = True
          retNodes.append(tile)
      if(not set):
        retNodes.append(posLocNode)
    return retNodes
4

1 に答える 1

0

対話型インタープリターを起動して、何が見つかるか見てみましょう。(あなたは質問であなたのクラスの名前を与えなかったので、私はそれを呼びましたSearch。)

>>> Search().aStar((0,0), (2,2))
Traceback (most recent call last):
  ...
  File "q19128695.py", line 25, in aStar
    openSet.remove(curNode)
KeyError: <__main__.Node instance at 0x104895518>

OK、最初の問題は、これらのNodeインスタンスが自明ではないということです。「Node instance at 0x104895518」では何もできないので、クラスに__repr__メソッドを追加しましょう。Node

def __repr__(self):
    return 'Node({0.value}, {0.pos}, {0.cost})'.format(self)

そしてさらに試みる:

>>> Search().aStar((0,0), (2,2))
Traceback (most recent call last):
  ...
  File "q19128695.py", line 25, in aStar
    openSet.remove(curNode)
KeyError: Node(East, (1, 2), 3.41421356237)

OK、それはより有益です。Python デバッガーを起動して、事後分析を行います。

>>> import pdb
>>> pdb.pm()
> q19128695.py(25)aStar()
-> openSet.remove(curNode)
(Pdb) openSet
set([Node(North, (2, -1), 6.0), Node(East, (2, 2), 4.65028153987), 
     Node(West, (-1, 1), 5.0), Node(North, (0, -1), 5.0),
     Node(South, (1, 3), 6.65028153987), Node(South, (0, 3), 6.0), 
     Node(East, (3, 0), 6.0), Node(West, (-1, 0), 5.0),
     Node(North, (1, -1), 5.0), Node(East, (3, 1), 6.65028153987),
     Node(West, (-1, 2), 6.0)])
(Pdb) closedSet
set([Node(0, (0, 0), 4), Node(South, (2, 1), 3.41421356237),
     Node(East, (1, 1), 3.0), Node(South, (0, 1), 3.0),
     Node(East, (2, 0), 3.0), Node(East, (1, 0), 3.0),
     Node(East, (1, 2), 3.41421356237), Node(South, (0, 2), 3.0)])
(Pdb) curNode
Node(East, (1, 2), 3.41421356237)
(Pdb) curNode in closedSet
True

したがって、ノードはすでに閉じられています。これはどうして起こったのでしょうか?ノードが にopenSetopenHeap2 回追加された場合に発生する可能性があります。その後、2 回ポップされopenHeapますが (ヒープには複数の同一のアイテムが存在する可能性があるため)、削除できるのはopenSet1 回だけです。問題のコードは次のようになります。

if t not in openSet or cost < t.cost:
    t.parent = curNode
    t.cost = cost
    openSet.add(t)
    heapq.heappush(openHeap, (cost,t))

これに関する最初の問題は、オブジェクトとメソッド(cost, t)を提供するために苦労したにもかかわらず、ペアをプッシュすることです。代わりに、ヒープにプッシュするだけです。Node__lt____gt__t

heapq.heappush(openHeap, t)

これには、他の場所でいくつかの変更が必要です。

openHeap.append((curNode.cost,curNode))
while openSet:
    curNode = heapq.heappop(openHeap)[1]

あなたは書かなければならないでしょう

openHeap = [curNode]
while openSet:
    curNode = heapq.heappop(openHeap)

さて、2 つ目の問題 (これは私のせいです。申し訳ありません) は、tが既に存在する場合、openSetそれをヒープに再度追加してはならないということです。代わりに、再ヒープ化する必要があります。

t_open = t in openSet
if not t_open or cost < t.cost:
    t.parent = curNode
    t.cost = cost
    if t_open:
        heapq.heapify(openHeap)
    else:
        openSet.add(t)
        heapq.heappush(openHeap, t)

デバッガーの出力に戻って、これを思い出してください。

(Pdb) curNode
Node(East, (1, 2), 3.41421356237)

それ3.41421356237はあなたを心配する必要があります: コストは常に整数であるべきではありませんか? コスト計算がまだ間違っているようです。それは言います:

    cost = (curNode.cost
            - self.manHatDist(curNode.pos, end) 
            + self.euclidDist(curNode.pos, current)
            + self.manHatDist(t.pos, end))

しかし、その 3 行目は次のように言う必要があります。

            + self.euclidDist(curNode.pos, t.pos)

これらすべての修正が完了したら、もう一度試してみましょう。

>>> Search().aStar((0,0), (2,2))
['North', 'North', 'East', 'East']

コメントへの返信

  1. Search().aStar(...)「通訳からどうやって電話したの?」インタープリターを実行し、インタープリター プロンプトでそのコード行を入力しました。チュートリアルを参照してください

  2. 「したがって、ユークリッド距離は常に 1 になります。」はい、一様コスト グリッドでパスを検索している場合、隣接間のユークリッド距離は常に同じになります。

  3. 「今思えば、curNode.cost - self.manHatDist(curNode.pos, end)常にゼロです」それは正しくありません。あなたの実装でcostは、検索ノードの は、(i) 最初からそのノードに到達するコストと、(ii) そのノードから最後に到達するコストの許容可能な推定値を加えたものです。したがって、許容される推定値を差し引くと、(i) に戻る必要があります。

于 2013-10-02T10:36:07.867 に答える