-
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...
-
A game of cops and robbers on planar graph
A game of cops and robbers on planar graph “Cops and Robbers” 게임은 그래프 $G$ 상에서 정의되는 추격-회피 문제의 한 유형이다. 이 게임은 두 명의 플레이어, ‘Cop’ (C)와 ‘Robber’ (R)가 참여한다. 게임의 규칙은 다음과 같다. 먼저 Cop이, 그 다음 Robber가 그래프 상의 정점을 선택하여 위치한다. 이후 두 플레이어는 교대로 인접한 정점으로 이동한다. Cop이 Robber와 동일한 정점을 차지하게 되면 Cop의 승리로, Robber가 이러한 상황을 무한히 회피할 수 있다면 Robber의 승리로 규정된다. 본 논의는 Robber가 현재 위치에...
-
Advanced Game Search Algorithms (1)
1. Introduction 이번 글에서는 게임 에이전트의 가장 단순한 형태인 Random Agent부터 시작하여 Greedy, Minimax, Alpha-Beta Pruning의 핵심 원리를 다룹니다. 또한 에이전트의 성능을 객관적으로 평가하기 위해 SPRT(Sequential Probability Ratio Test)라는 평가 기법을 소개합니다. 이를 이용하면 통계적으로 두 에이전트 간의 실력 차이를 엄밀하게 검증할 수 있습니다. 이후 이어지는 글에서는 Minimax Algorithm의 추가적인 Search Pruning 기법을 알아보고, MCTS 등의 현대적인 탐색 기법과 NNUE와 같은 neural network를 이용한 평가 방법을 살펴보겠습니다. 이번 글에서 소개하는 방법론은 $2$인, 제로섬, 턴제, 완전정보,...
-
Ladder Decomposition
개요 트리의 Ladder Decomposition은 Heavy-Light Decomposition과 유사하게, 트리를 경로들의 집합으로 분해하는 기법이다. 이번 글에서는 Ladder Decomposition의 정의와 알고리즘, 그리고 이를 응용해서 풀 수 있는 문제에 대해 알아보고자 한다. 정의 Ladder Decomposition를 한 문장으로 줄여 말하면 ‘HLD인데, subtree의 크기가 아니라 높이를 대신 본 것’ 이다. 구체적으로, Ladder Decomposition은 다음과 같은 알고리즘으로 구할 수 있다. 먼저 $h(u)$ 를 정점 $u$를 루트로 하는 서브트리의 높이라 정의하자. 루트부터 DFS를 실행하면서 정점 $v$에 도달 했을 때, $v$의 자식들이 $c_1$, $c_2$,...
-
Zip Tree
서론 Zip Tree는 Robert Tarjan, Caleb Levy, Stephen Timmel이 제시한 랜덤 기반의 Binary Search Tree의 일종이다. 논문에서는 Rotate연산 대신 Zip과 Unzip연산을 통해 트리의 균형을 맞춘다고 소개되어 있지만, 이는 사실 기존에 Treap 자료구조에 대해 다룬 논문에 기재된 Split과 Join연산의 구현과 구조가 동일하다. 본 글에서는 그럼에도 Zip Tree가 널리 알려진 Treap의 형태와 어떤 차이점이 있는지 소개하고, 얻을 수 있는 기대효과를 분석해 보고자 한다. Skip List vs Zip Tree Zip Tree는 Skip List를 Balanced Binary Search Tree로 변환한...