Algorithm : Backtracking

LeemHyungJun·2023년 5월 26일
0

Algorithm

목록 보기
7/10

1. Intro

  • Tree 방문 순서의 종류

    위의 그림의 경우 순서 나열
    • preorder
      • 자신->왼쪽->오른쪽
      • 1->2->3->4->5
    • inorder
      • 왼쪽->자신->오른쪽
      • 2->1->4->3->5
    • post order
      • 왼쪽->오른쪽->자신
      • 2->4->5->3->1
    • level order
      • 깊이 순서로 방문
      • 1->2->3->4->5
  • 깊이 우선 검색
    • root가 되는 노드 방문 후 후손 노드를 왼쪽에서 오른쪽으로 방문한다.
    • preorder 순서
  • pseudo code
void dfs(node v)
{
 node u;
    
   visit v; //자신 방문
   for (each child u of v)
   	dfs(u);
}

3. 4-Queens problem

무작정 알고리즘

  • 4x4 의 판으로 구성된 경우 44=2564^4 = 256 가지의 경우를 따져야함

상태공간트리

  • root 부터 leaf까지 모두 탐색 해야하기 때문에 비효율적이다.

되추적(backtracking)

  • 특정 노드를 확인하여 유망한지(promising) 아닌지를 판별하여 더 이상 후손 노드를 탐색하지 않도록 하여 효율성을 높여주는 방식
  • 유망하지 않은 노드들은 pruning 하기 / 유망한 노드만 자손을 검색하기
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);
}

dfs VS. backtracking

  • dfs : 155개의 노드 검색
  • backtracking : 27개의 노드 검색
  • pseudo code
    • 위의 코드는 방문한 후 유망한지 확인하는 것
    • 아래의 코드는 방문하기 전 유망한지 확인하는 것 (더 효율적)
void expand (node v)
{
	node u;
    
    for (each child u of v)
    	if (promising(u))
        	if(there is a solution at u)
            	write the solution;
            else
            	expand(u);
}

4. n-Queen problem

void queens(index i)
{
	if(promising(i))
    	if(i==n)
        	cout<<col[1] through col[n];
        else
        	for(j=1; j<=n; ++j)
            {
            	col[i+1] = j;
                queens(i+1);
            }
}

bool promising(index i)
{
	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;
}
  • 유망한지 여부 파악
    • col[i] == col[k] : 같은 column인지 확인
    • abs(col[i]-col[k]) == i-k) : 같은 대각에 있는지 확인
  • 문제의 분석
    • 유망한 마디의 개수를 정확하게 구하기 위한 방법은 상태공간트리의 갯수를 직접 세어보는 방법밖에 없다.
    • but 이 방법은 알고리즘을 실행해야 알 수 있는 분석방법이기에 진정한 분석방법이 아니다.

5. 부분집합의 합 구하기

  • n 개의 item을 가지고 무게의 합이 W가 되는 부분집합을 찾는 문제
  • 무게가 증가하는 순서로 데이터를 정렬하면 유망한지 아닌지를 빠르게 판단할 수 있다.
  • notation
    • weightweight : 수준 i의 마디까지 포함된 무게의 합
    • totaltotal : 남아있는 아이템의 무게의 총 합
    • 유망하지 않은 경우
      • weight+wi+1>Worweight+total<Wweight + w_{i+1} > W \\ or \\ weight+total<W
void sum_of_subsets(index i, int weight, int total)
{
	if(promising(i))
    	if(weight == W)
        	cout<<include[1] through include[i];
        else
        {
        	include[i+1] = "yes";
            sum_of_subsets(i+1, weight + w[i+1], total-w[i+1]); //w[i+1] 포함
            include[i+1] = "no";
         	sum_of_subsets(i+1, weight , total-w[i+1]); //w[i+1] 불포함
        }
}

bool promising(index i)
	return (weight+total >= W && (weight == W||weight + w[i+1] <=W);

6. 그래프 색칠하기 (graph coloring)

Intro

  • 인접하는 지역의 경우 다른 색으로 칠하는 문제
  • 연결되는 그래프의 경우 다른 색으로 칠하는 문제

평면 그래프 (planer graph)

  • 평면 상에서 edge가 교차되지 않고 그리는 방법

되추적 기법

  • pseudo code
  • 중요 부분
    • if(W[i][j] && vcolor[i] == vcolor[j])
    • 연결되어 있으면서 같은 색깔인지 확인하는 코드
void m_coloring(index i)
{
	if(promising(i))
    	if(i==n)
        	cout<<vcolor[1] through vcolor[n];
        else
        	for(color =1; color<=n; color++)
            {
            	vcolor[i+1] = color;
                m_coloring(i+1);
            }
}

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

0개의 댓글