네비게이션 알고리즘 연습하기

다음과 같은 배열에서 0,0 위치에서 출발해서 4,4 위치까지 가는 경로에서 최소 비용으로 가는 경로를 출력하는 프로그램을 만들어 보시오.(너비우선 탐색)

0	1	1	1	1
1	1	1	1	1
1	1	1	1	1
1	1	1	1	1
1	1	1	1	0

BFS 알고리즘으로 찾는 방법

 

 

 

다음과 같은 배열에서 0,0 위치에서 출발해서 4,4 위치까지 가는 경로에서 최소 비용으로 가는 경로를 출력하는 프로그램을 만들어 보시오.

 

0	1	1	1	1
10	10	10	10	1
2	1	1	1	1
1	1	10	10	10
2	1	1	1	1

만약 위의 프로그램을 이용해서 출력해 보면 다음과 같은 경로가 출력 될 것이다.

int arr[5][5]={{0,1,1,1,1},
                    {10,10,10,10,1},
                    {2,1,1,1,1},
                    {1,1,10,10,10},
                    {2,1,1,1,1}};

 

즉 3.4 위치를 그냥 건너 뛰고 4.4 위치에 도착하게 된다.

그렇다면 BFS로 제대로 된 경로를 찾으려면 어떻게 해야 할까?

종착역에 도착했다고 해서 끝내면 안된다.

큐를 이용해서 더 찾아 갈 곳이 없을때 까지 계속 수행을 해야 한다.

그렇다면 연산 횟수는 몇번만에 찾을 수 있을까?

5 * 5 배열의 크기에서 41번만에 찾아 가는 것을 알 수 있다. 이보다 좀더 복잡한 맵이라고 하면 더욱 많이 걸리는 것은 자명한 일이다.

 

다익스트라 알고리즘을 이용하여 문제를 해결 해 보자.

 

AStar(A*) 알고리즘을 이용해서 문제를 풀어 보자.

 

여기서는 A*  알고리즘도 다익스트라 알고리즘과 동일한 결과를 얻게 되지만 맵이 큰 경우에는 A*가  앞으로의 예상 경로의 거리를 측정하기 때문에 조금 더 효율적인 알고리즘이 된다.