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

== 알고리즘의 종류 ==
아래 서술되는 알고리즘의 대부분이 미로를 [[그래프(이산수학)|그래프]] 자료구조로 표현한다. 교차점(갈림길)을 노드, 각각의 길을 에지로 하는 무방향성 또는 방향 그래프를 사용한다.[* 무방향성 그래프는 양방향의 weight가 같은 방향 그래프와 동치이다.] 이때 에지의 weight값은 대체적으로 미로의 길이. [[내비게이션]]용의 지도 매핑 자료구조의 경우 길이가 아닌 통과하는 시간(해당 도로의 평균 속도로 산출)을 weight로 하기도 한다. weight는 최단 경로를 찾으려고 할 때만 의미가 있으므로 어찌됐든 경로만 찾으면 되는 경우라면 weight는 1로 다 통일해도 상관없다. 그렇지만 0으로 하진 말자. 그랬다간 다익스트라 알고리즘은 출발점에서 도착점으로 가는 '''모든''' 경로를 찾으려고 한다. 최단부터 최장까지. 미로가 3차원 미로여도 2차원 그래프 자료구조로 충분히 표현할 수 있다. 이론상으로는 n차원의 미로 전부를 표현 가능하므로 시간에 따라 길이 변화하는 미로도 같은 자료구조로 표현 가능. 그러나 특정 길에 들어가면 트리거가 작동해서 막혔던 곳이 열린다던지 하는 미로는 n차원 그래프 모델만 가지고는 표현하기 까다롭다. 그러나 어떻게든 표현을 해 낸다면 아래 서술하는 BFS/DFS이하 '''모든''' 알고리즘으로 '''반드시''' 해답이 나온다.

트리거가 존재하는 미로에 대한 힌트라면 모든 트리거의 상태를 combination(순서가 중요한 경우 permutation)으로 생성한 추가 차원을 도입하고 해당 차원으로 이동하는 갈림길을 에지로 추가하는 것인데 이쯤 되면 이건 미로탐색 알고리즘이라기보단 TSP(여행하는 세일즈맨 문제)에 가까워지므로 여기까지만 한다.

메모리가 모자랄 경우 트리거가 작동하지 않은 상태와 트리거를 작동한 상태 두 개의 미로를 각각 생성하고 각각에 대해 현재 위치에서 목적지까지 가는 다익스트라 알고리즘을 푸는 방법을 적용한다. 물론 이 방법이든 저 방법이든 탐색 공간이 줄어들지는 않는다. 단지 쓸데없거나 불가능한 상태 조합까지 메모리에 올리지 않을 뿐이다.

그리고 미로탐색 알고리즘에 들어가는 자료구조는 '''유한'''한 수의 노드와 에지를 가지는 그래프이던지 최장 거리 제약이 걸려 있어야 한다. 둘 중 하나는 무한해도 되지만 만약 둘 다 무한일 경우 알고리즘이 영원히 안 끝날 수 있다. 특히 도달할 수 있는 경로가 없는 경우 모든 알고리즘이 무한히 동작해버린다. 일반적으로 메모리 용량 초과로 인해 에러를 내면서 강제 종료하지만 이건 알고리즘의 종료조건에 해당하지 않는 현실 세계의 제약에 걸린 케이스. 좌/우선법같이 메모리에 여행 경로를 기록하지 않는 알고리즘은 정말로 무한히 돈다.

요약

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

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

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

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