문제)
Description
교재와 강의자료를 참고하여 외판원 순회 문제를 분기한정법으로 해결하는 Algorithm 6.3의 구현을 완성하시오.
분기한정을 위한 Best FS의 방문순서대로 노드의 상태를 출력해야 함에 유의하시오.
또, 방향 그래프에서는 bound 값이 무한대일 경우에 INF라고 출력하도록 해야 함에 유의하시오!!!
Input
첫 줄에 정점의 개수 n과 간선의 개수 m이 주어진다.
둘째 줄부터 m개의 간선이 u, v, w의 형태로 주어진다.
Output
첫째 줄부터 분기한정법으로 방문하는 노드의 상태를 아래와 같이 출력한다.
level bound path[0] path[1] ...... path[k]
(마지막에 공백이 출력되지 않도록 유의할 것)
노드의 상태 출력이 모두 끝나면 다음 줄에 최적값 minlength를 출력한다.
다음 줄에는 1번 정점을 출발점으로 하는 최적 순회 경로를 출력한다.
(최적 순회 경로는 여러 개가 있을 수 있으나, 교재와 강의자료에서 선택하는 순회 경로를 출력하도록 유의할 것)
또한, 방향 그래프에서는 bound 값이 무한대일 경우에는 INF라고 출력하도록 해야 함에 유의하시오!!!
코드)
import heapq
from copy import deepcopy
class Node:
bound = 0
def __init__(self, level: int, path: list):
self.level = level
self.path = path
def length(path: list) -> int:
# len = 0
# i = 0
# while path[i] != path[-1]:
# if path[i] != path[-2]:
# len += W[path[i]][path[i + 1]]
# i += 1
# return len
p_len = 0
i = 0
for i in range(0, len(path) - 1):
p_len += W[path[i]][path[i + 1]]
return p_len
def hasOutgoing(v: int, path: list) -> bool:
# i = 0
# while path[i] != path[-2]:
# if path[i] == v:
# return True
# i += 1
# return False
temp = path[:-1]
if v in temp:
return True
return False
def hasIncoming(v: int, path: list) -> bool:
# i = 1
# while path[i] != path[-1]:
# if path[i] == v:
# return True
# i += 1
# return False
temp = path[1:]
if v in temp:
return True
return False
def bound(v: Node) -> int:
lower = length(v.path)
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 j == 1 and i == v.path[-1]:
continue
if hasIncoming(j, v.path):
continue
if min > W[i][j]:
min = W[i][j]
lower += min
if lower >= INF:
return INF
return lower
def remaining_vertex(path: list) -> int:
total = n * (n + 1) // 2
total_path = sum(path)
return total - total_path
def func() -> None:
global opttour
global minlength
cnt = 0
PQ = []
v = Node(0, [1])
v.bound = bound(v)
print(v.level, v.bound, *v.path, sep=' ')
heapq.heappush(PQ, (v.bound, cnt, v))
while len(PQ):
v = heapq.heappop(PQ)[2]
if v.bound < minlength:
for i in range(2, n + 1):
cnt += 1
if i in v.path:
continue
u = Node(v.level + 1, deepcopy(v.path))
u.path.append(i)
if u.level == n - 2:
u.path.append(remaining_vertex(u.path))
u.path.append(1)
if length(u.path) < minlength:
minlength = length(u.path)
opttour = u.path.copy()
else:
u.bound = bound(u)
if u.bound < minlength:
try:
heapq.heappush(PQ, (u.bound, cnt, u))
finally:
pass
if u.level > n - 3:
if length(u.path) >= INF:
print(u.level, "INF", *u.path, sep=' ')
else:
print(u.level, length(u.path), *u.path, sep=' ')
else:
if u.bound >= INF:
print(u.level, "INF", *u.path, sep=' ')
else:
print(u.level, u.bound, *u.path, sep=' ')
if __name__ == "__main__":
INF = 9999
opttour = []
minlength = INF
n, m = map(int, input().split()) # 정점과 간선의 개수
W = [[INF] * (n + 1) for _ in range(n + 1)] # 인접행렬
for i in range(n + 1):
W[i][i] = 0
for _ in range(m):
u, v, w = map(int, input().split()) # 간선의 정보
W[u][v] = w
func()
print(minlength)
print(*opttour, sep=' ')
2번째 코드)
from copy import deepcopy
import heapq
INF = 9999 # 경로가 없거나, 무한대를 위한 것
class Node:
# 노드를 만듬
def __init__(self, level: int, path: list) -> None:
self.level = level
self.path = path
self.bound = self.getbound()
def length(self) -> int:
# 해당 경로까지의 길이를 찾는 메서드
path_len = 0 # 최초 길이는 0
for i in range(len(self.path) - 1):
# path가 [1, 3, 5]라면 adj[1][3]와 adj[3][5]을 더해야함
path_len += adj[self.path[i]][self.path[i + 1]]
return path_len
def outgoing(self, v: int) -> bool:
# bound 관련 함수
# 만약 path가 [1, 4, 5, 2]라면 1, 4, 5를 체크한다.
# 1, 4, 5는 이미 정해져있는 length이기 때문에, 2번과 다른 노드들이 bound를 결정한다.
return (True if v in self.path[:-1] else False)
def incoming(self, v: int) -> bool:
# bound 관련 함수
# 만약 path가 [1, 4, 5, 2]라면 4, 5, 2를 체크한다.
# 출발 정점을 제외하고는 돌아가서는 안 된다
return (True if v in self.path[1:] else False)
def getbound(self) -> int:
# 해당 경로의 하한 길이를 찾는 메서드
lower = self.length() # 해당 path까지의 길이
for i in range(1, n + 1): # 모든 정점을
if self.outgoing(i):
# 이미 i에서 어떤 노드로 향한 경로가 있다는 뜻임
continue
min = INF
for j in range(1, n + 1):
# 경로가 정해지지 않은 노드들이 최소 경로를 찾기 위한 것
# 최소가 되는 i -> j를 찾아야한다.
if i == j: # 자기 자신으로 못 감
continue
if j == self.path[0] and i == self.path[-1]:
# i가 path의 마지막 노드이고, j가 만약에 출발한 노드라면
# 이는 고려하면 안 됨
continue
if self.incoming(j):
# 이미 어떤 노드에서 j로 향한 경로가 있다는 뜻임
continue
min = adj[i][j] if min > adj[i][j] else min
# i -> j가 min보다 작다면 min을 업데이트
# 이때 i에서 출발해서 도착 가능한 모든 j에 대한 최솟값임
lower += min # bound를 구하기 위해 더함
return (INF if lower >= INF else lower)
# 이랬는데 INF를 넘긴다면 그냥 INF를 반환
def create_adj():
# 인접 행렬을 만드는 함수
adj = [[INF] * (n + 1) for _ in range(n + 1)] # 인접행렬
for i in range(n + 1):
adj[i][i] = 0 # 자기 자신에 대한 경로는 0
for _ in range(m):
u, v, w = map(int, input().split()) # 출발 정점, 도착 정점, 가중치
adj[u][v] = w
return adj
def remaining_vertex(path: list) -> int:
# 마지막 남은 노드를 찾는 함수
total = n * (n + 1) // 2 # 모든 n을 다 더함
total_path = sum(path) # 모든 경로를 더함
return total - total_path # 빼면 가지 않은 노드가 나옴
def travel2():
minlength = INF # 최소 길이를 정의
optour = [] # 최소 경로
cnt = 0 # PQ에 넣을 때 중요함..
PQ = [] # 우선순위 큐를 만듬
v = Node(0, [1]) # 출발 정점을 1로 하고, 레벨을 0로함
# 만약 2에서 출발하는 것이라면 이것만 바꾸면 됨
print(v.level, v.bound, *v.path, sep=' ')
heapq.heappush(PQ, (v.bound, cnt, v)) # bound가 작고, cnt가 작은 순대로 넣음
while PQ:
# PQ가 비어있지 않다면
v = heapq.heappop(PQ)[2]
if v.bound < minlength:
# 경로의 하한선이 최소 길이보다 작아야 유망함
for i in range(1, n + 1):
# 출발 정점이 1이므로, 2부터 n까지 살펴봄
# 원래 위의 주석이 맞는데, 변형으로 나올 수 있어서 1부터 찾는 것으로 함
# 어차피 바로 아래의 if문에 의해 없어짐
cnt += 1
if i in v.path:
# i가 만약에 이미 경로상에 있다면 살펴보지 않음
continue
u = Node(v.level + 1, deepcopy(v.path))
u.path.append(i)
# u를 생성하고, i에 갔다고 가정함
if u.level == n - 2:
# 만약 u의 level이 n - 2라면 여러 자식으로 뻗을 필요가 없음
# 왜냐면 갈 곳은 하나밖에 안 남았기 때문임
u.path.append(remaining_vertex(u.path)) # 안 간 마지막 노드에 방문
u.path.append(u.path[0]) # 맨 처음 노드로 간다고 가정
# 출력을 위한 코드
print(u.level, "{}".format("INF" if u.length() >= INF else u.length()), *u.path, sep=' ')
if u.length() < minlength:
# 그랬을 때 경로가 지금까지 찾은 최소 길이보다 작으면 업데이트
minlength = u.length()
opttour = deepcopy(u.path)
else: # 여러 자식으로 가봐야 한다면
u.bound = u.getbound() # 해당 마디의 하한 값을 찾아봄
# 출력을 위한 코드
print(u.level, "{}".format("INF" if u.bound >= INF else u.bound), *u.path, sep=' ')
if u.bound < minlength: # 하한 값이 지금까지 찾은 최소 길이보다 작다면
heapq.heappush(PQ, (u.bound, cnt, u)) # 유망(자식으로 갈 가치가 있음)하므로 PQ에 넣음
print(minlength)
print(*opttour, sep=' ')
if __name__ == "__main__":
n, m = map(int, input().split()) # 정점 개수, 간선 개수
adj = create_adj() # 인접 행렬을 만듬
travel2()