A* algorithm implementation

A* 알고리즘을 구현해 보았다. 전체 코드는 Github 에 업로드 되어있다.

def calc_path(self):
        start = self.grid.start
        start.mindistance = 0.0
        start.h_value = self.heuristic(start)
        openset = [start]
        closedset = set()

        while openset:
            u = heapq.heappop(openset)
            closedset.add(u)

            if u == self.grid.goal:
                break

            for target in self.get_neighbors(u):
                g = 1.0 + u.mindistance
                h = self.heuristic(target)
                f = g + h
                if not target.is_obs:
                    if target.isopen or target in closedset:
                        if target.mindistance > g:
                            target.h_value = f
                            target.mindistance = g
                            target.previous = u
                    else:
                        target.isopen = True
                        target.h_value = f
                        target.mindistance = g
                        target.previous = u
                        heapq.heappush(openset, target)

        self.build_path()

target이 openset에 들어있는지 확인하는 것 때문에 몇 시간을 허비했다;

priority queue에서 target을 검색하면 log(n) 시간이 걸리기 때문에 n이 커지면 dijkstra 알고리즘보다 비 효율적이게 되었다.

그래서 한참을 고민했는데, 그냥 노드에 openset에 들어있는지를 표시하는 플래그를 다는 것으로 해결...