내가 공부하기 위한 공간 - [알고리즘] 14 - 백트래킹(nQueen, 색칠, 외판원, 0-1배낭)

[백트래킹]

정의 : 해를 찾는 도중, 해가 아니면 되돌아 가서 해를 찾음

• 유명하면 탐색, 아니면 돌아감

 

[n-Queen]

체스에서 퀸에 관한 문제

n*n의 타일에서 n개의 퀸을 배치할 때, 다른 퀸을 잡지 못하도록 배치하는 방법

• 4미만은 해가 없음
• 여러 해 있을 수 있음

<4-Queen>

퀸은 같은 행에 있을 수 없음을 이용, 각 행마다 1개씩

1행부터 차례대로 수행

(1,1)배치 > (2,1)(2,2) 배치 불가 > (2,3)배치 > 3행에 놓을 수 없음 > 백트래킹해서 (2,4)로 되돌아감

…

이와 같이 해가 없으면 백트래킹을 통해 해를 찾음

결과 : (1,2)(2,4)(3,1)(4,3)

• 만약 해를 찾아도 계속 탐색한다면 (1,3)(2,1)(3,4)(4,2)도 찾을 수 있음

<유사코드>

queens( index i ) // i : 행 번호
{ 	index j
	if ( promising(i) )
    { if (i == n ) print "solution"
        else
            for( j=1; j <= n ; j++ )// i+1 행의 열 번호
            { col[i+1] = j 			// col[i] : i번째 행 퀸의 열 번호
                queens(i+1)
            }
    }
}

promising( index i )
{
    index k=1; bool flag = true;
    while( k < i && flag)
    { // 같은 열 검사 및 같은 대각선 검사
        if( col[i] == col[k] || abs( col[i] - col[k] ) == i - k ) flag = false
        k++
    }
    return flag; // true: 유망함, false: 유망하지 않음
}

시간복잡도 : N!, 유망하면 탐색하지 않기때문

 

 

[색칠]

여러 구역이 나눠져 있고, 인접한 구역과 다른 색을 가지도록 색칠할 때, 필요한 색깔 수를 구하는 문제

• 예) 1-2-3 이면 1과 2는 다른 색이어야 하고, 1과 3은 같은 색일 수 있으므로 최소 필요색은 2개
• 최소 필요색의 수는 같지만 색칠 방식이 다를 수 있음

<유사코드>

kColoring(i , c) // i: 정점, c: color
{
    if ( valid(i, c) )
    {
        color[i] ← c
        if (i == n) { return TRUE }
        else
        { 	result ← FALSE
            d ← 1 // d: new color
            while (result == FALSE and d ≤ k)
            { 	result ← kColoring(i+1, d) // i+1: 다음 정점
            	d++
            }
        }
        return result
    }
    else { return FALSE }
}

valid(i, c) // i: 정점, c: color
{
	for j ← 1 to i-1
    {
        // 정점 i , j가 인접하고, 두 정점이 같은 색이면 않됨
        if ( (i, j) ∈ E and color[j] == c ) return FALSE
    }
    return TRUE
}

시간복잡도 : k^n

 

 

[외판원]

그래프에서 각 노드를 1번씩 방문한 후 다시 처음으로 돌아올 때 최소 경로

• 해를 찾으면서 최소 경로를 갱신

1번부터 출발한다 가정

1번에서 갈 수 있는 노드들로 확장

경로 수치를 갱신 후 2번에서 갈 수 있는 노드들 확장

이를 반복, 확장이 안되거나 다시 처음으로 되돌아 갈 수 없으면 해가 없으므로 백트래킹

해를 찾은 이후에도 최소 경로로 갱신하기 위해 끝까지 수행

 

<유사코드>

BacktrackTSP(tour)
{
    if (tour가 완전한 해이면) {
    	if (tour의 거리 < bestSolution의 거리) // 더 짧은 해를 찾았으면
    		bestSolution = (tour, tour의 거리)
    }
    else {
        for (tour를 확장 가능한 각 점 v에 대해서)
        { 	newTour = tour + v // 기존 tour의 뒤에 v를 추가
            if (newTour의 거리 < bestSolution의 거리)
                BacktrackTSP(newTour)
        }
    }
}

시간복잡도 : O(n!)

 

 

[0-1 배낭]

핵심은 bound를 이용해 백트래킹 여부를 확인하는 것

bound : 현재 상태에서 가능한 최대 가치

• 물건을 1개씩 담을때와 안담을 때를 나누면서 현재 무게, 가치, bound를 구함

<예시>

C=50

1, 100 10, 10

2, 120 20, 6

3, 180 30, 6

4, 150 50, 3

물건을 고려하기 전 

0

0

bound : 100+120+20*6=340

• 20은 50-(10+20)

1)물건1을 담았을 때

100

10

bound : 340

2)물건1, 2를 담았을 때

220

30

bound : 340

물건을 더이상 못담음 > 백트래킹

2)물건 1만 담았을 때

100

10

bound : 100+180+10*3=310

3)물건 1, 3담았을 때

280

40

bound:310

백트래킹

3)물건 1만 담았을 때

100

10

bound : 100+40*3=220

바운드가 이미 찾은 해(물건1,2담았을 때)랑 같으므로 더 탐색 X > 백트래킹

1)물건 1을 안담았을 때

0

0

300

2)물건 2만 담았을 때

120

20

300

3)물건 2, 3담았을 때

300

50

300

백트래킹

3)물건 2만 담았을 때

120

20

270

백트래킹

2)물건을 전부 안담았을 때

0

0

180+20*3=240

탐색끝, 결과 : 물건 2와 3을 담았을 때 300, 50

 

<유사코드>

checknode(node v) // best : 지금까지 찾은 가장 좋은 해
{ // value(v) : v 노드에서의 해
    value(v) 계산
    if( value(v) > best ) best = value(v)
    if( promising(v) )
    {
    	for( each child u of v ) checknode(u);
    }
}

promising( node v )
{
    if( v 노드에서 배낭 용량 초과) return false
    bound 계산
    if( bound < best ) return false
    return true
}

시간복잡도 : 2^n, 담냐 안담냐로 나뉘기 때문