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"로 지정하여 다른 파일로 가져 오려고하면 경고가 발생할 수 있습니다.
에서 Node의 __lt__구현, 나는 두 번째 매개 변수를 호출하지 것이다 comparator. 비교기는 비교하는 것이지만이 경우에는 다른 노드 일뿐입니다. other_node또는 뭔가 더 적절할 것입니다.
에서는 heuristic개인적으로 elsethere를 사용합니다.
if (distance == "Manhattan"):
return abs((x1 - x2) + abs(y1 - y2))
else:
return math.sqrt((x2 - x1)**2 + (y2 - y1)**2)
행 중 하나만 실행된다는 것이 더 명확 해집니다. 개인적으로 나는 "초기 종료"전제 조건 검사 인 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]
나는 그것이 무슨 일이 일어나고 있는지 훨씬 쉽게 볼 수 있다고 생각합니다.
다시 말하지만 많은 곳에서 한 줄에 두 개 이상의 변수를 할당합니다.
(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]
나는 그것들을 분해 할 것입니다. 특히 한 줄에서 3+에 도달하면 독자가 어떤 변수가 어떤 값과 일치하는지 확인하려면 .NET Framework의 각 측면에 무엇이 있는지 확인하는 대신 왼쪽부터 계산해야합니다 =.
에서는 세트 여야 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)