Today, I Learned

1. AI

Berkeley CS 188

Arc Consistency and Beyond.
Limitations: 솔루션이 남아있지 않은 경운데, Consistency한 경우가 있음. -> K-Consistency

K-Consistency
1-Consistency: Node Consistency(Unary Consistency)
2-Consistency: Arc Consistency
k-Consistency: k개의 노드를 한번에 생각하는 경우임. k가 올라갈수록 당연히 cost는 비싸짐.

Strong k-consistency는 1,2,...k-1 consistent까지 만족한다는 뜻이고,
Strong n-consistency = backtrack 없이 문제를 풀 수 있다는 것임.

Independent subproblems는 별개의 문제로 본다. 근데 이게 얼마나 효과적일까? 전혀 안효과적임. CSP자체가 서로 얽힌 문제 를 푸는건데, 그 속에서 Independent problem으로 쪼갠다? 어림도 없음

Loop이 없는 constrain graph의 경우 n * d^2 타임에 풀 수 있음 <=> d^n에 비하면 엄청 엄청 작은 숫자.

Iterative Algorithm

• is one of local search
  일단 던져놓고, conflicts를 최대한 줄이는 방향으로 수정해나가는 것.

  바꿨는데 새로운 문제를 야기할 수 있나? ㅇㅇ
  안 끝날수도 있나? ㅇㅇ
  기다리면 optimal solution 나오나? ㄴㄴ
  왜쓰냐? 빠르다.

Local search
Complete? ㄴㄴ
Optimal? ㄴㄴ

Simulated Annealing - 경우에 따라 내려가는 선택을 하면서 최적을 찾아가는 방법
Genetic Algorithm
- 어떤 답의 일부와 다른 답의 일부를 합쳐 새로운 답을 얻어내는 것.
optimal? ㄴㄴ