제약 프로그래밍

제약 프로그래밍(Constraint programming, CP)은 인공지능, 컴퓨터 과학, 운용과학의 광범위한 기술을 활용하는 조합 문제를 해결하기 위한 패러다임이다. 제약 프로그래밍에서 사용자는 일련의 결정 변수에 대해 실행 가능한 솔루션에 대한 제약 조건을 선언적으로 명시한다. 제약 조건은 실행할 단계나 단계의 순서를 지정하지 않고 찾을 솔루션의 속성을 지정한다는 점에서 명령형 프로그래밍 언어의 일반적인 기본 형식과 다르다. 제약 조건 외에도 사용자는 이러한 제약 조건을 해결하기 위한 방법을 지정해야 한다. 이는 일반적으로 시간순 퇴각검색 및 제약 조건 전파와 같은 표준 방법을 사용하지만 문제별 분기 휴리스틱과 같은 사용자 정의 코드를 사용할 수도 있다.

제약 프로그래밍은 제약 조건을 논리 프로그램에 포함하는 제약 조건 논리 프로그래밍에 뿌리를 두고 있으며 제약 조건 논리 프로그래밍의 형태로 표현될 수 있다. 이러한 논리 프로그래밍 변형은 프롤로그 II에 도입된 특정 제약 클래스를 1987년에 확장한 재퍼(Jaffar)와 라세즈(Lassez)Jaffar, Joxan, and J-L. Lassez. "Constraint logic programming." Proceedings of the 14th ACM SIGPLAN-SIGACT Symposium on Principles of Programming Languages. ACM, 1987.에 의해 탄생했다. 제약 논리 프로그래밍의 첫 번째 구현은 프롤로그 III, CLP(R) 및 CHIP이었다.

논리 프로그래밍 대신 제약 조건을 함수형 프로그래밍, 용어 재작성 및 명령형 언어와 혼합할 수 있다. 제약 조건을 기본적으로 지원하는 프로그래밍 언어로는 오즈(함수 프로그래밍) 및 칼레이드스코프(Kaleidscope, 명령형 프로그래밍)가 있다. 대부분의 제약 조건은 기존 명령형 언어에 대한 별도의 라이브러리인 제약 조건 해결 툴킷을 통해 명령형 언어로 구현된다.

 같이 보기 
 조합 최적화
 수학적 최적화

 각주 

 외부 링크 
 Association for Constraint Programming
 CP Conference Series 
 Guide to Constraint Programming
, an Oz-based free software (X11-style)

분류:제약 프로그래밍
분류:프로그래밍 패러다임
분류:선언형 프로그래밍