미로 해결 알고리즘

Maze-solving algorithm
나무 미로의 로봇

미로 해결 알고리즘은 미로를 푸는 자동화된 방법이다. 무작위 마우스, 벽 팔로워, 프러약스, 트레모의 알고리즘은 미로에 대한 사전 지식이 없는 여행자가 미로 안에서 사용하도록 설계되어 있는 반면, 데드엔드 필링과 최단 경로 알고리즘은 한 번에 미로 전체를 볼 수 있는 사람이나 컴퓨터 프로그램에 의해 사용되도록 설계되어 있다.

루프가 없는 미로는 "단순히 연결된" 미로, 또는 "완벽한" 미로라고 알려져 있으며, 그래프 이론에서 나무와 같다. 미로 해결 알고리즘은 그래프 이론과 밀접한 관련이 있다. 직감적으로 미로의 길을 적당한 방법으로 당겨서 쭉 뻗으면 그 결과가 나무와 비슷하게 만들어질 수 있었다.[1]

랜덤 마우스 알고리즘

이것은 매우 비지각적인 로봇이나 아마도 마우스에 의해 구현될 수 있는 사소한 방법이다. 단순히 교차점에 도달할 때까지 현재의 항로를 따라 진행하고, 그 다음에 따를 방향에 대해 무작위로 결정하는 것이다. 그러한 방법은 결국 항상 적절한 해결책을 찾을 수 있지만, 이 알고리즘은 매우 느릴 수 있다.

벽 팔로워

오른쪽 규칙을 사용한 통과

미로를 가로지르는 데 가장 잘 알려진 규칙은 벽 팔로워로, 왼쪽 또는 오른쪽 규칙으로도 알려져 있다. 만약 미로가 단순히 연결되어 있다면, 즉, 미로의 모든 벽이 미로의 외측 경계로 연결되어 있다면, 한 손을 미로의 한쪽 벽과 접촉함으로써 해결사는 길을 잃지 않도록 보장되고, 해결사가 있다면 다른 출구에 도달할 것이다. 그렇지 않으면 알고리즘은 모든 복도를 가로지른 입구로 되돌아갈 것이다. 적어도 한 번은 벽의 연결된 부분 옆에. 알고리즘은 깊이 우선 순서에 따라 트리를 가로지르는 것이다.

왜 벽이 작품을 추종하는지에 대한 또 다른 관점은 위상학적이다. 만약 벽이 연결되어 있다면, 그것들은 고리 또는 원으로 변형될 수 있다.[2] 그리고 나서 벽 뒤를 따라가는 것은 처음부터 끝까지 원을 그리며 걷는 것으로 줄어든다. 이 아이디어를 더 발전시키기 위해, 미로 벽의 연결된 요소들을 함께 그룹화함으로써, 둘 이상의 해결책이 있더라도 이들 사이의 경계가 정확히 해결책이라는 것을 주목하라(오른쪽 그림 참조).

미로가 단순하게 연결되지 않은 경우(즉, 시작 또는 끝점이 통로 루프로 둘러싸인 구조물의 중심에 있거나, 경로가 서로 교차하고 아래에 있으며 해결 경로의 그러한 부분이 통로 루프로 둘러싸인 경우), 이 방법은 목표에 도달하지 못할 것이다.

또 다른 우려는 미로 입구에서 벽을 따라가기 시작할 수 있도록 주의해야 한다는 것이다. 미로가 단순히 연결되지 않고 미로 내부의 임의적인 지점에서 벽을 따라가기 시작한다면, 스스로 돌아 다니고 출입구가 없는 별도의 벽을 따라 갇힌 자신을 발견할 수 있을 것이다. 만약 벽 팔로잉이 늦게 시작되는 경우라면 벽 팔로잉이 시작된 위치를 표시하려고 시도한다. 벽 팔로잉은 언제나 당신이 시작했던 곳으로 당신을 이끌기 때문에, 만약 당신이 두 번째로 당신의 시작점을 마주하게 된다면, 당신은 미로가 단순히 연결되지 않았다고 결론 내릴 수 있고, 당신은 아직 따라오지 않은 대안적인 벽으로 전환해야 한다. 다른 방법론은 아래의 서약 알고리즘을 참조하십시오.

