정리 블로그

1. Constraint Satisfaction Problem
 - Variable과 Domain 사이의 제약조건을 통해 미리 Variable에 대한 Domain을 제한하여 수행 속도를 올리는 방법

2. Map-Coloring Problem

 - 위처럼 나눠져 있는 지도에서 3개의 색으로 인접한 구역의 색과 겹치지 않도록 칠하는 방법이 있는지를 구하는 문제
 - Constraint graph를 통해 인접하는 구역을 표현할 수 있고, 해당 그래프를 이용해 색칠 하는 것이 가능

3. Varieties of Constraints
 - Variable의 수에 따라 분류 가능
 - Unary constraints : 하나의 변수를 특정 도메인으로 제약하는 Constraint
 - Binary constraints : 두개의 변수로 제약하는 Constraint
 - higher-order constraints : 3개 이상의 변수로 제약하는 Constraint

4. Cryptarithmetic

       T W O
    + T W O
    -----------
     F O U R
 - 같은 문자의 경우 같은 숫자이며 해당 연산 결과와 맞는 경우가 있는지 찾는 문제
 - Constraint를 정의하여 문제 풀이 가능

5. Real-world CSPs
 - Assignment Problems : 누가 어떤 과목을 강의 할지
 - Timetabling problems : 어떤 class를 언제 어디서 강의 할지
 - Transportation scheduling : 배송을 효율적으로 하는 방법

6. Backtracking search
 - 가능한 경우의 수를 모두 해보는 방식으로 graph에서 dfs방식으로 탐색.
 - 모든 경우의 수를 탐색하므로 정확한 결과를 얻을 수 있지만 필요 없는 계산이 너무 많음.(Cost가 높다)

7. Most constrained variable
 - 가장 단순한 방법으로 가능한 경우의 수 중 가장 빠른 것 부터 적용하는 방법

8. Most constraining variable
 - 가장 많은 연관성(제약)을 가진 곳부터 Domain을 할당하는 방식

9. Least constraining value
 - Domain 중 영향을 가장 적게 주는 value를 선택하는 방식.

10. Forward checking
 - 특정 variable의 value를 정해주고 난 뒤, constraint에 의해 value가 선택되지 않은 variable의 domain이 바뀌게 되는데,
   바뀔 때 마다 Domain을 바꿔 주어서 연산을 줄이는 방식

11. Arc consistency
 - 특정 Variable의 value가 정해졌을 때, constraint에 의해 value가 선택되지 않았을 경우 variable의 domain이 바뀌게 되고,
   해당 Domain의 남은 수가 1개일 경우 해당 value만 가능하므로 이 value를 선택했을 경우를 가정해 다시 Domain을 계속 줄여나가는 방식
 - AC-3 알고리즘이라고 불린다.

1. Game Playing

 - Game Playing은 AI research의 좋은 문제이다. 

 - 결과가 간단하고, 평가하기 쉽다.

 - 특정 시간 안에 decision making을 해야 한다.

2. Game Playing as Searching

 - 두 명이서 하는 턴제보드게임일 때

 - states          : 보드의 상태

 - operators     : 규칙에 맞게 움직이는 경우들

 - initial state    : 현재의 보드 상태 

 - goal state     : 최종적으로 이기거나 지는 상태

3. Minimax Algorithm

 - 현재  상태에서 수행 가능한 operator로 진행했을 때, AI 턴일 때는 점수가 가장 높은 쪽으로, 상대방 턴일 때는 점수가 가장 낮은 쪽으로 가도록 한다.

