5장. 되추적 (Back-tracking)

◆ 되추적!?

어떤 수에서 더이상 확장할 수 없거나 유망하지 않다면 전 단계로 돌아가면서, 상태 공간을 만듦.

그 상태공간을 돌아다니면서 해를 찾는 방법.

 

마디의 유망성:

✓ 전혀 해답이 나올 가능성이 없는 마디는 유망하지 않다(non-promising)
✓ 그렇지 않으면 유망하다(promising).

되추적이란?

✓ 어떤 마디의 유망성을 점검한 후, 유망하지 않다고 판정이 되면 그 마디의 부모마디(parent)로 돌아가서(backtrack) 다음 후손마디에 대한 검색을 계속하게 되는 절차.
✓ 부모마디로 돌아가는 것  → 가지치기(pruning)
✓ 이 과정에서 방문한 마디만으로 구성된 부분트리
→  가지친 상태공간 트리(pruned state space tree)

 

---

◆ 트리 방문 순서

---

◆ n-queens 문제

n개의 Queen을 서로 상대방을 위협하지 않도록 nxn 판에 위치시키는 문제.
(i, col[i]) 가 확정된 퀸 좌표 

 

[pseudo code]

void queens(index i){
    index j;
    if(promising(i))	// 만약 col[i] 위치에 놓아도 된다면 (유망하다면)
        if (i==n)	// 만약 col의 마지막 원소까지 채워졌다면
            cout << col[1] through col[n];	// 유망한 위치를 모두 찾은것이므로 프린트
        else	// 아직 덜 채워졌다면
            for (j=1; j<=n; j++){	// 1부터 n까지 j 돌리기
                col[i+1] = j;	// 다음 행 j열에 퀸을 넣어봄. 유망하다면 이대로 진행할것이고
                queens(i+1);	// 아니라면 그대로 return되고 다음 i값과 j값이 들어갈 것임	
        }
}

// col[i] 위치가 유망한지 판단
bool promising(index i) {
    index k;
    bool switch;
    k=1;
    switch = true;		// 우선 true로 초기화
    while ( k<i && switch ){	// 아직 유망한 경우, 지금까지 확정된 col[i-1]까지와 비교
        if( col[i]==col[k] || abs(col[i]-col[k]) == i-k)	// 같은 열이거나, 대각선인 경우
        	switch = false;	// 유망하지 않다고 확정하고 return
        k++;		// k를 1~i-1까지 증가시켜가면서, 지금까지 확정된 col[k]들과
            		// 이번 col[i]를 비교해, 유망한지 판단
    }
    return switch;	// 중간에 false되면 바로 리턴될 것이고,
			// 지금까지 확정된 애들이랑 다 판정했는데 여전히 유망하면 true
}

초기 입력은 queens(0)

 

n과 col[]은 전역 변수. 수도코드에서 배열의 index는 1부터 시작한다 하고.

처음 입력은 queens(0)이며, col[]은 0으로 초기화되어 있음.

(i, col[i])가 queen이 위치한 좌표(행,열)임. 1차원 배열 기준, 한칸씩 오른쪽으로(한줄씩 아래로) 가면서 확인함

 

그림과 같이 행의 차와 열의 차의 절댓값이 같다면, 대각선에 있는 것!

 

---

◆ n-queens 문제 - 상태 공간 트리의 최대 크기

1) 이론적인 최대크기 상한값

깊이 1인 경우는 n개의 노드를 가지고,  2인 경우 n개의 노드가 각자 n개의 노드를 가지고, ... 이런식으로 깊이 n인 경우까지 간 것이 이론적 상한값. 그러나 되추적을 사용하면 얘넬 전부 방문하지는 않기 때문에, 이론적인 값일 뿐임 ㅇㅇ

 

2) 같은 열에 위치하는 경우를 제외하고 계산한 최대크기 상한값

어떤 두 개의 퀸이 같은 열에 위치할 수 없다는 사실을 이용. (유망한 마디만 세어서 상한을 구함)

예를 들어 n = 8이라 하자. 첫번째 Queen은 어떤 열에도 위치시킬 수 있고, 두 번째는 기껏해야 남은 7열 중에서만 위치시킬 수 있고, 세 번째는 남은 6열 중에서 위치시킬 수 있다.