벽 팔로잉은 2D 평면에 결정론적인 방법으로 고차원 통로를 투영할 수 있는 경우 3D 또는 고차원 미로에서 수행할 수 있다. 예를 들어 3D 미로에서 "상향" 통로가 북서쪽을 향하고 "하향" 통로가 남동쪽을 향한다고 가정할 수 있다면, 다음과 같은 규칙을 적용할 수 있다. 단, 2D와 달리 현재 방향을 알아야 왼쪽과 오른쪽 중 어느 방향이 첫 번째인지 판단할 수 있다.

서약 알고리즘

좌측: 좌측 방향 해결기 끼임
오른쪽 : 서약 알고리즘 솔루션

미로의 입구와 출구가 미로의 외벽에 있는 한(외벽이 외부 경계와 연결되지 않은 곳/경계가 닫히지 않는 곳) 미로는 벽 팔로워 방식으로 해결할 수 있다. 하지만, 해결사가 미로 안에서 시작된다면, 그것은 출구에서 분리되는 구역에 있을 수 있고, 벽 팔로워들은 계속해서 그들의 링을 돌 것이다. Permise 알고리즘(Exeter의 John Permise의 이름을 따서 명명)은 이 문제를 해결할 수 있다.[3][4]

장애물을 우회하도록 설계된 Permise 알고리즘은 임의로 선택한 방향이 필요하며, 이는 우선이 될 것이다. 장애물을 만났을 때, 회전 각도가 계수되는 동안 한 손(오른손이라고 말함)은 장애물을 따라 유지된다(시계 방향은 양, 시계 반대 방향은 음). 해결사가 다시 원래의 우선 방향을 향하게 되고, 턴의 각도 합이 0일 때, 해결사는 장애물을 떠나 원래의 방향으로 계속 움직인다.

손은 "회전 합"과 "현재 방향"이 모두 0일 때만 벽에서 제거된다. 이를 통해 알고리즘은 대문자 "G" 모양의 트랩을 피할 수 있다. 알고리즘이 첫 번째 벽에서 좌회전한다고 가정하면 벽 옆에서 360도 회전한다. '현재 제목'만을 추적하는 알고리즘은 가장 오른쪽 하단 벽 헤딩을 왼쪽으로 벗어나 다시 왼쪽의 곡선 구간으로 달려나가면서 무한 루프(infinite loop)로 이어진다. Permise 알고리즘은 그 지점에서 "회전 합"이 0이 아니기 때문에 가장 오른쪽 벽을 떠나지 않는다(주 360도는 0도와 같지 않다). 그것은 벽을 따라 쭉 따라다니며, 마침내 바깥과 글자 모양 바로 밑을 향하게 한다.

이 알고리즘은 나침반을 가진 사람이 용해자의 초기 위치에 관계없이 내부의 어느 지점에서든 유한한 2차원 미로의 외부 출구로 자신의 길을 찾을 수 있도록 한다. 그러나 이 알고리즘은 역행하는 것, 즉 미로 바깥쪽의 입구에서 그 안에 있는 어떤 최종 목표까지 길을 찾는 것에는 효과가 없을 것이다.

트레모 알고리즘

트레모 알고리즘 큰 녹색 점은 현재의 위치를 나타내고, 작은 파란색 점은 경로에 단일 자국을 나타내며, 빨간 십자가는 이중 자국을 나타낸다. 일단 출구가 발견되면, 그 경로는 단독 표기된 경로를 통해 추적된다.

샤를 피에르 트레모에 의해 발명된 트레모 알고리즘은 길을 표시하기 위해 바닥에 선을 그어야 하는 미로에서 빠져나오는 길을 찾는 효율적인 방법이며, 구절이 잘 정의된 모든 미로에서 효과가 보장되지만,[6] 최단 경로를 찾는 것은 보장되지 않는다.[5]

