Greedy

• 과거 미래 고려 X
• best at the moment(local optimal)
• solution is always optimal

Coin Change

• Selection Procedure
  • 가장 금액 높은 코인 먼저
• Feasibility Check
• Solution Check
• EX
  • make 36 out of 25 10 10 5 5 1
    • 25+10+1 =36 ⇒optimal

while(코인이 있고 instance 해결 안되면) {
	Grab the Largest Coin;
	if(목표값보다 커지면)
		reject the coin
	else
		add the coin to the change;
	if(목표값과 같다면)
		instance 해결;
}

Minimal Spanning Trees

• 그래프 G(V,E) 있을 떄, G의 모든 vertices 포함 하면서 tree 여야 한다.
  • Tree: V = n, E= n-1
• T=(V,F), F ⊆ E
• MST란 그런 신장트리(Spanning Tree) 중 가장 weight 가 작은 것.

Prim’s Algorithm

1. 시작 정점(vertice)에서 최소 가중치의 간선(edge)로 연결된 정점을 MST에 추가
2. MST에 인접한 정점 중 최소 가중치 간선 정점 선택해 추가
3. MST의 간선이 V-1개가 될 때까지 반복

$T(n) = n^2$

• nearest[i] : v_i에 가장까가운 정점 in Y. distance[i]: v_i와 nearest[i]사이 weight, vnear : 추가될 정점
• Y에 어떤 정점을 넣을지 정하기 위해선 매 iter마다 계산해야

//W[i][j] : 정점 i에서 정점 j 사이 weight
void prim(int n, const number W[][], set_of_edges& F){
	index i, vnear;
	number min;
	edge e;
	index nearest[2..n];
	number distance [2..n];
	F=0;
	
	for(i=2;i<=n;i++){
		nearest[i]=1;
		distance[i]= W[1][i];
	}

	repeat(n-1 times){ 
	//edge 개수가 n-1개 이기 때문에
		min=INF;
		for(i=2;i<=n;i++)
			if(0<=distance[i]<min){
				min = distance[i];
				vnear=i;	
			}
		e = edge; // vnear과 nearest[vnear]을 연결하는 edge
		add e to F;
		distance[vnear]=-1
		for(i=2;i<=n;i++)
			if(W[i][vnear]<distance[i]){
				distance[i] = W[i][vnear];
				nearest[i]= vnear;
			}
	}	
}

Kruskal’s Algorithm

1. 그래프의 간선을 오름차순(nondecreasing order)로 정렬.
2. 순서대로 사이클을 형성하지 않는 간선 선택.
3. 해당 간선을 MST에 추가
4. 모든 간선에 대해 (2)과정 반복.

Dijkstra’s Algorithm for Signle-Source Shortest Paths

• weighted,directed graph에서 v1에서 다른 모든 vertices로의 최단 거리를 구한다.

High level

Y = {v1};
F = 0;
while (instance 해결할 때까지){
	V-Y에서 vertex v 고른다,
		그 vertex는 v1에서 최단거리를 거진다.
		오직 Y에 있는 vertices를 중간지점으로 사용한다.
	vertex v를 Y에 추가한다;
	edge를 F에 추가한다;
	
	if(Y==V) // 해결
		instance is solved;
}

• $touch[i]$ : index of the v in Y
• $length[i]$ : v_1에서 Y에 있는 정점만을 거쳐 v_i까지 최단거리

$length[i] = length[vnear]+W[vnear][i]$

void dijkstra(int n, const number W[][], set_of_edges& F){
	index i, vnear;
	edge e;
	index touch[2..n];
	number length[2..n];

	F=0;
	for(i=2;i<=n;i++){
		touch[i]=1;
		length[i] = W[1][i];
	}

	repeat(n-1 times){
		//vertices가 n-1개
		min=INF;
		for(i=2;i<=n;i++)
			if(0<=length[i]<min){
				min = length[i];
				vnear = i;
			}	
		e = edge // touch[vnear]
		add e to F;
		for(i=2;i<=n;i++)
			if(length[vnear] + W[vnear][i] < length[i]){
				length[i] = length[vnear]+W[vnear][i];
				touch[i] = vnear;
			}
			length[vnear]= -1; // vnear을 Y에 추가한다.
	}
}

$T(n) = 2(n-1)(n-1)$

Scheduling

Minimize Total Time in the System

EX) t_1 = 5, t_2 = 10, t_3 = 4

[1,2,3] : 5+ 5+10 + 5+10+4 = 39

[3,1,2]: 4+ 4+5 + 4+5+10 =32

Smallest service time first

$T(n) => \theta(n\log n)$

GA is optimal

Proof)

S : t_1,t_2….,t_i t_i+1,….,t_n → T

S: t_1,t_2,…,t_i+1, t_i,…,t_n → T

X = t_1+…+t_i-1

$T = X + (x+t_i)+(x+t_i+t_{i+1})$

$T' = X + (x+t_{i+1})+(x+t_{i+1}+t_{i})$

$T' = T+t_{i+1}-t_i <T$ ⇒ 모순 발생!

Scheduling with Deadlines

Maximize the total profit

EX) D= (2,1,2,1) , P= (30,35,25,40)

[2,1] : 35+ 30 = 65

[4,1] : 40+ 30 = 70

Job을 Profit높은 순으로 정렬 후 데드라인에 맞게 선택한다

void schedule(int n, const int deadline[], sequence_of_integer& J){
	index o;
	sequence_of_integer K;
	J=[1];
	for(i=2; i<=n; i++){
		K = J with i addded according to nondecreasing values of deadline[i];
		if (K is feasible)
			J=K;
	}	
}

$W(n) => \theta(n^2)$

4.4 Huffman

• Data Compression
• 최적의 Prefix-free Binary code를 찾는다
• 빈도수 높은 건 짧게, 빈도수 낮은 건 길게 바꾼다

struct nodetype{
	char symbol;
	int frequency;
	nodetype* left;
	nodetype* right;
};

• PQ 사용해서 우선순위 높은 노드부터 remove한다.
• Min Heap 사용

$T(n) = (n-1) * (Min-Heap-opreations) = (n-1)*(\log n) = \theta(n\log n)$

4.5 Knapsack Problem

Fractional KSP → Greedy Approach : Select item by Largest profit per weight

0/1 KSP → Greedy X

• Greedy 적용하면 profit/weight가 큰 순으로 선택하게 되는데 이것이 전체 문제에 대한 최적해로 이어지지 않을 수 있다.

DP for 0/1 KSP

KNAP(s,Y) :

• item : 1 2 … s … n
• maximize $\sum_{i=1}^s p_ix_i$
• $\sum_{i=1}^s w_ix_i \le Y$

$y_1, y_2, y_3 ..., y_n$ ⇒ Optimal Sol for KNAP(n,W)

만약 $y_n=0$ (n번째 아이템을 선택 안 할때) → $y_1,...,y_{n-1}$ 이 KNAP(n-1,W)의 optimal sol이다.

ex) W=10, P=(10,4,3,5,2), W=(5,4,2,3,2) 일 때

Y = (1, 0, 1, 1, 0)이면 (1,0,1,1)이 W=10, P=(10,4,3,5), W=(5,4,2,3)의 최적해다.

만약 $y_n = 1$ (선택한다면) $y_1,...,y_{n-1}$ 이 KNAP(n-1,W-wn)의 optimal sol이다.

$P[n][W] = \max(P[n-1][W], p_n + P[n-1][W-w_n]) ,w_n\le W$

$w_n>W, P[n][W] = P[n-1][W]$

시간복잡도 : $O(nW)$

문제 크기에 따라 계산시간 다르다