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ให้เป็น "module-private" เพื่อที่การพยายามอิมพอร์ตไปยังไฟล์อื่นอาจทำให้เกิดคำเตือน

ใน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+ ในบรรทัดเพื่อให้ผู้อ่านเห็นว่าตัวแปรใดตรงกับค่าใดพวกเขาจะต้องนับจากด้านซ้ายแทนที่จะตรวจสอบว่ามีอะไรอยู่ในแต่ละด้านของ a =.

---

ใน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)