되추적 기법

23. 되추적 기법#

슬라이드

본문 내용을 요약한 슬라이드를 다운로드할 수 있다.

주요 내용

  • 제약 충족 문제

  • 되추적 기법

  • n-여왕말 문제

  • 그래프 색칠하기

수정할 내용:

  • Kopec 3.3절 The eight queens problem 참고

23.1. 제약 충족 문제#

제약 충족 문제constraint-satisfaction problem(CSP)는 여러 개의 대상 각각에 할당할 값을 특정 도메인(영역)에서 정해진 제약 조건에 따라 선택하는 문제이다.

예를 들어 4-여왕말 문제가 대표적인 제약 충족 문제이다. 여기서 여왕말은 체스판에서 상하좌우, 대각선 등 임의로 움직일 수 있다. 4-여왕말 문제는 1번, 2번, 3번, 4번으로 구분되는 네 개의 여왕말을 4x4 모양의 체스판에서 서로 잡히지 않도록 위치시키는 문제이다. 4-여왕말 문제를 정형화하면 다음과 같다. 대상 여왕말 각각은 변수로 표현된다.

  • 변수: 1번부터 4번까지 이름이 붙은 네 개의 여왕말

  • 도메인: 4x4 모양의 체스판에 포함된 1번 열부터 4번 열

  • 제약 조건: 서로 다른 두 개의 여왕말이 하나의 행, 열, 또는 대각선 상에 위치하지 않음

아래 그림은 4개의 여왕말이 앞서 언급된 제약 조건을 만족시키거나 못하는 경우를 함께 보여준다.

23.2. 되추적 기법#

되추적 기법은 제약 충족 문제를 해결하는 기법이며 백트래킹backtracking으로 불리기도 한다. 많은 제약 충족 문제가 제약 조건만 서로 다를 뿐 동일한 되추적 알고리즘으로 해결되기도 한다. 여기서는 두 개의 문제를 이용하여 되추적 기법의 활용법을 설명한다.

되추적 기법 이해에 필요한 개념은 다음과 같다.

  • 깊이 우선 탐색

  • 상태 공간 트리

  • 노드의 유망성

  • 가지치기

깊이 우선 탐색

깊이 우선 탐색depth-first-search(DFS)은 (루트 지정) 트리(rooted tree)를 대상으로 하는 모든 가능성을 탐색하는 일종의 완전 탐색brute force기법이다. 깊이 우선 탐색은 트리에 포함된 모든 노드를 아래 과정을 이용하여 탐색한다.

  • 루트 노드에서 시작해서 갈 수 있는 한 가장 왼쪽 자식 노드로 탐색 진행

  • 잎 노드에 다달한 경우 탐색 대상이 될 수 있는 자식 노드를 갖는 가장 가까운 조상 노드로 이동해서 깊이 우선 탐색 진행. 단, 한 번 탐색한 자식 노드는 무시.

위 과정을 실행하다가 더 이상 탐색 대상이 되는 노드가 존재하지 않는 경우 탐색을 중지한다. 아래 그림은 루트 노드에서 시작하여 깊이 우선 탐색의 대상이 되는 노드들의 순서를 보여준다.

상태 공간 트리

상태 공간 트리state space tree는 (대상) 변수가 가질 수 있는 모든 값으로 구성된 트리이다. 아래에 보여지는 트리는 4x4로 이루어진 체스판에 네 개의 체스 여왕말을 놓을 수 있는 위치를 노드로 표현한 상태 공간 트리이다.

  • 루트: 출발 노드이며 여왕말의 위치와는 무관함.

  • 깊이 \(k\)의 노드: \(k\) 번째 여왕말이 놓일 수 있는 열 위치

여기서 깊이는 노드가 루트로부터의 경로의 길이를 가리킨다.

노드의 유망성

노드가 지정된 제약 조건을 만족시키는 경우 유망하다promissing고 말한다. 예를 들어, 아래 그림에서 첫째 여왕말의 위치에 따라 둘째 여왕말이 놓일 수 있는 위치에 해당하는 노드의 유망성이 결정된다. 둘째 여왕말에 대해 1번, 2번 칸에 해당하는 노드는 유망하지 않다.

가지치기

가지치기pruning특정 노드에서 시작되는 가지를 제거하는 과정을 가리킨다. 아래 그림은 4x4로 이루어진 체스판에 네 개의 여왕말을 놓을 수 있는 위치를 노드로 표현한 상태 공간 트리에서 유망하지 않은 노드를 가지치기한 결과를 보여준다.

4-여왕말 문제 되추적 알고리즘

