Alpha-pruning 기반의 최장 지속 선호 경로 탐색 기법 = Alpha-pruning based Method for searching the preferred longest lasting path

국문 초록 (Abstract)

흔히 경로 탐색 알고리즘에서 주로 찾는 결과는 최단 거리 혹은 최단 시간 처럼 경로에 대한 "최단" 을 많이 찾는다. 이렇게 "목적지까지 최단시간으로 이동하려면 어떻게 해야 할까" 혹은 "목적지까지 가는 가장 짧은 길은 뭘까" 등과 같은 일반적인 문제에서 벗어나서 본 논문에서는 새로운 문제를 제시하려 한다. 일반적으로 우리가 A라는 역에서 B라는 역까지 이동하기 위해 위에서 언급한 최단 시간 및 최단 거리 알고리즘이 적용된 애플리케이션을 사용 한다면, 대부분 어느 역에서 어느 역으로 환승하라 혹은 이동하라 라는 결과를 보인다. 이러한 애플리케이션을 이용함에 있어서 교통 약자 그룹과 아닌 그룹의 차이점은 추천된 경로를 이용함에 있어서 불편함을 느끼는 것에 있다.
그러므로 교통 약자 그룹에게는 환승을 많이 해서 빨리 가는 경로, 혹은 빠른 이동시간을 가지는 경로보다는 "좀 더 오랫동안 앉아 갈 수 있는 경로" 혹은 "비교적 빨리 가지 않아도 편안하게 갈 수 있는 경로" 혹은 “비교적 빨리 가지 않더라도 앉아서 갈 수 있는 시간이 가장 긴 경로” 같은 결과를 보여줄 필요성이 있다. 본 논문에서 제시하는 문제는, Graph상에서 출발지와 목적지가 주어지고, 그 Graph 위를 이동하는 어떤 객체가 존재 할 때, 그 객체가 출발지에서 목적지까지 가기위한 최단 경로의 가중치에 최대한 가까운 가중치를 가지는 path 이면서 객체의 상태가 "주어진 특정 상태를 최대한 오랫동안 유지하는 path"를 찾는 문제이다.
본 연구에서 제시한 문제를 해결하기 위한 방법으로써 출발지에서 도착지까지의 모든 경로를 탐색 후에 주어진 특정 상태를 최대한 오랫동안 유지하는 경로를 찾는 방법과 그 보다 좀 더 빠른 연산 속도를 보이기 위해, 출발지에서 도착지까지의 모든 경로를 탐색하는 도중, 더 이상 탐색하지 않아도 되는 경로에 대해 추가적인 연산을 하지 않기 위한 Alpha-pruning 기반의 최장 지속 선호 경로 탐색 기법을 제안하였다. 실험으로 실제 지하철 노선도에 두 가지 방법을 적용하고, 그에 따른 각각의 연산 속도의 비교와 그에 따른 이유에 대해 보일 것이며, 동일한 경로 탐색질의에 대한 최단 경로의 결과와 본 탐색 기법간의 결과의 차이점에 대해 보인다.

목차 (Table of Contents)

• 1. 서론 1
• 2. 관련 연구 4
• 2.1 다익스트라 알고리즘(Dijkstra Algorithm) 4
• 3. 최장 지속 선호 경로 탐색 기법 5
• 3.1 기본 개념 5
• 3.2 최단 경로를 위한 다익스트라 알고리즘 12
• 4. 연구 내용 및 설명 13
• 4.1 All paths 13
• 4.2 Alpha-pruning paths 16
• 5. 실험 및 결과 분석 18
• 5.1 실험 설계 18
• 5.2 실험 결과 19
• 5.2.1 최단 경로 및 최장 지속 선호 경로 연산 결과 1 19
• 5.2.2 최단 경로 및 최장 지속 선호 경로 연산 결과 2 20
• 5.2.3 최단 경로 및 최장 지속 선호 경로 연산 결과 3 22
• 5.2.4 최단 경로 및 최장 지속 선호 경로 연산 결과 4 24
• 5.3 All Paths의 연산 속도와 Alpha-pruning paths의 연산 속도 비교 실험 26
• 5.3.1 환승역 미분류 실험 26
• 5.3.2 환승역 분류 실험 27
• 6. 결론 29
• 7. 참 고 문 헌 30
• 감사의 글 31
• Abstract 32