Constraint satisfaction problems

줄여서 약자 CSP 이야 이번장 부터는 문제를 이용해서 이론을 도출하는 식으로 한번 공부를 해볼려고 한다.

먼저 기본적인 개념을 잡고 가자
우선 Constraint satisfaction problems(CSP) 문제를 푸는데 있어서 어떤 제약을 만족해야 되는 그런 문제를 말한다.

state는 Variable Xi 로 나타내고, domain Di 에서 오는 value 값을 지닌다.
goal테스트를 만족하기 위해서 set of constarint를 만족 하여야 한다.

이것을 간단히 Map-coloring 예제로 나타내면 다음 그리과 같다.

다음과 같이 Varialble은 지도의 지역들 지역들이 가지는 색깔값들은 domain Di에서 오게 되고 Constraint는 위와 adjacent 하는 지역은 다른 컬러를 지녀야 한다는 것이다.


1. 강의록 12 ~ 13 페이지에 소개된 backtracking search를 이용하여 4-queens problem을 풀면 어떻게 될지 강의록 17 페이지에 보인 것과 같은 형태로 그려보라.

먼저 backtracking search가 어떻게 돌아가는건지 한번 알아보도록 하자.

다음과 같이 Varialble은 지도의 지역들 지역들이 가지는 색깔값들은 domain Di에서 오게 되고 Constraint는 위와 adjacent 하는 지역은 다른 컬러를 지녀야 한다는 것이다. 이것을 토대로 이제 문제도 한번 풀어보자.

이런식으로 문제를 쉽게 풀 수 있다.

2. Backtracking search를 이용하여 graph coloring problem을 풀기 위해 most constrained variable과 most constraining variable 및 least constraining value heuristic을 모두 사용하면서 forward checking까지 적용하고자 핚다. 아래 graph의 node들에 {Blue, Green, Red}를 칠핛 경우 생성되는 search tree를 그려보라. 단, variable이나 value의 우선 순위가 같을 경우에는 그 이름의 alphabet 순을 따라 선택핚다.

이문제를 풀기위해서 백트래킹도 알아야 하겠지만 most contrained variable 과 most contraining variable, least constraining value heuristic, forward cheking 까지 알아야 한다.

most constrained variable
fewest legal value를 선택을 한다.

most constraining variable
영향을 제일 많이 주는 variable 부터 선택을 한다.

least constraning value
영향을 가장 적게 주는 value 부터 선택한다.
-> 남아 있는 variable중 fewest value 선택

forward cheking
어떤 variable 이든 더이상 legal value가 존재 하지 않으면 종료를 하는것이다. variable에 value를 assign 하면서 다른 남은 variable들에게 어떤 value가 assign될 수 있는지 항상 체크 하는것이다.

요렇게 푸는 것이다.

3. 위 2번 graph의 B에는 Red 그리고 F 에는 Green이 지정되어 있는 상태에서 forward checking과 arc consistency algorithm을 적용하고자 핚다. 교과서 Figure 5.7의 AC3 algorithm을 이용핛 경우 종료 시까지 총 몇 개의 arc가 처리되고 몇 개의 arc가 다시 queue로 insert되며 또핚 최종 결과는 어떻게 되는가? 단, queue에는 arc들이 다음과 같은 순서로 들어 있다고 가정핚다: AB, BA, AD, DA, AE, EA, BC, CB, BE, EB, CE, EC, CF, FC, DE, ED, EF, FE.

Arc consistency 가 뭔지를 알아야 한다.