Python: реализация алгоритма Astar

Question

Я реализовал алгоритм 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)

Answer 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«закрытым для модуля», чтобы попытка импортировать его в другой файл потенциально могла вызвать предупреждения.

В Node«S __lt__реализации, я бы не назвал второй параметр comparator. Компаратор - это то, что сравнивает, тогда как в данном случае это просто еще один узел. other_nodeили что-нибудь было бы более подходящим.

---

В heuristic, я бы лично использовал elseтам:

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+ в строке, чтобы читатель увидел, какая переменная совпадает с каким значением, ему нужно будет считать слева, а не просто проверять, что находится с каждой стороны =.

---

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