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
'Computer Science > Algorithm' 카테고리의 다른 글
| [파이썬으로 배우는 알고리즘 기초] 6. 배낭 문제 (0) | 2022.06.09 |
|---|---|
| [파이썬으로 배우는 알고리즘 기초] 5. 백트래킹 (0) | 2022.06.08 |
| [파이썬으로 배우는 알고리즘 기초] 4. 탐욕 알고리즘(2) (0) | 2022.06.08 |
| [파이썬으로 배우는 알고리즘 기초] 4. 탐욕 알고리즘(1) (0) | 2022.06.08 |
| [파이썬으로 배우는 알고리즘 기초] 3. 동적 계획법 (2) (0) | 2022.06.07 |
