전공/알고리즘

Greedy Algorithm

nongdamgom 2024. 4. 19. 23:26

Greedy Algorithms

Design : BF -> D&C -> DP -> Greedy 
DP : optimal solution -> O(n^3) : NOT practical in fields
Design Naming >> BF. D&C. DP(=mathematical programming)
>> Greedy의 의미는 무엇인가요? 

* Greedy algorithm: sprit - 학생들마다 greedy 설계는 달라질 수 있다.
* Real-life problems: mostly optimization problems.

If we assume, "local optimal --> global optimal" "Greedy"

Greedy Algorithm:
Grabs data items in sequence, each time with BEST choice, without thinking Future.
--> BEST choice: local optimal choice(o), global(x)
---> in terms of my viewpoint(intuition, heuristics 경험)


Q. Why GREEDY algorithm is so important in CS?


Example: MST Minimum Spanning Tree (spanning tree == 모든 vertax들이 다 연결되어있는 tree)
MST == edge들의 연결이 가장 짧은 모든 vertax가 연결된 tree



MIT :  Minimum Spanning Trees

더보기

MST applications: smartphone, KTX railway, Network망 사업자
---> 많은 문제들의 MODELing.


Question: Solve MST --> 기말시험.
--> Brute-force solution algorithm for MST
--> D&C, DP algorithms for MST
--> Greedy algo, for MST
--------> comparison using TC. -----> which one is BEST.

 

Greedy Algorithm <Design>

-----------------------------------
while NOT solved yet {
Step1. Selection (local optimal choice, ranking) 

=> 각 선택에 있어서 우선순위 판단
Step2. Feasibility (contraints, optional) 

=> step 1에서 이미 제약조건 만족하는것만 했다면 건너 뛸 수 있는 단계 ( 내가 선택한 우선순위가 문제 조건에 맞는지)
Step3. Solution check ( termination )
}

 


Example: MST (Minimum Spanning Tree)

Greedy_MST(input: graph G=(V,E)

 => 반드시 optimal을 주도록 design 되는 것이 아님, Minimum 이 되도록 내가 그냥 Local Optimal Choice 를 준거임
-------------------------------------------

F = empty set
while NOT solved yet{
	Select an edge 'e' (LOC) ==> ranking(scoring) function(그리디에서 가장 중요)
	if e creates NO cycle then add e to F
	if T = (V,F) is a Spanning Tree, then stop/exit. 
}


==> output: MST = T(V,F) F is a subset of E. ( 모든 vertex를 포함하는 minimum edge들의 subset F)

 

How to select 'e'?

=> Prim's alg, Kruskal's algo.