분기한정법은 이전 되추적 기법에서 사용했던 상태공간트리와 유망한지 여부를 사용합니다.
되추적은 특정 답을 뽑아내기 위한 방법이었다면, 분기한정법은 최적의 해를 구하는 문제에 사용할 수 있는 방법입니다.
위 사진은 최소화 분기한정법의 대표 사진입니다.
만약 저 팻말이 최소 트래킹 코스 거리를 나타낸다면 (실제 거리 >= 팻말 표시) A를 트래킹했을 때 거리가 200 미만이라면 B를 트래킹 할 필요 없겠죠?
또한 A와 B의 하한이 지금처럼 나와있다면, 당연히 A를 먼저 트래킹하는 것이 유리하겠죠?
생각보다 어렵지 않습니다. 정말요 ^^
그렇다면 바로 분기한정법에 대해 알아보러 가시죠!
목차
0. 배낭채우기
분기한정법은 영어로 branch and bound입니다. 가지랑 영역? 정도로 해석할 수 있겠네요.
모든 해를 다 체계적으로 고려하면서 최적화할 수치의 상한과 하한 영역을 설정하고 이 영역 밖의 해는 제거합니다.
이렇게 제거하면서 파생되는 해는 살펴보지 않습니다. 되추적이랑 굉장히 유사하죠?
이제 배낭채우기 문제를 해결해봅시다.
S는 아이템들이고, w_i는 아이템 i의 무게, p_i는 아이템 i의 가격, W는 배낭에 들 수 있는 무게의 최대값입니다.
우리가 구하길 원하는 것은 p의 합이 최대가 되면서 w의 합은 W보다 작은 케이스입니다.
이 문제는 되추적으로도 해결이 가능합니다.
상태공간트리를 만들고 첫 번째 아이템을 배낭에 넣는 경우와 안 넣는 경우를 모두 고려합니다. 이런 식으로 진행하면 뿌리 마디로부터 마지막 마디까지 모든 경로는 해답 후보가 됩니다.
대신 이 문제는 최적의 해를 찾는 문제이므로 검색이 완전히 끝날 때까지는 해답을 알 수가 없습니다. 검색을 하는 과정동안 항상 최적의 해를 기억해야 합니다.
아래는 최적화 문제를 풀기 위한 되추적 알고리즘 수도코드입니다.
현재까지 최고의 시나리오라면 best에 저장하고,
다음으로 진행할 수 있다면(promising(v)) checknode를 재귀로 다시 한번 돌립니다.
이제 알고리즘을 좀 더 구체화 해보겠습니다.
profit을 그 마디에 오기까지 넣었던 아이템의 값어치의 합,
weight을 그 마디에 오기까지 넣었던 아이템의 무게의 합,
bound를 마디가 수준 i에 있고, 수준 k에 잇는 마디에서 총 무게가 W를 넘는다고 하면 아래와 같다고 가정합니다.
bound는 이론적으로 현 상태에서 얻을 수 있는 최대 이익이 되죠.
위 규칙을 정확하게 숙지한 상태에서 S를 p/w 내림차순 순서대로 정렬합니다. (p/w는 아이템의 단위 무게당 값어치를 의미합니다)
S = (($40,2),($35,5),($18,3),($25,5),($10,5))이고, W가 16인 경우를 생각해보겠습니다.
첫 번째 아이템을 넣은 상태에서의 bound를 계산하면
bound = 40 + 35 + 18 + 25 + 1*(10/5) = 118 + 2 = 120
이 나옵니다. 다섯번째 아이템이 들어갈 수 있는 공간은 다섯번째 아이템의 1/5밖에 남지 않았기 때문입니다!
이제 maxprofit을 지금까지 찾은 최선의 해답이 주는 값어치라고 둡니다.
그러면 bound <=maxprofit이면 수준 i에 있는 마디는 유망하지 않습니다.
위 정보를 바탕으로 알고리즘을 테스트해보겠습니다.
maxprofit(현재까지 최선의 값어치), profit(그 마디까지 아이템의 값어치 합), weight(그 마디까지 아이템의 무게의 합)를 모두 0으로 두고 S를 p/w의 내림차순으로 정렬합니다.
DFS로 그 마디의 profit과 weight를 계산하고, bound(이론적으로 현 상태에서 얻을 수 있는 최대의 이익)를 계산합니다.
만약 weight < W이고 bound > maxprofit이면 검색을 계속합니다. 만약 아니라면 돌아갑니다.(되추적합니다)
아래 예시문제를 실제로 테스트해보겠습니다.
먼저 첫 노드에서는 bound는 40 + 30 + 9 * 50/10 = 115가 됩니다.
그리고 내려갑니다. 왼쪽은 넣었을 때, 오른쪽은 안 넣었을 때 기준입니다.
오른쪽으로 내려가면 새롭게 bound를 계산하면 30 + 50 + 1 * 10/5 = 82가 나옵니다.
DFS방식으로 내려가기 때문에 오른쪽 노드는 내버려두고 먼저 왼쪽부터 쭉 처리합니다.
(3,1)에서 3개를 넣는 순간 w가 17이 되고 w > W기 때문에 더이상 유망하지 않습니다.
(3,2)에서 다시 양쪽으로 내려가면 maxprofit이 80임을 알 수 있습니다.
이제 다시 올라가서 (2,2)로 갑니다.
왼쪽으로 내려가면 maxprofit이 90임을 확인하게 되고, 오른쪽으로 내려가면 bound가 90보다 작아지기 때문에 유망하지 않는다는 것을 확인할 수 있습니다.
이제 맨 처음으로 돌아가서 (1,2)로 가면 bound가 82여서 90보다 작기 때문에 더 이상 유망하지 않습니다.
그 결과 (1,0,1,0)이 정답이 되는 것을 확인할 수 있습니다. (마지막 잎 마디에서는 bound = maxprofit이므로 더 이상 유망하지 않아 진행할 수 없습니다)
이렇게 해서 총 13개의 노드를 탐색하게 됩니다.
0.0. 분기한정 가지치기 - DFS
이번에는 분기한정 가지치기로 깊이우선탐색(DFS)를 해보도록 하겠습니다.
아래는 knapsack 함수의 수도코드입니다.
자세히 살펴보면 위에서 한 되추적의 내용과 사실상 다를게 없습니다.
먼저 첫 if문에서는 유효성 검사와 최대이익 검사를 합니다.
만약 maxprofit보다 새로운 profit이 더 크다면 maxprofit을 갱신합니다.
그리고 i번째까지 판단했다는 의미로 numbest에 i를 넣고, 현재 어떤 아이템을 배낭에 넣었는지를 담은 배열인 bestset에 현재 담은 배열을 복사합니다.
두 번째 if문에서는 유망한 경우 다음 요소를 넣은 경우의 수를 체크합니다.
include배열의 다음 요소에 yes(배낭에 넣음)을 넣고 knapsack을 재귀로 돌립니다. 이 과정에서 profit과 weight에 다음 요소를 넣었다는 것을 반영해줍니다.
그 다음에는 다음 요소를 안 넣었다는 경우의 수를 체크합니다.
include배열의 다음 요소에 no(배낭에 안 넣음)을 넣고 knapsack을 재귀로 돌립니다. profit과 weight는 그대로인데 i만 i+1로 바꿔줍니다.
promising 함수의 수도코드입니다.
맨 처음에는 weight이 W와 같거나 W를 초과하면 유망하지 않음을 반환합니다.
그 다음에는 totweight와 bound를 더해줍니다. 우선 무게 조건을 만족할 때까지 계속해서 넣어줍니다.
그 다음에 아직 들어가지 않은 요소가 있다면 빈 자리에 잘라서 넣어줍니다. 이게 bound가 됩니다.
이렇게 했는데 bound(이론적으로 현 상태에서 얻을 수 있는 최대의 이익)이 maxprofit보다 크면 아직 가능성이 있다(유망하다)는 말이므로 true를 반환합니다. 아니면 false를 반환합니다.
출력을 위해서는 numbest와 maxprofit를 미리 초기화하고, knapsack 함수를 돌립니다.
그리고 작업을 완료하고 maxprofit과 bestset을 출력하는 식이죠.
아래는 파이썬으로 구현한 분기한정 가지치기 DFS입니다.
조금 차이점이 있다고 한다면 인덱스가 0부터이기 때문에 kp의 맨 앞 매개변수가 -1이 되었다는 것 정도입니다. 이외에는 kp에 주석을 달아놓았기 때문에 참고하시면 됩니다.
기타 지정값은 n=4, W=16, p=[40,30,50,10], w=[2,5,10,5] 입니다.
# 분기한정 가지치기 깊이우선탐색
# profit = 그 마디까지 넣었던 아이템 값어치의 합
# weight = 그 마디까지 넣었던 아이템 무게의 합
# bound = 현 상태에서 얻을 수 있는 최대 이익
def kp(i, profit, weight):
global bestset
global maxp
if(weight <= W and profit > maxp): # weight가 W보다 작거나 같거나 profit이 최대이익보다 크면
maxp = profit # 최고이익 새로설정
bestset = include[:] # bestset 배열복사
# best = include는 best를 include의 reference로 만든다.
# 한 번 동일한 값을 가진 후 그 이후는 계속 동일함.
if promising(i, weight, profit): # 다음으로 진행할 수 있으면?
include[i+1] = 1
kp(i+1, profit+p[i+1],weight+w[i+1]) # 다음꺼 넣었을 때
include[i+1] = 0
kp(i+1, profit,weight) # 다음꺼 안 넣었을 때
def promising(i, weight, profit):
global maxp
if(weight >= W): # weight이 목표 W 초과하면
return False # False
else: # 아니면
j = i+1
bound = profit
totweight = weight
while j<n and totweight + w[j] <= W:
totweight += w[j]
bound += p[j]
j += 1
k = j
if k<n:
bound += (W-totweight)*p[k]/w[k]
return bound > maxp
n=4
W=16
p=[40,30,50,10]
w=[2,5,10,5]
maxp=0
include =[0,0,0,0]
bestset = [0,0,0,0]
kp(-1,0,0)
print(maxp)
print(bestset)
이 알고리즘이 점검하는 마디의 수는 2^(n+1) - 1 = O(2^n)가 됩니다.
지수형태의 Big-O라는 이야기는 탐색하는데 시간이 오래 걸리는 알고리즘이라는 소리가 되겠죠.
0.1. 분기한정 가지치기 - BFS
이번에는 너비우선검색(BFS)으로 알고리즘을 구현해보겠습니다.
BFS의 기본은 level 순서대로 검색하는 것이었죠?
아래 사진과 같은 순서대로 검색됩니다.
BFS는 Queue로 구현할 수 있습니다.
아래는 Queue로 구현한 BFS의 수도코드입니다.
BFS를 이용하여 bound계산을 하는 수도코드입니다.
bound조건을 보면 best를 기준으로 value값에 따라 best를 갱신하고, bound에 따라 Queue에 마디들을 넣습니다.
함수의 골격이 잡혔으니 위 BFS&bound 함수를 이용하여 knapsack2 함수를 만들어봅시다.
knapsack2 함수에서도 똑같이 queue를 하나 만들고, u라는 노드를 하나 만들어서 그곳에 level, weight와 profit를 넣어줍니다.
2가지 케이스로 나눠서 만약 아이템을 넣으면 넣은 아이템의 w와 p를 추가한 후 Queue에 넣고, 넣지 않으면 그대로 복사만 한 후에 Queue에 넣습니다.
bound 함수는 weight와 W를 비교해서 weight가 더 크면 현재 가방에 넣은 아이템들의 무게의 합이 W를 초과한다는 것이므로 0을 return합니다. (더이상 검색하지 않는다는 의미와 같습니다!)
그 다음에는 현재 weight에서 새롭게 넣을 수 있는 아이템들을 순서대로 넣어줍니다.
위에서 bound 계산한 것과 동일한 방식입니다.
그리고 그 bound값을 return해줍니다.
수도코드를 이용하여 실제로 파이썬 코드를 작성하였습니다.
파이썬 코드에서는 include라는 배열을 하나 만들어서 현재까지 어떤 요소를 담았는지를 포함하는 부분을 추가로 생성하였습니다.
include가 아래 코드에서 어떻게 동작하는지를 추가로 말씀드리면 넣었을 때는 u.include[u.level]을 1로 바꿔주고, 넣지 않았을 때는 그대로 둡니다. 처음에 초기화할 때 include의 모든 요소를 0으로 초기화 했기 때문에 건드릴 필요가 없기 때문입니다.
# 분기한정 가지치기 너비우선탐색
import queue
import copy
class Node:
def __init__(self,level,weight, profit, include):
self.level = level
self.weight = weight
self.profit = profit
self.include = include
def kp_BFS():
global maxProfit
global bestset
q = queue.Queue()
temp = n*[0]
v = Node(-1,0,0,temp)
q.put(v)
while not q.empty():
v = q.get()
level = v.level + 1
weight = v.weight + w[level]
profit = v.profit + p[level]
include = v.include[:]
u = Node(level,weight,profit,include)
u.include[u.level] = 1
if u.weight <= W and u.profit > maxProfit:
maxProfit = u.profit
bestset = u.include[:]
if compBound(u) > maxProfit:
q.put(u)
u = Node(level,v.weight,v.profit,v.include)
if compBound(u) > maxProfit:
q.put(u)
# 왜 마지막거가 남아있을까?
def compBound(u):
if u.weight >= W:
return False
else:
j=u.level+1
bound = u.profit
totweight = u.weight
while j<n and totweight + w[j] <= W:
totweight += w[j]
bound += p[j]
j += 1
k = j
if k<n:
bound += (W-totweight)*p[k]/w[k]
return bound
n=4
W=16
p=[40,30,50,10]
w=[2,5,10,5]
include=[0]*n
maxProfit =0
bestset=n*[0]
kp_BFS()
print(bestset)
다만 이 너비우선 검색은 총 17개의 마디를 검색합니다. 깊이우선 알고리즘의 13개에 비해 좋지 않은 효율을 가지고 있다는 점을 기억하셔야 합니다.
0.2. 분기한정 가지치기 - 최고우선검색
이번에는 최고우선검색(best-first search)입니다.
주어진 마디의 모든 자식마디를 검색하고, 유망하면서 확장되지 않은 마디를 살펴보고, 그 중에서 가장 좋은 한계치를 가진 마디를 확장하는 방식입니다.
이 알고리즘의 핵심은 최고의 bound를 가진 마디를 우선적으로 선택하는 것인데, 그 방법으로 priority queue를 사용합니다.
priority queue는 heap을 사용하면 쉽게 구현할 수 있습니다.
heap은 보통 완전이진트리구조를 가지는 것이 일반적이고, 부모는 자식들에 비해 항상 더 크거나(maxheap) 항상 더 작습니다(minheap).
maxheap 기준으로 가장 큰 값을 찾을 때는 O(1)입니다. 맨 위의 값만 가져오면 되기 때문이죠.
max값을 가져오면 나머지 값들을 정리해야 하는데 그 과정은 O(log n)이 걸립니다.
그리고 데이터를 추가할 때는 맨 마지막에 자료를 추가하고 다시 정렬해야 하므로 O(log n)이 걸립니다.
완전이진트리로 구성된 힙의 경우 i번째 노드를 기준으로 왼쪽 자식은 2*i, 오른쪽 자식은 2*i+1의 index에 자료가 들어있게 되고, 부모 노드의 index는 n/2를 내림한 값이 됩니다.
아래 그림은 maxheap의 예시입니다.
최고우선검색의 기본적인 원리를 나타낸 수도코드입니다.
너비우선검색 방법에서는 Queue 안에 넣었지만, 이번엔 PrimaryQueue 안에 넣습니다.
이렇게 되면 최고의 케이스를 우선적으로 계산함으로써 PQ에 들어갈 요소를 최소화할 수 있게 됩니다.
위 수도코드를 바탕으로 만든 knapsack3 함수입니다.
Primary Queue를 사용한 점만 제외하면 사실상 같습니다.
수도코드를 바탕으로 분기한정 가지치기 최고우선탐색을 파이썬으로 구현하였습니다.
파이썬에서 제공하는 Primary queue는 기본적으로 min-heap이기 때문에
가장 큰 bound를 추출하기 위해서 앞에 -를 붙였습니다.
(bound가 60 40 20이 있다고 하면 min-heap에서는 20이 가장 먼저 나오는데 이 순서를 뒤집기 위해서 -를 붙여서 PQ에 넣어준 것입니다!)
그리고 PQ에 넣을 때 ( , ) 튜플 형식으로 넣어줘서 bound와 Node를 함께 넣어줬습니다.
그래서 pq.get()[1]에서 가장 bound가 큰 친구의 Node를 가져올 수 있는 것이죠!
# 분기한정 가지치기 최고우선탐색
import queue
class Node:
def __init__(self,level,weight, profit, bound, include):
self.level = level
self.weight = weight
self.profit = profit
self.bound = bound
self.include = include
def __lt__(self, other): # 마술함수
return self.bound < other.bound
def kp_Best_FS():
global maxProfit
global bestset
temp = n*[0]
v = Node(-1,0,0, 0.0,temp)
pq = queue.PriorityQueue() # default가 min-heap
v.bound = compBound(v)
pq.put((-v.bound,v)) # min-heap이기 때문에 제일 작은 것을 먼저 빼온다. 그래서 bound 앞에 -를 붙인다.
u = Node(0,0,0, 0.0,temp)
while (not pq.empty()):
v = pq.get()[1]
if v.bound > maxProfit:
# Left child node - 따로 저장을 하면 pq에 잘 저장된다.
level = v.level + 1
weight = v.weight + w[level]
profit = v.profit + p[level]
include = v.include[:]
u = Node(level, weight, profit, 0.0, include)
u.include[level] = 1
if u.weight <= W and u.profit > maxProfit: # 배낭보다는 작아야한다 / Profit이 더 크다면
maxProfit = u.profit # maxProfit 갱신
bestset = u.include # 현재 include를 bestset에 저장
u.bound = compBound(u)
if u.bound > maxProfit:
pq.put((-u.bound,u))
# Right child node
u = Node(level,v.weight, v.profit, 0.0, v.include)
u.bound = compBound(u)
if u.bound > maxProfit:
pq.put((-u.bound,u))
def compBound(u):
if u.weight >= W:
return False
else:
j=u.level+1
bound = u.profit
totweight = u.weight
while j<n and totweight + w[j] <= W:
totweight += w[j]
bound += p[j]
j += 1
k = j
if k<n:
bound += (W-totweight)*p[k]/w[k]
return bound
# heap이 minheap이라 bound를 계산하여 -를 하여 리턴한다. 비교를 < maxProfit으로 수행한다.
n=4
W=16
p=[40,30,50,10]
w=[2,5,10,5]
include=[0]*n
maxProfit =0
bestset=n*[0]
kp_Best_FS()
print(bestset)
print(maxProfit)
분기한정 가지치기 최고우선검색을 사용하면 검색하는 마디는 11개가 됩니다.
DFS방식은 13개, BFS방식은 17개를 검색했으니 훨씬 이득입니다!!
1. 외판원 문제
외판원 문제는 하나의 노드에서 출발하여 다른 노드들을 각각 한번씩만 방문하고 다시 출발노드로 돌아오는 가장 짧은 경로를 결정하는 문제입니다.
이 문제 역시 Brute force(무작정 알고리즘)으로 풀 수 있습니다.
현재 노드와 이미 방문한 노드를 제외한 모든 노드에 방문할 수 있으므로 (n-1)(n-2)...(1) 이 됩니다.
이 경우 경로의 총 개수는 (n-1)!이 되겠죠?!
분기한정법으로 해결하기 전에 먼저 해밀토니안 회로에 대해서 알 필요가 있습니다.
해밀토니안 회로(일주여행경로)는 어떤 한 마디에서 출발하여 그래프 상의 각 정점을 한번씩만 경유하여 다시 출발한 정점으로 돌아오는 경로입니다. 딱 외판원 문제죠?
여기서 경로에 가중치(거리)가 주어진다면 어떻게 될까요?
경우의 수를 계산해서 가중치(거리)가 최소가 되는 길을 찾으면 됩니다.
만약 모든 노드가 연결이 되어있다면 최적해는 아래와 같습니다.
외판원 문제를 동적계획법 알고리즘을 이용해서 해결하려고 한다면 시간복잡도가 (n-1)(n-2)2^(n-3)이 나옵니다.
O((n^2)*(2^n))이라는 말인데, 동적계획법 알고리즘의 기본동작을 수행하는데 걸리는 시간이 1나노초라면 n이 40이면 6년 이상이 걸리게 됩니다.
그렇기 떄문에 분기한정법을 사용해서 문제를 해결해야 합니다.
먼저 상태공간트리를 구축합니다.
각 마디는 출발마디로부터의 일주여행경로를 나타냅니다.
root 마디의 여행경로는 [1]이 되고, root에서 뻗어나가는 level1 여행경로는 각각 [1,2], [1,3], ... [1,5]가 되고, 그 다음 [1,2]에서 뻗어나가는 level2 여행경로는 각각 [1,2,3], ... , [1,2,5]가 되고 이런 식으로 끝까지 뻗어나가면 완전한 일주여행경로를 가지게 됩니다.
따라서 최적일주여행경로를 구하기 위해서는 마지막까지 도달한 경로를 모두 검사하여 그 중에서 가장 길이가 짧은 경로를 찾으면 됩니다.
이제 한계값을 직접 구해보겠습니다. v1~v5는 각각의 노드를 의미합니다.
bound는 떠나는 비용의 하한들의 합이 됩니다.
아무것도 결정되지 않은 상태에서는 모든 경로로 이동할 수 있으므로 행렬내 행에서 가장 최소값이 각 노드에서 떠나는 비용의 하한이 됩니다.
만약 v1에서 v2로 가는 경로가 결정된 경우에는 v2~v5에서 떠나는 비용의 하한을 계산합니다.
v2에서는 v1로 다시 갈 수 없기 때문에 3,4,5로만 이동이 가능합니다.
v3,4,5의 경우 v2로 다시 갈 수 없습니다. 이미 방문한 노드이기 때문에 v2와 자기 자신을 제외한 노드로 이동할 수 있습니다.
그리고 마지막에 일주경로의 하한에는 v1->v2 경로의 길이도 함께 더해줍니다.
아래는 분기한정 가지치기로 최고우선검색을 하여 구축한 상태공간트리입니다.
상태공간트리가 어떻게 만들어지는 지에 대해서 자세하게 풀어서 작성해보겠습니다!
먼저 [1,2],...[1,5] 까지의 경로의 bound를 계산합니다.
그 중에서 가장 bound가 낮은 22에서 가지를 뻗어나갑니다. (가지를 뻗는다는 말은 노드를 PQ에 넣는다는 말과 같습니다)
그러면 6,7,8번 값이 생성되는데, 이제 이전 경로와 합해서 가장 낮은 bound의 가지를 늘려줍니다.
2(31), 6(22), 7(27), 8(39), 4(30), 5(42) 가 잎 마디(마지막 마디)가 되는데, 이 중에서 가장 bound가 작은 6(22)의 가지를 늘려줍니다.
9와 10번 노드는 완전한 경로로 마무리되었기 때문에, 그 중에서 가장 거리가 짧은 31을 minlength에 저장합니다.
이제 minlength보다 value가 높아지는 경우 PQ에 넣지 않습니다.
그리고 다시 2(31), 7(27), 8(39), 4(30), 5(42) 중에서 bound가 가장 낮은 7의 가지를 늘려줍니다.
7의 가지들의 value가 모두 31보다 크므로 더이상 신경쓰지 않습니다.
다음엔 2(31), 8(39), 4(30), 5(42) 중에서 가장 bound가 낮은 4의 가지를 늘려줍니다.
다음엔 2(31), 8(39), 15(30), 5(42) 중에서 가장 bound가 낮은 15의 가지를 늘려줍니다.
여기서 13, 14번 노드는 PQ에 넣지 않습니다. 이미 minlength인 31보다 value가 크기 때문입니다.
마지막으로 2(31), 8(39), 16(30), 17(48), 5(42)이 나오는데, 여기서 bound가 가장 작은 16을 확인하니 완전한 경로입니다.
minlength에 16의 value인 30을 저장합니다.
남은 PQ의 값들은 모두 bound가 minlength보다 크므로 그대로 알고리즘이 종료됩니다.
이때 총 방문 노드는 17개이고, 생성 가능한 노드는 1+4+4*3+4*3*2가 됩니다.
맨 끝에 4*3*2*1를 더해주지 않은 이유는 마지막 노드는 자동으로 결정되기 때문입니다.
아래 코드는 외판원 문제에 대한 수도코드입니다.
전체적인 맥락은 배낭채우기 문제와 동일합니다. 대신 이미 방문한 경로는 다시 방문하지 않도록 i is not is v.path인 경우에만 방문합니다.
수도코드를 바탕으로 만든 파이썬 코드입니다.
tMin(minlength)의 경우 10000으로 설정하였으나 만약 더 큰 값이 존재하는 경우에는 유의미하게 큰 수로 지정하시면 됩니다.
# 외판원 문제
import queue
class Node:
def __init__(self,bound ,path):
self.bound= bound
self.path = path
# def __cmp__(self, other):
# return cmp(self.bound, other.bound)
def TSP_Best_FS():
global minLength
global optTour
path=[start]
v = Node(0,path)
v.bound = compBound(v)
q = queue.PriorityQueue()
q.put((v.bound,v.path))
while not q.empty():
v.bound, v.path= q.get()
if(v.bound < minLength):
if len(v.path)==n-1:
A = v.path[:]
B = [x for x in V if x not in A]
C=[x for x in B if x !=start]
if compLength(v.path)+W[v.path[n-2]][C[0]]+W[C[0]][start] < minLength:
minLength = compLength(v.path)+W[v.path[n-2]][C[0]]+W[C[0]][start]
optTour = v.path[:]+[C[0]]
else:
C=[ x for x in V if x not in v.path]
for x in C:
u = Node(0,v.path+[x])
u.bound = compBound(u)
print("path bound ", u.path, u.bound)
if u.bound < minLength:
q.put((u.bound,u.path))
def compBound(u):
global start
# if len(u.path)==n-1:
# print(" uPP ", u.path, u.path[n-2],compLength(u.path), W[u.path[n-2]][start])
# return compLength(u.path)+W[u.path[n-2]][start]
# else:
tbound = 0
A = u.path[:]
B = [x for x in A if x != start]
C= [x for x in V if x not in A]
temp1=0
tMin=10000
for y in C:
if W[u.path [ len(u.path)-1]][y] < tMin:
tMin = W[u.path [ len(u.path)-1]][y]
tbound += tMin
for y in C:
tMin = 10000
D = [ x for x in C if x != y]
D.append(start)
for z in D:
if W[y][z]<tMin:
tMin=W[y][z]
tbound += tMin
return tbound+compLength(u.path)
def compLength(a):
length =0
for x in range (0,len(a)-1):
length += W[a[x]][a[x+1]]
return length
start =0
n=5
W=[[0,14,4,10,20],[14,0,7,8,7],[4,5,0,7,16],
[11,7,9,0,2],[18,7,17,4,0]]
V=list()
for x in range(0,n):
V.append(x)
optTour=list()
print(V)
minLength=10000
TSP_Best_FS()
print(minLength)
print(optTour)
하지만 분기한정법을 이용한 최고우선검색 알고리즘을 사용하더라도 시간복잡도가 지수적이거나 더 오래 걸리기 때문에 "이런 방법을 사용할 수 있다", 혹은 "bound함수는 이렇게 구성할 수 있다"정도로만 파악해도 성공입니다.
만약 계산하는데 이렇게 오랜 시간이 걸리는 경우 부득이하게 부분적으로 최적을 계산하는 근사 알고리즘등을 사용하여 값을 구해내기도 합니다.
지금까지 분기한정법에 대해 알아보았습니다.
Rough하게 말하면 조금 발전된 형태의 Brute Force 혹은 DP라고 보시면 될 것 같습니다.
그렇다고 해서 쓸 데 없는 알고리즘이거나 한 것은 아니고 실제로 적은 단계를 거치는 경우 유의미하게 검색량을 줄일 수 있기 때문에 꼭 짚고 넘어가야 하는 알고리즘입니다.
다음 포스팅은 익숙한 정렬 문제입니다. 어려운 파트를 넘겼으니 조금 편하게 보실 수 있을 거라고 생각합니다!
그렇다면 다음 포스팅에서 뵙도록 하겠습니다 :)
최근댓글