21-03-03 알고리즘 기초강의(3)

해밀턴 경로 문제

G = (V, E)가 연결된 무방향 그래프일 때 한 정점에서 출발하여 그래프의 모든 정점을 한 번씩만 방문하고 출발점으로 되돌아오는 경로
모든 간선을 한 번씩 방문하는 오일러 경로와 비슷

해밀턴 경로를 백트랙킹 방식으로 해결하기

상태공간트리의 구축
→ 트리의 레벨 0에서 출발 정점을 선정(경로의 0번째 정점)
→ 트리의 레벨 1에서 출발 정점을 제외한 각 정점을 출발 정점 다음에 올 첫째 정점으로 고려함
→ 트리의 레벨 2에서는 앞에서와 같은 정점들을 두번째 정점으로 고려함
→ 이후 레벨도 같은 방식으로 고려함
→ 마지막으로 수준 n - 1에서 정점들을 n - 1째 정점으로 고려함
→ 마지막 정점에서 출발 정점으로 돌아오는 경로가 있는지 고려함

def hamiltonian (i , W, vindex):
    n = len(W) - 1
    if (promising(i, W, vindex)):
        if (i == (n - 1)):
            print(vindex[0:n])
        else:
            for j in range(2, n + 1):
                vindex[i + 1] = j
                hamiltonian(i + 1, W, vindex)

인접 행렬 W[i][j]: i번째 정점과 j번째 정점간에 간선이 있으면 True, 없으면 False
promising을 위한 유망 함수의 조건
1. n-1번째 정점은 출발 정점과 반드시 인접해있어야 한다 (마지막엔 돌아와야 하므로)
2. 경로상의 i번째 정점은 그 경로에서 i-1번째 정점과 반드시 인접해야 한다 (다음 노드로 고려하기 위해)
3. i번째 정점은 그 앞에 오는 i-1개의 정점들 중 하나가 될 수 없다 (한번 방문한 노드는 한 번만 방문해야 하므로 되돌아 갈 수 없다)

def promising (i, W, vindex):
    flag = True
    # n-1번째 정점은 출발 정점과 반드시 인접해있어야 한다 
    if ((i == (n - 1)) and not W[vindex[n-1]][vindex[0]]):
        flag = False
    # 경로상의 i번째 정점은 그 경로에서 i-1번째 정점과 반드시 인접해야 한다
    elif ((i > 0) and not W[vindex[i-1]][vindex[i]]):
        flag = False
    # i번째 정점은 그 앞에 오는 i-1개의 정점들 중 하나가 될 수 없다
    else:
        j = 1
        while (j < i and flag):
            if (vindex[i] == vindex[j]):
                flag = False
            j += 1
    return flag

외판원 문제 (The Traveling Salesperson Problem, TSP)

외판원은 출발 도시에서 모든 도시를 방문하고 다시 되돌아와야 한다
출장 시간을 최소로 줄이기 위한 방문 계획을 구하는 문제
가중치가 있는 방향 그래프라고 가정했을 때, 완전 그래프라면 (n-1)! 시간 복잡도를 가지므로 log(n)보다 나쁘다

Dynamic programming으로 외판원 문제를 해결하기

W: 주어진 그래프 G = (V, E)의 인접 행렬
V: 모든 도시의 집합
A: V의 부분집합
D[vi][A]: A에 속한 도시를 각각 한 번씩만 거쳐서 vi에서 v1로 가는 최단 경로의 길이 // 모든 경로의 집합 중에 최적해
재귀적 관계식을 찾기
- D[vi][A] = min(W[i][j] + D[vj][A - {vj}]), A ≠ ∅
- D[vi][∅] = W[i][1], A = ∅

비트를 이용한 부분 집합의 표현과 연산

V - {v1} = {v2, v3, v4}

A = { v4, v2 } = { 1, 0, 1 } = 5 와 같이 통과하는 정점을 1로, 통과하지 않는 정점을 0으로 표현

