Today, I Learned
1. AI
What is search for?
search는 문제의 한 종류이며, 어떤 문제를 search를 통하여 해결할 수 있다면 그 방법을 사용하는 것.
search 를 할 때는, 우리는 길도 알아야 하고, 그 길을 어떻게 찾아갈지에 대한 정보를 바탕으로 풀어야함.
그리고 그 길이 어떤 길이고, 어떻게 도달할지에 관심이 큼.
그것과 다른 "Identification problem" 같은 경우 path에는 관심이 없고, 그냥 할당하는 문제 자체에 관한 것.
Constrain을 표시하는 방법들
1. Implicit하게 표시 WA != NT
snnipet of code 로써 코드단에서 실행할 때 violate한지 판단할 수 있게 표시하는 방법
2. explicit하게 표시 (WA, NT) is one of (red, green), (red, blue) ...
pair가 가질 수 있는 영역을 나타내는 것.
그래서 솔루션의 formation은?
WA=red, NT=green .. 등 과 같이.
N-Queen 문제에서,
Variable을 squares라고 하면? X_ij Domain은 queen이 있거나 없거나 {0,1} 둘 중에 하나. Constrain은? explicit하게 4개, Implicit하게 퀸의 숫자는 n개라고 하나 둬야함. -> constrain도 많고 그렇게 좋은 formulation이 아님.
Variable을 각 Row라고 하면? Q_k Domain은 queen이 있는 위치 {1,2, ... N}. Constrain은? explicit하게 (Q_1, Q_2) is one of (1,3), (1,4)...
Constrain Graph에서,
각각의 Edge는 어떤 constrain이 있는지를 알려주지는 않지만, 해당 위치에 constrain이 존재한다는 사실을 알려줌.
자 그럼 아까 이해 안됐던 cryptarithmetic의 graph에서, variable은 F T U W R O X_1, X_2, X_3 가 되고, constrain을 정해보면
O + O = R + 10X_1 처럼 어떤 Constain은 2개 이상의 variable과 관계 된것을 알 수 있음. 이를 그래프에 나타내보면, 원래는
constrain이 있는 애들끼리만 연결해줬었는데, 어떻게 연결할거냐? 2개 이상을? 그래서 네모가 나옴. 네모를 통해서 연결하는 거고 수업때 4 constrain 까지 나온다는 거는,
U, W, X_1, X_2가 관계된, 또는 F, T, U, W, R, O가 서로 달라야한다는 constrain등 up to 6개와 관련있는 constrain이 생기는 거임.
Sudoku에서의 Constrain들
column 다 다르고, row다 다르고, 작은 상자 다 다름. 추가적으로 이미 채워져 있는 영역은 unary constrain을 가지는 것과 같다고 볼 수 있음.
Solve CSP
Goal test를 할 때, assignment가 complete 되었는지, constrains를 다 만족하는지 두가지를 체크해야함.
Backtrack에 도움을 주는 과정인 Filtering
- Forward checking
WA를 색칠했을때, Backtracking은 끝. 근데 Forward checking은 인접한 혹은 관련있는 애들 찾아보면서 걔네가 가능한 영역 줄여나가야함.
이미 불가능하다는것을 알 수 있는 상황이 있지만, Forward Checking은 assign한 애와 unassign된 애들만 보고 가려나갈 뿐, 미리 detect하는 애는 아니기 때문에 그럴 수 있음.
즉, It doesn't detect looming conflicts between unassigned and other unassigned variables.
- Consistency of A single Arc
X -> Y 의 Consistency를 체크할건데, assign된 놈을 Head(Y)에 두고, 다른애들(X)에 대해서 Y와 conflict를 가지는 애들을 지움.
"Delete from the tail"인데, 하나라도 만족하는 domain은 남겨두는 거임.
근데, 어떤 변수에서 domain을 하나라도 지우는 순간, 그 도메인을 가리키는 모든 arc에 대해서 확인을 다시 해야함. -> 미리 detect할 수 는 있지만, 거기서 overhead가 발생함.
Ordering
- "Pick variable with fewest domain left"
왜 Min? not Max?
어차피 모든 variable을 모두 할당해야하는데, Fail first 하는것이 도움이기 때문에. 그니깐 어차피 맞을거 먼저 맞는게 낫다는 마인드.
- "Least Constraining Value"
왜 빡센거 부터 안하고?
어차피 모든 variable을 모두 할당해야하는데, 빡센걸 할 필요가 없음. 그냥 널널한거 부터 해서 되면 장땡.
