Backtracking 백트래킹

✔ Polynomial time 알고리즘을 찾기 어려울 때
✔ 모든 경우의 수를 탐색할 때
✔ DFS 탐색을 이용

용어정리

🟢 백트래킹 : 상태 공간 트리를 탐색하는 것
🟢 promising : 해당 노드에서 더 탐색했을 때 답을 얻을 가능성이 있는 경우
🟢 nonpromising : 더이상 답을 얻을 가능성이 없는 경우
🟢 pruning : nonpromising할 경우 바로 부모노드의 다른 자식노드를 탐색하는 것

n-Queens Problem

• n x n 체스판과 n개의 queen
• n개의 queen을 겹치지 않게 놓는 문제

해결법

• 한 열에는 하나의 queen만 놓을 수 있다.
• 하나의 열에 하나의 queen을 놓았다는 가정 하에, 각 queen이 어떤 행에 놓이는지 확인한다.

def promising(col,i) : #유효성 체크 함수
  if i == 0 : return True
  else :
    k = 1
    switch = True
    while k<i and switch :
      if (col[i] == col[k]) or (abs(col[i] - col[k])) == i - k :
        #같은 행에 있거나 대각선 상에 있다면 nonpromising
        switch = False
      k += 1
    return switch

def queens(col,i,n) :
  if promising(col,i) :
    if i == n :
      for k in range(1,n+1) :
        print(col[k], end=' ')
      print()
    else :
      for j in range(1,n+1) :
        col[i+1] = j
        queens(col,i+1,n)

n = 4
col = [0 for x in range(n+1)]
queens(col,0,n)

Monte Carlo Algorithm

• 백트래킹의 효율성을 체크하기위한 알고리즘
• 주어진 instance에서 시간이 얼마나 걸릴지 대충 예측할 수 있다.

The Sum-of-Subset Problem

• n개의 정수 weight들과 1개의 정수 W
• weight를 조합해서 W가 되는 모든 집합을 찾는 문제

  예를 들어,
  w1 = 1, w2 = 2, w3 = 4, w4 = 5 이고 W=6 일 때
  w1 + w4 = 1 + 5 = 6
  w2 + w3 = 2 + 4 = 6
  따라서 solution은 {w1,w4}, {w2,w3}

def promising(i,weight,total,w,W) :
  return (weight + total) >= W and (weight == W or weight + w[i+1] <= W)

def sumofsubsets(i,weight,total,w,W,include) :
  if promising(i,weight,total,w,W) :
    if weight == W :
      for k in range(1,i+1) :
        print(include[k],end=' ')
      print()
    else :
      include[i+1] = "yes"
      sumofsubsets(i+1, weight+w[i+1], total-w[i+1], w, W, include)
      include[i+1] = "no"
      sumofsubsets(i+1, weight, total-w[i+1], w, W, include)

W = 21
w = [5,10,6,11,16,0]
w.sort()
include = [0 for x in range(len(w))]
sumofsubsets(0,0,sum(w),w,W,include)

Graph Coloring

인접 노드에 각기 다른 색갈을 칠하는 문제

m-coloring problem

• 최대 m개의 다른 색을 가지고
• 인접 노드에 다른 색을 칠하는 문제
• 보통은 NP-complete 문제이지만 아래는 polynomial time에 해결 가능하다.
  - 2-coloring problem
  - 4-coloring in planar graph

def promising(i) :
  switch = True
  j = 1
  while j < i and switch :
    if W[i][j] and vcolor[i] == vcolor[j] : switch = False
    j+=1
  return switch

def m_coloring(i) :
  if promising(i) :
    if i == n :
      for k in range(1,n+1) :
        print(vcolor[k],end=' ')
      print()
    else :
      for color in range(1,m+1) :
        vcolor[i+1] = color
        m_coloring(i+1)

n = 4; m = 3
W = [
  [0,0,0,0,0],
  [0,0,1,1,1],
  [0,1,0,1,0],
  [0,1,1,0,1],
  [0,1,0,1,0]
]
vcolor = [0,0,0,0,0]
m_coloring(0)