4 개의 여왕말을 서로 공격하지 못하도록 위치시키는 4-여왕말 문제를 해결하는 되추적 알고리즘은 상태 공간 트리를 대상으로 깊이 우선 탐색, 노드의 유망성 판단, 가지치기를 아래 과정에 따라 반복 실행한다.

  • 4x4로 이루어진 체스판에 네 개의 체스 여왕말을 놓을 수 있는 위치를 노드로 표현한 상태 공간 트리의 루트에서부터 깊이 우선 탐색 실행

  • 탐색 과정에서 유망하지 않은 노드를 만나면 가지치기 실행 후 깊이 우선 탐색 대상이 될 수 있는 자식 노드를 갖는 조상 노드로 되돌아가서, 즉 되추적하여 그곳에서부터 깊이 우선 탐색 실행. 단, 이미 탐색한 자식 노드는 제외

  • 탐색이 더 이상 진행할 수 없는 경우 알고리즘 종료

아래 그림은 4-여왕말 문제에 대해 되추적 알고리즘을 적용하는 과정을 보여준다.

유망하지 않은 노드에서 가지치기를 하는 되추적 알고리즘은 그렇지 않은 일반 깊이 우선 탐색에 비해 훨씬 적은 수의 노드를 대상으로 탐색한다. 예를 들어 4-여왕말 문제를 일반 깊이 우선 탐색으로 해결하고자 할 경우 155 개의 노드를 탐색해야 하지만 되추적 알고리즘을 적용하면 27개의 노드만 탐색하면 된다.

23.3. n-여왕말 문제#

4-여왕말 문제를 일반화한 n-여왕말 문제를 해결하는 되추적 알고리즘 구현한다. n-여왕말 문제를 정의하는 변수, 도메인, 제약 조건은 다음과 같다.

  • (대상) 변수: 1번부터 n번까지 이름이 붙은 n 개의 여왕말

  • 도메인: nxn 모양의 체스판에 포함된 1번부터 n번 열

  • 제약 조건: 서로 다른 두 개의 여왕말이 하나의 행, 열, 또는 대각선 상에 위치하지 않음

예를 들어 8-여왕말 문제를 정의하는 변수와 도메인은 다음과 같다. 8개의 여왕말 모두 1열부터 8열 어딘가에 위치할 수 있다. 단, 그 중에서 제약 조건을 만족하는 열을 찾아야 한다.

from collections import defaultdict

# 변수: 네 개의 여왕말의 번호, 즉, 1, 2, ..., 8
variables = range(1, 9)

# 도메인: 각각의 여왕말이 자리잡을 수 있는 가능한 모든 열의 위치. 
domains = defaultdict(list)

columns = range(1, 9)
for var in variables:
    domains[var] = columns

domains

defaultdict(list,
            {1: range(1, 9),
             2: range(1, 9),
             3: range(1, 9),
             4: range(1, 9),
             5: range(1, 9),
             6: range(1, 9),
             7: range(1, 9),
             8: range(1, 9)})

유망성 판단

되추적 기법을 이용하여 1번 여왕말부터 차례대로 위치시킬 것이다. 따라서 여왕말을 특정 열에 위치시킬 때마다 그때까지 자리가 정해진 여왕말들과의 제약 조건이 성립함을 보여야 한다. 즉, 새로운 여왕말을 위치시킬 때마다 해당 여왕말의 유망성을 확인해야 한다.

이를 위해 되추적 기법이 진행되는 동안 자리를 잡은 여왕말들의 정보를 저정해야 한다. 여기서는 여왕말 번호와 해당 여왕말의 위치한 열의 번호를 각각 키와 값으로 사용하는 사전을 이용한다. 예를 들어 4번 여왕말까지 위치시킨 경우 아래 assignment 변수가 가리키는 사전에 네 개의 여왕말의 위치 정보가 담겨 있다.

assignment = {1:1,
              2:5,
              3:8,
              4:6}

