조합 최적화 기법 분류

1. P vs NP

1) P-Class (Polynomial)

- 현재 컴퓨터 기술로 해결할 수 있는 식

- 일반적으로 O(n^3)이하인 식

2) NP-Class (Non-deterministic Polynomial)

- 말 그대로 아직 결정되지 않은 식

- 현재 컴퓨터 기술로 해결할 수 없는 식

- 양자컴픁터를 사용하면 p가 되어 풀수 있다. → O(2^n), O(n!)의 경우에 해당

2. 전역최적해법 vs 지역최적해법

1) 전역최적해법

- 항상 최선의 결과를 가짐 (강점)

- 구현하기 위해 많은 시간과 메모리 공간을 요구 (약점)

- ex) BNB, Dynamic Programming, Backstacking

2) 지역최적해법

- 구현이 비교적 간단하다. (강점)

- 복잡하고 대구모인 문제에서 매우 좋은 해를 빨리 찾는다. (강점)

- 초적의 결과가 보장된다면 최적의 해를 보장한다 (강점)

- 보장이 되지 않는다면 최적의 결과가 나오지 않을 수 있다. (약점)

- ex) Greedy Heuristic, Metaheurstics (Simulate Aneeling, Tabu search, Genetic Algorithms, etc)

3. 머신러닝

- 경험을 통해서 나중에 유사하거나 같은 일을 더 효율적으로 처리할 수 있도록 시스템의 구조나 파라미터를 바꾸는 것

- 컴퓨터가 지식을 갖게 하는 것

- 지도학습 vs 비지도학습

1) 지도학습

- 머신러닝의 한 방법

- 주어진 정답을 이용해 미지의 데이터데 대한 미래값을 예측한다.

- ex) k-NN, k-NCN, NB, SVM, Logistic Regression, NN, Decision Tree, LDA 등

2) 비지도학습

- 입력된 데이터를 가지고 패턴 및 특성 들을 발견한다.

- ex) 군집분석, 계층분석, 딥러닝

3) 강화학습

- 답을 직접적으로 주지 않고 경험을 통해 기대 보상이 최대치가 되도록 하는 학습

- 어떤 모르는 환경에서 동작하는 에이전트가 있을 대 현재 상태에서 향후 기대되는 누적 보상값이 최대가 되는 행동을 선택하는 정책을 찾는 것