Somnipathy

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에 들어있는지를 표시하는 플래그를 다는 것으로 해결...

얼마전에 생각했던 Rubik's cube 해결 알고리즘을 고민하면서, 이곳 저곳을 찾아봤다. 찾아보다보니, 구현 자체보다는 그에 관련된 내용들을 많이 접하고 공부하는 게 더 중요하다는 생각이 들었다.

이번에 소개할 알고리즘은 A*(A star) algorithm이다. 이 알고리즘은 Shortest path problem을 푸는 데 주로 사용된다. A* 알고리즘은 다익스트라(Dijkstra) 알고리즘의 변형판 쯤된다.

우선, 해당 알고리즘을 소개하기전에, 다익스트라 알고리즘과 Best-first search에 대해 간단히 이야기해보자.

다익스트라 알고리즘과 Best-first search는 둘 다 greedy 알고리즘이며, 어쨌든 출발 지점에서 도착 지점까지의 가장 짧은 경로를 탐색하는데 사용된다.

둘 사이의 가장 중요한 차이점은 다음과 같다.

1. 다익스트라 알고리즘은 출발지점과 앞으로 선택할 지점 간의 거리를 기준으로 다음 선택지를 고른다.

2. Best-First search는 도착지점과 앞으로 선택할 지점 간의 거리를 기준으로 다음 선택지를 고른다.

그러니까, 대략적으로 다익스트라는 출발지를 중심으로 하고, 출발지와 도착지의 거리를 반지름으로 하는 범위에 있는 것들을 대부분 탐색하게 된다. 반면에, Best-first search는 도착지점으로 향하는 방향에 있는 녀석들만 탐색하게 된다. 따라서 best-first search가 다익스트라에 비해 수행시간이 훨씬 빠르다.

여기에서 best-first search는 문제점이 있다. 바로 다익스트라는 찾은 경로가 shortest path라는 것을 보장해주는 반면에 best-first search는 그렇지 않다는 것이다.

그렇다면 다익스트라가 최선의 방법일까? 그건 아니다.

A*알고리즘은 다익스트라 알고리즘을 보정해준다. 휴리스틱을 통해서.

휴리스틱이란, 쉽게 말해서 적당히 추측해서 괜찮은 방향으로 진행하는 것이다.

위의 두 알고리즘과 비교했을 때, A*알고리즘은 Best-first search가 탐색하는 범위 정도로 비슷하게 탐색을 하면서, 동시에 그 경로가 shortest path임을 보장해준다!! (짱짱맨이네)

A*알고리즘에서는 (현재까지 온 경로에 대한 정보 + 이후 경로를 통해 도착점까지 갈 추측된 정보)를 바탕으로 다음 선택지를 선택한다.

Rubik's cube 문제를 풀기 위해 A*알고리즘을 변형한 알고리즘을 누군가 만들었는데, 현재까지는 그게 제일 효율적인 듯 하다. 어쨌든 이런 저런 알고리즘들을 공부하고, 그 생각방식을 배워가면서 나만의 Rubik's cube 해법을 찾아봐야겠다.

A*알고리즘은 다음의 링크에서 엄청나게 잘~ 설명되어있으니, 이 포스트 내용이 부실하다고 생각되는 분들은 읽어보시길!

Introduction to A*

여담인데, 나는 2004년부터 한 2010년 정도 까지 rubik's cube를 취미생활로 했었다. 그동안 다양한 퍼즐도 많이 사고, 큐브도 많이 사고 그랬는데 나중에 안한다고 주변 지인들에게 다 나눠줬더니... 흠 막상 요즘 다시 하고 싶어지네.. 다시 살까