-
F-deletion 문제의 FPT 알고리즘
Introduction NP-hard로 분류되는 여러 그래프 관련 문제들을 아래와 같이 다른 관점에서 살펴보자. Vertex Cover Vertex Cover란 모든 간선의 최소 하나의 끝점을 포함하도록 하는 최소 크기의 vertex subset(minimum size vertex cover)을 찾는 문제이다. 이는, 다르게 생각하면 그래프에서 최소 개수의 정점을 제거하여, 그래프의 간선이 없도록 만드는 문제와 같다. 즉, $G$가 $\newcommand{\F}{\mathcal{F}}\mathcal{F} = {K_2}$ 를 minor로 포함하지 않도록 하는 것과 동치이다. Feedback Vertex Set Feedback Vertex Set 문제는 그래프에서 최소 개수의 정점을 제거하여 cycle을 포함하지 않도록 하는 문제이다....
-
Tensor Network
텐서 네트워크(Tensor Network Diagram)는 양자 컴퓨팅, 인공지능에 이르기까지 다양한 분야에서 활용되는 강력한 수학적 도구입니다. 복잡해 보이는 텐서 연산을 쉽게 하기 위해서는 다양한 트릭들이 필요한데, 텐서 네트워크는 텐서간의 연산을 그래프로 표현해서 복잡한 연산을 간단하고 직관적으로 다룰 수 있게 해줍니다. 이번 포스트에서는 텐서 네트워크 중에서도 양자 컴퓨팅에 자주 쓰이는 부분들을 소개하고자 합니다. 내용은 참고문헌 [1]을 주로 참고하였습니다. Quick Review: Bra-Ket Notation 우선 기본적인 bra-ket 표기법은 간략하게만 복습하고 넘어가겠습니다. bra-ket 표기법은 Paul Dira이 1939년에 제안한 표기법으로, 양자 상태를...
-
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이나...