[파이썬으로 배우는 알고리즘 기초] 7. 해밀턴 경로와 외판원 문제

7-0. 해밀턴 경로 문제(Hamiltonian Path Problem)

• 연결된 무방향 그래프의 한 정점에서 출발하여, 그래프의 모든 정점을 한 번씩만 방문하고 다시 원래 출발한 정점으로 되돌아오는 경로 구하기
• 오일러 경로(Eulerian Path): 모든 간선을 한 번씩만 방문 --- 한 붓 그리기
• 백트래킹으로 해결
  
  

def promising(i, W, vindex):
    flag = True
    if i == (N - 1) and not W[vindex[N - 1]][vindex[0]]:
        flag = False
    elif i > 0 and not W[vindex[i - 1]][vindex[i]]:
        flag = False
    else:
        j = 1
        while j < i and flag:
            if vindex[i] == vindex[j]:
                flag = False
            j += 1
    return flag

def hamiltoninan(i, W, vindex):
    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
                hamiltoninan(i + 1, W, vindex)

N = 4
edges = [
    [1, 2],
    [1, 3],
    [1, 4],
    [2, 3],
    [2, 4],
    [3, 4]
]
W = [[False] * (N + 1) for _ in range(N + 1)]
for edge in edges:
    W[edge[0]][edge[1]] = W[edge[1]][edge[0]] = True
vindex = [-1] * (N + 1)
vindex[0] = 1
hamiltoninan(0, W, vindex)

---

7-1. 외판원 문제(Traveling Salesperson Problem)

• 해밀턴 경로 문제에서 그래프에 가중치가 추가되어 최단 비용이 되는 경로 구하기
• W: 주어진 그래프 G = (V, E)의 인접 행렬
• V: 모든 도시의 집합
• A: V의 부분 집합
• D[vi][A]: A에 속한 도시를 각각 한 번씩만 거쳐서 vi에서 v1로 가는 최단 경로의 길이

1) 동적 계획법으로 해결

• 1. 재귀 관계식
  i != 1 이고 vi가 A에 속하지 않으면
       D[vi][A] = minimum(W[i][j] + D[vj][A-{vj}]), A!=ø
      D[vi][ø] = W[i][j], A!=ø
  2. 상향식 방법
       P[n][W]를 계산하려면 P[n-1][W], P[n-1][W-wn]만 필요
       P[i][w]를 계산하려면 P[i-1][w], P[i-1][w-wi]만 필요

def isIn(i, A): # 부분집합 A에 vi가 있는지
    if A & (1 << (i - 2)) != 0:
        return True
    else:
        return False

def diff(A, j): # 부분집합 A에서 vj를 제외
    t = 1 << j - 2
    return A & ~t

def count(A, n): # A의 원소 갯수
    cnt = 0
    for i in range(n):
        if A & (1 << i) != 0:
            cnt += 1
    return cnt

def minimum(W, D, i, A):
    minV = 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 minV > m:
                minV = m
                minJ = j
    return minV, minJ

def travel_dp(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(2, 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

INF = 999
W = [
    [-1, -1, -1, -1, -1],
    [-1, 0, 2, 9, INF],
    [-1, 1, 0, 6, 4],
    [-1, INF, 7, 0, 8],
    [-1, 6, 3, INF, 0]
]
D, P = travel_dp(W)
print('Minlength =', D[1][2 ** (len(W) - 2) - 1])

 

2) 분기 한정법으로 해결

• 하한값(lower bound)구하기: 경로 길이의 하한은 정점을 떠나는 간선 가중치 최솟값들의 합
• 한계 값은 내부 노드에서 계산 / 여행 경로의 길이는 리프 노드에서 계산

from queue import PriorityQueue

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 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]]
        prve = path[i]
    return total

def hasOutgoing(v, path):
    for i in range(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

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 travel_bb(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))

INF = 999
W = [
    [-1, -1, -1, -1, -1, -1],
    [-1, 0, 14, 4, 10, 20],
    [-1, 14, 0, 7, 8, 7],
    [-1, 4, 5, 0, 7, 16],
    [-1, 11, 7, 9, 0, 2],
    [-1, 18, 7, 17, 4, 0]
]
minlength = INF
opttour = None
travel_bb(W)

print('Minlength =', minlength)
print('Optimal tour =', opttour)

 

 

 

※ 강의 링크: https://inf.run/v8Rn