미로탐색 알고리즘
1. 개요
대학생 로봇&프로그래밍 경진대회에 많이 주어지는 과제다.
말 그대로 로봇과 그 로봇에 탑재할 인공지능 프로그래밍을 만드는 것. 인공지능 프로그래밍의 목적은 미로를 최단시간안에, 최단거리로 돌파하는 거다. 이때 사용되는 로봇은 마이크로 마우스라 부르는 경우가 대부분이다. 요즘은 마이크로 마우스를 쓰지 않고 단순히 알고리즘 자체만을 요구하는 경우도 많다.
단순한 듯 하지만 백지 상태에서 짜려고 하면 꽤 어렵다는 것을 알 수 있다. 하지만 워낙 경진대회에서 많이 울궈먹은 과제라 구글링을 조금만 해도 관련 정보들이 우수수 쏟아져 나온다. 미로를 모르는 상태에서 1차 주행을 하는 법, 그 정보를 저장하는 법, 알고리즘에 따라 길을 찾아 나가는 방법 등등이 다 올라와 있다.
컴퓨터학과 학생이라면 아마 졸업하기 전에 과제로 한 두 번은 나올 법한 주제다. 속 편하게 우선법이나 좌선법을 이용해서 효율 극악의 알고리즘을 짜와도 대부분 통과시켜 주지만 요즘 몇몇 교수님들은 '''우선법, 좌선법 제외'''라는 초 강수를 둘 때도 있으니 조심.
2. 알고리즘의 종류
아래 서술되는 알고리즘의 대부분이 미로를 그래프 자료구조로 표현한다. 교차점(갈림길)을 노드, 각각의 길을 에지로 하는 무방향성 또는 방향 그래프를 사용한다.[1] 이때 에지의 weight값은 대체적으로 미로의 길이. 내비게이션용의 지도 매핑 자료구조의 경우 길이가 아닌 통과하는 시간(해당 도로의 평균 속도로 산출)을 weight로 하기도 한다. weight는 최단 경로을 찾으려고 할 때만 의미가 있으므로 어찌됐든 경로만 찾으면 되는 경우라면 weight는 1로 다 통일해도 상관없다. 그렇지만 0으로 하진 말자. 그랬다간 다익스트라 알고리즘은 출발점에서 도착점으로 가는 '''모든''' 경로를 찾으려고 한다. 최단부터 최장까지. 미로가 3차원 미로여도 2차원 그래프 자료구조로 충분히 표현할 수 있다. 이론상으로는 n차원의 미로 전부를 표현 가능하므로 시간에 따라 길이 변화하는 미로도 같은 자료구조로 표현 가능. 그러나 특정 길에 들어가면 트리거가 작동해서 막혔던 곳이 열린다던지 하는 미로는 n차원 그래프 모델만 가지고는 표현하기 까다롭다. 그러나 어떻게든 표현을 해 낸다면 아래 서술하는 BFS/DFS이하 '''모든''' 알고리즘으로 '''반드시''' 해답이 나온다.
트리거가 존재하는 미로에 대한 힌트라면 모든 트리거의 상태를 combination(순서가 중요한 경우 permutation)으로 생성한 추가 차원을 도입하고 해당 차원으로 이동하는 갈림길을 에지로 추가하는 것인데 이쯤 되면 이건 미로탐색 알고리즘이라기보단 TSP(여행하는 세일즈맨 문제)에 가까워지므로 여기까지만 한다.
메모리가 모자랄 경우 트리거가 작동하지 않은 상태와 트리거를 작동한 상태 두 개의 미로를 각각 생성하고 각각에 대해 현재 위치에서 목적지까지 가는 다익스트라 알고리즘을 푸는 방법을 적용한다. 물론 이 방법이든 저 방법이든 탐색 공간이 줄어들지는 않는다. 단지 쓸데없거나 불가능한 상태 조합까지 메모리에 올리지 않을 뿐이다.
그리고 미로탐색 알고리즘에 들어가는 자료구조는 '''유한'''한 수의 노드와 에지를 가지는 그래프이던지 최장 거리 제약이 걸려 있어야 한다. 둘 중 하나는 무한해도 되지만 만약 둘 다 무한일 경우 알고리즘이 영원히 안 끝날 수 있다. 특히 도달할 수 있는 경로가 없는 경우 모든 알고리즘이 무한히 동작해버린다. 일반적으로 메모리 용량 초과로 인해 에러를 내면서 강제 종료하지만 이건 알고리즘의 종료조건에 해당하지 않는 현실 세계의 제약에 걸린 케이스. 좌/우선법같이 메모리에 여행 경로를 기록하지 않는 알고리즘은 정말로 무한히 돈다.
2.1. 좌선법/우선법
우선법 항목 참고. 단순히 왼쪽이나 오른쪽 벽을 계속 짚고 가는 알고리즘이다. 자신이 이미 지나간 길을 체크하지 않기 때문에 메모리 소비는 적지만 사이클이 생기는 미로는 통과가 불가능할 수 있다는 단점이 있다. 그리고 이렇게 찾은 경로가 최단 경로가 아닐 가능성이 높다.
2.2. DFS/BFS
깊이 우선 탐색(Depth-first search), 너비 우선 탐색(Breadth-first search) 의 약어이다. 일반적으로 깊이 우선 탐색보다 너비 우선 탐색쪽이 확률적으로 더 짧은 경로를 찾는다. 모든 경로의 weight가 같은 경우에는 BFS탐색이 항상 최단 경로를 찾는다.
좌선법/우선법 알고리즘하고 연관은 없는 알고리즘이지만 좌/우선법 알고리즘이 작동하는 건 DFS와 닮았다. 차이점이라면 DFS/BFS는 자신이 이미 방문한 길을 기억하고 있어서 같은 길을 반복해서 돌지 않는다는 것. 그래서 맵이 무한하거나 길이 없는 경우가 아니라면 반드시 해답을 찾아낸다.
2.3. 다익스트라 알고리즘
주어진 시작 지점에서 출구를 향하는 '''최단 경로'''를 찾아내는 알고리즘. 위의 BFS알고리즘의 발전형이다. 사실 이 알고리즘은 특정 지점에서 특정 지점까지 가는 최단 경로 모두를 알아낼 수 있다. 하지만 단점은 최단 경로인 게 확인될 때까지 가능한 모든 경로를 테스트하기 때문에 아무래도 아래의 A* 알고리즘에 비해 성능이 몹시, 많이 떨어진다. 그래서 실시간 길찾기 알고리즘으로 다익스트라 알고리즘은 적절하지 않다.
다익스트라 알고리즘은 분신술 알고리즘이다. 초기값은 최단 경로 '''없음''', 최단 경로의 길이 '''무한대'''로 시작한다. 갈림길이 나타나면 미로를 탐색하는 탐색자(traveler)가 갈림길의 갯수만큼 분신을 만들어 각각의 길을 따라간다. 그리고 자신과 자신의 원본(부모 객체)이 지나간 길을 지워나간다. 그러다가 더 이상 갈 데가 없는 분신은 스스로 소멸한다. 만약 분신들 중 하나가 출구를 찾아냈다면 해당 분신과 그의 모든 원본들이 여행한 경로를 해답(최단 경로)에 기록하고 그 길이를 최단 경로로 설정한다. 그리고 모든 분신들에게 최단 길이를 '''방송'''하고 스스로는 소멸한다. 최단 길이보다 먼 길을 돌고 있는 분신들은 이 때 모두 소멸한다. 나중에라도 스스로의 여행 거리가 방송된 최단 거리를 넘어가면 스스로 소멸한다. 남아 있는 분신들 중 더 짧은 경로로 해답을 찾은 분신이 있다면 그 경로로 해답을 갱신하고 최단 길이를 또 방송한다. 그리고 다음 time step으로 이동. 이 과정을 모든 분신들이 없어질 때까지 반복. 모든 분신이 소멸하면 기록돼있는 최단 경로를 해답으로 제출한다. 만약 해답이 없다면 그 미로는 출구로 통하는 길이 없는 것이다.
기술적인 이유로 무한대 값을 설정할 수 없다면 충분히 큰 값을 설정해야 한다. 충분히 큰 값이 아닐 경우 해답이 존재하는 미로인데도 경로가 없다고 해답을 낸다. 초보가 저지르기 쉬운 실수로 초기값의 최단 길이를 0이나 -1로 넣는 게 있다. 이렇게 하면 다익스트라 알고리즘이 시작하자마자 끝나면서 '경로 없음'이라는 결과를 뱉기 때문에 엄한 델 디버깅하게 될 위험이 있다.[2]
다익스트라 알고리즘의 천적은 바로 완전 개방형 맵. 커다란(무한한) 빈 박스에 출발점과 도착점만 찍혀 있고 장애물이 전혀 없는 미로의 경우다. 이런 미로는 첫 최단 경로(직선 경로)를 찾아낼 때까지 출발점에서 그 거리에 비례하는 원형 탐색 공간을 소비한다. 최악의 경우는 도착점 주위에 벽이 둘러쳐져 있고(도달 불가능) 공간이 무한대인 맵이다. 이 경우 다익스트라 알고리즘은 무한히 분신을 생성하다가 메모리 초과로 뻗는다.
다익스트라로 최단 경로가 아닌 어쨌거나 출구로 갈 수 있는 길 아무거나 하나만 찾고 싶다면 분신 중 하나가 출구에 도착한 순간 해답을 내고 종료하면 된다. 근데 이럴거면 아래쪽의 A*알고리즘이 더 효율적이므로 그걸 쓰는 걸 추천.
만약 모든 에지의 weight값이 같다면 맨 처음 해답을 낸 분신이 최단 경로가 된다.[3] 또한 좀 꼼수를 써서 분신들로부터 목적지까지 대각선으로 질러가는 남은 거리(장애물을 무시한 직선 거리)를 계산했을 때 현재 계산된 최단 길이를 초과할 경우 소멸하게 만들 수도 있다.[4] 이렇게 하면 2차원 지도 상에서 탐색 공간의 반지름이 절반으로 줄어든다. 단 이 방법은 weight값에 음수값이 없다는 조건을 만족해야 한다.
부수적인 장점으로 다익스트라 알고리즘은 쉽게 병렬화가 가능하다. GPU같이 코어가 수백 수천개가 집적돼있는 기기에서 다익스트라 알고리즘은 최대의 성능을 발휘한다. 분신 하나당 쓰레드 하나를 생성하는 방식으로 코딩하면 된다. 밑의 A* 알고리즘은 DFS기반이라 어디서 어떻게 쓰레드를 나눌지가 명확하지 않다.
2.4. A* 알고리즘
위의 다익스트라 알고리즘의 개선 버전. 대부분의 인공지능 길찾기 알고리즘은 A*로 구현된다. 다익스트라와 다른 점은 갈림길에서 방향을 선택할 때 출구와 가까워지는 방향을 우선 탐색한다. 또는 현재 노드의 다음 노드를 미리 보고 해당 노드에서 목적지까지 경로를 무시한 직선거리를 계산해서 더 짧은 거리를 선택하는 방법도 있다. 갈림길에서 탐색 방향을 고를 때, 다익스트라 알고리즘이 출발지로부터의 실제 거리만을 고려한다면 A*는 도착지까지의 예상 거리도 함께 고려한다는게 커다란 차이점이다.
맞는 이야기 같은데 왜 실선이 그어져 있는지 잘 모르겠다..?
도착지까지의 예상 거리를 표현하는 휴리스틱 함수가 admissible하다면 최단 경로가 보장된다.[5] 하지만 그 최단 경로 자체가 최장 경로와 별 차이가 안 나는 미로(애초에 빙빙 돌아가는 미로)에서는 절약되는 탐색 공간이 거의 없어서 이점이 별로 없다는 단점이 있다. 그렇지만 미로 자체가 다수의 사이클을 형성하는 현실의 지도 같은 걸로 최단 경로를 찾고자 한다면 이 방법으로 찾아야 탐색 공간을 크게 절약할 수 있다. 다익스트라는 자기 부모가 아닌 분신이 지나간 길은 안 지나간 것으로 간주하기 때문에 사이클이 많이 만들어지는 지도의 경우 분신들이 너무 많은 수가 만들어져서 문제가 된다.
그리고 목적지가 어딘지 모르는 경우나 목적지까지 남은 거리를 구할 방법이 없는 경우에는 A* 알고리즘을 쓸 수 없다. 지도나 미로 같은 고정된 공간은 이런 문제가 없지만 동굴을 탐사한다든가(출구가 어딨는지, 있기는 한지조차 모르는 경우) 초차원의 자료구조를 탐색중이라거나(목적지까지 남은 거리 계산 불가)하는 경우가 있을 수 있다.
그리고 거리 대신 여행 시간을 edge 가중치로 사용하면 A* 알고리즘으로 최단 '거리' 대신 최단 '여행시간'을 구할 수도 있다. 예를 들어 A* 알고리즘으로 서울에서 부산까지 가는 경로를 계산하라고 하면, 경로 길이를 edge 가중치로 사용했을 때는 고속도로 따위는 싹 다 무시하고 산넘고 물건너가는 직선 경로를 가장 먼저 찾아내겠지만 여행 시간을 edge 가중치로 사용했을 때는 멀리 돌아 가더라도 더 짧은 시간 안에 갈 수 있는 경로를 찾아낼 것이다. 다만 여행 시간을 edge 가중치로 사용하려면 휴리스틱 함수도 그에 알맞게 정의해야 하는데, admissible하게 정의하기가 조금 더 까다롭다.
다익스트라와 A*의 장단점을 잘 저울질해서 일단 출발은 다익스트라로 하되 각각의 여행자는 제한된 수의 분신을 만들면서 A*처럼 탐색해 나가는 알고리즘이 있다. 주요 거점(공항, 철도역 등)에 대한 휴리스틱을 저장해놓고 그 지점을 경유하는 여행자를 A*방식으로 출발시키는 등이다. 거점에서 거점으로 이동하는 경로(서울역 - 부산역)는 다익스트라 알고리즘으로 충분히 빠르게 풀 수 있으므로 거점간 환승 정보만 A*로 계산하는 방법이다. 거점-거점 그래프는 역, 나들목, 인터체인지, 공항 등으로 제한되기 때문에 갈림길이나 교차로마다 노드가 생성되는 도보여행(또는 자동차여행) 그래프보다 훨씬 작다.
3. 미로 '제작' 알고리즘
미로와 관련된 컴퓨터 과학의 문제로는 미로제작 문제가 있다. 미로를 탐색하는 것과 마찬가지로 미로를 제작하는 데에도 여러 알고리즘을 사용할 수 있는데, 기본적인 백트래킹(재귀)을 활용한 방식, 크러스컬 알고리즘이나 Prim같은 최소신장트리(Minimum Spanning Tree)를 만드는 알고리즘, 재귀 분할 알고리즘 등 다양한 방법을 시도할 수 있다. 여기에 다양한 알고리즘들이 소개되어 있다.
4. 미로 '개척' 알고리즘
미로 '''탐색''' 알고리즘은 스스로 미로를 변형 시키면서 길을 찾아가는 건 고려하지 않는다. 뭐 마이크로 마우스에다 오버스펙의 모터를 끼우고 닥돌시키면 미로 벽을 부숴버리면서 통로 개척이 가능하지만 일단 그건 반칙이다. 마이크로 '''마우스'''라고 벽을 쏠아서 구멍을 낸다든지 하면 안 된다.
물론 미로개척 알고리즘이 있긴 하다. 원래는 도달이 불가능한 특정한 두 지점을 최소 비용으로 잇거나, 최소한의 추가 경로로 최단 거리를 최대한 단축시키는 답을 찾는 알고리즘이 미로개척 알고리즘에 속한다. 당연히 미로탐색 알고리즘과는 전혀 다르다.
[1] 무방향성 그래프는 양방향의 weight가 같은 방향 그래프와 동치이다.[2] C 언어에서 unsigned int 자료형에 -1값을 대입하면 오버플로를 일으키면서 해당 자료형의 최대값이 자동 대입된다. 하지만 이건 트릭이고 컴파일러 경고를 받으므로 권장되지 않는다.[3] 당연하다. 에지의 weight가 모두 같다면 에지를 통과한 수가 가장 적은 탐색자가 가장 짧은 거리를 여행한다. 다익스트라 알고리즘의 타임 스텝은 모든 탐색자가 에지 하나를 통과하는 것이 기준이다.[4] 거리를 정수로 재는 경우 맨하탄법(X,Y각 축에 사영한 직선 거리를 더하는 방법)으로 재면 정수 거리를 잴 수 있다. 단 각도가 45도에 가까워질수록 오차가 커진다. 그러나 길 자체가 직교밖에 안 하는 미로는 맨하탄법으로도 정확한 거리를 잴 수 있다.[5] 예상 남은 거리가 실제 남은 거리보다 작은 경우 admissible하다고 한다. 이 경우 알고리즘 결과가 다른 모든 경로의 진행 거리 + 남은 예상 거리보다 작으며, 남은 예상 거리는 실제 남은 거리보다 작기 때문에, 결과적으로 다른 모든 경로의 거리보다 작게 된다.