Algorithm - Backtracking - sum of subsets & graph coloring

부분집합의 합 구하기 문제

• n개의 item을 이용하여 item들의 무게 합이 W가 되는 부분집합을 구하는 문제
  

• Weight가 증가하는 순으로 데이터를 정렬하면 데이터의 유망성을 쉽게 판단할 수 있다.

• wi를 넣을 수 없다면 그 이후로는 고려할 필요가 없다.

• weight : 수준 i의 마디까지 포함된 무게의 합

• total : 남아있는 아이템의 무게 총합

pseudo code

python

def promising(i, weight, total):
    return (weight + total >= W) and (weight == W or weight + w[i+1] <= W)
# return에 들어가있는 조건문과 같이 검사하여 weight의 합으로 W를 만들수 있는지에 대한 여부를 판단합니다.


def s_s(i, weight, total, include):
    global node
    if promising(i, weight, total):
        node += 2  # 유망하다고 판단되면 새로운 노드 2개를 만들어 유망성을 점검합니다.
        if weight == W:
            node -= 2
            # weight == W를 만족하면 해를 찾은 경우이지만 promising조건에 True를 반환하기 때문에
            # 추가되지 않은 node 2개를 차감합니다.
            print("W = ", W, "를 만족시키는 해 :", include)
            # W를 표현하기 위해 사용된 weight의 포함 여부를 출력합니다.
        else:
            # 다음 가중치를 포함시키거나 포함시키지 않고 함수를 재귀적으로 호출하며
            # weight의 요소의 합이 W를 만족시키는지 확인합니다.
            include[i+1] = 1
            s_s(i+1,weight+w[i+1], total - w[i+1], include)
            include[i+1] = 0
            s_s(i+1, weight, total - w[i+1], include)

graph coloring

• 지도에서 인접하는 지역을 구분하기 위해 색깔을 할당하는 문제
• 지도의 구역을 노드로 표현하면 그래프로 나타낼 수 있다.

planar graph

• 평면 상에서 이음선들이 서로 엇갈리지 않게 그릴수 있는 그래프
  
• 어떠한 planar graph라도 4가지 색깔로 표현할 수 있다.
• 완전 그래프, 이분 그래프는 대표적인 non-planar graph이다.

m-coloring 문제

• m가지 색깔을 가지고 그래프를 색칠하는 문제

pseudo code

분석

• 상태공간트리상의 마디의 총수
  

• 최악의 경우로는 m=2일 때 거의 모든 경우를 생성한 후에 답이 없다는 것을 알아내는 경우다.

python

def color(i, vcolor):
    global node2
    # 유망하다고 판단되면 m개 만큼의 노드를 생성한 후 유망성 및 결과를 검증합니다.
    if promising2(i, vcolor):
        node2 += m
        if i == n - 1:
            node2 -= m
            print(vcolor)
            # 모든 노드를 검사한 후에는 추가적인 node가 필요없으므로
            # 추가된 node를 차감해줍니다.
        else:
            for c in range(1, m + 1):
                vcolor[i + 1] = c
                color(i + 1, vcolor)
        # n번 노드의 색깔의 교체해가며 유망성 및 결과를 확인합니다.


def promising2(i, vcolor):
    switch = True
    j = 0
    # 연결되어 있으면서 색깔이 같은 노드가 있는 경우를 유망하지 않다고 판단하며
    # 그 외의 경우는 유망하다고 판단하여 True/False값을 반환합니다.
    while j < i and switch:
        if W[i][j] and vcolor[i] == vcolor[j]:
            switch = False
        j += 1
    return switch