컴퓨터원리 서울대학교 Campus내의 효율적인 이동경로 및 예상시간에 관한 연구

컴퓨터원리 서울대학교 Campus내의 효율적인 이동경로 및 예상시간에 관한 연구 [컴퓨터원리] 서울대학교 Campus내의 효율적인 이동경로 및 예상시간에 관한 연구[1].doc 목차 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) 매트랩 우리 교과서