Python：Astarアルゴリズムの実装
迷路を表すグリッドとともに、開始位置と終了位置を指定した迷路に関連するオンラインジャッジの問題に対してAstarアルゴリズムを実装しました。パス自体と一緒にパスの長さを出力します。以下は、ユークリッド距離を使用したPythonでの実装です。
import heapq, math, sys
infinity = float('inf')
class AStar():
def __init__(self, start, grid, height, width):
self.start, self.grid, self.height, self.width = start, grid, height, width
class Node():
def __init__(self, position, fscore=infinity, gscore=infinity, parent = None):
self.fscore, self.gscore, self.position, self.parent = fscore, gscore, position, parent
def __lt__(self, comparator):
return self.fscore < comparator.fscore
def heuristic(self, end, distance = "Euclidean"):
(x1, y1), (x2, y2) = self.start, end
if (distance == "Manhattan"):
return abs(x1 - x2) + abs(y1 - y2)
return math.sqrt((x2 - x1)**2 + (y2 - y1)**2)
def nodeNeighbours(self, pos):
(x, y) = pos
return [(dx, dy) for (dx, dy) in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)] if 0 <= dx < self.width and 0 <= dy < self.height and self.grid[dy][dx] == 0]
def getPath(self, endPoint):
current, path = endPoint, []
while current.position != self.start:
path.append(current.position)
current = current.parent
path.append(self.start)
return list(reversed(path))
def computePath(self, end):
openList, closedList, nodeDict = [], [], {}
currentNode = AStar.Node(self.start, fscore=self.heuristic(end), gscore = 0)
heapq.heappush(openList, currentNode)
while openList:
currentNode = heapq.heappop(openList)
if currentNode.position == end:
return self.getPath(currentNode)
else:
closedList.append(currentNode)
neighbours = []
for toCheck in self.nodeNeighbours(currentNode.position):
if toCheck not in nodeDict.keys():
nodeDict[toCheck] = AStar.Node(toCheck)
neighbours.append(nodeDict[toCheck])
for neighbour in neighbours:
newGscore = currentNode.gscore + 1
if neighbour in openList and newGscore < neighbour.gscore:
openList.remove(neighbour)
if newGscore < neighbour.gscore and neighbour in closedList:
closedList.remove(neighbour)
if neighbour not in openList and neighbour not in closedList:
neighbour.gscore = newGscore
neighbour.fscore = neighbour.gscore + self.heuristic(neighbour.position)
neighbour.parent = currentNode
heapq.heappush(openList, neighbour)
heapq.heapify(openList)
return None
if __name__ == '__main__':
sys.stdin = open('input.txt', 'r')
sys.stdout = open('output.txt', 'w')
matrix = [[int(num) for num in line.split()] for line in sys.stdin]
size = matrix.pop(0)
coordinates = matrix.pop(0)
n, m = size[0], size[1]
x1, y1, y2, x2 = coordinates[0], coordinates[1], coordinates[2], coordinates[3]
path = AStar((x1-1, y1-1), matrix, n, m).computePath((y2-1, x2-1))
print(len(path))
for pos in path:
print(pos[0] + 1, pos[1] + 1)
回答
self.start, self.grid, self.height, self.width = start, grid, height, width
私はこれらすべてをそのように同じ行に置くことはしません。複数行にまたがって読む方がはるかに簡単だと思います。
self.start = start
self.grid = grid
self.height = height
self.width = width
私はおそらくNode、ネストされたクラスではなく、トップレベルとしてクラスを持っているでしょう。私はあなたがそれを中に持っていることによって多くを得ているとは思わないAStar。名前を付けて_Node「module-private」にすることで、別のファイルにインポートしようとすると警告が発生する可能性があります。
実装で、私は2番目のパラメータを呼び出すことはありません。コンパレータは比較するものですが、この場合、それは単なる別のノードです。または何かがより適切でしょう。Node__lt__comparatorother_node
でheuristic、私は個人的にelseそこを利用します：
if (distance == "Manhattan"):
return abs((x1 - x2) + abs(y1 - y2))
else:
return math.sqrt((x2 - x1)**2 + (y2 - y1)**2)
1行だけが実行されることが明確になります。個人的には、が「早期終了」の前提条件チェックelseである場合にのみ無視し、if残りの関数全体をブロック内にネストしないようにします。ただし、ここでは問題ありません。
nodeNeighbors（そうあるべきですnode_neighbors）いくつかの行にまたがってよりきれいになります：
def nodeNeighbours(self, pos):
(x, y) = pos
return [(dx, dy)
for (dx, dy) in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]
if 0 <= dx < self.width and 0 <= dy < self.height and self.grid[dy][dx] == 0]
これにより、何が起こっているのかを簡単に確認できるようになると思います。
繰り返しますが、多くの場所で、1行に2つ以上の変数を割り当てています。
(x1, y1), (x2, y2) = self.start, end
current, path = endPoint, []
openList, closedList, nodeDict = [], [], {}
x1, y1, y2, x2 = coordinates[0], coordinates[1], coordinates[2], coordinates[3]
私はそれらを分割します。特に、1行で3+に到達すると、読者がどの変数がどの値と一致するかを確認するには、の両側にあるものを確認するだけでなく、左から数える必要があります=。
computePathように、それは思わclosedList設定する必要があります。順序が重要であるようには見えずneighbour in closedList、リストよりもセットの方が高速になります。にopenList渡されているため、リストである必要があるように見えますheapify。
私は再割り当てしたいとは思わないstdinとstdout。の再割り当てはstdin完全に不要のようであり、変更stdoutすると、後でprintステートメントを使用してデバッグするのが難しくなります。印刷されたすべてのテキストをファイルに送信する必要はありません。
必要に応じて、印刷時に印刷するファイルを指定できます。
with open('output.txt', 'w') as out_f:
print("To file!", file=out_f)