알고리즘 7주차 월요일

Branch and Bound - Best First Search
모든 Node를 방문하지 않는다. 만들지도 않는다. Start에서는 두 개의 Node를 만들지만 Expand를 할 것인가 아니면 그만 둘 것인가를 결정해야 된다. 방문하지 않는다면 경우의 수가 줄어들게 된다. 그럴만한 가치가 있는 지를 판단하는 작업을 해야 한다.

Item should be sorted in descending order according to bi/wi 첫 번째 O1이 단위 무게당 가치가 큰 것이 오게 되는 sorting을 거쳐야 한다.

 

Branch and Bound
각각의 Node마다 Benefit weight bound를 계산한다. 첫 번째 아이템을 Knapsack 집어넣었을 때 이익을 계산해야 한다. Don't choose O1의 Benefit은 0이 되고 Choose O1의 Benefit은 O1의 Benefit이 된다. O2의 경우는 Benefit이 두 개를 더한 값이 된다. Choose의 경우는 들어온 아이템의 benefit이 더해진다. bound는 현재 있는 Node를 밑으로 Expand를 한다고 가정했을 때 아마도 얻을 수 있는 Benefit의 Upper Bound를 의미한다. 밑으로 Node가 있고 Expand가 있어도 이것 이상으로 얻을 수 없다가 Upper Bound가 된다. 내가 최대한으로 얻을 수 있는 가능성이 있는 값을 예측해보는 것이다. 밑으로 내려가봤자 더 얻기 힘들다면 expand를 하지 않는다. level i라는 것에서 Total Weight를 계산한다.
Tot_Weight은 여태까지 Knapsack에 집어넣은 W1 + W2 + .. 에서 시작을 한다. W4를 집어넣을 수 있으면 집어넣고 5번째 아이템을 집어넣을 수 있는 여유가 있으면 또 집어넣.... W, 집어넣을 수 있는 전체 용량을 벗어나지 않는 한에서 계속 집어넣는다. weight은 현재까지 집어넣은 Weight들의 합을 의미하고 그다음 wj는 앞으로 집어넣게 될 Weight들을 의미한다.

 

Branch and Bound
tot_weight 은 지금까지 집어넣은 Weight와 집어넣을 Weight를 말한다. 최대한 아이템의 합이 tot_weight이다. 1번 O 2번 X 3번 O 인 상태라고 해보자 그럼 W1 과 W3이 들어가 있을 것이다. 그 다음 4번 5번 6번을 집어넣을 수 있지만 7번은 못넣는 상황. 나머지 부분이 존재하는데 마치 7번째 아이템을 잘라서 집어넣을 수 있다고 가정을 하는 것. 그렇다면 그렇게 넣게 되면  W - tot_weight에서 잘라서 7번 아이템을 집어넣었을 때를 의미한다. 단위무게당 Benefit이 높은 순서대로 sort를 했기 때문에

 

Branch and Bound
extand를 한 Node들 중에서 Max Benefit이 전역변수로 필요하다. bound가 10이고 max가 20이면 어떻게 되는가? 해당 노드 아래로 extand해봤자 얻을 수 있는 최대가 10밖에 안되므로 extand 할 필요가 없다는 것이다. 만약 bound가 30이라고 하면 30을 받는 보장은 없지만 해볼 만 하기에 Extand를 하게 된다. 

 

Branch and Bound
Promising, 밑으로 expand를 해도 되겠다, nonpromising expand해도 필요없다. bound가 max_benefit보다 작거나 같을때 또는 weight이 W보다 큰 경우 non-promising에 해당한다. promising의 경우 bound가 max_benefit보다 크거나 weight가 W보다 작거나 같은 경우에 promising할 수 있다고 표현한다.

 

Branch and Bound
첫 번째 case는 weight이 W보다 큰 경우 현재 Knapsack 보다 weight가 큰 경우 benefit은 의미가 없게 된다. 두 번째 경우 집어넣을 수 있지만 bound가 Max_benefit보다 작거나 같아서 expand를 할 필요가 없어진다. 이 경우 유효하기는 하지만 Extand할 필요가 없다.

 

