Backtracking 백트래킹 - 백트래킹 탐색에서는 탐색을 진행하다, 더 이상 진행할 수 없다면, 왔던 길을 되돌아가 다른 길을 찾는다. - 즉, 백트래킹은 DFS와 같은 방식으로 탐색하는 모든 방법을 통칭하는 개념이다. - 백트래킹 알고리즘마다 DFS와 약간의 차이는 있겠지만, 기본적으로는 모두 DFS의 카테코리에 속한다. - 백트래킹 알고리즘들이 모두 상태 공간 트리를 실제로 구성하여 수행하는 것은 아니지만, 백트래킹의 진행 과정은 상태 공간 트리의 Root부터 Leaf까지 DFS 방식으로 탐색하는 것과 논리적으로 동일하다. - 백트래킹에서는 상태 공간 트리를 탐색할 때, Parent에서 Child로 진행하며 최적해에 가까워져 가는데, Child로 진행하는중에 더 이상 진행할 가치가 없는(오답인)..
State Space Tree Search 상태 공간 트리 탐색 - 문제 해결 과정의 중간 상태들을 모두 Node로 구현해놓은 트리이다. - 상태 공간 트리의 Leaf Node는 해당 문제의 해(Solution)에 해당된다. - Optimum(최적해)는 Leaf Node 어딘가에 위치해 있고, 이를 효율적으로 찾아내는 것이 이 포스트의 주요 이슈이다. Brute Force (주먹구구식 탐색) - 상태 공간 트리에 존재할 수 있는 모든 Leaf Node들을 계산하여 모든 경우의 수를 조사하는 방법이다. - 대부분의 경우에서, 허용치를 넘어선 나쁜 성능을 보인다. Example. Asymmetric TSP Problem with Brute Force using State Space Tree - 위와 같은, ..
Hamiltonian Cycle Problem 해밀토니안 사이클 문제 [Input] - Undirected Graph \(G = (V, E)\) [Query] - \(G\)에 해밀토니안 사이클이 존재하는가? - 해밀토니안 사이클 결정 문제는 TSP로 Reduction(변환)하여 해결할 수 있다. 그 근거는 아래 포스트를 참고하자. * NP-Completeness Theory (NP-완비성 이론) (URL) [Algorithms] NP-Completeness Theory | NP-완비성 이론 NP-Completeness Theory NP-완비성(완전성) 이론 - NP-완비성 이론에서는 어떤 문제가 NP-완비군에 속하는지에 대한 여부를 결정하는 여러 가지 기법들이 연구된다. - NP-완비군이란, 풀이 자체는..
Approximation Algorithms 근사 알고리즘 * Traveling Sales Person Problem (TSP) (방문 판매원 문제) (URL) Reference: Introduction to Algorithms 3E (CLRS) (Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 저, MIT Press, 2018) Reference: 쉽게 배우는 알고리즘 (문병로 저, 한빛아카데미, 2018)
Clique Problem클릭 문제 - 1972년 Richard M. Karp가 NP-Completeness임이 입증된 문제로, 그래프 G = (V, E)와 양의 정수 k가 주어졌을 때, 그래프 G에 크기가 k인 Clique이 존재하는가에 대한 문제이다. * Clique- 완전 그래프인 부분 그래프를 의미한다. [Input]Graph \(G = (V, E)\)Positive Integer \(k\)[Query]그래프 \(G\)에 크기가 \(k\)인 완전 부분 그래프(=Clique)가 존재하는가? * Graph (그래프) (URL) [Data Structures] Graph | 그래프Graph 그래프 - 현상이나 사물을 Vertex(정점)와 이들을 잇는 Edge(간선)로 구성하는 방법으로, V..
Bounded Degree-Spanning Tree Problem (BD-ST Problem) 제한된 차수를 가진 신장 트리 문제 [Input] Graph \(G = (V,E)\) Positive Real Number \(k\) [Query] 모든 정점의 차수가 \(k\) 이하인 \(G\)의 신장 트리가 존재하는가? Mechanism (원리) Implementation (구현) Performance (성능) Verification (검증) Theorem. Bounded Degree Spanning Tree Problem는 NP-Complete이다. * 어떤 문제가 NP-Complete이려면, NP이고 NP-Hard이어야 한다. - 이 때, NP-Hard임을 증명하는 것은 기존에 NP-Hard임이 증명된 ..
Longest Path Problem 최장 경로 문제 [Input] Positive Weighted Graph \(G = (V, E)\) \(s, t \in V\) Positive Real Number \(k\) [Query] 정점 \(s\)에서 정점 \(t\)에 이르는 길이가 \(k\) 이상인 단순 경로가 존재하는가? Mechanism (원리) Implementation (구현) Performance (성능) Verification (검증) Theorem. Longest Path Problem은 NP-Complete이다. * 어떤 문제가 NP-Complete이려면, NP이고 NP-Hard이어야 한다. - 이 때, NP-Hard임을 증명하는 것은 기존에 NP-Hard임이 증명된 문제를 해당 문제로 Red..
Traveling Sales Person Problem (TSP Problem) 방문 판매원 문제 [Input] Positive Weighted Undirected Graph \(G = (V, E)\) Positive Real Number \(k\) [Query] Ver. Desicion Problem : \(G\)에 길이가 \(k\) 이하인 해밀토니안 사이클*이 존재하는가? Ver. Optimization Problem : \(G\)에서 길이가 가장 짧은 해밀토니안 사이클의 길이는 얼마인가? * Hamiltonian Cycle (해밀토니안 사이클; 한 붓 그리기) (URL) - 그래프의 모든 정점을 한 번씩만 방문하여 원래의 출발점으로 되돌아오는 경로를 의미한다. - 특히, Complete Graph(..
