Loading presentation...

Present Remotely

Send the link below via email or IM

Copy

Present to your audience

Start remote presentation

  • Invited audience members will follow you as you navigate and present
  • People invited to a presentation do not need a Prezi account
  • This link expires 10 minutes after you close the presentation
  • A maximum of 30 users can follow your presentation
  • Learn more about this feature in our knowledge base article

Do you really want to delete this prezi?

Neither you, nor the coeditors you shared it with will be able to recover it again.

DeleteCancel

Make your likes visible on Facebook?

Connect your Facebook account to Prezi and let your likes appear on your timeline.
You can change this under Settings & Account at any time.

No, thanks

최단경로탐색 이론

No description
by

JoonHo Park

on 21 September 2012

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of 최단경로탐색 이론

최단경로 탐색 기법들 Results 최단경로 탐색문제 Notes GPS의 보급 최단경로? 다익스트라(Dijkstra) 알고리즘 플로이드(Floyd) 알고리즘 이행적 폐쇄 알고리즘 A* 알고리즘 다익스트라 알고리즘의 원리 다익스트라 알고리즘이란? 지도 VS 네비게이션 details notes 최단경로가 사용되는 예 GPS 신호의 민간 수신은 1983년 소련에 의한 한국 항공기 KAL-007기의 격추 사건을 계기로 1984년 레이건 대통령이 공식 선언하였다. 최근 GPS 기술의 발전으로 인해 이를 기반으로 한 위치 기반 서비스에 대한 관심이 늘고 있다.

최단 시간 경로를 제공하는 교통 정보 시스템에 대하여 알아보기로 하였다. 두 노드를 연결하는 링크들의 가중치의 합이 최소인 경로를 말한다. 박준호, 박진희, 이승규, 이재원 How? 최단경로탐색 문제 화물운송 시스템 GPS를 이용한 네비게이션 시스템 다익스트라 알고리즘 VS 플로이드 알고리즘 플로이드 알고리즘이란? 플로이드 알고리즘의 원리 플로이드(Floyd) 알고리즘 동서울
의류물류센터 의정부
우편집중국 서인천
물류센터 심곡우편국 서인천우편국 연희우편국 강북우편국 도봉우편국 노원물류센터 회룡우편국 양주물류센터 의정부우편국 서울,경기,
강원.. 최단 거리를 구하는 또 하나의 알고리즘으로
동적 계획법을 이용한다.
플로이드 알고리즘은 모든 노드에서 출발해서 출발 한 노드을 제외한 모든 노드을 도착점으로 하는 최단거리를 한번 에 구하는 알고리즘이다.< 다익스트라와의 차이점 >

* 동적 계획법이란?
최적해를 구해 나가는 알고리즘의 하나로 한 문제에 대해 작은 해를 구해서 그것을 이용하여 큰 해 즉 최적해를 구해나가는 상향식 방식을 사용하는 기법이다. 최단 거리를 구하는 알고리즘으로 그리디 알고리즘을
기본으로 사용하고 있다.
하나의 노드에서 출발하여 시작 노드를 제외한 모든 노드를 도착점으로 하는 최단거리를 구하는 알고리즘이다.
단, 다익스트라 알고리즘은 노드갯수 만큼 반복해야 한다.

* 그리디 알고리즘 이란?
그리디 알고리즘은 전후 상황을 파악하지 않고, 현재 시점에서 가장 최적의 상황을 찾아 경로를 파악해 나가는 기법이다. 즉, 각각의 지점에 대하여 경로를 파악하는 것이다. 출발노드가 A일때 경우를 알아보면다음과 같다. 위 표와 같이 노드A에서
각 노드로 가는 최단경로는
B는 4, C는 7, D는 6 이 된다. 단, 다익스트라 알고리즘의 경우 출발지에 따른 계산해야 한다. 따라서 출발지가 달라질 경우 알고리즘을 다시 계산해야 하는 단점이 있다.
즉, 출발지가 A에서 B나 C로 변경될 경우 계산을 다시 해야한다. 속도면 다익스트라는 사용자가 지정한 출발점을 제외한 모든 노드와의 최단 거리를 구하지만 한번에 모든 노드간의 최단 거리를 최단거리를 구하는 플로이드 보단 상대적으로 속도가 빠르다고 할수 있다. 활용도 사용자가 출발지를 바꾸게 되면 다익스트라는 그때 그때 마다 다시 최단 거리를 구해야 하지만 플로이드는 이미 한번에 다 구했으므로 바로 바로 쓸수 있으므로 활용도면에선 플로이드가 좋다고 할수 있다. 다익스트라 > 플로이드 플로이드 > 다익스트라 다익스트라(Dijkstra) 알고리즘 기본적인 알고리즘의 원리는 다익스트라와 같이 간단하다 B에서 C로 갈수 있는 경로가 있고 또한 B에서 D를 경유해 C로 갈수 있는 경로가 있다고 하자 전자는 거리가 12이고 후자는 6+4인 10이다 그러면 플로이드 알고리즘에서는 B->D->C 루트를 최단 거리로 업데이트한다. 단, 플로이드 알고리즘은 다익스트라와는 다르게 모든 점점에서 출발해서 출발 한 정점을 제외한 모든 정점을 도착점으로 하는 최단거리를 구하는 알고리즘 이다. 1. 어떠한 경로도 거치지 않을 때

자기 자신은 가중치가 0이고 갈수 없는 노드일때는 가중치가 무한대가 된다. 2. A를 지나 간다고 할때

D에서 B로 갈때 바로 가면 가중치가 9이지만 D->B->A로 가면 거리가 5가 되므로 최단 거리가 9에서 5로 바뀐다. 3. B를 지나 간다고 할때

A에서 C로는 갈수 없지만 A->B->C 경로로는 갈수 있으므로 최단거리가 15가 된다.
A에서 출발하여 D로 갈때도 앞 경우와 마찬가지로 바로는 가지 못하지만 B를 경유 하면 갈수 있으므로 최단거리는 9가 된다. 4. C를 지나 간다고 할때

C를 경유할때는 어떠한 루트도 기존에 구해 놨던 최단 거리보다 작은 값이 나오지 않으므로 변화가 없다. 5. D를 지나 간다고 할때 <최종 단계>

B에서 출발하여 A에 도착할때와 B에서 출발하여 C에서 도착할때, C에서 출발하여 A에 도착할때가 각각 기존의 루트 보다 D를 경유해서 가는 것이 최단 거리가 된다. Bellman-Ford 알고리즘 최소 비용 신장 트리 알고리즘 최단 경로 탐색 알고리즘들은
위의 사례에서처럼 최단경로, 최소시간경로, 최소비용경로 등 경로 탐색에 있어서 여러 최단경로 탐색 알고리즘을 적절하게 이용하여 정확한 교통정보 서비스를 제공하며,
이러한 최단경로 탐색 기법을 활용하여 시간과 비용을 절약해주고 교통 정보를 제공함으로 신뢰성과 만족도를 제공해 줄 것이다. 피지 추론을 이용한 최단 경로 탐색 알고리즘 도로 상황의 변화에 영향을 미치는 요소들로는 시간대, 강수 정보, 차로 통제 정보의 세가지를 고려한 최단경로를 탐색하는 알고리즘을 구현
Full transcript