분기점에서 나오는 경로는 방문하지 않거나, 한 번 표시되거나, 두 번 표시된다. 알고리즘은 다음 규칙에 따라 작동한다.

  • 각 경로를 따라갈 때 한 번 표시하십시오. 그 자국은 길의 양끝에서 볼 수 있어야 한다. 따라서 컴퓨터 알고리즘의 일부로 저장하기보다는 물리적 표시로 만들어지는 경우 경로의 양 끝에 동일한 표시가 만들어져야 한다.
  • 두 개의 표시가 있는 경로는 절대 들어가지 마십시오.
  • 표시가 없는 분기점(입력한 경로에 있는 경로를 제외하고)에 도착하면 임의의 표시되지 않은 경로를 선택하고 따라 이동한 후 표시하십시오.
  • 그렇지 않은 경우:
    • 만약 당신이 들어온 길에 표시가 하나만 있다면, 돌아서서 다시 표시하면서 그 길을 따라 돌아가라. 특히 이 경우는 막다른 골목에 다다를 때마다 일어나야 한다.
    • 그렇지 않을 경우 남은 경로 중 가장 적은 표시(가능한 경우 0, 그렇지 않으면 1)를 임의로 선택하고 그 경로를 따라 표시한다.

"돌아서 돌아오다"는 규칙은 루프가 있는 미로들을 효과적으로 연결시켜준다; 우리는 루프를 닫을 길을 찾을 때마다 막다른 골목으로 간주하고 돌아온다. 이 규칙이 없다면, 만약 우리가 뒤로 돌아가지 않고 임의로 다른 길을 따라간다면, 아직 밝혀지지 않은 미로의 일부에 대한 접근을 차단할 수 있다.

마침내 해결책에 도달했을 때, 정확히 한 번 표시된 경로는 출발점으로 돌아가는 길을 나타낼 것이다. 출구가 없을 경우 이 방법은 모든 경로가 두 번 표시된 시작 부분으로 다시 이동한다. 이 경우 각 경로는 정확히 두 번, 각 방향으로 한 번 걸어 내려간다. 그 결과 걷는 것을 양방향 이중추적이라고 한다.[7]

본질적으로 19세기에 발견된 이 알고리즘은 약 100년 후 깊이 우선 검색으로 사용되어 왔다.[8][9]

데드 엔드 필링

데드엔드 필링은 모든 데드엔드를 채우는 미로를 해결하기 위한 알고리즘으로 정확한 방법만 채우지 않는다. 종이로 된 미로나 컴퓨터 프로그램으로 미로를 푸는 데 쓰일 수 있지만, 이 방법은 미로 전체를 한 번에 보기 때문에 미지의 미로 안에 있는 사람에게는 유용하지 않다. 방법은 1) 미로에서 모든 막다른 곳을 찾아낸 다음 2) 각 막다른 곳에서 첫 번째 분기점이 충족될 때까지 경로를 "충전"하는 것이다. 일부 구절은 다른 막다른 구절을 먼저 제거하기 전에는 막다른 구절의 일부가 되지 않는다는 점에 유의하십시오. 여기서 막다른 골목에 가득 채우는 영상을 볼 수 있다: [1][2].

공정의 각 단계가 미로의 토폴로지를 보존하기 때문에 데드엔드 충전은 결승선에서 출발을 실수로 "차단"할 수 없다. 게다가, 최종 결과는 어떤 막다른 골목도 포함할 수 없기 때문에 이 과정은 "너무 빨리" 멈추지 않을 것이다. 따라서 완벽한 미로(루프가 없는 마제)에서 데드엔드 충전이 이루어진다면 해결책만 남게 될 것이다. 부분적으로 땋은 미로(일부 루프가 있는 미로)에서 행해진다면, 가능한 모든 해결책은 그 이상 아무것도 남지 않을 것이다. [3]

재귀 알고리즘

만약 미로의 전지적 시야가 주어진다면, 간단한 재귀 알고리즘은 어떻게 끝까지 가는지를 알려줄 수 있다. 알고리즘에는 시작 X와 Y 값이 주어질 것이다. X와 Y 값이 벽에 없는 경우, 메소드는 이미 이전에 X와 Y 값을 사용하지 않았는지 확인하면서 인접한 모든 X와 Y 값과 함께 자신을 호출할 것이다. X와 Y 값이 최종 위치의 값일 경우, 방법의 모든 이전 인스턴스를 올바른 경로로 저장한다.

