-
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...
-
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가 현재 위치에...