Python: Triển khai thuật toán Astar
Tôi đã triển khai thuật toán Astar cho một vấn đề trên một thẩm phán trực tuyến liên quan đến các vị trí bắt đầu và kết thúc của mê cung cùng với một lưới đại diện cho mê cung. Tôi xuất ra chiều dài của đường dẫn cùng với chính đường dẫn đó. Sau đây là cách triển khai trong Python bằng cách sử dụng khoảng cách Euclide:
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)
Trả lời
self.start, self.grid, self.height, self.width = start, grid, height, width
Tôi sẽ không đặt tất cả những thứ này vào cùng một dòng như vậy. Tôi nghĩ sẽ dễ dàng hơn nhiều nếu đọc trải dài trên nhiều dòng:
self.start = start
self.grid = grid
self.height = height
self.width = width
Tôi có thể sẽ có Nodelớp là toplevel thay vì lồng nhau. Tôi không nghĩ rằng bạn đang đạt được nhiều lợi nhuận bằng cách có nó bên trong AStar. Bạn có thể đặt tên nó _Nodethành "module-private" để cố gắng nhập nó vào một tệp khác sẽ có khả năng gây ra cảnh báo.
Trong Node's __lt__thực hiện, tôi sẽ không gọi tham số thứ hai comparator. Bộ so sánh là một cái gì đó so sánh, trong khi trong trường hợp này, đó chỉ là một nút khác. other_nodehoặc một cái gì đó sẽ thích hợp hơn.
Trong heuristic, cá nhân tôi muốn sử dụng một elseở đó:
if (distance == "Manhattan"):
return abs((x1 - x2) + abs(y1 - y2))
else:
return math.sqrt((x2 - x1)**2 + (y2 - y1)**2)
Nó làm rõ ràng hơn rằng chỉ một trong các dòng sẽ được thực thi. Cá nhân tôi chỉ bỏ qua elsetrong trường hợp như vậy nếu ifkiểm tra điều kiện "thoát sớm" và tôi muốn tránh lồng toàn bộ phần còn lại của hàm vào trong một khối. Đó không phải là vấn đề ở đây.
nodeNeighbors( lẽ ranode_neighbors ) sẽ rõ ràng hơn bị phá vỡ qua một số dòng:
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]
Tôi nghĩ rằng điều đó làm cho nó dễ dàng hơn rất nhiều để xem những gì đang xảy ra trong đó.
Một lần nữa, ở nhiều nơi, bạn chỉ định hai hoặc nhiều biến trên một dòng:
(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]
Tôi sẽ chia tay chúng. Đặc biệt là khi bạn đạt đến 3+ trên một dòng, để người đọc thấy biến nào khớp với giá trị nào, họ sẽ cần đếm từ bên trái thay vì chỉ kiểm tra những gì ở mỗi bên của a =.
Trong computePath, có vẻ như closedListnên là một bộ. Có vẻ như thứ tự không quan trọng với nó, và neighbour in closedListsẽ nhanh hơn với một bộ so với một danh sách. Có vẻ như openListbắt buộc phải là một danh sách do nó được chuyển đến heapify.
Tôi không nghĩ rằng tôi sẽ chỉ định lại stdinvà stdout. Việc gán lại stdincó vẻ như hoàn toàn không cần thiết và việc thay đổi stdoutsẽ khiến việc gỡ lỗi sau này trở nên khó khăn hơn khi sử dụng các printcâu lệnh. Bạn không nhất thiết muốn tất cả văn bản in được gửi vào tệp.
Nếu cần, bạn có thể chỉ định tệp bạn muốn in khi in:
with open('output.txt', 'w') as out_f:
print("To file!", file=out_f)