[Algorithm] 개념 2 정리

시간복잡도 정리

 

Dynamic

• 최단경로 : n^3
• 0-1배낭 : min(2^n, nW)
• 최적이진탐색트리OBST : n^3

Backtracking

• 그래프 색칠 노드의 수 : m^n

Branch and Bound

• 0-1배낭 : 2^n

 

방법 핵심 정리

1. Dynamic: 작은 부분들부터 계산해서 Bottom-up으로 올라가며 작은 부분들의 결과를 이용해 다음 단계 결과를 계한하는 것. 의존적. 한번 계산한 값은 바뀌지 않음
   principle of optimality 최적성원칙을 만족해야 함 - 큰 문제의 최적해는 최적의 작은 문제 해들로 구성되어야 함
   최적화 문제
2. Backtracking : state space tree를 사용해 bound를 만족하는 노드에 대해 promising유망함을 점검하고 유망한 노드만 그 자식노드들을 탐색함. 유망하지 않으면 이전 노드로 돌아감backtrack
   최적화, 결정문제
   • monte carlo 수행시간 측정 : 같은 레벨에서 각 노드의 promising점검 방법이 동일, 같은 레벨의 각 노드가 같은 수의 자식
     -전형적인 경로를 무작위로 생성하여 그 경로상의 노드 수를 셈 - 반복해서 평균치.
3. Branch and Bound : 현재 노드의 경로에서 나올 수 있는 최적의 결과값인 bound를 계산해 promising여부 점검
   큐에서 가장 bound값이 좋은 노드를 꺼내 아직도 현재 최적값보다 좋을 가능성이 있는지 점검하고 그 직속자식노드들을 탐색함. 탐색하면서 bound값을 계산해서 현재까지의 최적값보다 좋으면 큐에 넣음.