Python: Implementierung des Astar-Algorithmus

Question

Ich habe einen Astar-Algorithmus für ein Problem in einem Online-Richter implementiert, der sich auf Labyrinth mit Start- und Endpositionen sowie auf ein Gitter bezieht, das das Labyrinth darstellt. Ich gebe die Länge des Pfades zusammen mit dem Pfad selbst aus. Das Folgende ist die Implementierung in Python unter Verwendung der euklidischen Distanz:

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

Ich würde das nicht alle so auf die gleiche Linie bringen. Ich denke, es wäre viel einfacher, über mehrere Zeilen verteilt zu lesen:

self.start = start
self.grid = grid
self.height = height
self.width = width

---

Ich würde wahrscheinlich die NodeKlasse als oberste Ebene anstatt verschachtelt haben. Ich glaube nicht, dass Sie viel gewinnen, wenn Sie es in sich haben AStar. Sie können es so benennen _Node, dass es "modulprivat" ist, sodass beim Versuch, es in eine andere Datei zu importieren, möglicherweise Warnungen ausgegeben werden.

In Nodeder __lt__Implementierung würde ich den zweiten Parameter nicht aufrufen comparator. Ein Komparator ist etwas, das vergleicht, während dies in diesem Fall nur ein weiterer Knoten ist. other_nodeoder etwas wäre angemessener.

---

In heuristicwürde ich persönlich von einem elsedort Gebrauch machen :

if (distance == "Manhattan"):
    return abs((x1 - x2) + abs(y1 - y2))
else:
    return math.sqrt((x2 - x1)**2 + (y2 - y1)**2)

Es macht klarer, dass nur eine der Zeilen ausgeführt wird. Persönlich vernachlässige ich das elsein einem solchen Fall nur, wenn ifes sich um eine Voraussetzungsprüfung für "vorzeitiges Beenden" handelt, und ich möchte vermeiden, den gesamten Rest der Funktion in einem Block zu verschachteln. Das ist hier allerdings kein Problem.

---

nodeNeighbors( was sein solltenode_neighbors ) wäre sauberer über mehrere Zeilen gebrochen:

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]

Ich denke, das macht es viel einfacher zu sehen, was darin vor sich geht.

---

Wiederum weisen Sie an vielen Stellen zwei oder mehr Variablen in einer Zeile zu:

(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]

Ich würde die auflösen. Insbesondere wenn Sie in einer Zeile 3+ erreichen, muss der Leser von links zählen, um zu sehen, welche Variable mit welchem ​​Wert übereinstimmt, anstatt nur zu überprüfen, was sich auf jeder Seite von a befindet =.

---

In computePathscheint closedListes ein Set zu sein. Es sieht nicht so aus, als ob die Reihenfolge wichtig ist, und es neighbour in closedListwird mit einem Satz schneller sein als mit einer Liste. Es sieht jedoch so aus, openListals müsste es eine Liste sein, da sie an übergeben wird heapify.

---

Ich glaube nicht, dass ich stdinund neu zuweisen würde stdout. Die Neuzuweisung von stdinscheint völlig unnötig zu sein, und Änderungen stdouterschweren das spätere Debuggen mithilfe von printAnweisungen. Sie möchten nicht unbedingt, dass der gesamte gedruckte Text an die Datei gesendet wird.

Bei Bedarf können Sie angeben, in welche Datei beim Drucken gedruckt werden soll:

with open('output.txt', 'w') as out_f:
    print("To file!", file=out_f)