Somnipathy

얼마전에 생각했던 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를 취미생활로 했었다. 그동안 다양한 퍼즐도 많이 사고, 큐브도 많이 사고 그랬는데 나중에 안한다고 주변 지인들에게 다 나눠줬더니... 흠 막상 요즘 다시 하고 싶어지네.. 다시 살까

오늘 저녁을 먹고 집으로 돌아오는 길에, 갑자기 불현듯이 뭔가가 떠올랐는데 큐브의 해법, 정확히는 큐브를 최소 회전으로 맞추는 해법을 찾아주는 알고리즘을 짜보는 게 어떨까? 하는 생각이 들었다. 일단 요즘 머리를 너무 안쓰면서 사는 것 같기도 하고(...) 요즘 의욕에 넘쳐서 무언갈 막 하고 싶은데, 막상 할 줄 아는 것도 별로 없고, 몇천줄짜리 코딩을 미친듯이 해보고 싶지만 마땅히 코딩할만한 소재도 없고 해서 재미없던 참이어서 갑자기 떠오른 저 생각이 반가웠다.

그래서 스스로 고민해서 해법을 찾아보자! 하고 집에 돌아오는 길에 고민을 해봤는데, 아무리 생각해도 너무 어려워서..ㅋㅋ

큐브가 뭔지는 다음의 링크에서 확인.

위키피디아 링크(큐브)

일단 일반적으로 많이 알려진 해법이 있는지 검색을 해보았다.

딱 눈에 띄던게 바로 God's Algorithm 이었다. 알고리즘이 어떤건진 다음의 링크를 참조하시길.

위키피디아 링크 (God's algorithm)

쨌든, 결론은 이거였다.

큐브의 해법을 찾는건 NP문제이고(...) 내가 고민해봤자 효율적인 알고리즘은 못짬(...)

아무튼 NP문제라면 일반적인 방식말고, 휴리스틱으로 접근해서 문제 해결을 해야할텐데 고민을 좀 해봐야겠다. God's algorithm 이라길래 구체적인 알고리즘이 있는 줄 알았는데, 결국 뒤숭숭하게 그냥 이야기 였음..;

어쨌든 덧붙여서 algorithm 카테고리가 mathematics 카테고리 아래에 있으니 수학적인 이야기도 하자면, 일반적인 n^3 크기의 큐브를 맞추는 데 필요한 최대 회전수는 n^2/log(n) 에 비례한다고 한다. 그리고 3x3x3 큐브에 한정해보면, 3x3x3 큐브의 모든 경우에 대해 20회전 이내의 회전으로 맞출 수 있다는 것이 2010년에 증명되었다고 한다.

세상엔 참 똑똑한 사람들이 많은 듯...