Python: Implementasi algoritma Astar

Question

Saya telah menerapkan algoritma Astar untuk masalah pada hakim online yang berkaitan dengan labirin yang diberikan posisi awal dan akhir bersama dengan kisi yang mewakili labirin. Saya menampilkan panjang jalur bersama dengan jalur itu sendiri. Berikut ini adalah implementasi dengan Python menggunakan jarak Euclidean:

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

Saya tidak akan menempatkan semua ini pada baris yang sama seperti itu. Saya pikir akan lebih mudah membaca tersebar di beberapa baris:

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

---

Saya mungkin akan memiliki Nodekelas sebagai tingkat atas daripada bersarang. Saya tidak berpikir Anda mendapatkan banyak keuntungan dengan menyimpannya di dalam AStar. Anda dapat menamainya _Nodeuntuk menjadikannya "module-private" sehingga mencoba mengimpornya ke file lain berpotensi memunculkan peringatan.

Dalam Node's __lt__pelaksanaan, saya tidak akan menyebut parameter kedua comparator. Pembanding adalah sesuatu yang membandingkan, sedangkan dalam kasus ini, itu hanyalah node lain. other_nodeatau sesuatu yang lebih tepat.

---

Di heuristic, saya secara pribadi akan menggunakan di elsesana:

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

Ini membuatnya lebih jelas bahwa hanya satu baris yang akan dieksekusi. Secara pribadi, saya hanya mengabaikan elsedalam kasus seperti itu jika ifitu adalah pemeriksaan prasyarat "keluar awal", dan saya ingin menghindari menumpuk seluruh fungsi lainnya di dalam blok. Tapi itu bukan masalah di sini.

---

nodeNeighbors( yang seharusnyanode_neighbors ) akan lebih bersih dipecah menjadi beberapa baris:

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]

Saya pikir itu membuatnya lebih mudah untuk melihat apa yang terjadi di dalamnya.

---

Sekali lagi, di banyak tempat Anda menetapkan dua atau lebih variabel dalam satu baris:

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

Saya akan memecahnya. Terutama setelah Anda mencapai 3+ dalam satu baris, agar pembaca dapat melihat variabel apa yang cocok dengan nilai apa, mereka harus menghitung dari kiri alih-alih hanya memeriksa apa yang ada di setiap sisi a =.

---

Dalam computePath, sepertinya closedListharus menjadi satu set. Ini tidak tampak seolah-olah urutan penting dengannya, dan neighbour in closedListakan lebih cepat dengan satu set daripada dengan daftar. Sepertinya openListdiperlukan daftar meskipun karena itu diteruskan ke heapify.

---

Saya tidak berpikir saya akan ditugaskan kembali stdindan stdout. Penetapan ulang stdintampaknya sama sekali tidak diperlukan, dan perubahan stdoutakan mempersulit proses debug nanti menggunakan printpernyataan. Anda tidak perlu selalu ingin semua teks tercetak dikirim ke file.

Jika perlu, Anda dapat menentukan file apa yang ingin Anda cetak saat mencetak:

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