1) 0 번위치가 현재 보드 상태라고 가정하고, depth는 4까지 탐색한다.

    (네모는 AI의 선택으로 움직일 수 있는 상태들, 동그라미는 상대의 선택으로 움직일 수 있는 상태들이다.)

    (각 네모, 동그라미 속 숫자는 클수록 AI에게 유리하다.)

 2) 왼쪽으로 계속 내려가서 4의 가장 왼쪽 노드까지 내려간다. 10과 무한대를 비교

 3) 3에서 4로 갈때는 상대의 선택이므로 AI에게 가장 불리한 선택을 한다고 가정하고 10을 선택한다.

 4) 그 뒤, 오른쪽을 탐색하고 5라는 결과를 불러온다.

 5) 2에서 3은 AI의 선택이므로 5와 10 중 더 큰 값을 가져온다.

 6) 위 과정을 계속 반복하면 -7이 가장 크므로 -7 쪽으로 움직인다.

4. Alpha-Beta Pruning

 - Minimax algorithm을 기반으로 더 빠르게 노드들을 탐색하기 위한 알고리즘

 1) Alpha Cutoff

   a) 처음 D와 E를 비교했을 때, D가 더 작으므로 B는 5가 된다. ( alpha = 5 )

   b) 그 다음 오른쪽으로 내려가서 F를 탐색한다.

   c) C는 F와 G 중에서 작은 수를 가져온다. F가 4라면 G가 어떤 수라도 C가 4보다 클 수 없다.

   d) 이미 alpha값이 5이므로 C는 4를 가져오고 G를 보지 않는다.

 2) Beta Cutoff 

   a) 처음 H와 I를 비교했을 때, I가 더 크므로 D는 5가 된다. ( beta = 5 )

   b) 그 다음 오른쪽으로 내려가서 J를 탐색한다.

   c) E는 J와 K 중에서 큰 수를 가져온다. J가 10라면 K가 어떤 수라도 E가 10보다 작을 수 없다.

   d) 이미 beta값이 5이므로 E는 10를 가져오고 K를 보지 않는다.

Genetic Algorithm

1. n-Queen Problem

 1) 문제 정의 : N x N 크기의 체스판이 주어질 떄, N개의 퀸이 서로 공격이 불가능하도록 놓는 경우를 구하는 문제

 2) ex : N = 4

2. Genetic Algorithm

 1) Fitness function으로 Fitness 검사 : 어느 정도 해에 가까운지 수치값으로 나타내는 함수로 수치값을 계산

 2) 검사된 결과 중 가장 높은 값은 두 개, 다음 높은 순으로 두 개를 뽑아 서로 형질을 바꾼다.(유전)

 3) 거기에 랜덤(자리, 번호 둘다)으로 형질을 바꿔준다.(돌연변이)

   ex) ①( 3 3 4 2 )   4  4/7      ①( 3 3 | 4 2 )           ( 3 3 | 1 2 )          ( 3 ① 1 2 )

        ②( 1 2 1 2 )   1  1/7      ②( 1 2 | 1 2 )           ( 1 2 | 4 2 )          ( 1 2 4 2 )

        ③( 1 2 3 4 )   0  0/7      ①( 3 | 3 4 2 )           ( 1 | 3 4 2 )          ( 1 3 4 ④ )

        ④( 1 1 1 3 )   2  2/7      ④( 1 | 1 1 3 )           ( 3 | 1 1 3 )          ( 3 1 ③ 3 )

               ⓐ                                ⓑ                       ⓒ                      ⓓ

   ⓐ         : Fitness 검사 : 두개씩 퀸을 페어로 봤을 때 서로 공격이 불가능 한 페어의 개수를 센 값이 클수록 Fitness가 높다.

   ⓑ ~ ⓒ  : 유전 나누는 구간을 랜덤으로 정해 서로 바꾼다(위 예제에선 ①이랑 ②, ③ 이랑 ④를 바꿨다)

   ⓓ         : ⓒ가 끝난 뒤, 특정 지점의 번호를 바꿔준다.(돌연변이)

3. 장단점

 1) 장점

   ① 거의 최적에 가까운 해(near optimal)를 빠르게 찾아낼 수 있다.

   ② parallel 작업이 가능하다

 2) 단점

   ① 어떤 방식으로 최적을 구했는지 재현이 거의 불가능하다.