반응형 prim1 Greedy Algorithm Design Pattern 1(탐욕 알고리즘) 이번에 알아볼 디자인 패터은 탐욕 알고리즘(GA, Greedy Algorithm)이다. 해당 디자인 패턴은 저번에 알아본 동적 계획법과 마찬가지로 최적화문제(max/min)를 해결하는데 쓰인다. 즉 문제가 최적 부분 구조를 가지고 있어야 한다고 했었다. 이에 대해 다시 짚고 넘어가자면 origin program의 최적해(solution)가 부분 문제의 최적해들로써 구성되어야, 그 문제가 최적 부분 구조를 가졌다고 할 수 있는 것이다. 이전 글의 예시들을 다시 본다면 이해할 수 있을 것이다. 계속하자면, GA의 설계 전략은 최적해를 얻을 때까지 일련의 절차를 따르는데, 이때 현재 단계의 action에 따른 일련의 과거/미래 단계의 action의 잠재적 단점은 고려하지 않는다(\(A_{1} \rightarr.. 2021. 10. 19. 이전 1 다음 반응형
