미로탐색 알고리즘_{(r1 문단 편집)}

=== [[A* 알고리즘]] ===
위의 [[다익스트라 알고리즘]]의 개선 버전. 대부분의 [[인공지능]] 길찾기 [[알고리즘]]은 A*를 베이스로 삼아 구현된다. 다익스트라와 다른 점은 갈림길에서 방향을 선택할 때 출구와 가까워지는 방향을 우선 탐색한다. 또는 현재 노드의 다음 노드를 미리 보고 해당 노드에서 목적지까지 경로를 무시한 직선거리를 계산해서 더 짧은 거리를 선택하는 방법도 있다. 갈림길에서 탐색 방향을 고를 때, 다익스트라 알고리즘이 출발지로부터의 실제 거리만을 고려한다면 A*는 도착지까지의 예상 거리도 함께 고려한다는게 커다란 차이점이다.

A*로 최단 경로를 찾고 싶다면 먼저 A*로 근사해를 구한 다음에 같은 문제를 A*에서 구한 근사 최적해를 최장 거리로 제한한 [[다익스트라 알고리즘]]으로 다시 풀면 된다. 이 경우 [[A* 알고리즘]]에서 찾은 근사 최적 경로보다 긴 경로는 다익스트라에서 탐색하지 않고 버릴 수 있으므로 탐색 공간이 많이 절약된다.

도착지까지의 예상 거리를 표현하는 휴리스틱 함수가 admissible하다면 최단 경로가 보장된다.[* 예상 남은 거리가 실제 남은 거리보다 작은 경우 admissible하다고 한다. 이 경우 알고리즘 결과가 다른 모든 경로의 진행 거리 + 남은 예상 거리보다 작으며, 남은 예상 거리는 실제 남은 거리보다 작기 때문에, 결과적으로 다른 모든 경로의 거리보다 작게 된다.] 하지만 그 최단 경로 자체가 최장 경로와 별 차이가 안 나는 [[미로]](애초에 빙빙 돌아가는 미로)에서는 절약되는 탐색 공간이 거의 없어서 이점이 별로 없다는 단점이 있다. 그렇지만 미로 자체가 다수의 사이클을 형성하는 현실의 지도 같은 걸로 최단 경로를 찾고자 한다면 이 방법으로 찾아야 탐색 공간을 크게 절약할 수 있다. 다익스트라는 자기 부모가 아닌 분신이 지나간 길은 안 지나간 것으로 간주하기 때문에 사이클이 많이 만들어지는 지도의 경우 분신들이 너무 많은 수가 만들어져서 문제가 된다.

그리고 목적지가 어딘지 모르는 경우나 목적지까지 남은 거리를 구할 방법이 없는 경우에는 [[A* 알고리즘]]을 쓸 수 없다. 지도나 미로 같은 고정된 공간은 이런 문제가 없지만 동굴을 탐사한다든가(출구가 어딨는지, 있기는 한지조차 모르는 경우) 초차원의 자료구조를 탐색중이라거나(목적지까지 남은 거리 계산 불가)하는 경우가 있을 수 있다.

더 구체적인 예시를 들자면, [[루빅스 큐브]]는 [[다익스트라 알고리즘]]으로 해답을 찾을 수 있는데 큐브의 현재 상태가 목적 상태(모든 색이 맞춰진 상태)에서 얼마나 가까운지를 판단할 수가 없다. 색 12개가 다른 상황(한 회전만에 끝)이 색 2개가 다른 상황(적어도 2회전 이상 필요)보다 가까운 경로인데 이걸 어떻게 판단하겠는가? 그러나 일단 큐브가 '''풀린''' 경로 하나가 주어지면 다른 경로가 이미 구해진 경로보다 더 짧은지는 회전수를 셈으로써 계산할 수 있다.

그리고 거리 대신 여행 시간을 edge 가중치로 사용하면 [[A* 알고리즘]]으로 최단 '거리' 대신 최단 '여행시간'을 구할 수도 있다. 예를 들어 A* 알고리즘으로 [[서울]]에서 [[부산]]까지 가는 경로를 계산하라고 하면, 경로 길이를 edge 가중치로 사용했을 때는 [[고속도로]] 따위는 싹 다 무시하고 산넘고 물건너가는 [[직선]] 경로를 가장 먼저 찾아내겠지만 여행 시간을 edge 가중치로 사용했을 때는 멀리 돌아 가더라도 더 짧은 시간 안에 갈 수 있는 경로를 찾아낼 것이다. ~~[[다익스트라 알고리즘]]이 [[비행기]]와 고속열차를 경유하는 사실상의 최단 경로를 구할 때 A* 알고리즘은 별도의 [[휴리스틱]]이 첨가되지 않는 한 '도보 [[여행]]' 최단 경로를 구한다.~~ 다만 여행 시간을 edge 가중치로 사용하려면 휴리스틱 함수도 그에 알맞게 정의해야 하는데, admissible하게 정의하기가 조금 더 까다롭다.

다익스트라와 A*의 장단점을 잘 저울질해서 일단 출발은 다익스트라로 하되 각각의 여행자는 제한된 수의 분신을 만들면서 A*처럼 탐색해 나가는 알고리즘이 있다. 주요 거점(공항, 철도역 등)에 대한 휴리스틱을 저장해놓고 그 지점을 경유하는 여행자를 A*방식으로 출발시키는 등이다. 거점에서 거점으로 이동하는 경로(서울역 - 부산역)는 다익스트라 알고리즘으로 충분히 빠르게 풀 수 있으므로 거점간 환승 정보만 A*로 계산하는 방법이다. 거점-거점 그래프는 역, 나들목, 인터체인지, 공항 등으로 제한되기 때문에 갈림길이나 교차로마다 노드가 생성되는 도보여행(또는 자동차여행) 그래프보다 훨씬 작다.

요약

문서 편집을 저장하면 당신은 기여한 내용을 CC BY-NC-SA 2.0 KR 또는 기타 라이선스 (문서에 명시된 경우) 로 배포하고 기여한 문서에 대한 하이퍼링크나 URL을 이용하여 저작자 표시를 하는 것으로 충분하다는 데 동의하는 것입니다. 이 동의는 철회할 수 없습니다.

비로그인 상태로 편집합니다. 로그인하지 않은 상태로 문서 편집을 저장하면, 편집 역사에 본인이 사용하는 IP(216.73.216.107) 주소 전체가 영구히 기록됩니다.

미로탐색 알고리즘(r1 문단 편집)

미로탐색 알고리즘_{(r1 문단 편집)}