이것은 사실상 격자점 단위로 표현된 깊이 우선 검색이다. 전지적 시야는 암기에 의한 루프 입력을 방지한다. 다음은 Java의 샘플 코드: 

부울[][] 미로 = 새로운 부울[너비][높이]; // 미로 부울[][] 와셔 = 새로운 부울[너비][높이]; 부울[][] 올바른 경로 = 새로운 부울[너비][높이]; // 미로의 해결책 인트로 스타트엑스, 스타트Y; // 미로의 X 및 Y 값 시작 인트로 endX, 끝Y;     // 미로의 X 및 Y 값 끝내기  공중의 공허하게 하다 마제를 풀다() {     미로 = 메이즈 생성(); // 메이즈 만들기(거짓 = 경로, 참 = 벽)     을 위해 (인트로 배를 젓다 = 0; 배를 젓다 < 미로.길이; 배를 젓다++)           // 부울 배열을 기본값으로 설정         을 위해 (인트로 망토를 입히다 = 0; 망토를 입히다 < 미로[배를 젓다].길이; 망토를 입히다++){             와셔[배를 젓다][망토를 입히다] = 거짓의;             올바른 경로[배를 젓다][망토를 입히다] = 거짓의;         }     부울 b = 재귀솔브(스타트엑스, 스타트Y);     // 부울 배열(정확한 경로)을 남기시겠습니까?      // 참 값으로 표시된 경로.     // b가 거짓이면 미로에 대한 해결책이 없다. } 공중의 부울 재귀솔브(인트로 x, 인트로 y) {     만일 (x == endX && y == 끝Y) 돌아오다 진실의; // 끝에 도달한 경우     만일 (미로[x][y]    와셔[x][y]) 돌아오다 거짓의;     // 벽에 있거나 이미 여기에 있는 경우     와셔[x][y] = 진실의;     만일 (x != 0) // 왼쪽 가장자리가 아닌 경우 확인         만일 (재귀솔브(x-1, y)) { // 방법 1을 왼쪽으로 불러오기             올바른 경로[x][y] = 진실의; // 해당 경로 값을 true로 설정;             돌아오다 진실의;         }     만일 (x != 너비 - 1) // 오른쪽 가장자리에 있지 않은지 확인         만일 (재귀솔브(x+1, y)) { // 방법 1을 오른쪽으로 불러오기             올바른 경로[x][y] = 진실의;             돌아오다 진실의;         }     만일 (y != 0)  // 상단 모서리가 아닌 경우 확인         만일 (재귀솔브(x, y-1)) { // 메서드 원 업(Method up             올바른 경로[x][y] = 진실의;             돌아오다 진실의;         }     만일 (y != 높이 - 1) // 아래쪽 가장자리가 아닌 경우 확인         만일 (재귀솔브(x, y+1)) { // 방법 1을 아래로 불러오기             올바른 경로[x][y] = 진실의;             돌아오다 진실의;         }     돌아오다 거짓의; }

메이즈라우팅 알고리즘

미로-라우팅 알고리즘은 미로의 어떤 두 위치 사이의 길을 찾기 위한 낮은 오버헤드 방법이다. 이 알고리즘은 처음에 CMP(칩 멀티프로세서) 영역에 대해 제안되며 어떤 그리드 기반 미로에서도 작동하도록 보장된다. 이 알고리즘은 그리드의 두 위치(메이즈) 사이의 경로를 찾는 것 외에도 소스와 대상 사이에 경로가 없을 때를 감지할 수 있다. 또한 알고리즘은 미로 크기에 상관없이 고정된 기억 복잡성을 가진 미로에 대한 사전 지식이 없는 내부 여행자가 사용하도록 되어 있다. 경로를 찾고 도달할 수 없는 위치를 탐지하기 위해 총 4개의 변수가 필요하다. 그럼에도 불구하고 알고리즘은 최단 경로를 찾는 것이 아니다.

미로-라우팅 알고리즘은 맨해튼 거리(MD) 개념을 사용하며 MD가 한 위치에서 주변 4개 위치로 이동할 때 정확히 1씩 증가/감소하는 그리드의 속성에 의존한다. 여기에 도달할 수 없는 위치를 감지할 수 없는 유사 부호가 있다. 

