상세 컨텐츠

본문 제목

[알고리즘] Backtracking (백트래킹)

PROGRAMMING/Algorithm

by koharin 2022. 1. 8. 23:20

본문

728x90
반응형

Overview


  • Backtracking
  • n-Queens 문제
  • Sum-of-Subset 문제 (부분집합의 합 구하기 문제)
  • 그래프 색칠하기 문제
  • Hamiltonian Circuits Problem
  • Monte Carlo 기법 (probabilistic Algorithm)

 

Backtracking


1) Backtracking

  • 노드의 유망성 점검 후 유망하지 않으면 부모로 되돌아가(backtracking) 다음 자식노드의 유망성 점검하여 문제의 답 찾는 기법
  • 마디의 유망성
    • 전혀 해답이 나올 가능성이 없는 마디는 유망하지 않다(non-promising)고 판단, 그렇지 않으면 유망하다(promising)고 판단
  • 어떤 집합에서 특정 기준을 만족하도록 원소를 선택하는 문제 해결에 적합
    • 예) n-Queens 문제
  • 깊이 우선 탐색(depth-first search)을 변형한 기술

 

2) Tree traversal

  • 트리에서 각 노드를 한 번만 방문하는 과정
  • 노드 방문 순서에 따라 분류: 전위 순회(preorder), 중위 순회(inorder), 후위 순회(postorder), 레벨 순서 순회(level-order)

preorder

  • Root-L-R
  • 노드 방문
  • 왼쪽 서브 트리 전위 순회
  • 오른쪽 서브 트리 전위 순회
  • 깊이 우선 순회(depth-first traversal)이라고도 함
preorder(node)
	print node.value
    if node.left != null
    	then preorder(node.left)
    if node.right != null
    	then preorder(node.right)

 

inorder

  • L-Root-R
  • 왼쪽 서브 트리 중위 순회
  • 노드 방문
  • 오른쪽 서브 트리 중위 순회
inorder(node)
	if node.left != null
    	then inorder(node.left)
    print node.value
    if node.right != null
    	then inorder(node.right)

 

postorder

  • L-R-Root
  • 왼쪽 서브 트리 후위 순회
  • 오른쪽 서브 트리 후위 순회
  • 노드 방문
postorder(node)
	if node.left != null
    	then postorder(node.left)
    if node.right != null
    	then postorder(node.right)
    print node.value

 

level-order

  • 모든 노드를 낮은 레벨부터 차례대로 순회
  • 너비 우선 순회(breadth-first traversal)

 

3) Depth First Search(DFS, 깊이우선탐색)

void DepthFirstSearch(node v){
	node u;
    visit v;
    for(each child u of v)
    	DepthFirstSearch(u);
}

 

4) Backtracking Algorithm

void checknode(node v){
	if(promising(v))
    	if(there is a solution at v)
        	write the solution;
        else
        	for(each child u of v)
            	checknode(u);
}

 

 

 

n-Queens 문제


1) 4-Queens 문제

  • 4개의 Queen을 서로를 위협하지 않도록 4 x 4 체스판에 위치시키는 문제
  • 상태 공간 트리(State Space Tree)
    • 해의 후보들의 모임?
    • 문제 해결 과정에서 중간 상태를 한 노드로 나타낸 트리. 
    • root에서 leaf 노드까지 경로가 candidate solution(해답 후보)가 되는데, 깊이우선검색을 통해 해답후보 중에서 해답을 찾는다.
      • 비효율적 -> 해답이 될 가능성이 없는 마디의 후손마디까지 모두 검색해야 함. 
  • 노드 방문했을 때 노드를 포함한 경로가 해답이 될 수 없으면 해당 노드는 유망하지 않다고 판단, 해답의 가능성이 있으면 유망하다고 함
  • pruning(가지치기): 유망하지 않는 노드가 포함된 경로는 더 이상 고려하지 않는 과정
  • backtracking 알고리즘
void checknode(node v){
	node u;
   	if(promising(v))
    	if(there is a solution at v)
        	write the solution;
        else
        	for(each child u of v)
            	checknode(u);
}

  • 상태공간트리
    • 방문한 노드만 나타낸 트리

 

 