위치가 이미 정해진 여왕말들을 대상으로 다음 세 개의 제약 조건이 성립함을 확인한다.

  • 동일한 행에 위치하지 않기: 각각의 여왕말이 다른 행에 위치되도록 하기에 알고리즘이 작동하기에 자연스럽게 처리됨.

  • 동일한 열에 위치하지 않기: 서로 다른 키에 대해 동일한 값이 사용되지 않도록 해야 함.

  • 동일한 대각선 상에 위치하지 않기: 두 개의 여왕말 q1, q2가 동일한 대각선 상에 위치하려면 행과 열의 차이의 절댓값이 같아야 함(아래 그림 참고. 아래 식에서 예를 들어 q1r과 q1c는 각각 q1이 위치한 행과 열의 좌표를 가리킴.

    abs(q1r - q2r) == abs(q1c - q2c)

아래 promissing_queens() 함수가 이미 자리를 차지한 여왕말들을 대상으로 세 개의 제약 조건이 만족하는지 여부를 확인한다.

def promissing_queens(assignment=defaultdict(int)):

    # q1: 모든 여왕말 대상으로 유망성 확인
    for q1r, q1c in assignment.items(): # q1의 행과 열

        # q2 = 아랫쪽에 자리한 여왕말들과 함께 제약 조건 성립 여부 확인
        # q1r과 q2r은 자연스럽게 다름
        for q2r in range(q1r + 1, len(assignment) + 1): 
            q2c = assignment[q2r]
            if q1c == q2c:                       # 동일 열에 위치?
                return False
            if abs(q1r - q2r) == abs(q1c - q2c): # 동일 대각선상에 위치?
                return False 

    # 모든 변수에 대해 제약조건 만족됨
    return True

되추적 함수 구현

아래 backtracking_search_queens() 함수는 n-여왕말 문제를 되추적 기법으로 해결한다. 함수 정의에 사용된 변수들의 기능은 다음과 같다.

  • num_queens: 여왕말의 개수

  • variables: 여왕말 번호

  • domains: 각 여왕말의 도메인(영역). 여기서는 모두 1부터 num_queens 까지의 번호 사용.

  • assignment 매개변수: 되추적 과정에서 이미 자리를 차지한 여왕말들의 위치 정보를 담은 사전 객체

  • unassigned: 아직까지 자리를 잡지 못한 여왕말들의 번호로 구성된 리스트

  • first: unassigned 에 포함된 여왕말 중에서 가장 낮은 번호의 여왕말. 즉, 이제 위치시켜야할 여왕말 번호.

함수 본체에 사용되는 for 반복문은 새로운 여왕말을 위치시키기 위해 모든 열을 대상으로 되추적 기법을 아래와 같이 적용한다.

  • 유망성이 확인되면 되추적 기법을 재귀적으로 적용

  • 유망성이 확인되지 않으면 바로 재귀 적용 중지 후 가장 가까운 조상 노드의 형제 노드로 이동하여 되추적 기법 재귀 적용

def backtracking_search_queens(num_queens, assignment=defaultdict(int)):
    
    # 변수
    variables = range(1, num_queens+1)
    
    # 도메인: 각각의 여왕말이 위치할 수 있는 칸
    domains = defaultdict(list)

    columns = range(1, num_queens+1)
    for var in variables:
        domains[var] = columns
    
    # 재귀 종료 조건: 모든 변수에 대한 값이 지정된 경우
    if len(assignment) == len(variables):
        return assignment
    
    # 재귀 실행: 아직 자리 잡지 못한 여왕말이 존재하는 경우
    unassigned = [v for v in variables if v not in assignment]
    first = unassigned[0] # 다음 대상 여왕말
    
    # first 여왕말 위치시키기. 재귀 적용
    for value in domains[first]:
        # 기존의 assignment를 보호하기 위해 복사본을 활용함.
        # 되추적이 발생할 때 이전 할당값을 기억해 두기 위해서임.
        local_assignment = assignment.copy()
        local_assignment[first] = value

        # local_assignment 값이 유망하면 되추적 기법 재귀 적용
        # 즉, 다음 여왕말 대상으로 되추적 기법 적용
        if promissing_queens(local_assignment):
            result = backtracking_search_queens(num_queens, local_assignment)

            # 모든 여왕말을 위치시켰을 때 여왕말들의 정보 반환
            if result is not None:
                return result

    # 유망성 확인에 실패한 경우 재귀 종료. 즉 가지치기 실행.
    return None

4-여왕말 문제와 8-여왕말 문제의 해결책은 다음과 같다.

backtracking_search_queens(4)

defaultdict(int, {1: 2, 2: 4, 3: 1, 4: 3})

backtracking_search_queens(8)

defaultdict(int, {1: 1, 2: 5, 3: 8, 4: 6, 5: 3, 6: 7, 7: 2, 8: 4})

n-여왕말 문제 되추적 알고리즘의 시간 복잡도

n 개의 여왕말이 주어졌을 때 상태 공간 트리에 포함된 노드의 수는 다음과 같다.

\[ 1 + n + n^2 + n^3 + \cdots + n^n = \frac{n^{n+1}-1}{n-1} \]

따라서 되추적 알고리즘이 탐색해야 하는 노드 수는 경우마다 다를 수 있지만 최대 n의 지수승 만큼 많은 수의 노드를 탐색해야 할 수도 있다. 하지만 이보다 더 효율적인 알고리즘은 아직 알려지지 않았다.

23.4. m-색칠 문제와 4색 정리#

23.4.1. m-색칠 문제#

m-색칠m-coloring 문제는 최대 m 개의 색color을 이용하여 무방향 그래프의 서로 인접한 노드가 서로 다른 색을 갖는다는 조건이 만족되도록 색칠하는 문제이다. 예를 들어 아래 무방향 그래프에 대해서는 최소 세 종류의 색을 사용해야 색칠 조건이 만족될 수 있음을 보여준다.

m-색칠 문제는 지도를 색칠할 때 유용하게 활용된다.

이유는 지도와 평면 그래프가 서로 일대일 대응되기 때문이다. 평면 그래프는 서로 교차하는 간선이 없는 무방향 그래프이다. 예를 들어 아래 왼쪽 지도와 오른쪽 평면 그래프는 서로 일대일 대응된다.

  • 노드: 지도에 사용된 국가, 지역 등의 영역

  • 간선: 서로 인접한 두 영역 연결

m-색칠 문제를 알고리즘을 되추적 기법으로 해결할 수 있다. 설명을 위해 먼저 앞서 언급한 그래프를 대상으로 3-색칠 문제에 되추적 기법을 적용하는 과정을 살펴 본다.

아래 그래프는 깊이 우선 탐색에 노드의 유망성과 가지치기를 적용한 결과를 보여준다. 단, 1, 2, 3은 각각 빨강, 파랑, 갈색을 가리킨다.

m-색칠 문제를 해결하는 되추적 알고리즘 구현하려 하기 위해 먼저 m-색칠 문제를 정의하는 변수, 도메인, 제약 조건을 확인하면 다음과 같다.

  • (대상) 변수: 1번부터 n번까지 이름이 붙은 n 개의 노드

  • 도메인: 1번부터 m번까지 이름이 붙은 m 종류의 색

  • 제약 조건: 간선으로 연결된 이웃 노드는 서로 다른 색을 가져야 함.

예를 들어 4 개의 노드로 구성된 평면 그래프에 대한 3-색 문제를 정의하는 변수와 도메인은 다음과 같다. 각각의 노드에 동일하게 빨강(1), 파랑(2), 갈색(3) 어느 색도 취할 수 있다. 단, 제약 조건을 만족시켜야 한다.

from collections import defaultdict

# 변수: 네 노드의 번호, 즉, 1, 2, 3, 4
variables = [1, 2, 3, 4]

# 도메인: 각각의 노드에 칠할 수 있는 가능한 모든 색상
# 3-색칠하기: 1(빨강), 2(파랑), 3(갈색)
domains = defaultdict(list)
colors = [1, 2, 3]

for var in variables:
    domains[var] = colors

domains

defaultdict(list, {1: [1, 2, 3], 2: [1, 2, 3], 3: [1, 2, 3], 4: [1, 2, 3]})

유망성 판단

새로운 노드의 색을 지정할 때 두 해당 노드와 간선으로 연결된 노드들의 색상을 확인해야 한다. 따라서 노드의 유망성을 확인할 때 간선에 대한 정보와 그때까지 색칠해진 노드의 색 정보를 알아야 한다.

아래 promissing_colors() 함수는 평면 그래프의 간선 정보가 주어졌을 때 새로운 노드에 할당된 색이 기존에 지정된 노드들의 색과 함께 제약 조건을 만족시키는지 여부를 판단한다.

  • variable: 새롭게 색이 할당된 노드

  • constraints: 평면 그래프의 간선 정보를 담은 사전

  • assigment: 되추적 기법 적용 기간동안 색이 할당된 노드들의 정보를 담은 사전

def promissing_colors(variable: int, constraints=defaultdict(list), assignment=defaultdict(int)):
    """새로운 노드인 variable에 색을 할당할 때 
    간선으로 연결된 이웃 노드와의 색이 달라야 한다는
    제약조건을 assignment가 만족하는지 여부 확인
    """

    for var in constraints[variable]:
        if (var in assignment) and (assignment[var] == assignment[variable]):
            return False

    return True

예를 들어 아래 평면 그래프의 간선 정보는 다음과 같다.

# 각 노드에 대한 이웃 노드의 리스트
constraints = {
    1 : [2, 3, 4],
    2 : [1, 3],
    3 : [1, 2, 4],
    4 : [1, 3]
}

되추적 함수 구현

아래 backtracking_search_colors() 함수는 m-색칠 문제를 되추적 기법으로 해결한다. 함수 정의에 사용된 변수들의 기능은 다음과 같다.

  • num_nodes: 노드의 수

  • num_colors: 사용 가능한 색의 수

  • constraints: 평면 그래프의 간선 정보를 담은 사전

  • assigment: 되추적 기법 적용 기간동안 색이 할당된 노드들의 정보를 담은 사전

함수 본체에 사용되는 for 반복문은 새로운 노드의 색을 지정하기 위해 사용 가능한 모든 색을 대상으로 되추적 기법을 아래와 같이 적용한다.

  • 유망성이 확인되면 되추적 기법을 재귀적으로 적용

  • 유망성이 확인되지 않으면 바로 재귀 적용 중지 후 가장 가까운 조상 노드의 형제 노드로 이동하여 되추적 기법 재귀 적용

def backtracking_search_colors(num_nodes, num_colors, constraints=defaultdict(list), assignment=defaultdict(int)):
    """assignment: 각각의 변수를 키로 사용하고 키값은 해당 변수에 할당될 값"""

    # 변수
    variables = range(1, num_nodes+1)

    # 도메인: 각각의 노드에 칠할 수 있는 가능한 모든 색상
    domains = defaultdict(list)
    colors = range(1, num_colors+1)

    for var in variables:
        domains[var] = colors
        
    # 재귀 종료 조건: 모든 변수에 대한 값이 지정된 경우
    if len(assignment) == len(variables):
        return assignment
    
    # 재귀 실행: 아직 색이 지정되지 않은 노드가 존재하는 경우
    unassigned = [v for v in variables if v not in assignment]
    first = unassigned[0] # 다음 대상 노드
    
    # first 노드 색칠하기. 재귀 적용
    for value in domains[first]:
        # 주의: 기존의 assignment를 보호하기 위해 복사본 활용
        # 되추적이 발생할 때 이전 할당값을 기억해 두기 위해서임.
        local_assignment = assignment.copy()
        local_assignment[first] = value
        
        # local_assignment 값이 유망하면 재귀 호출을 사용하여 변수 할당 이어감.
        if promissing_colors(first, constraints, local_assignment):
            result = backtracking_search_colors(num_nodes, num_colors, constraints, local_assignment)

            # 모든 노드의 색이 지정되었을 때 해당 정보 반환
            if result is not None:
                return result

    # 유망성 확인에 실패한 경우 재귀 종료. 즉 가지치기 실행.
    return None

앞서 언급한 간선 정보를 가지며 4개의 노드를 사용하는 평면 그래프를 세 가지 색으로 칠하는 방법은 다음과 같다.

backtracking_search_colors(4, 3, constraints)

defaultdict(int, {1: 1, 2: 2, 3: 3, 4: 2})

하지만 앞서 설명한 대로 두 가지 색으로는 칠할 수 없다. 즉, 아래 함수의 실행값이 None 이다.

if not backtracking_search_colors(4, 2, constraints):
    print("두 가지 색으로 색칠 제약조건 충족 불가능")

두 가지 색으로 색칠 제약조건 충족 불가능

m-색칠 문제 되추적 알고리즘의 시간 복잡도

n 개의 노드를 m 개의 색으로 칠해야 하는 문제의 상태 공간 트리의 노드의 수는 다음과 같다.

\[ 1 + m + m^2 + m^3 + \cdots + m^n = \frac{m^{n+1}-1}{m-1} \]

따라서 되추적 알고리즘이 최대 m과 n의 지승 만큼 많은 수의 노드를 탐색해야 할 수도 있다. 하지만 이보다 더 효율적인 알고리즘은 아직 알려지지 않았다.

23.4.2. 4색 정리#

1852년에 영국인 프랜시스 구쓰리Francis Guthrie가 영국 지도를 작성할 때 인접한 두 개의 주를 서로 다른 색으로 칠하기 위해 필요한 색이 최소 4개면 된다는 4색 정리를 주장하였다. 하지만 이 4색 정리가 증명되기까지 124년이 걸렸다.

최초의 증명은 1976년에 아펠K. Appel과 하켄W. Haken이 제시하였다. 두 사람의 증명이 500 여쪽 논문으로 제시되었는데 일부 내용은 컴퓨터 프로그램을 사용하도록 되어 있다. 그런데 증명에 사용된 컴퓨터 프로그램에 대한 신뢰성 때문에 오랜 시간동안 100% 인정받지 못하다가 2005년에 곤티에G. Gonthier에 의해 증명의 완전성이 검증되었다.

23.5. 연습문제#

  1. (실습) 되추적 기법

Contents