제약 프로그래밍

3. 제약 논리 프로그래밍

제약 논리 프로그래밍은 제약 조건을 호스트 언어에 포함시키는 것이다. 처음 사용된 호스트 언어는 논리 프로그래밍 언어였으므로 이 분야는 처음에 제약 논리 프로그래밍이라고 불렸다. 두 패러다임은 논리 변수 및 백트래킹과 같은 많은 중요한 기능을 공유한다. 오늘날 대부분의 프롤로그 구현에는 제약 논리 프로그래밍을 위한 하나 이상의 라이브러리가 포함되어 있다.^[1]

제약 프로그래밍과 논리 프로그래밍의 차이점은 주로 세계를 모델링하는 방식과 접근 방식에 있다. 일부 문제는 논리 프로그램으로 작성하는 것이 더 자연스럽고 간단하며, 다른 문제는 제약 프로그램으로 작성하는 것이 더 자연스럽다.^[1]

제약 프로그래밍 접근 방식은 많은 제약 조건이 동시에 충족되는 세계 상태를 찾는 것이다. 일반적으로 문제는 다수의 알려지지 않은 변수를 포함하는 세계 상태로 표시된다. 제약 프로그램은 모든 변수에 대한 값을 검색한다.^[1]

시간적 동시 제약 프로그래밍(TCC) 및 비결정적 시간적 동시 제약 프로그래밍(MJV)은 시간을 처리할 수 있는 제약 프로그래밍의 변형이다.^[1]

다음은 제약 논리 언어의 예이다.^[2]

4. 제약 만족 문제

제약 만족 문제(Constraint Satisfaction Problem, CSP)는 주어진 제약 조건을 만족하는 변수 할당을 찾는 문제이다. CSP는 변수 집합, 각 변수의 값 영역(domain), 그리고 변수 간의 제약 조건 집합으로 구성된다.

유한 영역(CSP)에 대한 제약 만족 문제는 다음 세 가지 요소 $(\backslash mathcal\{X\},\backslash mathcal\{D\},\backslash mathcal\{C\})$로 정의된다.

• $\backslash mathcal\{X\}\; =\; \backslash \{x\_1,\; \backslash dots,\; x\_n\; \backslash \}$는 문제의 변수 집합이다.
• $\backslash mathcal\{D\}\; =\; \backslash \{\backslash mathcal\{D\}\_1,\; \backslash dots,\; \backslash mathcal\{D\}\_n\; \backslash \}$는 변수의 영역 집합이다. 즉, 모든 $k\; \backslash in\; [1;\; n]$에 대해 $x\_k\; \backslash in\; \backslash mathcal\{D\}\_k$이다.
• $\backslash mathcal\{C\}\; =\; \backslash \{C\_1,\; \backslash dots,\; C\_m\; \backslash \}$는 제약 조건 집합이다. 제약 조건 $C\_i=(\backslash mathcal\{X\}\_i,\; \backslash mathcal\{R\}\_i)$는 변수 집합 $\backslash mathcal\{X\}\_i\; =\; \backslash \{x\_\{i\_1\},\; \backslash dots,\; x\_\{i\_k\}\backslash \}$와 관계 $\backslash mathcal\{R\}\_i\; \backslash subseteq\; \backslash mathcal\{D\}\_\{i\_1\}\; \backslash times\; \backslash dots\; \backslash times\; \backslash mathcal\{D\}\_\{i\_k\}$로 정의되며, $\backslash mathcal\{X\}\_i$의 변수에 대해 동시에 허용되는 값 집합을 정의한다.

• 외연적 제약 조건: 제약 조건은 해당 조건을 만족하는 값 집합을 열거하여 정의된다.
• 산술 제약 조건: 제약 조건은 산술 표현식, 즉 를 사용하여 정의된다.
• 논리적 제약 조건: 제약 조건은 명시적 의미론으로 정의된다. (예: ''모두 다름(AllDifferent)'', ''최대(AtMost)'')

