[로봇내비게이션 강의정리] Shortest path Algorithm

다익스트라 알고리즘

다익스트라 알고리즘은 각 노드에서 모든 노드로 가는 최단경로를 알 수 있는 알고리즘이다.(계산을 통해서)

 

다익스트라 알고리즘

1) A노드를 방문하면 A의 이웃노드들 업데이트( O~B, O~C )

2) 업데이트 후 이웃 노드들까지 가는 비용을 원래 알던 값과 비교하여 priority queue에 push한다.

3) priority queue에서 pop하고, pop된 노드는 src노드에서 해당 노드까지 최단경로가 확정된 것이다. 이 상태에서 다시 1번으로 돌아가 반복한다.

 

의사코드는 다음과 같다.

목적지가 주어지지 않는 다익스트라

목적지가 주어지지 않고 모든 노드에 대해서 비용을 다 계산하는 케이스.

여기서 while문 안에 있는 u는 priority queue에서 pop해서 나온 노드를 말한다.

 

목적지가 주어진 경우

여기서 

if dist[u] = infinity : break 라는 게 있는데

목적지 노드까지 갈 수 없는 경우를 말한다. 그래프를 만들었는데 목적지까지 link들이 연결되어 있지 않은 경우가 이에 해당한다.

 

 

가장 일반적인 다익스트라 사용 알고리즘

바로 위 의사코드도 목적지가 주어지는 경우이며 목적노드로 도달하기까지 거치는 이웃노드들로의 최단경로를 업데이트하는 다익스트라 알고리즘 의사코드이다.

 

d(u) : src 노드 ~ u 노드까지의 거리

w(u,v) : u에서 v로가는 비용.

추가된 파란색 부분 : 방문 안했으면 우선순위 큐에 추가한다는 말이다.

 

아래 그림들을 통해서 이해해보자

3번 그림을 보자.

2번 노드는 pop하면서 빨간색 노드로 지정했는데 빨간색으로 지정한 노드는 최단경로라고 확정된 것을 의미한다.

어떻게 확정할 수 있을까?

src노드 기준으로 주변 노드를 계속 찾아나가는데 현재 상태에서 2번으로 가는 것이 가장 짧은 경로이기 때문이다. 3, 6번을 거치는 경우는 src노드 입장에서는 반드시 당장 2번으로 가는 경우보다 비용이 크다.

다시 말하면 3번 그림 상태에서는 2번노드로 가는 비용이 7로써 최단경로라고 확정할 수 있으나, 3번과 6번노드로 가는 비용은 9와 14로써 최단비용이라고 단언할 수 없다. 왜냐하면 2번노드로 가서 3번노드로 갔을 때 비용이 8만큼 들 수도 있다는 가능성이 남아있기 때문이다.

 

4번의 경우도 마찬가지이다.

 

 

---

A* 알고리즘

g(A) : 출발지 ~ A 노드까지 계산되어 나온 비용

h(A) : A ~ goal 까지 가는데 걸리는 예상비용. 휴리스틱값을 말한다. 이 값은 목적지가 나올 때까지 계속 바뀔 수 있다.

h(A)는 A ~ goal까지의 실제값보다 작으면 알고리즘이 문제 없이 돌아간다.

 

다익스트라 알고리즘은 A*알고리즘의 특별한 케이스(목적지가 주어지지 않아 모든 경우에 대해서 shortest path를 계산하는 case)

 

A*알고리즘의 의사코드는 다음과 같다.

<의사코드 정리>

의사코드 정리

여기서 openset은 priority queue로 구성하는 것이 좋다.

 

의사코드 설명 참고자료 : https://deliorange.tistory.com/110

A* 알고리즘 쉬운 개념 설명

 

 

 

Weight Matrix 개념설명

Weight Matrix

matrix 안에 비용을 적어 넣는다. 무한대로 표시된 값은 아직 탐사가 안된 노드이거나 갈 수 없는 노드를 말한다.

 

adjacency matrix개념설명

adjacency matrix

주변 노드와의 연결관계를 나타낸다. 매트릭스 안에 값은 0과 1로만 표현한다.