분기한정법과 0-1 배낭 문제

  • 깊이우선탐색(DFS)와 너비우선탐색(BFS)
  • 분기한정법(Branch-and-Bound) : BFS 기반 상태공간트리로 문제를 해결
  • 항상 한계값을 고려하므로 최적화 문제를 해결하기 좋음
  • 최적우선탐색(Best-First-Search w/ Branch-and-Bound)

BFS로 배낭문제를 해결하기

1
2
3
4
5
6
7
8
9
10
11
12
13
# 슈도 코드
def breadth_first_search(tree):
    queue_of_node Q
    node u, v
    initialize(Q)
    v = root of tree
    visit v
    enqueue(Q, v)
    while(!empty(Q)):
        dequeue(Q, v)
        for (each child u of v):
            visit u
            enqueue(Q, u)
  • 분기한정법으로 0-1 배낭 문제를 해결하려면?
    • 일반적으로 BFS가 DFS보다 나쁨
    • 유망 함수 외에 추가적인 용도로 한계값(bound)를 사용
    • 주어진 어떤 노드의 모든 자식 노드를 방문하고
      → 유망하면서 확장하지 않은 노드들을 모두 살펴보고
      → 한계값이 가장 좋은 노드를 우선적으로 확장
    • 지금까지 찾은 최적해보다 한계값이 더 좋을 때 유망함

파이썬에서 우선순위 큐 쓰는 법 예시

1
2
3
4
5
6
7
8
from queue import PriorityQueue

PQ = PriorityQueue()
data = [4, 1, 3, 2]
for i in range(len(data)):
    PQ.put(data[i])
while(not PQ.empty()):
    print(PQ.get())

파이썬으로 분기한정법 구현하기

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
from queue import PriorityQueue


class SSTNode:

    def __init__(self, level, profit, weight):
        self.level = level
        self.profit = profit
        self.weight = weight
        self.bound = 0

    def print(self):
        print(self.level, self.profit, self.weight, self.bound)


def bound(u, p, w):
    n = len(p) - 1
    if u.weight >= W:
        return 0
    else:
        result = u.profit
        j = u.level + 1
        totweight = u.weight
        while j <= n and totweight + w[j] <= W:
            totweight += w[j]
            result += p[j]
            j += 1
        k = j
        if k <= n:
            result += (W - totweight) * p[k] / w[k]
        return result


def knapsack4(p, w, W):
    PQ = PriorityQueue()
    v = SSTNode(0, 0, 0)
    maxprofit = 0
    v.bound = bound(v, p, w)
    PQ.put((-v.bound, v))
    while not PQ.empty():
        v = PQ.get()[1]
        print("POP:", end="")
        v.print()
        if v.bound > maxprofit:
            level = v.level + 1
            weight = v.weight + w[level]
            profit = v.profit + p[level]
            u = SSTNode(level, profit, weight)
            if u.weight <= W and u.profit > maxprofit:
                maxprofit = u.profit
            u.bound = bound(u, p, w)
            print("\tPUT:", end="")
            u.print()
            if u.bound > maxprofit:
                PQ.put((-u.bound, u))
                print("\t\tYES")
            u = SSTNode(level, v.profit, v.weight)
            u.bound = bound(u, p, w)
            print("\tPUT:", end="")
            u.print()
            if u.bound > maxprofit:
                PQ.put((-u.bound, u))
                print("\t\tYES")
    return maxprofit