• $\backslash mathcal\{X\_\{\backslash mathcal\{A\}\}\}\; \backslash subseteq\; \backslash mathcal\{X\}$는 변수의 부분 집합이다.
• $\backslash mathcal\{V\_\{\backslash mathcal\{A\}\}\}\; =\; \backslash \{\; v\_\{\backslash mathcal\{A\}\_1\},\; \backslash dots,\; v\_\{\backslash mathcal\{A\}\_k\}\backslash \}\; \backslash in\; \backslash \{\; \backslash mathcal\{D\}\_\{\backslash mathcal\{A\}\_1\},\; \backslash dots,\; \backslash mathcal\{D\}\_\{\backslash mathcal\{A\}\_k\}\backslash \}$는 할당된 변수가 취하는 값의 튜플이다.

• 해 찾기 (모든 제약 조건 만족)
• 문제의 모든 해 찾기
• 자동 정리 증명을 통해 문제의 불만족 증명

5. 제약 최적화 문제

제약 최적화 문제(Constraint Optimization Problem, COP)는 제약 만족 문제에 목적 함수(Objective Function)가 추가된 형태이다.

최소화 또는 최대화 COP의 ''최적 해''는 ''목적 함수''의 값을 최소화 또는 최대화하는 해이다.

COP의 해를 찾는 과정에서 사용자는 다음 결과를 원할 수 있다.

• 모든 제약 조건을 만족하는 해 찾기
• 목적에 따라 최상의 해 찾기
• 발견된 최상의 해의 최적성 증명
• 문제의 불만족성 증명

6. 정제 모델 vs 교란 모델

제약 기반 프로그래밍 언어는 다음 두 가지 접근 방식을 따른다.^[3]

• 정제 모델: 문제의 변수는 처음에 할당되지 않으며, 각 변수는 범위 또는 도메인에 포함된 모든 값을 가질 수 있는 것으로 가정한다. 계산이 진행됨에 따라, 다른 변수의 가능한 값과 호환되지 않는 것으로 나타나면 변수의 도메인 내 값들이 제거되고, 각 변수에 대해 단일 값이 발견될 때까지 이 과정이 반복된다.
• 교란 모델: 문제의 변수에는 단일 초기 값이 할당된다. 다른 시점에 하나 이상의 변수가 교란(이전 값에 대한 변경)을 받으면, 시스템은 교란과 일치하는 다른 변수에 새 값을 할당하려고 시도하면서 변경 사항을 전파한다.

7. 영역

제약 프로그래밍에서 사용되는 제약 조건은 일반적으로 특정 영역(Domain)에 적용된다.^[5] 제약 프로그래밍에서 널리 사용되는 영역은 다음과 같다.

• 불린 영역: 참/거짓 제약만 적용된다. (SAT 문제)
• 정수 영역, 유리수 영역
• 구간 영역: 특히 스케줄링 문제에 사용된다.^[5]
• 선형 영역: 선형 함수만 설명하고 분석한다. (물론 비선형 문제에 대한 접근 방식도 존재한다)
• 유한 영역: 제약 조건이 유한 집합에 대해 정의된다.
• 혼합 영역: 위에 언급된 두 개 이상의 영역을 포함한다.

8. 제약 전파

지역 일관성은 제약 만족 문제의 변수 또는 제약 조건의 부분 집합의 일관성과 관련된 속성이다. 이는 검색 공간을 줄이고 문제를 더 쉽게 해결하는 데 사용될 수 있다. 노드 일관성, 아크 일관성, 경로 일관성을 포함한 다양한 종류의 지역 일관성 조건이 활용된다.

