내가 공부하기 위한 공간 - [알고리즘] 15 - 백트래킹(부분집합, 해밀튼회로)

[부분집합]

각 물건의 가중치에 대해 n개의 물건이 있을 때, 이들의 부분집합을 구성하여 가중치 합이 W인 것을 모두 구하는 문제

 

W=60, 물건들이 (10, 20, 30, 40)이라면 부분집합 (2,4)와 (1,2,3)은 가중치의 합이 60이 됨

1. 각 물건을 오름차순으로 정렬
2. 각 물건을 부분집합에 포함하거나, 포함하지 않도록 상태공간트리를 만들어 나감
3. 가중치 합이 W가 아니면 하위 노드로 확장하고, 초과하면 백트래킹
4. 가중치 합이 W가 되는 모든 노드는 해가 됨

<유사코드>

function subsetSum(S, n, currentSum, index, subset):
    if currentSum == targetSum:
        print(subset)
        return

    if index == n or currentSum > targetSum:
        return

    // include S[index]
    subset.append(S[index])
    subsetSum(S, n, currentSum + S[index], index + 1, subset)
    subset.pop()

    // exclude S[index]
    subsetSum(S, n, currentSum, index + 1, subset)

시간복잡도 : 2^n, 각 물건이 포함되냐 안되냐 2가지로 나뉘기 때문

 

[해밀튼 회로]

연결된 비방향성 그래프에서 어떤 한 정점에서 출발하여 그래프 상의 모든 정점을 단 한번만 경우하여 다시 출발한 정점으로 돌아오는 경로

 

해밀튼 회로 문제는 주어진 그래프에 해밀튼 회로가 존재하는지를 찾는 것

 

백트래킹으로 이 문제를 해결하려면 상태공간트리를 구성할 때 다음 사항을 고려

• 경로상의 i 번째 정점은 (i-1) 번째 정점과 인접

• 마지막 n 번째 정점은 첫번째 정점과 인접

• 경로상의 i 번째 정점은 이전의 정점들과 중복되어서는 안됨(모든 정점은 단 한번만 지나야하

기 때문)

function hamiltonian(graph, path, position):
    if position == number_of_vertices:
        if graph[path[position - 1]][path[0]] == 1:
            print("Hamiltonian Circuit found:", path + [path[0]])
        return

    for v in range(1, number_of_vertices):
        if isSafe(v, graph, path, position):
            path[position] = v
            hamiltonian(graph, path, position + 1)
            path[position] = -1  // backtrack

function isSafe(v, graph, path, position):
    if graph[path[position - 1]][v] == 0:
        return False
    if v in path:
        return False
    return True

시간복잡도 : n!