[컴퓨터원리] 서울대학교 Campus내의 효율적인 이동경로 및 예상시간에 관한 연구
등록일 / 수정일- 페이지 / 형식
- 자료평가
- 구매가격
- 2010.06.23 / 2019.12.24
- 18페이지 /
doc (MS워드 2003이하) - 평가한 분이 없습니다. (구매금액의 3%지급)
- 1,400원
최대 20페이지까지 미리보기 서비스를 제공합니다.
자료평가하면 구매금액의 3%지급!
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
추천 연관자료
- 목차
-
1. 서론
1) 연구동기
2. 배경 및 이론
1) 다익스트라 알고리즘
2) 인접행렬의 표현
3. 방법 및 과정
1) 3D 표현을 위한 데이터 수집 및 서울대학교 캠퍼스의 표현
2) 다익스트라 알고리즘 구현
3) 4차원 인접행렬과 2차원 인접행렬의 연동 및 정수
4) 입력된 데이터로 경로 출력
5) 시간과 거리의 계산
6) 데이터 입력 프로그램
7) 데이터 등록 프로그램
4. 결과
1) 서울대학교 캠퍼스의 3D 모습과 모든 경로들
2) 데이터 입력 프로그램의 실행
3) 오직 걸을 경우 프로그램의 실행
4) 버스와 걷는 것을 고려했을 경우 프로그램의 실행
5. 결론 및 논의
1) 결론 및 우리 최단 프로그램만의 특징
2) 응용분야
3) 한계점
6. 참고문헌
- 본문내용
-
2. 배경 및 이론
1) 다익스트라 알고리즘
다익스트라 알고리즘은 1959년 다익스트라가 고안해낸 단일출발점에 대해 최단경로문제를 푸는 알고리즘이다. 관심 있는 단일 정점에서 다른 각 정점으로 가는 최단경로가 존재한다고 가정한 뒤 푸는 알고리즘으로 그 경로가 연결되어 있지 않는 경우는 수정을 좀 가하여 알고리즘을 풀면 된다. 다익스트라 알고리즘은 다음과 같이 전개된다.
최단경로를 구하기 위한 한 정점 만 포함하도록 집합 를 초기화한다. 이음선의 집합 (인접행렬)를 공집합으로 초기화시킨다. 이 조건에서 먼저 에서 가장 가까운 정점 를 선택하여 에 추가하고, 이음선 를 에 추가한다. 다음 에서 - 에 속한 정점으로 가는 경로 중에서 에 속한 정점만을 중간에 거쳐가는 경로를 검사한다. 이 경로들 중에서 가장 짧은 경로가 최단 경로가 된다. 이 경로의 끝에 위치한 정점을 에 추가하고, 그 경로상에서 그 정점으로 가는 이음선을 에 추가한다. 가 모든 정점의 집합인 와 같아질 때까지 이 과정을 되풀이한다. 이 시점에서 최단경로에 속한 이음선을 포함하게 된다. 이렇게 이루어지는 것이 다익스트라 알고리즘이다.
이러한 알고리즘을 통해 한 정점에서 다른 정점으로의 경로를 계속해서 추적해내어 최단거리 혹은 최단시간 경로 추적 프로그램 이용자를 위해 그 경로를 출력해낼 수 있을 것이다.
2) 인접행렬의 표현
인접행렬은 다익스트라 알고리즘을 쓰기 위해 꼭 필요한 행렬이다. 한 점에서 다른 점으로 가기 위해 있는 거리 정보라고 말할 수 있다. 예를 들어 n개의 점을 각각 1부터 n까지 이름을 새로 붙였다고 가정하자. 이때 이 시스템의 인접행렬에서 (i,j)는 i점에서 j점까지의 거리 혹은 시간을 의미하다. 점의 개수가 적으면 각 점에 정수의 정보를 입력하여 쉽게 인접행렬을 만들 수 있다. 하지만 좌표평면의 모든 점을 인접행렬로 옮기기 위해서는 너무 많은 시간과 어려움이 발생하며 다익스트라 알고리즘 실행 시 더 많은 루프를 돌아야하기 때문에 불편함이 따른다. 그러므로 한 좌표를 하나의 정수와 일대일 대응시킬 수 있는 함수를 만들어야 한다. 이는 다음과 같은 연관성으로 극복할 수 있다.
- 참고문헌
-
(1) Richard Neapolitan 외 1명, 도경구 역, Foundation of Algorithms using java pseudocode, 사이텍미디어, 2004.
(2) Sanjoy Dasgupta 외 2명, Algorithms, McGraw-Hill, 2008.
(3) 매트랩 우리 교과서
자료평가
-
아직 평가한 내용이 없습니다.