이런 식으로 계속했을 경우 마디의 수는 1 + 8 + 8 * 7 + 8 * 7 * 6 + …+ 8! = 109,601가 된다.

이 결과를 일반화 하면 유망한 마디의 수는 1+ n + n(n −1) + n(n −1)(n − 2) +...+ n! 을 넘지 않는다. 

=> 그러나 이 경우도, 같은 대각선에 위치하는 경우를 제외하지 않았기 때문에 유망하지 않은 값이 많이 포함된 결과임.

 

!! 같은 열, 같은 대각선까지 다 계산하는건 직접 해봐야 할 수 있음. 다음은 대충 추정한 표

 

 

위치를 어떻게 표현하느냐에 따라 상태공간 트리가 달라지기도 함

이렇게 각 자리에 번호를 매겨서 표현하면 또 달라짐~  이렇게하면 쫌 더 복잡 

 

---

◆ 되추적 - 바둑 게임

바둑 게임에 되추적방법을 적용할 수 있는가?

 

• 돌이 위치할 수 있는 지점의 수 : 19*19 = 361

 

1) 매번 361개의 자리에 놓을 수 있다고 가정할 때 상한 = 361³⁶¹

 

2) 이미 놓은 위치에는 못 넣는다는 가정 하의 상한 = 361!

 

---

◆ 부분집합의 합 구하기 문제 (sum of subsets problem)

무게가 증가하는 순(작은 순)으로 데이터를 정렬하고, 다음 두가지 기준에 의해 유망한지 판단
1) 이 다음 거 넣었을 때 W를 넘으면 안 유망
2) 앞으로 남은 거 다 넣어도 W보다 작으면 안 유망

n개의 item을 이용해, item들의 무게 합이 W가 되도록 하는 부분집합을 구하는 문제

 

 

1) 모든거 표현해서 해를 찾는 상태공간 트리 방법

n = 3, w₁ = 2, w₂ = 4, w₃ = 5, W = 6이라 하자.

한 노드에서 w_깊이 를 선택하면 왼쪽, 선택 안하면 오른쪽으로 보내고, 노드에는 그 합을 표시한 것.

최종적으로, w1을 넣고 w2를 넣고 w3를 안 넣은 값(왼쪽, 왼쪽, 오른쪽)이 구하고자 하는 W라는 걸 알 수 있음

 

 

 

2) 무게가 증가하는 순으로 데이터 정렬 (유망한지 쉽게 판단)

i번째 까지 포함된 무게의 합이 weight라 하고, 남아 있는 아이템의 무게 총합을 total이라 하자.

• weight + w_i+1 > W 이거나, weight + total < W이면 유망하지 않음!

즉, 이번 아이템을 넣었을 때 원하는 W 보다 무게가 커지면 유망하지 않고

현재까지 더한 것 + 남은 것을 다 더해도 W보다 작으면 유망하지 않다는 뜻. 그 이후엔 고려할 필요 없음

 

n = 4, w₁ = 3, w₂ = 4, w₃ = 5, w₄ = 6, W = 13 이라 하자.

 

맨 왼쪽 아래 노드는 다음 거 더했을 때 W보다 커지므로 유망하지 않아서 그만한 것이고,

맨 오른쪽 아래 노드는 남은거 다 더해도 W보다 작으므로 유망하지 않아서 그만한 것

 

이처럼 promising 조건을 잘 이용하면 전체 마디를 생성하지 않아도 해를 구할 수 있는 것~

 

[pseudo code]

void sum_of_subsets(index i, int weight, int total)	//지금까지의 weight와 total을 체크할 것
{
    if(promising(i))	// 유망하다면
        if (weight == W)	// 만약 지금까지의 weight가 W가 되었다면
        	cout << include[1] through include[i];	// include[]의 원소들 출력
        else{	// 아직 W가 안 되었다면
            include[i+1]=“yes”;	// i+1번째 w를 포함해보자
            sum_of_subsets(i+1, weight+w[i+1],total-w[i+1]);	// i+1번째 포함했을때의 weight와 남은 total 넘김
            include[i+1]=“no”;	// i+1번째 w를 제외해보자
            sum_of_subsets(i+1, weight,total-w[i+1]);	// i+1번째 제외했을 때의 weight와 total 넘김
       }
}