# vi가 A에 속해있을 때
def isIn(i, A):
    if((A & (1 << (i - 2)) != 0):
        return True
    else:
        return False
# A - {vj} : 차집합을 구하는 비트 연산
def diff (A, j):
    t = 1 << (j - 2)
    return (A & (~t))
# A의 원소가 k개인가?
def count (A, n):
    count = 0
    for i in range(n):
        if((A & (1 << i)) != 0):
            count += 1
    return count

*파이썬으로 TSP 문제를 DP식으로 해결하기**

def travel (W):
    n = len(W) - 1
    size = 2 ** (n -1)
    D = [[0] * size for _ in range(n + 1)]
    P = [[0] * size for _ in range(n + 1)]
    for i in range(1, n + 1):
        D[i][0] = W[i][1]
    for k in range(1, n - 1):
        for A in range(1, size):
            if (count(A, n) == k):
                for i in range(2, n + 1):
                    if(not isIn(i, A)):
                        D[i][A], P[i][A] = minimum(W, D, i, A)
    A = size - 1
    D[1][A], P[1][A] = minimum(W, D, 1, A)
    return D, P

def minimum(W, D, i, A):
    minValue = INF
    minJ = 1
    n = len(W) - 1
    for j in range(2, n + 1):
        if (isIn(j, A)):
            m = W[i][j] + D[j][diff(A, j)]
            if (minValue > m):
                minValue = m
                minJ = j
    return minValue, minJ

외판원 문제를 분기 한정법으로 해결하기

상태공간트리의 최적우선탐색
→ 각 노드에서 한계값을 구하고 특정 노드에서 얻을 수 있는 경로 길이의 하한을 구해야 함
→ 경로 길이의 하한이 현재의 최소 경로 길이보다 작은 경우 유망함
하한값의 정의
→ 각 여행 경로는 정점을 정확히 한 번씩만 거쳐야 한다
→ 정점을 떠나는 간선 가중치 최소값들의 합
분기한정 가지치기 최고우선탐색
→ 한계값은 리프 노드가 아닌 노드에서만 계산하고 여행 경로의 길이는 리프 노드에서 계산한다

파이썬으로 TSP를 Branch-and-Bound 방식의 BFS로 해결하기

class SSTNode:

    def __init__ (self, level):
        self.level = level
        self.path = []
        self.bound = 0
    
    def contains(self, x):
        for i in range(len(self.path)):
            if (self.path[i] == x):
                return True
        return False

def travel2 (W):
    global minlength, opttour
    n = len(W) - 1
    PQ = PriorityQueue()
    v = SSTNode(0)
    v.path = [1]
    v.bound = bound(v, W)
    minlength = INF
    PQ.put((v.bound, v))
    while (not PQ.empty()):
        v = PQ.get()[1]
        if (v.bound < minlength):
            for i in range(2, n + 1):
                if (v.contains(i)): 
                    continue
                u = SSTNode(v.level + 1)
                u.path = v.path[:]
                u.path.append(i)
                if (u.level == n - 2):
                    for k in range(2, n + 1):
                        if (not u.contains(k)):
                            u.path.append(k)
                    u.path.append(1)
                    if (length(u.path, W) < minlength):
                        minlength = length(u.path, W)
                        opttour = u.path[:]
                else:
                    u.bound = bound(u, W)
                    if (u.bound < minlength):
                        PQ.put((u.bound, u))

def bound(v, W):
    n = len(W) - 1
    total = length(v.path, W)
    for i in range(1, n + 1):
        if hasOutgoing(i, v.path):
            continue
        min = INF
        for j in range(1, n + 1):
            if i == j: # 셀프 노드
                continue
            if hasIncoming(j, v.path): 
                continue
            if j == 1 and i == v.path[len(v.path) - 1]:
                continue
            if min > W[i][j]:
                min = W[i][j]
        total += min
    return total   

def length(path, W):
    total = 0
    prev = 1
    for i in range(len(path)):
        if i != 0:
            prev = path[i - 1]
        total += W[prev][path[i]]
        prev = path[i]
    return total

def hasOutgoing(v, path):
    for i in range(0, len(path) - 1):
        if path[i] == v:
            return True
    return False

def hasIncoming(v, path):
    for i in range(1, len(path)):
        if path[i] == v:
            return True
    return False

21-03-03 알고리즘 기초강의(3)

해밀턴 경로 문제

해밀턴 경로를 백트랙킹 방식으로 해결하기

외판원 문제 (The Traveling Salesperson Problem, TSP)

Dynamic programming으로 외판원 문제를 해결하기

외판원 문제를 분기 한정법으로 해결하기

Harry Kim