모든 지역 일관성 조건은 해를 변경하지 않고 문제를 변경하는 변환으로 적용할 수 있는데, 이러한 변환을 '''제약 전파'''라고 한다.^[6] 제약 전파는 변수의 영역을 줄이거나, 제약 조건을 강화하거나, 새로운 제약 조건을 생성하여 작동한다. 이는 검색 공간을 줄여 일부 알고리즘으로 문제를 더 쉽게 해결할 수 있도록 한다. 제약 전파는 일반적으로 불완전하지만, 특정 경우에는 완전한 불만족 검사기로도 사용될 수 있다.

9. 제약 해결

제약 만족 문제(Constraint Satisfaction Problem, CSP)를 해결하기 위한 세 가지 주요 알고리즘 기법은 다음과 같다:^[1]

10. 예시

다음은 프롤로그를 사용한 고전적인 복면산 문제 SEND+MORE=MONEY를 푸는 프로그램이다.

```prolog

sendmore(Digits) :-

Digits = [S,E,N,D,M,O,R,Y], % 변수 생성

Digits :: [0..9], % 변수를 영역에 대응시킨다.

S #\= 0, % 제약: S는 0이 아니다.

M #\= 0,

alldifferent(Digits), % 모든 요소는 각각 다른 값이 된다.

1000*S + 100*E + 10*N + D % 다른 제약

+ 1000*M + 100*O + 10*R + E

#= 10000*M + 1000*O + 100*N + 10*E + Y,

labeling(Digits). % 탐색 시작

```

인터프리터는 퍼즐의 각 문자에 대응하여 변수를 생성한다. `::`라는 기호는 이러한 변수의 영역을 지정하는 것으로, 위의 예에서는 값의 범위가 {0, 1, 2, 3, ..., 9}가 된다. 제약 `S#\=0`과 `M#\=0`은 이들 변수가 0이 되지 않음을 지정한다. 인터프리터는 이러한 제약을 평가하여, 이들 변수가 취할 수 있는 범위에서 0을 제외한다. 다음으로 제약 `alldifferent(Digits)`를 평가한다. 이것은 범위를 좁히는 것은 아니며, 단순히 저장된다. 마지막 제약은 "SEND+MORE=MONEY"의 각 문자를 숫자로 바꾼 식이 수식으로서 참임을 나타낸다. 이 제약으로부터, 먼저 M=1이 도출된다(4자리 수와 4자리 수의 덧셈으로 5자리 수가 된다는 것은, 답의 5자리 수는 반드시 1이 된다). 여기서 변수 M에 관련된 모든 제약이 호출되고, `alldifferent` 제약에의 제약 전파에 의해, 다른 변수가 취할 수 있는 범위에서 1이 제외된다. 제약 전파에 의해 모든 변수의 값이 유일하게 정해지거나, 모든 제약을 만족하는 해가 없다는 것이 판명된다. 다만, 어느 쪽이라고도 판별할 수 없이 종료되는 경우도 있다.

11. 명령형 제약 프로그래밍

명령형 프로그래밍에서도 제약 프로그래밍을 별도의 라이브러리로 사용하는 경우가 많다. 주요 제약 프로그래밍 라이브러리는 다음과 같다.

참조

_[1] 서적 Handbook of Constraint Programming https://books.google[...] Elsevier 2006-08-18
_[2] 간행물 Constraint logic programming https://dl.acm.org/c[...] ACM 1987
_[3] 서적 Constraint Programming https://books.google[...] Springer Science+Business Media 1993
_[4] 논문 Kaleidoscope: A constraint imperative programming language. ftp://trout.cs.washi[...] Springer Berlin Heidelberg 1994-01
_[5] 서적 Constraint-Based Scheduling: Applying Constraint Programming to Scheduling Problems https://books.google[...] Springer Science & Business Media 2012-12-06
_[6] 간행물 Handbook of Constraint Programming Elsevier 2006
_[7] 서적 Handbook of Constraint Programming https://books.google[...] Elsevier 2006-08-18
_[8] 간행물 Constraint logic programming https://dl.acm.org/c[...] ACM 1987