Backtracking

Backtracking

greedy처럼 일련의 집합을 만들어 하나씩 답에 만족시키는 것을 만든다.

greedy와 다르게, 조건에 맞지 않는다면 번복할 수 있다. 되돌아갈 수 있다.

- used to solve problems in which a sequence of objects is chosen from a specified set so that the sequence satisfies some criterion.

- after each choice has been made and added to a partial solution, it can be retracted from the solution set later by backtracking

---

5.1 The Backtracking Technique

N queens problem

->체스판에 N개의 queen 말을 놓는 문제.

sequence: n positions where the queens are placed

set: n2 possible positions on the chessboard

criterion: no two queens threaten each other

 

ex) 4 queens

- Number of all possible configurations C(16,4) = 1820

- Since no two queens can be in the same row, we can eliminate some possibilities: 4 × 4 × 4 × 4 = 256

- State representation : Queen in the i-th row is in the j-th column

여기서 백트래킹이니까, 1,1들어간뒤 2,1들어갈 때 backtrack한다.

 

backtracking의 the State space Tree - pruned tree

(1) NonPromising/ Promising

NonPromising Node:

- a node that cannot possibly lead to a solution 

(1,2) 과 (2,2) 인 경우.

 

Promising Node:

- a node that is not nonpromising

 

Backtracking

- do a depth-first search of a state space tree checking whether each node is promising

- if nonpromising, backtrack to the node’s parent and try other path

-> Backtracking can be implemented by a recursive depth-first search algorithm.

 

-전형적인 backtracking 알고리즘 형태

public static void checknode(node v)
{
  node u;

  if (promising(v))
	if (there is a solution at v)
		write the solution
	else
		for (each child u of v)
			checknode(u) ;
}

promising 한지 판단하고, 해라면 해를 출력 아니라면 아래child 검사

* nonpromising 한 경우에 recursive 함수형태에서는 자연스레 backtracking된다.

 

N queens pruned tree / code

1, pruned tree

nonpromising인 경우 backtrack되어 내려가지 않는 상태 표시한 tree

 

2. N-queens problem의 promising() 조건 생각하기

 

1. 같은 column 아니어야 한다.

!( col(i) == col(k) )

2. 같은 diagonal 아니어야 한다.

| col(i) - col(k) | == i-k (i>k)

 

3. code

public static void queens( index i) {
  index j;
  if (promising(i))
    if (i==n)
      system.out.print ( col[1] .. col[n] )
    else
      for (j=1; j<=n; j++) {
      col[i+1] = j;
      queens(i+1) ;
}
}

public static boolean promising (index i)
{
  index k; boolean switch ;
  
  k = 1;
  switch = true ;
  while (k<i && switch) {
    if (col[i]==col[k]) || abs(col[i]-col[k]) == i-k)
      switch = false ;
      k++;
  }
	return switch ;
}

---

5.5 Graph Coloring

 

The m-coloring problem

problem of finding all ways to color an undirected graph

using at most m different colors, so that no two adjacent vertices are the same color

인접한 vertex들이 서로 다른 색깔인 그래프.

planar graph로 바꾸어 표현될 수 있다.

 

m- color pruned tree / code

1.pruned tree

backtracking으로 promising한 node들만 그린 pruned state space tree.

 

2. promising

    if ( W[i][j] && vcolor[i] == vcolor[j] )

(1) edge가 있는지 없는지

(2) edge가 있는 경우, 색깔이 같은지

 

3.code

public static void m_coloring(index i)
{
  int color ;

  if (promising(i) )
  if (i==n)
    system.out.print( vcolor[1] .. vcolor[n] )
  else
    for (color=1; color<= m; color++) {
      vcolor[i+1] = color ;
      m_coloring(i+1) ;
    }
}

public static boolean promising(index i)
{
  index j ; bool switch ;
  switch = true;
  j = 1 ;
  while ( j < i && switch ) {
    if ( W[i][j] && vcolor[i] == vcolor[j] )
      switch = false ;
      j++ ;
  }
return switch ;
}

---

5.7 The 0-1 Knapsack Problem

위 두 problem은 decision problem이다.

배낭 문제는 optimization문제이기에 best solution을 찾는 것이 필요하다.

 

public static void checknode (node v)
{
  node u;
  if (value(v) is better than best)
  	best = value(v) ;
    
  if (promising(v))
    for (each child u of v)
    	checknode(u) ;
}

 

지금보다 더 좋으면, 보관하자

traveling 과 다르게, leafnode까지 안가도 해를 구할 수 있다.

 

 

State of the knapsack

(1) Current profit (지금까지 담은 profit의 합)

(2) Current weight

(3) The upper bound on the maximum profit (branch and bound 

현재 상태에서 담을 수 있는 최대 값

-> the maximum profit that can be obtained by allowing fraction of an item in the knapsack

-> That is, the maximum profit that can be obtained for the fractional knapsack problem

 

pruned tree

(1) profit / weight의 오름차순으로 item정렬

(2) The upper bound : $115. (W=16을 꽉 채웠을 때 넣을 수 있는 profit)

(3) current profit이 upperbound보다 overweight이 된 경우, backtrack한다.

그림 (1. current profit, 2. current weight, 3. upper bound)

 

code

public static void knapsack(index i, int profit, int weight)
{
  if ( weight <= W && profit > maxProfit ) {
    maxProfit = profit ;
    numBest = 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);
  }
}

index i : i를 담는 경우.

 

첫번째 if : best update

(1) maxProfit update

(2) numBest = i

0~i까지 담은 상태. i값을 저장

(3) bestSet = include

bool include집합을 bestSet에 저장

*include 집합 : [0,1,0,1,0,1] 처럼 담는 원소를 1로 표현한 bool 집합

두번째 if : 담는 경우, 담지 않는 경우 구분해 recursion한다.

public static 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 ;
  }
}

if : overweight 그리고 같다면 false

같은 경우 expand할 여지가 없기 때문에 false

 

else : i+1 ~ n의 item으로 W-weight값을 채운다

(1) while문 : 온전히 담을 수 있는 경우

(2) if문

fractional으로 W 꽉 채워서 담는다

(3)

return값은 maxProfit보다 현재bound가 더 클 때 반환한다.