Algorithm_09

Stack

계산기 1

• 문자열로 된 계산식이 주어질 때, 스택을 이용하여 이 계산식의 값을 계산할 수 있다.
  • 중위 표기법(infix notation)
    • 연산자를 피연산자의 가운데 표기하는 방법
  • 후위 효기법(postfix notation)
    • 연산자를 피연산자 뒤에 표기하는 방법

백트래킹

• 백트래킹 기법은 해를 찾는 도중에 막히면 되돌아가서 다시 해를 찾아 가는 기법이다.
• 최적화 문제와 결정 문제를 해결할 수 있다.
• 결정 문제 : 문제의 조건을 만족하는 해가 존재하는지의 여부를 답하는 문제
  • 미로 찾기
  • n-Queen 문제
  • Map coloring
  • 부분 집합의 합 문제 등

백트랙킹과 깊이 우선 탐색과의 차이

• 어떤 노드에서 출발하는 경로가 해결책으로 이어질 것 같지 않으면 더 이상 경로를 따라가지 않음으로써 시도의 횟수를 줄임.
• 백트래킹은 깊이우선탐색과 다르게 모든 경로를 추적하지 않고 불필요한 경로를 조기에 차단
• 깊이 우선 탐색은 소요시간 多
• 백트래킹 알고리즘을 적용하면 일반적으로 경우의 수가 줄어들지만 이 역시 최악의 경우에는 여전히 지수함수 시간을 요하므로 처리 불가능

백트래킹 기법

• 어떤 노드의 유망성을 점검한 후에 유망하지 않다고 결정되면 그 노드의 부모로 되돌아가 다음 자식 노드로 감
• 어떤 노드를 방문하였을 때 그 노드를 포함한 경로가 해답이 될 수 없으면 그 노드는 유망하지 않다고 하며, 반대로 해답의 가능성이 있으면 유망하다고 한다
• 가지치기 : 유망하지 않는 노드가 포함되는 경로는 더 이상 고려하지 않는다

1. 상태 공간 트리의 깊이 우선 검색을 실시
2. 각 노드가 유망한지를 점검한다.
3. 만일 그 노드가 유망하지 않으면, 그 노드의 부모 노드로 돌아가서 검색을 계속

미로찾기

• 이동 방향을 4방향으로 제한한다.
• 스택을 이용해 갈 곳이 없으면 다시 뒤로 돌아간다.
• 스택을 이용해 다시 경로를 찾는다
• Ex) 일반 백트래킹 알고리즘

  def checknode(v): # node
      if promising(v):
          if there is a solution at v:
              write the solution
          else:
              for u in each child of v:
                  checknode(u)

부분집합

• 어떤 집합의 공집합과 자기자신을 포함한 모든 부분집합을 powerset이라고 하며 구하고자 하는 어떤 집합의 원소 개수가 n일 경우 부분집합의 개수는 2^n개 이다.
• 만드는 법

  1. 일반적인 백트래킹 접근 방법 이용
  2. n개의 원소가 들어있는 집합의 2^n개의 부분집합을 만들 때는, true 또는 false 값을 가지는 항목들로 구성된 n개의 배열을 만드는 방법을 이용
  3. 여기서 배열의 i번째 항목은 i번째의 원소가 부분집합의 값인지 아닌지를 나타내는 값 이다.

• Ex)

def backtack(a, k, input):
	global MAXCANDIDATES
    c = [0] * MAXCANDIDATES
    
    if k == input:
    	process_solution(a,k) # 답이면 원하는 작업
    else:
    	k += 1
    	ncandidates = construct_candidates(a, k, input, c)
        for i in range(ncandidates):
        	a[k] = c[i]
            backtrack(a, k, input)
def construct_candidates(a, k, input, c):
	c[0] = True
    c[1] = False
    return 2
    
MAXCANDIDATES= 2
NMAX = 4
a = [0] * NMAX
backtrack(a, 0, 3)