포인트 src, dst;// 소스 및 대상 좌표 // cur는 또한 현재 위치의 좌표를 나타낸다. 인트로 MD_best = MD(src, dst);// 지금까지 우리가 했던 것 중 가장 가까운 MD를 저장한다. // MD를 더 작게 만드는 것은 생산적인 경로 입니다. 하는 동안에 (꾸러미 != dst) {     만일 (저기에 존재한다 a 생산적인 경로) {         가져가다 그 생산적인 경로;     } 다른 {         MD_best = MD(꾸러미, dst);         이매진 a , 줄 사이에 꾸러미 그리고 dst;         가져가다 그 맨 처음의 경로 에 그 남겨진/맞다 의 그 , 줄; // 왼쪽/오른쪽 선택은 다음 손 규칙에 영향을 미친다.         하는 동안에 (MD(꾸러미, dst) != MD_best    저기에 한다 아닌 존재하다 a 생산적인 경로) {             따르다 그 맞다-손짓하다/남겨진-손짓하다 통치를 하다; // 선택한 선의 반대쪽     } }

최단 경로 알고리즘

해결책이 많고 막다른 길이 없는 미로, 가장 짧은 길을 찾는 것이 유용할 수 있다.

미로가 여러 개의 해결책을 가지고 있을 때, 해결사는 처음부터 끝까지 가장 짧은 경로를 찾기를 원할 수 있다. 최단 경로를 찾기 위한 알고리즘은 여러 가지가 있는데, 대부분은 그래프 이론에서 나온 것이다. 그러한 알고리즘 중 하나는 폭 우선 검색을 구현하여 최단 경로를 찾는 반면, 다른 알고리즘인 A* 알고리즘은 휴리스틱 기법을 사용한다. 너비 우선 검색 알고리즘은 큐를 사용하여 시작부터 결승에 도달할 때까지 점점 더 거리 순서로 셀을 방문한다. 방문한 각 셀은 출발지로부터의 거리 또는 출발지 가까이에 있는 인접 셀이 대기열에 추가되도록 했는지 추적할 필요가 있다. 결승 위치가 발견되면 셀의 경로를 가장 짧은 경로인 시작점까지 거꾸로 따라가십시오. 가장 간단한 형태의 폭 우선 검색은 가중 그래프에서 최단 경로를 찾는 것과 같은 한계가 있다.

참고 항목

참조

  1. ^ 유튜브의 미로에서 나무로
  2. ^ 유튜브에서 변신한 미로
  3. ^ Abelson; diSessa (1980), Turtle Geometry: the computer as a medium for exploring mathematics, ISBN 9780262510370
  4. ^ 시모어 파퍼트, "교육 향상을 위한 기술의 이용", MIT 인공지능 메모 298호, 1973년 6월
  5. ^ 2010년 12월 2일, 공개 컨퍼런스 – Academy de Macon (Burgundy – 프랑스)에서 Jean Pelletier-Tibert 교수에 의해 – (Abstract가 Logeno 학술지에 2011년 3월 – ISSN0980-6032)
    샤를 트레모 (1859년 ~ 1882년) 파리의 에콜 폴리테크니크 (X:1876) 프랑스 전신 기사
  6. ^ 에두아르 루카스: 1882년 제1권, 레크레이션스 제1권 1882년.
  7. ^ Even, Shimon (2011), Graph Algorithms (2nd ed.), Cambridge University Press, pp. 46–48, ISBN 978-0-521-73653-4.
  8. ^ Sedgewick, Robert (2002), Algorithms in C++: Graph Algorithms (3rd ed.), Pearson Education, ISBN 978-0-201-36118-6.
  9. ^ Fattah, Mohammad; et, al. (2015-09-28). "A Low-Overhead, Fully-Distributed, Guaranteed-Delivery Routing Algorithm for Faulty Network-on-Chips". NOCS '15 Proceedings of the 9th International Symposium on Networks-on-Chip. Nocs '15: 1–8. doi:10.1145/2786572.2786591. ISBN 9781450333962. S2CID 17741498.

외부 링크