[알고리즘] Backtracking

Backtracking

• *상태 공간 트리에서 DFS를 수행하여 promissing 노드만 탐색한다.
• non-promissing한 노드는 가지치기(pruning)하여 효율적으로 탐색한다

 

*상태 공간 트리(State Space Tree) 

• 루트 노드부터 리프 노드까지의 경로가 후보 솔루션이 된다.
• non-promissing한 경로는 탐색하지 않고 부모 노드로 돌아가 다른 자식 노드를 탐색한다.

void checknode(node v){
	node u;
    if(promising(v))                    //현재 노드(v)가 promising하다면,
    	if(there is a solution at v)    //v에서 결론이 나오면, 결론 반환
        	write the solution;
        else                            //v에서 끝나지 않는다면,
        	for (each child u of v)     //v의 자식 노드 u를 재귀적으로 호출
            	checknode(u);
}

 

---

[연습 문제1]

• n-Queens Problem
  • n x n 체스판에서 n개의 퀸을 서로 위협하지 않도록 배치하는 문제
  • 서로 다른 퀸은 같은 행, 열, 또는 대각선에 위치하지 않아야 한다.

void queens(index i){
	index j;
    if(promising(i)){                      //i위치가 promising한 경우
    	if(i == n)                         //i가 끝이라면 (끝까지 도달한 경우)
        	cout << col[1] through col[n]; //결과 출력
       	else
        	for(j=1;j<=n;j++){
            	col[i+1] = j;              //다음 열 검사
                queens(i+1);               
            }
        }
}

//i위치가 위협받지 않는 위치인지 확인하는 함수
bool promising(index i){
	index k;
    bool switch;
    k = 1;
    switch = TRUE;
    while( k < i && switch ){              //1열부터 k열까지, 이미 queen이 존재하는지, 대각선위치에 존재하는지 확인
    	if(col[i] == col[k] || abs (col[i] - col[k]) == abs(i-k))
        	switch = FALSE;
        k++;
    }
    return switch;
}

 

*백준

https://www.acmicpc.net/problem/9663

 

---

[연습 문제2]

공부 필요

• Graph Coloring Problem
  • m-Coloring : 인접한 영역이 같은 색이 되지 않도록 m개의 색으로 지도 또는 그래프를 색칠하는 문제

void m_coloring(index i){
	int color;            //색깔 번호
    if(promising(i))      //i에 color을 칠할 수 있을 때
    	if(i == n)        //모든 칸에 다 칠했다면,
        	cout << vcolor[1] through vcolor[n]; //결과 출력
        else
        	for(color = 1 ; color <= m ; color++){
            	vcolor[i+1] = color;             //i+1 에 색깔 넣어서 검사
                m_coloring(i+1);
            }
}

bool promising(index i){
	int j;
    bool switch;
    switch = TRUE;
    j = 1;
    while (j<i && switch){
    	if(w[i][j] && vcolor[i] == vcolor[j])
        	switch = FALSE;
        j++
    }
    return switch;
}

 

---

[연습 문제3]

공부 필요

• The Hamiltonian Circuits Problem (해밀턴 회로 문제) 
  • 주어진 그래프에서 각 정점을 정확히 한 번 방문하고 시작점으로 돌아오는 경로를 찾는 문제
  • 완전 그래프에서 항상 해밀턴 회로가 존재한다.

void hamiltonian(index i){
	index j;
    if(promising(i))
    	if(i==n)
        	cout << vindex[1] through vindex[n]; 
        else 
        	for(j=2;j<=2;j++){   //시작을 제외한 모든 정점에 대해서 시도
            	vindex[i+1] = j;
                hamiltonian(i+1);
            }
}

bool promising(index i){
	int j;
    bool switch;
    if(i == n && !W[vindex[n]][vindex[1]]) //끝까지 왔는데, 처음 위치로 돌아오지 않은 경우
    	switch = FALSE;
    else if(i>1 && !W[vindex[i-1]][vindex[i]]) //이웃하지 않는 경우
    	switch = FLASE;
    else {
    	switch = TRUE;
        j = 1;
        while( j < i && switch){ //i번째 정점이 이미 선택되었는지 검사
        	if(vindex[i] == vindex[j])
            	switch = FALSE;
            j++;
        }
    }
    return switch;
}

 

---

 

[연습 문제4]

공부 필요

• The 0-1 Knapsack Problem
  • 제한된 무게 내에서 최대 가치를 얻도록 물건을 선택하는 문제

void knapsack(index i, int porfit, int weight){
	if(weight <= W && profit > maxprofit){ //잔여무게 보다 weight가 작으면서(추가할 수 있으면서, maxprofit보다 가치가 크다면)
    	maxprofit = profit;
        numset = i;
        bestset = include;
    }
    if(promising(i)){
    	include[i+1] = "YES";
        knapsack(i+1, profit + p[i+1], weight + w[i+1]);
        include[i+1] = "NO";
        knapsack(i+1, profit, weight);
    }
}
    
bool promising(index i){
    index j,k;
    int totweight;
    float bound;
    if(weight >= W)
        return FALSE;
    else{
        j = i + 1;
        bound = profit;
        totweight = weight;
        while((j<=n) && (totweight + w[j] <= W)){
            totweight = totweight + w[j];
            bound = bound + p[j];
            j++;
        }
        k = j;
        if(k<=n)
            bound = bound + (W - totweight) * p[k] / w[k];
        return bound > maxprofit;
    }
}