마이크로 마우스 - 미로 시뮬레이션 프로그램 - 탐색 알고리즘 1

탐색 알고리즘에 대해 이야기 하기.
탐색 알고리즘은 워낙 많은 분들이 이야기하기 때문에.. 나의 방법도 하나의 방법이라 생각해 주면 좋을 듯하다.

가장 대표적인 방법에서 확장방식으로 진행( 내가 처음 배울때 이렇게 있었음)
좌측 우선(좌수법): 좌측을 먼저 보고
우측 우선(우수법): 우측을 먼저 보고
직진 우선(직진법): 직진을 먼저 보고
구심법 : ....
등고선법: ....

지금은 더 많은 탐색 알고리즘이 있을 듯합니다..
탐색하기전에 detect 즉, 장애물을 우선 감지합니다.
마우스는 기본 3곳 좌, 우, 앞 이고 확장 개념으로 5곳 좌, 우, 앞, 좌대각, 우대각, 그리고 나머지 6곳 좌, 우, 앞, 좌대각, 우대각, 후방, 이렇게 장애물을 감지합니다.

그럼 마우스가 가야 할 곳을 탐지해야겟지요.?!
이때 3곳을 기본으로 탐지합니다. (좌:Left, 우:Right , 앞:Front), 탐지 방법에 대한 경우의 수는 6가지
그럼 갈 수 있는 방향도 6가지로 아래와 같다.
좌측 우선(좌수법): L-F-R, L-R-F,
우측 우선(우수법): R-F-L, R-L-F,
직진 우선(직진법 : F-R-L, F-L-R

이렇게 해서 이동 알고리즘의 "장애물 감지 -> 회전" 부분에 위 알고리즘을 넣으면,
마우스가 잘 돌아 다닌다. 그러나 알고 있듯이, 마우스 얘가 왔던 길(찾았던 길)만 계속해서 지나가거나. loop에 빠져서 다른 길을 가지 못하는 경우가 발생한다.
이때 사용하는 것이 확장 좌/우/앞 우선법 을 사용한다. 즉, 지나갔던 길은 다시 지나가지 않는다.
근데 길을 가다 보면 갈림길에서 가지 않았던 길을 가려면 지나갔던 길을 다시 지나가야 하는데. 이때는 지나간 것은 지나간데로 가다가. 분기점에서 여기는 내가 안지나 갔으니까. 지나가야지 하고 행동하는 것이 확장 방식이다.
이렇게 하면 loop 발생 되는 미로가 없는 것을 때는 미로 탐색을 잘 할 것이다.

loop가 발생되는 미로에 대해서는 나중에 이야기 하자.(생각할 것이 많다.)

우여 곡절 끝에 미로의 모든 지역에 대해 탐색을 마쳤다. 그러면, 집(home) 또는 start Position으로 이동을 해야 한다.
그리고 목적지(Goal) 도 확인 해야한다.

그렇다면, 이제는 어떠한 알고리즘을 사용해야지??
고민이 된다.

오늘은 여기까지, 여기에 이어서 계속 작성할 것이다.