📕 잠깐 내가 이해한게 맞는지 정리

 

 

• Dynamic Programming
• Greedy 
• Back Tracking
• Branch and bound

 

• Greedy는 반례가 있어서 적용 안되는 경우가 있다.
  - 0-1 knapsack problem
• Greedy가 적용되지 않는 경우 Dynamic Programming 을 쓴다.
• Dynamic Programming 이 적용되지 않을 때 BackTracking을 쓴다.
  - Dynamic Programming 은 2^n의 부분집합을 검사하니까 오래걸리는데 이걸 Backtracking이 Tree 형태의
  pruned state space tree 로 promising 하는 경우만 check 한다.
• Backtracking 에서 발전된게 Branch and bound 이다.

 

그리디는 local 한 최적해를 구하고

그게 global 하게 최적한지는 우리가 증명해야하는거니까

n 인거고 backtracking 은 최악에 전체 부분집합

 

그리디가 global 하게 최적화된 해라는게 증명되면 그리디가 대부분 빠름