제약조건 전파

소개글

제약조건 전파에 대한 보고서 자료입니다.

목차

1.1 Source

1.2 검색 결과

1.3 설명

2.2 설명

본문내용

제약조건 전파는 1행부터 8행까지 차례대로 제약조건에 걸리지 않도록 단계적으로 퀸을 놓는다. 만약 1행에 1열을 퀸을 놓으면 2행에는 1열 2열을 제외한 3열에서 8열까지 모두 퀸을 놓을 수 있다. 이 때 각각의 퀸에 대하여 그 이후 단계의 경우의 수를 모두 계산하여 퀸을 놓게 된다.
소스의 main() 함수를 보면 Initialize(), Calculate(); 함수 두개가 있다.
Initialize() 함수는 퀸을 놓을 판을 초기화한다.
Calculate() 함수는 단계별로 퀸을 제약조건에 걸리지 않는 자리를 모두 검색하여 퀸을 놓는다. 이 함수는 재귀 호출로 깊이 우선 탐색 방법을 이용하여 각 단계별로 퀸을 놓는데 퀸의 개수가 8이면 종료하게 된다.
만약 퀸의 개수가 8이면 각 행마다 퀸을 다 놓았기 때문에 Display() 함수로 화면에 출력한다.
그렇지 않으면 해당 행마다 제약조건에 걸리지 않는 열을 검색하여 퀸을 놓는다.
각 행과 열의 제약조건 검사 방법은 다음과 같이 충돌이 없는 가로 열을 먼저 선택한 후 대각선 방향으로 퀸이 걸리는지 모두 검사하여 충돌이 나지 않는 곳에 퀸을 놓는다.
.
2.2 설명
휴리스틱 교정은 1행부터 8행까지 임의로 퀸을 놓은 다음 제약조건에 만족하도록 퀸을 교정해 나가는 방법이다. 1행에서 각 열의 충돌횟수를 검사하여 가장 충돌이 적은 열으로 퀸을 옮긴다. 이 때 만약 가장 충돌이 적은 열이 두 군데 이상이면 각각의 수를 모두 계산하여 퀸을 교정하게 된다.
1행부터 8행까지 교정해 하였는데도 제약조건에 만족하지 못하면 다시 1행부터 교정해 나간다.
만약 다음 예와 같이 가장 적은 충돌 횟수가 둘 이상일 경우 각각의 경우를 다 교정하게
소스의 main() 함수에서 ‘종료’, ‘초기 예제’와 ‘갑 입력’ 세 가지 메뉴가 있다.
종료는 말 그대로 프로그램을 종료하는 것이고 초기 예제는 교재에 있는 8퀸 문제를 해결하는 것이고 값 입력은 사용자가 직접 퀸을 놓을 위치를 입력 받도록 하였다.
main() 함수는 크게 Default(), Input(), Display(), Repair() 함수로 구성되어 있다.
Default() 함수를 실행하면 퀸을 놓을 위치를 초기 값이 입력 된다.
Input() 함수는 사용자가 직접 퀸을 놓을 위치를 입력 받는다.
Display() 함수는 교정 전의 퀸의 위치가 출력된다. 이 함수는 Repair() 함수 내에도 있는데 이 때는 교정 후 위치를 출력된다.
Repair() 함수는 단계적으로 각 행마다 최소 충돌횟수가 되는 열에 퀸을 놓는다. 이 함수는 재귀 호출 방법으로 깊이 우선 탐색 이용하여 각 단계별로 퀸을 교정해 나간다. 8행에서 퀸을 교정완료 했을 때 제약조건에 걸리지 않는지 확인을 위하여 다시 1행부터 8행까지 검사한다 만약 제약조건에 걸리지 않으면 Display() 함수로 화면에 출력한다.
각 행과 열의 충돌 횟수 검사 방법은 다음과 같이 대각선 방향과 가로 방향을 모두 검사하여 충돌 횟수를 카운트한다.
- 10 -

키워드

제약조건,   인공지능,   Constraint,   Satisfaction,   제약 만족 문제