2) n-Queens 문제

  • n x n 서양 장기판에서 배치한 Queen들이 서로 위협하지 않도록 n개의 Queen을 배치하는 문제
    • 일련의 원소: Queen을 배치한 n개의 위치
    • 기준: 어떤 두 Queen도 서로를 위협하지 않아야 함
  • 서로 상대방을 위협하지 않음
    • 같은 행, 같은 열, 같은 대각선 상에 위치하지 않는다.

promising 함수

  • 같은 열에 있으면 안 된다.
  • 대각선 판별
    • col(i): i번째 행에 있는 Queen의 열 위치
boolean promising(index i){
	index k=1;
    boolean p = true; // 노드 유망성 여부 
    while(k<=i && p){
    	if(col[i] == col[k] || abs(col[i]-col[k] == i-k)
        	p = false; // 같은 열에 있거나 같은 대각선에 있으면 유망성 X
        k++;
    }
    return p;
}

n-Queens 함수

void queens(index i){
	index j; // 열 인덱스
    if(promising(i))
    	if(i==n) // leaf 노드이면 
        	cout << col[1] through col[n]
        else
        	for(j=1; j<=n; j++){
            	col[i+1] = j;
                queens(i+1);
            }

 

3) n-Queens 문제 분석

  • 모든 노드 수: 1 + n + n^2 + ... + n^n = n^(n+1)-1/n-1
    • 실제로는 모든 노드 검사 X
  • 유망한 노드 수
    • 두 개의 queen은 같은 열에 위치할 수 없으므로, 열의 수가 하나씩 줄어간다.
    • 1 + n + n(n-1) + n(n-1)(n-2) + ... + n!
  • 2가지 분석 방법은 대각선 점검하는 경우를 고려하지 않으므로, 실제 유망한 마디 수는 훨씬 적을 수 있으며, 유망하지 않은 마디도 포함하여 알고리즘의 복잡도를 정확히 표현하지는 않는다.

 

 

Sum-of-Subset 문제


1) Sum-of-Subset 문제

  • n개의 양의 정수 Wi가 있을 때 부분집합의 원소들의 합이 W가 되는 모든 부분집합을 찾는 문제
  • 무게를 오름차순으로 정렬하여 노드의 유망성 점검이 쉽다.
  • 유망하지 않은 노드 조건
    • weight + Wi+1 > W
    • weight + total < W
void SumOfSubset(index i, int weight, int total){
	if(promising(i))
    	if(weight == W) print solution;
        else{
        	include[i+1] = true; // 다음 item 포함했을 때
            SumOfSubset(i+1, weight+w[i+1], total-w[i+1]);
            include[i+1] = false; // 다음 item 포함했을 때
            SumOfSubset(i+1, weight, total-w[i+1]);
        }
}
boolean promising(index i){
	return (weight+total >= W) && (weight == W || weight+w[i+1] <= W);
}

 

2) Sum-of-Subset 문제 분석

  • 상태공간트리에 최대 노드 수: 1 + 2 + 2^2 + ... + 2^n = 2^(n+1) - 1

 

 

그래프 색칠하기(Graph Coloring) 문제 


1) m-Coloring 문제

  • 문제: 노드를 최대 m개의 색으로 색칠하는 문제
  • 제약조건: 인접한 노드는 같은 색으로 칠할 수 없다.
  • 응용: 평면 그래프(planar graph) - 임의의 두 간선이 서로 교차되지 않도록 그래프를 평면에 그릴 수 있는 경우
  • 입력: 정점 n, 색 m, 인접행렬 W[i][j]
  • 출력: 최대 m개 색을 가지고 그래프에 색칠 가능한 모든 경우
void m_coloring(index i){
	int color;
    if(promising(i))
    	if(i==n) print output;
       	else
        	for(color=1; color <= m; color++){ // 다음 정점에 대해 모든 색 시도
            	vcolor[i+1] = color;
                m_coloring(i+1);
            }
}
bool promising(index i){
	index j;
    bool switch;
    switch = true;
    j=1;
    while(j < i && switch){ // 인접 정점이 동일한 색d이면
    	switch = false; // 노드 유망 X
        j++;
    }
    return switch;
}

 

