-
Map Matching Algorithm
개요 Map Matching이란 Vehicle의 GPS 좌표 목록이 주어졌을 때 실제 도로상에서 어떠한 경로로 이동했는지를 복원하는 문제입니다. 다시 말해 입력으로 위경도 timeseries 데이터와 방향그래프로 구성된 도로 데이터가 주어졌을 때 도로상의 경로를 출력하는 문제입니다. 이 포스팅에서는 2009년 마이크로소프트 연구진에서 저술한 Hidden Markov Map Matching Through Noise and Sparseness 논문에서 제시하는 Map Matching 문제를 해결하는 알고리즘에 대해 설명하겠습니다. 맵매칭 문제의 어려움 맵매칭을 하는 가장 단순한 방법은 gps 좌표를 가장 가까운 도로로 매칭하는 것입니다. 그러나 gps 측정은 완벽하지 않고...
-
Advanced Game Search Algorithms (2)
1. Introduction 지난 Advanced Game Search Algorithms (1) 글에서는 Random, Greedy와 Minimax 에이전트들을 알아보았습니다. 이번 글에서는 Minimax 에이전트를 개선하는 Iterative Deepening 기법과 여러 Search Pruning 기법을 알아보겠습니다. 이는 주어진 탐색 시간을 더 효율적으로 사용하며 깊은 깊이까지 game tree를 탐색해 에이전트의 성능을 극적으로 개선합니다. 이번 글에서 다룬 코드들은 여기에서 테스트해볼 수 있습니다. 2. Baseline Code 이번 글에서 구현할 에이전트들은 게임 트리 탐색을 이용하기 때문에 많은 수의 노드를 확인할 수록 더 좋은 move를 선택할 수 있습니다. 그러므로...
-
Linear Time MST Using Randomization
개요 Minimum Spanning Tree(MST)는 연결된 무방향 그래프에서 모든 정점을 포함하면서 총 간선 가중치의 합이 최소가 되는 스패닝 트리를 의미한다. 전통적으로 Kruskal, Prim, Boruvka와 같은 결정적 알고리즘이 널리 알려져 있다. 그러나 위 알고리즘들 모두 전체 그래프를 스캔하고, 정렬 혹은 우선순위 큐 등에 간선 정보를 담는 과정에 의해 시간복잡도는 $O(ElogV)$정도에 머무른다. 그 와중 상대적으로 간단한 무작위 알고리즘을 이용해 이 시간복잡도를 $O(E)$ 정도로 줄이는 아이디어가 있어, 이를 소개해보고자 한다. Boruvka’s Algorithm Boruvka’s Algorithm은 MST를 유도하는 대표적인 알고리즘으로, Prim이나...
-
Lie groups and Lie algebras in a nutshell
0. Introduction 리 군(Lie groups)은 현대 물리, 수학, 공학 등에서 널리 쓰이고 있습니다. 수학을 전공하지 않는 경우 연속적인 대칭군 정도로 생각하는 경우가 많습니다. 수학적으로 엄밀하게 리 군에 대해서 배우기에는 요구하는 선수지식이 너무나 많고, 물리 또는 공학에서는 필요한 토픽들 위주로 공부를 하게 되면서 리 군과 리 대수가 어떻게 정의되는지 모르는 상태로 넘어가는 경우가 많은 것 같습니다. 본 글에서는 리 군과 리 대수를 수학적으로 엄밀하면서도 전공자가 아니더라도 최대한 이해할 수 있는 수준으로 서술하려고 합니다. 미적분학과 선형대수 지식을...
-
Graph Measure와 Tree-decomposition (1): Tree-independence Number
0. Preliminaries Treewidth를 이용한 알고리즘에 대해 다루는 국문 블로그 글이 상당수 있어 많은 독자들이 익숙할 것으로 보이나, treewidth에 익숙하지 않은 독자들이 있을 수 있으니, treewidth에 대해 먼저 소개하고자 한다. Graph 상의 다양한 NP-hard 문제들 가운데 상당수는 트리 혹은 트리와 유사한, 특수한 종류의 그래프에서 쉽게 다항시간에 해결할 수 있는 경우가 많다. 이에, 그래프가 얼마나 tree에 가까운지에 대한 척도를 생각해볼 수 있다. 그래프 $G$에 대해 $G$의 tree-decomposition은 다음 두 조건을 만족하는 트리 $T$와 $\beta : V(G) \to...