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

nayoon kim

on 28 October 2015

Comments (0)

Please log in to add your comment.

Report abuse

Transcript of 최단경로 알고리즘!

최단경로 알고리즘!
design by Dóri Sirály for Prezi

데이크스트라 알고리즘
: 단일-쌍, 단일-출발, 단일-도착 최단 경로 문제를 풀 수 있다.

벨먼-포드 알고리즘
: 변의 가중치가 음수라면 단일 출발 문제를 풀 수 있다.

A* 탐색 알고리즘
: 탐색 속도를 높히기 위한 휴리스틱 방법을 사용하며, 단일-쌍 최단 경로 문제를 풀 수 있다.

플로이드-와셜 알고리즘
: 전체-쌍 최단 경로 문제를 풀 수 있다.

존슨의 알고리즘
: 전체-쌍 경로 문제를 풀 수 있고, 성긴 그래프에서는 플로이드-워셸 알고리즘보다 대체로 빠르다.

혼장 이론
: 국소적으로 가장 짧은 경로를 찾는다.


최단경로 알고리즘 종류
컴퓨터 과학에서, 데이크스트라 알고리즘은 어떤 변도 음수 가중치를 갖지 않는 유향 그래프에서 주어진 출발점과 도착점 사이의 최단 경로 문제를 푸는 알고리즘이다. 이름은 네덜란드의 컴퓨터과학자 에츠허르 데이크스트라의 이름에서 유래했다. 예컨대 어떤 그래프에서, 꼭짓점들이 각각 도시를 나타내고, 변들이 도시 사이를 연결하는 도로의 길이를 나타낸다면, 데이크스트라 알고리즘을 통하여 두 도시 사이의 최단 경로를 찾을 수 있다.

데이크스트라 알고리즘은 방향이 주어진 가중 그래프(weighted graph) G와 출발점 s를 입력으로 받는다. 그래프 G의 모든 꼭짓점들의 집합을 V라 하고, 그래프의 변을 출발점 u와 도착점 v의 순서쌍 (u, v)로 표현한다. G의 모든 변들의 집합을 E라 하고, 변들의 가중치는 함수 w: E → [0, ∞]로 표현한다. 이때 가중치 w(u, v)는 꼭짓점 u에서 꼭짓점 v로 이동하는 데 드는 비용(시간, 거리 등)이 된다. 경로의 비용은 경로 사이의 모든 변들의 가중치의 합이 된다. 데이크스트라 알고리즘은 V의 임의의 꼭짓점의 쌍 s와 t가 있을 때 s에서 t로 가는 가장 적은 비용이 드는 경로(최단 경로)를 찾는다. 이 알고리즘은 주어진 출발점 s로부터 다른 모든 꼭짓점까지의 최단 경로를 계산하는 데도 사용할 수 있다

데이크스트라 알고리즘이란 ?
그 중 우리가 쓸 것은?










!!!!!!!
여러분~~~

I에서 NC백화점까지 어떻게 가는게 최단 경로일까요?
목표!!!
출발!
몇 번 인가요~~~!!!
정답은 4번 입니다!
흔히 쓰이는 길은 1번이죠 ?
지금부터 그 속을 파헤쳐 보도록 하겠습니다
이 사진 처럼 최단 경로가 나옵니다

그리고 직접, 다이크스트라 알고리즘을 사용해서 최단경로를 알아보았습니다.일단, 다이크스트라 하는 방법을 알아봅시다.
<그 과정을 이제 보시죠 >
탐구동기 다시다시쓰기
A에서 B까지 최단거리로 이동하려고 할 때,
이동할 수 있는 경우의 수
를 구하여라.
점P(2,3)에서 점Q(5,6)까지
X축 위의 한 점을 지나게
이을 때
, 총 길이의 합이 최소가 되게 하는
X축 위의 좌표를 구하여라.
사람 구조하기
선과 선
점과 점
점과 선
~조 : 김나윤 김수인 차인영 이소현
데이크스트라 하는 방법
① 지도상의 모든 지점들과 집에서 각 지점들까지의
최단 거리를 나타내는 표
를 만든다.
② 집과 직접 길로 이어진 지점들까지의
최단 거리는 지도에 표시된 값으로 적고
그렇지 않은 지점들은 빈 칸으로 놓아둔다. 여기서 빈 칸의 값은 무한대를 뜻한다.

거리가 가장 짧은 건물부터
긴 지점 순으로 방문하고 방문한 건물은 색깔로 칠해 구별한다. 이때 방문한 경로도 색칠한다.
④ 새로운 지점을 방문하면 그 지점과 이어진 지점들까지의 거리를 새로 바꾼다. 단, 이전에 이미 최단 거리가 구해졌었다면 거리를 서로 비교해 작은 것으로 바꾸거나 유지한다.
⑤ 그래프의 모든 지점들을 방문할 때까지 ③,④의 과정을 반복한다.
(직접한 이론 실험)
먼저, 지도를 표로 간단히 나타낸다
이어진 지점들까지의 최단 거리는 지도에 표시된 값으로 적는다
거리가 가장 짧은지점부터 먼 지점순으로 방문한다

최종 최단경로
과연 이처럼 찾은 경로가 최단경로가 맞을까요?
<그래서 직!접!실행해 보았습니다 ^^>
일반적으로 사용하는 길과 이론적으로 나온 최단경로를 직접 시간을 재 보았습니다.
결론

실제로 데이크스트라 알고리즘을 써서 구한 최단경로가 진짜 최단경로인지 어리둥절 했었는데 직접 실험을 통해 예상했던 우리가 구한 최단경로가 진짜 최단경로라는 결론이 나왔다.
그리고 최단경로 알고리즘 중 하나인 데이크스트라 알고리즘을 이용해 최단경로를 직접 증명하였다.
또한 실제로 사용되고 있는 이 알고리즘의 구동원리를 알고 주변에 있는 수학에 대해 보는 시각을 넓혔으며 한발 더 다가가는 계기가 되었다


고도의 발전된 과학 문화로 혜택을 누리는 사람들
특히, 빨리빨리 하는 문화를 가진 우리나라 사람들에게 시간의 단축성은 중요해졌다.
그러던 와중, 모르는 길을 빨리 가려고 검색하면서, '이런 최단경로는 어떻게 나오는 걸까? 시간의 효율을 높이기 위해서 어떻게 이렇게 할 수 있을까 ?'라는 생각이 스쳤다.
그리고 이것을 탐구해 보기로 하였다.
하지만! 이와는 모순적이게 시간이 부족한 우리들
복습 파노라마
언제배운지 말해주면서 진행 <>
목 차
1. 탐구동기
2. 주제에 대한 복습
3.알고리즘 종류
4.데이크스트라 알고리즘
5.연구과정
6.결론
감상해 주셔서
감사합니다
ㄷ다시다시 보충
<우선 네이버 최단경로 검색을 해보았습니다.>
<자주 가는 길 >
<데이크스트라를 이용한 최단경로 >
4분 50초
4분 22초
Full transcript