2) m-Coloring 문제 분석

  • 상태공간트리 상의 마디 총 수: 1 + m + m^2 + ... + m^n = m^(n+1)-1/m-1

 

 

Hamiltonian Circuit Problem


1) Hamiltonian Circuit

  • 해밀토니안 순환경로: 연결된 무방향 그래프에서 주어진 정점에서 출발해서 모든 정점을 정확하게 한 번 방문하고 출발한 정점으로 되돌아오는 경로
  • 해밀토니안 순환경로 문제: 연결된 무방향 그래프에서 해밀토니안 순환경로 찾는 문제
  • 상태 공간 트리에서 노드 유망 여부
    • 경로에 있는 i번째 정점은 i-1번 정점과 인접해야 한다.
    • (n-1)번째 정점은 0번째 정점(출발정점)과 인접해야 한다.
    • i번째 정점은 그 앞의 i-1개의 정점들 중 하나가 될 수 없다.

 

2) Hamiltonian Circuit Problem

  • 문제: 연결된 비방향 그래프에서 해밀턴 경로 모두 구하기
  • 입력: 정점 수 n, 정점이 n개인 비방향 그래프 W[i][j]
  • 출력: 해밀턴 회로 이루는 모든 경로
void hamiltonian(index i){
	index j;
    if(promising(i))
    	if(i == n) print output;
    else
    	for(j=2; j <=n; j++){ // 
        	vindex[i+1] = j;
            hamiltonian(i+1);
        }
}
bool promising(index i){
	index j;
    if(i == n-1 && !W[vindex[n-1]][vindex[0]])
    	switch = false // 첫 번째 정점과 인접해야 함
    else if(i>0 && !W[vindex[i-1][vindex[i]])
    	switch = false; // i번째 정점은 (i-1)번째 정점과 인접해야 함
    else{
    	switch = true;
        j=1;
        while(j<i && switch){
        	if(vindex[i] == vindex[j]) // 이미 방문한 노드이면
            	switch = false;
            j++;
        }
    }
    return switch;
}

 

3) Hamiltonian Circuit Problem 분석

  • 상태공간트리에서 최대 노드 수: 1 + (n-1) + (n-1)^2 + ... + (n-1)^(n-1) = (n-1)^n - 1/n-2

 

 

Monte Carlo 기법 (Probabilistic Algorithm)


1) Monte Carlo 기법

  • backtracking 알고리즘 수행시간 추정
  • 어떤 입력이 주어졌을 때 점검하게 되는 상태공간트리의 경로를 무작위로 생성하여 그 경로 상에 있는 마디 수를 센다. 이 과정을 반복하여 나온 결과의 평균치를 알고리즘 수행시간 추정치로 함
  • 두 조건 만족
    • 상태공간트리의 같은 수준(level)에 있는 모든 마디의 유망성 여부 점검 절차는 같아야 함
    • 상태공간트리의 같은 수준에 있는 모든 마디는 반드시 같은 수의 자식마디를 가지고 있어야 함
  • n-Queens 문제는 두 조건 만족

 

2) Monte Carlo 알고리즘

1. 뿌리마디의 유망한 자식마디 개수: m0

2. 상태공간트리의 수준 1에서 유망한 마디 하나 랜덤하게 정하고, 해당 마디의 유망한 자식마디 개수 m1

3. 정한 마디의 유망한 마디 하나 랜덤하게 정하고, 해당 마디의 유망한 자식마디 개수 m2

4. ...

5. 더 이상 유망한 자식마디가 없을 때까지 과정 반복

  • mi는 수준 i에서 마디의 유망한 자식마디의 개수의 평균 추정치
  • 한 마디 자식마디의 총 개수: tj
  • 점검한 마디의 총 개수 추정치: 1 + t0 + m0t1 + m0m1t2 + ... + mi-1ti + ...

 

 

728x90
반응형

'PROGRAMMING > Algorithm' 카테고리의 다른 글

관련글 더보기