기록기록 우는 갈매기

Monte Carlo 알고리즘은 backtracking 알고리즘의 성능을 추정할 때 사용하는 알고리즘이다. Monte Carlo 알고리즘은 어떤 입력이 주어졌을 때 그에 따라 생성되는 상태공간트리의 전형적인 경로를 무작위로 생성하고 그 경로상에 있는 노드의 수를 센다. 이 과정을 여러 번 반복하여 나오는 결과의 평균치가 곧 추정치가 된다. 이처럼 Monte Carlo 알고리즘은 무작위 표본의 추정치를 사용하여 무작위 변수의 기대치를 측정하는 확률적 알고리즘이다. 이 알고리즘을 사용하기 위해 만족해야할 조건 2가지는 아래와 같다. ① 상태공간트리에서 같은 수준(level)에 있는 모든 노드에서는 같은 유망함수를 사용해야 한다. ② 상태공간트리에서 같은 수준에 있는 모든 노드들은 같은 수의 자식노드들을 가지..

n-Queens 문제란, nxn의 체스판에 n개의 퀸을 서로 충돌하지 않게 놓는 방법을 구하는 문제이다. 즉 서로 상대방을 위협하지 않도록 같은 행이나 같은 열, 또는 같은 대각선 상에 위치하지 않아야한다. 모든 경우를 따져가며 방법을 찾기에는 n이 커질수록 매우 다양한 경우를 따져야하므로 우리는 n-Queens문제에 backtracking 알고리즘을 적용하여 상태공간트리를 만들고, 유망한 노드들의 자식만 검사함으로써 검사해야 할 경우를 줄일 수 있다. n-Queens문제에 backtracking 알고리즘을 어떻게 적용하여 문제를 해결할 수 있는지 알아보자. 이전 글에서도 설명했다시피, backtracking 문제를 풀기위해 결정되어야 할 사항은 다음과 같다. ① 상태공간트리의 구조를 결정 ② 유망한지 ..

backtracking은 깊이우선탐색(DFS) 방식으로 상태공간트리를 탐색하는 알고리즘으로, 최적화 문제를 해결하는데에 사용될 수 있다. backtracking의 진행절차는 다음과 같다. ① 상태공간트리의 깊이우선검색(DFS)을 실시 ② 각 노드가 유망(promising)한지 점검 ③ 유망하지 않은 노드들은 더 이상 검색하지 않고 그 노드의 부모노드로 돌아가서 검색을 계속(pruning), 유망한 노드들은 그 노드의 자식노드를 검색 여기서 promising, 즉 유망하다는 것은 더 내려다볼 가치가 있다는 것이고 반대로 유망하지 않다(non-promising)는 것은 전혀 해답이 나올 가능성이 없다는 것을 의미한다. 유망하지 않으면 그 자식노드에 대한 탐색을 중단하고 부모노드로 돌아가는데, 이를 '가지친다..

다익스트라 알고리즘은 가중치가 있는 방향성 그래프에서 한 특정 정점에서 다른 모든 정점으로 가는 최단경로를 구하는 문제이다. 앞서 살펴본 프림 알고리즘, 크루스칼 알고리즘과 마찬가지로 최단 경로를 구하는 문제이며 그래프를 사용한다는 점에서 공통점이 있지만 다익스트라 알고리즘은 Minimum Spanning Tree를 구하는 문제가 아니라는 점에서 차이가 있다. 아래의 수도코드를 보면 프림 알고리즘의 수도코드와 유사하다는 것을 알 수 있지만, 이미 방문한 집합 V-Y에서부터 정점 v까지의 최단거리를 선택하는 프림 알고리즘과 달리 다익스트라 알고리즘은 출발점부터 정점 v까지의 최단거리를 구한다. 수도코드(high level) F:=∅ Y:={v1}; while(the instance is not solved..

크루스칼 알고리즘은 프림 알고리즘과 달리 한 정점이 locally optimal한지 결정할 때 단순히 edge의 가중치를 기준으로 결정한다. 즉, edge의 가중치가 작으면 작을수록 locally optimal한 것이다. 가중치가 작은 것 부터, 즉 유리한 것 부터 먼저 담으려는 크루스칼 알고리즘의 의도가 참 말그대로 'Greedy' 해보인다. 하지만 크루스칼 알고리즘이 대책없이 edge들을 마구마구 담아대는 것은 아니다. 순환 경로가 발생하지 않도록 정점들의 관계를 검사하는 작업을 치른다. 이 과정에 대해 더 자세히 알아보도록 하자. 수도코드(high level) F := ∅; //edge의 집합 초기화 create disjoint subsets of V, one for each vertex and c..

미래의 결과를 예측할 수 없는 상황에서 지금 내가 할 수 있는 최선의 결정은 무엇일까? 매 선택마다 그 순간에 가장 좋다고 생각되는 것을 선택하는 것이다. 즉, 그 순간에 가장 좋다고 생각되는 것을 선택함으로써 최종적인 해답에 도달한다. 매 순간 가장 좋다고 생각되는 것을 선택하면 그것이 궁극적으로도 최적이 될 수도 있기 때문이다. 이러한 원리의 접근방식이 바로 Greedy Approach이다. 하지만 이는 미래를 고려하지 않고 단지 그 순간에서의 optimal한 것을 선택한 것이므로, 그 해답이 궁극적으로 optimal라는 보장이 없다. 따라서 최적의 해답을 주는 알고리즘인지 검증하는 과정이 반드시 필요하다. 따라서 Greedy Approach 알고리즘의 구성은 다음과 같다. ① 선택 절차, selec..

외판원 문제란? home city에서 출발해 모든 city를 한번씩 거치고 다시 home city로 돌아오는 최단 경로를 구하는 문제이다. 만약 무식하게 모든 경우의 수를 다 알아본 후 가장 짧은 경로를 찾는다면 그 성능은 어떻게 될까? (n - 1)! 즉 O(n!)이라는 결과가 나온다. 이렇게 비효율적인 방법은 쓸모가 없으므로 우리는 동적계획법을 사용하여 TSP를 풀어보려고 한다. ① W : 그래프의 인접행렬 W[i][j] = 이음선의 가중치 (vi에서 vj로의 이음선이 있는 경우) = ∞ (vi에서 vj로의 이음선이 없는 경우) = 0 ( i = j인 경우 ) ② V : 모든 정점들이 담긴 집합 ③ A : V의 부분집합 ④ D[vi][A] : vi에서 A의 집합들을 한번씩 모두 지나면서 v1로 가는 ..

이항계수라하면 고등학교 때 잠깐 나타나고 말 것인줄 알았거늘..... 여기서 또 마주치다니 우리에게 너무나도 익숙한 이 이항계수 nCk 어쩌구 저쩌구가 동적 계획법과 어떤 관련이 있다는건지 알아보자..^^ 이항계수란? 이항계수는 n개의 원소중에서 k개를 순서에 상관없이 뽑았을 때 조합의 가짓수이다. 파스칼의 삼각형을 이용한 이항계수의 성질은 다음과 같다. nCk = n-1Ck-1 + n-1Ck 위 식과 그림을 보면 알 수 있듯, 파스칼 삼각형에서 n-1번째 줄 k-1번째 수와 n-1번째 줄 k번째 수를 합한 값이 n번째 줄 k번째 수의 값이 된다. 즉, 이전 항들의 수의 합이 다음 항의 수가 된다. 이는 전체 문제의 부분들이 서로 상관관계가 있다는 것이고, 따라서 이항계수는 dynamic programm..