Python: Astar algoritması uygulaması

Question

Labirenti temsil eden bir ızgara ile birlikte başlangıç ​​ve bitiş konumları verilen labirentle ilgili çevrimiçi bir jüri üzerindeki bir problem için Astar algoritmasını uyguladım. Yolun uzunluğunu yolun kendisiyle birlikte çıkardım. Aşağıdakiler, Öklid mesafesini kullanan Python'daki uygulama:

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

Bunların hepsini aynı satıra koymam. Birden fazla satıra yayılmış okumanın çok daha kolay olacağını düşünüyorum:

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

---

NodeSınıfı muhtemelen yuvalanmış yerine üst düzey olarak alırdım. İçeride bulundurarak pek bir şey kazanacağını sanmıyorum AStar. _NodeBaşka bir dosyaya aktarmaya çalışmak potansiyel olarak uyarılara neden olması için onu "modül-özel" yapmak için adlandırabilirsiniz.

In Nodebireyin __lt__uygulanması, ikinci parametre demezdim comparator. Bir karşılaştırıcı, karşılaştıran bir şeydir, oysa bu durumda bu sadece başka bir düğümdür. other_nodeyoksa bir şey daha uygun olur.

---

İçinde heuristic, şahsen bir elseoradan faydalanırdım :

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

Satırlardan yalnızca birinin yürütüleceğini daha net hale getirir. Kişisel olarak, elseböyle bir durumda , yalnızca if"erken çıkış" ön koşul kontrolü ise ihmal ediyorum ve işlevin geri kalanının tamamını bir bloğun içine yerleştirmekten kaçınmak istiyorum. Yine de burada sorun değil.

---

nodeNeighbors( olması gerekennode_neighbors ) birkaç satırdan daha temiz bir şekilde kırılmış olacaktır:

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]

Bence bu, içinde neler olduğunu görmeyi çok daha kolay hale getiriyor.

---

Yine, birçok yerde bir satıra iki veya daha fazla değişken atarsınız:

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

Ben onları kırardım. Özellikle bir satırda 3+ 'ye ulaştığınızda, okuyucunun hangi değişkenin hangi değerle eşleştiğini görmesi için, a'nın her iki tarafında ne olduğunu kontrol etmek yerine soldan saymaları gerekecektir =.

---

İçinde computePath, closedListbir set olmalı gibi görünüyor . Sipariş önemliymiş gibi görünmüyor ve neighbour in closedListbir setle, bir listeyle olduğundan daha hızlı olacak. Görünüşe göre openList, aktarıldığı için bir liste olması gerekiyor heapify.

---

Ben yeniden atama sanmıyorum stdinve stdout. Öğesinin yeniden atanması stdintamamen gereksiz görünüyor ve değiştirmek stdoutdaha sonra printifadeler kullanılarak hata ayıklamayı zorlaştıracak . Tüm yazdırılan metnin dosyaya gönderilmesini istemezsiniz .

Gerekirse, yazdırırken hangi dosyaya yazdırmak istediğinizi belirtebilirsiniz:

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