Branch and Bound
BFS와 유사하다고 볼 수 있다. 기본적으로 BFS를 apply한다. promising node와 non promising node를 계산하게 된다. 각 노드에서 benefit과 weight, bound를 계산하게 된다. 각각의 node마다 Bound가 계산되는데 가장 큰 Bound를 가진 노드를 중심으로 extand하게 된다. 단위 무게 당 Benefit이 가장 많이 나가는 것을 먼저 나오도록 sort를 한다.  

 

Branch and Bound
(0,0)이라고 하면 knapsack에 아무것도 들어가지 않은 상태를 의미한다. tot_weight은 현재까지 집어넣은 weight이므로 0이 된다. knapsack에 2와 5를 집어넣을 수 있게 된다. bound를 현재 집어넣어서 얻은 이익이 0이고 집어넣을 수 있는 이익은 40 + 30에 해당한다. 그러면 9만큼 남게 되는데, 3번 째 아이템 10을 9만큼 자르면 된다.

 

Branch and Bound
두 개의 Node 중 Bound가 더 큰 왼쪽 Node를 Extand하는 것이 좋다. 

 

---

​
Terms You should know or learn now
Vertex를 node라고 부른다. edge는 연결된 선을 의미한다. Degree라는 것은 몇 개의 Vertex들이 연결되어 있는 가를 말한다. 
Degree of A는 여기서 2라고 볼 수 있다. i라는 Vertex의 Degree는 3이라고 볼 수 있다. Digraph는 Edge의 방향성이 있을 때를 의미한다.
방향성이 있는 그래프를 Digraph라고 부른다. 몇 개의 Edge가 Vertex로 들어오는 가를 의미한다. H는 Indegree가 3이라고 볼 수 있다.
a같은 경우 output degree와 input degree로 볼 수 있다.

Terms you should know or learn now
Wegith는 실수일 수도 있고 정수 있 수 도 있다. Undirect 그래프에서 자기 자신으로 들어가는 graph는 존재하지 않는다.


Direct graph == Digraph Edge가 출발하는 곳을 head라고 하고 도착하는 곳을 tail이라고 한다. Direct Graph에서는 자기 자신으로
연결될 수 있다. 

Symmetric digraph, v에서 w w에서 v 둘다 존재하는 경우.
Complete Graph, 모든 노드가 edge가 연결되어 있을 때를 의미한다.

Size of Graph란. Number of node를 n으로 표현하기도 하고 r로 표현하기도 한다. Number of edge를 m 또는 e라고 표현한다.
Dense Graph는 edge가 많을 때, m = n(n-1)/2를 만족할 때 complete graph라고 부른다. 
Sparse graph는 edge가 적을 때를 의미한다. edge가 하나도 없을 때도 이렇게 부를 수 있다.

Paths and Cycles
P1도 path이고 P2도 path이다. cycle에서 vertex가 두 번 들어가게 되면 simple하지 않다고 표현한다.

Spanning Graph
모든 vertex가 포함되어있다면 그렇게 표현한다.

conected component 는 maximal connected subgraph라고 할 수 있다. 일부분은 connected component가 될 수 없다. 전체적으로 
살펴봐야 한다.

strongly connected digraph
u에서 v로 갈 수 있고 v에서도 u로 갈 수 있어야 한다. Acycle은 ciycle이 없는 겨우 Directed acyclic graph를 DAG라고 부른다. 

Example
Direct graph이다. 초록색 지역은 Strongly Connected Graph이다. 서로 양방향으로 어떻게든 갈 수 있다. vertex가 하나여도 가능하다.

Trees
tree라는 것은 graph이면서 Connected 되어있어야 한다. cycle이 존재하지 않는다,

Spanning Graph
원래 Graph에서 포함되고 있는 모든 Vertex를 포함해야 하는데 이와 동시에 Tree 구조를 만족할 수 있어야 한다.

Graph adjacency Matrix