기록기록 우는 갈매기

sum of subsets problem이란 n개의 양의 정수(w1,w2,...,wn)와, 임의의 양의 정수 W가 있을 때, 다 합쳐서 W가 되는 모든 부분집합을 구하는 문제이다. 이 문제를 백트래킹을 사용하여 해결할 수 있다. 먼저 backtracking 문제를 풀기위해서는 상태공간트리의 구조와, 유망함수를 구축해야한다. sum of subsets 문제의 경우 상태공간트리의 구조와 유망함수는 다음과 같다. ① 상태공간트리의 구조 오름차순으로 level을 결정 ② 유망함수(promising function) weight + wi+1이 W보다 큰가? ≫ non-promising weight + total이 W보다 작은가? ≫ non-promising 양의 정수들을 오름차순으로 정렬하고, 작은 것 부터 즉 ..

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)는 것은 전혀 해답이 나올 가능성이 없다는 것을 의미한다. 유망하지 않으면 그 자식노드에 대한 탐색을 중단하고 부모노드로 돌아가는데, 이를 '가지친다..