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 클릭 문제 [Input] Graph \(G = (V, E)\) Positive Integer \(k\) [Query] 그래프 \(G\)에 크기가 \(k\)인 완전 부분 그래프(=Clique)가 존재하는가? * Graph (그래프) (URL) Mechanism (원리) Implementation (구현) Performance (성능) Verification (검증) Theorem. Clique Problem은 NP-Complete이다. * 어떤 문제가 NP-Complete이려면, NP이고 NP-Hard이어야 한다. - 이 때, NP-Hard임을 증명하는 것은 기존에 NP-Hard임이 증명된 문제를 해당 문제로 Reduction하여 논리적 관계를 보이는 것으로 이루어진다. * 클릭..
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(..
NP-Completeness Theory NP-완비성(완전성) 이론 - NP-완비성 이론에서는 어떤 문제가 NP-완비군에 속하는지에 대한 여부를 결정하는 여러 가지 기법들이 연구된다. - NP-완비군이란, 풀이 자체는 가능하지만, 현실적인 시간내에 해결할 수 없다 "강력히 추정"되는 문제들이 속한 그룹을 의미한다. (이 추정에 대한 증명은 100만달러 포상금이 걸린, 밀레니엄 문제로 출제되어 있고 아직까지 해결되지 않았다.) ※ 현재까지 NP-완비군에 속하는 문제들은 모두 Polynomial Time내에 풀 수 있는 방법이 고안되지 않았다. - 그러나, 만약 NP-완비군에 속하는 하나의 문제라도 Polynomial Time내에 풀 수 있는 방법이 개발되면, 수 많은 NP-완비군에 속하는 모든 문제들이 P..
Matroid Theory 매트로이드 이론 - Greedy Algorithm(그리디 알고리즘)이 Optimal Solution(최적해)을 가려낼 수 있는 경우인지를 판별할 수 있게 하는 수학적 공간이다. * Greedy Algorithms (그리디 알고리즘, 탐욕 알고리즘) (URL) [Algorithms] Greedy Algorithms | 그리디 알고리즘, 탐욕 알고리즘 Greedy Algorithms 그리디 알고리즘, 탐욕 알고리즘 - 지금 당장의 최선의 선택지만을 골라가며 해를 도출해나가는 방법을 채택한 알고리즘을 의미한다. (당장, 눈앞의 이익만을 좇는다.) - 그리디 dad-rock.tistory.com - 단, Greedy한 방법을 적용할 수 있는 모든 경우를 판별해낼 수 있는 것은 아니라서..