bool promising(index i){
	// 남은 무게 체크 && 현재 무게 관련 체크
    return(weight+total>=W)&&(weight == W ||weight+w[i+1]<=W);
}

초기 호출 : sum_of_subsets(0,0,total)

 

 

※ promising 함수 return 값은! 

이 조건에 not을 붙인 것. A or B => not A and not B로 만든 것

 

 

※ 이번 i+1번째 아이템을 포함 안하더라도, 남은 아이템들 사이에서는 이번 아이템이 제외된 것이므로

total에서는 무조건 w[i+1]을 빼줘야 함

 

 

최악의 경우는.. 많이 밑에까지 내려가서 비로소 non promising이라는 것을 알게되는 경우임

한 레벨을 내려갈 때마다 2ⁱ만큼 노드 수가 많아지기 때문

 

---

◆ 그래프 색칠하기 문제 (graph coloring)

2차원 평면에서 영역을 나눈 맵에서, 인접하는 지역을 서로 구분하기 위해 색깔을 할당해주는 문제를 의미함.

어떤 지도이더라도 4개의 색깔이면 충분함!

이때 구분하기 위한 색깔의 수를 최소로 하고싶다!

 

■ 맵 칼라링 → 그래프 칼라링으로 변환하는 방법

각 영역을 노드로 표시하고, 인접하는 지역끼리 엣지를 만듦.

그래프에서도 역시, 엣지가 연결된 노드들 끼리는 같은 색깔을 부여하지 않는다!

 

 

■ planar graph(평면 그래프):

맵 칼라링 문제를 그래프 칼라링으로 바꿨을 때 만들어지는 그래프로, 평면 상에서 엣지들이 서로 엇갈리지 않게 그릴 수 있는 그래프.

이런식으로 그릴 수 있으면 평면 그래프임

 planar graph인 경우, 최대 4개의 색깔이면 충분히 구분 가능함.

※ nonplanar 그래프 예시

 

---

◆ m-coloring problem

W[i][j] && vcolor[i]==vcolor[j]   ←non promising
즉, i와 j가 연결되어 있는데, 두 칼라가 같다면 non promising

m개의 색깔을 가지고, n개의 노드가 지도에서 인접한 지역이 같은 색이 되지 않도록 지도에 색칠하는 문제.

여기서는 m=2인 경우는 불가능!

3부턴 가능. 구분할 수 있으면 어떻게 구분할 수 있는지까지 찾아야 함~

 

< 방법 >

1,2,3 선택지가 색깔 선택지임!

레벨이 노드 번호.

 

v2에서 1을 택하면, 연결된 v1과 같은 칼라이므로 유망하지 않음

v3에서 1을 택하면, 연결된 v1과 같은 칼라이므로 유망하지 않음

v3에서 2를 택하면, 연결된 v2와 같은 칼라이므로 유망하지 않음

 

 

[pseudo code]

void m_coloring(index i) {
    int color;

    if(promising(i))
        if(i==n) //이번에 해를 다 찾았으면
            cout << vcolor[1] through vcolor[n];	// 출력
        else	// 아직 찾고 있는 중이면
            for (color=1; color<=m; color++){	// 1~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){	// j는 1부터 i노드 이전까지 판단
    	// W[i][j]:연결표시. T or F
        if(W[i][j] && vcolor[i]==vcolor[j]) // i, j 노드가 연결되어있는데 두 칼라가 같다면
        	switch = false;	// 유망하지 않음
        j++;
    }
    return switch;
}

최상위 호출 : m_coloring(0)

 

vcolor[i]는 노드 i의 color을 의미

깊이 우선 탐색(DFS)의 형태가 되고. 함수 호출이 끝났을 때 바로 위로 돌아가는 되추적 방식

 

---

◆ 그래프 색칠하기 문제 (graph coloring) 분석

m개의 색과 n개의 노드라고 할 때, 상태 공간 트리 상의 총 마디 개수는 다음과 같다.

한 레벨 내려갈 때마다 m개의 색깔 선택지가 존재하기 때문!

 

최악의 경우에는, m=2인 경우, 거의 모든 경우를 생성하지 않고는 답이 없다 ㅇㅇ

▲ 이런 경우, 해가 없다는 걸 알 때까지 많은 노드를 생성해야 함.

(v1, v2, v3까지는 쭉 통과고, 거의 v5까지 가고 나서야 안된다는 걸 깨달음)