제약 만족도
Constraint satisfaction인공지능 및 운영 연구에서 제약 만족은 변수가 반드시 [1]만족해야 하는 조건을 부과하는 제약 집합을 통해 해결책을 찾는 과정이다.따라서 솔루션은 모든 제약 조건을 충족하는 변수의 값 집합, 즉 실행 가능한 영역의 한 지점입니다.
제약 만족에 사용되는 기술은 고려되는 제약의 종류에 따라 달라집니다.제약 만족 문제가 일반적으로 유한 도메인상의 제약에 기초한 문제와 식별될 정도로, 종종 사용되는 것은 유한 도메인상의 제약입니다.이러한 문제는 보통 검색, 특히 역추적 또는 로컬 검색을 통해 해결됩니다.제약 전파는 이러한 문제에 사용되는 다른 방법입니다.대부분의 방법은 일반적으로 불완전합니다.즉, 문제를 해결하거나 불만족스럽다는 것을 증명하는 경우가 있습니다만, 항상 그렇지는 않습니다.제약 조건 전파 방법도 검색과 함께 사용되어 주어진 문제를 쉽게 해결할 수 있습니다.기타 고려된 제약사항의 종류는 실수 또는 유리수이며, 이러한 제약조건의 문제 해결은 변수 제거 또는 심플렉스 알고리즘을 통해 이루어집니다.
일반적인 문제로서의 제약 만족은 1970년대에 인공지능 분야에서 비롯되었다(예: (로리에르 1978) 참조).그러나, 제약조건이 동등성을 정의하는 다변수 선형 방정식으로 표현될 때, 이 분야는 19세기의 조셉 푸리에로 거슬러 올라간다: 조지 단치히의 1946년 선형 프로그래밍을 위한 심플렉스 알고리즘의 발명 (수학적 최적화의 특별한 경우)은 문제를 해결하기 위한 실행 가능한 해결책을 결정할 수 있게 했다.수백 개의 변수가 있습니다.
1980년대와 1990년대에 프로그래밍 언어에 대한 제약의 임베딩이 개발되었습니다.제약 프로그래밍을 지원하는 최초의 언어는 프롤로그였습니다.그 이후로 제약조건 프로그래밍 라이브러리는 C++나 Java와 같은 다른 언어(예: Choco for[2] Java)로 사용할 수 있게 되었습니다.
제약 만족 문제
원래 인공지능에서 정의된 대로, 제약조건은 주어진 세계에서 변수 집합이 취할 수 있는 가능한 값을 열거합니다.가능한 세계는 세상이 [3]될 수 있는 방식(실제 또는 가상)을 나타내는 변수에 값을 완전히 할당하는 것입니다.비공식적으로 유한 도메인은 유한한 임의 요소 집합입니다.이러한 도메인에서의 제약 만족 문제는 도메인에서만 값을 가져올 수 있는 변수 집합과 변수 그룹에 대해 허용되는 값을 지정하는 제약 집합을 포함한다.이 문제에 대한 해결책은 모든 제약 조건을 충족하는 변수를 평가하는 것입니다.즉, 솔루션은 모든 제약조건이 이러한 값에 의해 충족되도록 각 변수에 값을 할당하는 방법입니다.
상황에 따라서는 추가 요건이 있을 수 있습니다.솔루션(및 가장 빠르고 계산적으로 효율적인 방법)뿐만 아니라 솔루션 도달 방법에 대해서도 관심이 있을 수 있습니다.예를 들어 논리적이고 계산적이지 않은 의미에서 가장 심플한 솔루션('정확하게 정의해야 한다'는 의미)을 원할 수 있습니다.이것은 스도쿠와 같은 논리 게임에서도 흔히 볼 수 있는 일입니다.
실제로, 제약조건은 종종 제약조건을 충족하는 변수의 모든 값을 열거하는 것이 아니라 콤팩트한 형태로 표현된다.가장 많이 사용되는 제약 조건 중 하나는 영향을 받는 변수의 값이 모두 서로 달라야 한다는(명백한) 제약 조건입니다.
제약 만족 문제로 표현될 수 있는 문제는 8개의 퀸 퍼즐, 스도쿠 해결 문제 및 기타 많은 논리 퍼즐, 부울 만족도 문제, 스케줄링 문제, 한계 오차 추정 문제 및 그래프 색칠 문제와 같은 그래프 상의 다양한 문제이다.
일반적으로 제약 만족 문제의 위의 정의에 포함되지 않지만, 산술 방정식과 부등식은 그들이 포함하는 변수의 값을 제한하므로 제약의 한 형태로 간주될 수 있다.이들의 영역은 숫자의 집합(정수, 유리 또는 실수)이며, 이는 무한합니다. 따라서 이러한 제약 조건의 관계도 무한할 수 . 예를 XY + 1({ 스타일 X+1에는 만족할 수 있는 값의 무한한 쌍이 있습니다.산술 방정식과 부등식은 종종 유한한 영역으로 제한되는 "제약 만족 문제"의 정의 내에서 고려되지 않는다.그러나 제약 조건 프로그래밍에서 자주 사용됩니다.
만족할 수 있는 값의 무한한 쌍이 있습니다.산술 방정식과 부등식은 종종 유한한 영역으로 제한되는 "제약 만족 문제"의 정의 내에서 고려되지 않는다.그러나 제약 조건 후토시키나 가쿠로(크로스섬이라고도 함)와 같은 유한 논리 퍼즐에 존재하는 산술 부등식이나 방정식은 비산술 제약(패턴 기반 제약 만족 및 논리[4] 퍼즐 참조)으로 취급할 수 있음을 알 수 있다.
해결하는
유한 도메인의 제약 조건 만족 문제는 일반적으로 검색 형식을 사용하여 해결됩니다.가장 많이 사용되는 기술은 백트랙킹, 제약조건 전파 및 로컬 검색의 변형입니다.이러한 기법은 비선형 구속조건의 문제에 사용됩니다.
변수 제거 및 심플렉스 알고리즘은 선형 및 다항식 방정식과 부등식, 무한 영역을 가진 변수를 포함하는 문제를 해결하기 위해 사용됩니다.이러한 문제는 일반적으로 최적화된 함수가 위반된 제약조건의 개수인 최적화 문제로 해결됩니다.
복잡성
한정된 도메인에서 제약 만족 문제를 해결하는 것은 도메인 크기에 관한 NP의 완전한 문제입니다.연구는 많은 다루기 쉬운 하위 사례를 보여주었으며, 일부는 허용된 제약 관계를 제한하고, 일부는 문제의 재구성된 버전에서 트리를 형성하기 위해 제약의 범위를 요구한다.연구는 또한 제약 만족 문제와 유한 모델 이론과 같은 다른 영역의 문제와의 관계를 확립했다.
제약 조건 프로그래밍
제약 프로그래밍은 문제를 인코딩하고 해결하기 위한 프로그래밍 언어로 제약을 사용하는 것입니다.이것은 종종 호스트 언어라고 불리는 프로그래밍 언어에 제약을 포함시킴으로써 이루어집니다.제약 프로그래밍은 Prolog II에서 용어 균등의 공식화에서 비롯되었으며, 이는 제약 조건을 논리 프로그래밍 언어에 포함시키기 위한 일반적인 프레임워크로 이어졌다.가장 일반적인 호스트 언어는 Prolog, C++ 및 Java이지만 다른 언어도 사용되고 있습니다.
제약 로직 프로그래밍
제약조건 논리 프로그램은 절 본문에 제약조건을 포함하는 논리 프로그램입니다.예를 들어, 이 조항은A(X):-X>0,B(X)제약조건을 포함하는 조항입니다.X>0체내에 있습니다.목표에도 제약이 존재할 수 있습니다.목표를 증명하기 위해 사용되는 절과 목표의 제약조건은 제약조건 스토어라는 집합으로 누적됩니다.이 집합에는 인터프리터가 평가를 진행하기 위해 만족할 수 있다고 가정한 제약 조건이 포함되어 있습니다.그 결과, 이 세트가 불만족스럽다고 검출되면, 인터프리터는 역추적을 실시한다.논리 프로그래밍에서 사용되는 용어 방정식은 단일화를 사용하여 단순화할 수 있는 특정 형태의 제약으로 간주됩니다.그 결과, 제약 스토어는 정규 논리 프로그래밍에서 사용되는 치환 개념의 확장으로 간주될 수 있다.제약조건 논리 프로그래밍에 사용되는 가장 일반적인 종류의 제약조건은 정수/합리/실수에 대한 제약조건과 유한 도메인에 대한 제약조건입니다.
동시 제약 로직 프로그래밍 언어도 개발되었습니다.이들은 종료되지 않을 수 있는 동시 프로세스를 프로그래밍하는 것을 목적으로 한다는 점에서 비동시 제약 논리 프로그래밍과는 크게 다릅니다.제약조건 처리 규칙은 동시 제약조건 로직 프로그래밍의 한 형태로 볼 수 있지만 비동시 제약조건 로직 프로그래밍 언어 내에서 사용되기도 합니다.그들은 조건의 진실에 기초하여 제약조건을 다시 쓰거나 새로운 제약조건을 추론할 수 있게 한다.
제약 조건 만족 도구 키트
제약 조건 만족 툴킷은 제약 조건 만족 문제를 인코딩하고 해결하기 위해 사용되는 필수 프로그래밍 언어용 소프트웨어 라이브러리입니다.
- Cassowary 제약 조건 해결사, 제약 조건 만족을 위한 오픈 소스 프로젝트입니다(C, Java, Python 및 기타 언어에서 액세스 가능).
- 상용 프로그래밍 언어 및 툴킷인 Comet
- Gecode는 C++로 작성된 오픈 소스 휴대용 툴킷으로 완전한 이론적 배경의 생산 품질과 매우 효율적인 구현으로 개발되었습니다.
- Gecode to [5]Lisp의 오픈 소스 포터블 래퍼인 Gelisp.http://gelisp.sourceforge.net/
- IBM ILOG CP Optimizer: C++, Python, Java.NET 라이브러리(독자 사양, 학술용 무료).[6]ILOG Solver/Scheduler의 후계자로 2006년 현재[7] 상용 제약 프로그래밍 소프트웨어의 시장 리더로 간주되고 있습니다.
- 오픈 소스 Java 제약 해결사 JaCoP.
- OptaPlanner는 다른 오픈 소스 Java 제약 해결사입니다.
- 상용 Java 기반 제약 해결사 Koalog.
- logilab-constraint는 제약 전파 알고리즘을 사용하여 순수 Python으로 작성된 오픈 소스 제약 해결사입니다.
- Minion은 모델/문제 지정을 위해 작은 언어를 사용하는 C++로 작성된 오픈 소스 제약 해결사입니다.
- 제약 만족 문제를 모델링하고 해결하기 위해 컴퓨터 지원 제약 만족 프로젝트에서 개발된 오픈 소스 프로그램인 ZDC.
기타 제약 조건 프로그래밍 언어
구속 툴킷은 구속조건을 필수 프로그래밍 언어에 포함시키는 방법입니다.그러나 이러한 라이브러리는 인코딩 및 문제 해결을 위한 외부 라이브러리로만 사용됩니다.Kaleidoscope 프로그래밍 언어에서는 제약 조건이 필수 프로그래밍 언어로 통합되는 접근 방식을 채택합니다.
기능 프로그래밍 언어에도 제약이 있습니다.
「 」를 참조해 주세요.
레퍼런스
- ^ Edward Tsang (13 May 2014). Foundations of Constraint Satisfaction: The Classic Text. BoD – Books on Demand. ISBN 978-3-7357-2366-6.
- ^ Choco: 제약 조건 프로그래밍을 위한 오픈 소스 Java 라이브러리입니다.https://choco-solver.org 2021년 12월 12일에 접속.
- ^ "4.1.1 Variables and Worlds‣ 4.1 Possible Worlds, Variables, and Constraints ‣ Chapter 4 Reasoning with Constraints ‣ Artificial Intelligence: Foundations of Computational Agents, 2nd Edition".
- ^ (영어) Berthier, Denis (20 November 2012). "Pattern-Based Constraint Satisfaction and Logic Puzzles". Lulu Publishers. ISBN 978-1-291-20339-4. Archived from the original on 12 January 2013. Retrieved 24 October 2012.
- ^ Mauricio Toro, Carlos Agen, Camilo Ruea, Gerard Assayag. "GELISP: 음악적 제약 만족 문제와 검색 전략을 나타내는 프레임워크." 이론 및 응용 정보기술 저널 86(2016.7-33.1).
- ^ Laborie P, Rogerie J, Shaw P, Vilim P (2018). "IBM ILOG CP optimizer for scheduling". Constraints. 23 (2): 210–250. doi:10.1007/s10601-018-9281-x. S2CID 4360357.
- ^ Francesca Rossi; Peter Van Beek; Toby Walsh (2006). Handbook of constraint programming. Elsevier. p. 157. ISBN 978-0-444-52726-4.
- Apt, Krzysztof (2003). Principles of constraint programming. Cambridge University Press. ISBN 978-0-521-82583-2.
- Dechter, Rina (2003). Constraint processing. Morgan Kaufmann. ISBN 978-1-55860-890-0.
- Dincbas, M.; Simonis, H.; Van Hentenryck, P. (1990). "Solving Large Combinatorial Problems in Logic Programming". Journal of Logic Programming. 8 (1–2): 75–93. doi:10.1016/0743-1066(90)90052-7.
- Freuder, Eugene; Mackworth, Alan, eds. (1994). Constraint-based reasoning. MIT Press. ISBN 978-0-262-56075-7.
- Frühwirth, Thom; Slim Abdennadher (2003). Essentials of constraint programming. Springer. ISBN 978-3-540-67623-2.
- Guesguen, Hans; Hertzberg Joachim (1992). A Perspective of Constraint Based Reasoning. Springer. ISBN 978-3-540-55510-0.
- Jaffar, Joxan; Michael J. Maher (1994). "Constraint logic programming: a survey". Journal of Logic Programming. 19/20: 503–581. doi:10.1016/0743-1066(94)90033-7.
- Laurière, Jean-Louis (1978). "A Language and a Program for Stating and Solving Combinatorial Problems". Artificial Intelligence. 10 (1): 29–127. doi:10.1016/0004-3702(78)90029-2.
- Lecoutre, Christophe (2009). Constraint Networks: Techniques and Algorithms. ISTE/Wiley. ISBN 978-1-84821-106-3.
- Marriott, Kim; Peter J. Stuckey (1998). Programming with constraints: An introduction. MIT Press. ISBN 978-0-262-13341-8.
- Rossi, Francesca; Peter van Beek; Toby Walsh, eds. (2006). Handbook of Constraint Programming. Elsevier. ISBN 978-0-444-52726-4. Archived from the original on 2012-10-04. Retrieved 2006-10-13.
- Tsang, Edward (1993). Foundations of Constraint Satisfaction. Academic Press. ISBN 978-0-12-701610-8.
- Van Hentenryck, Pascal (1989). Constraint Satisfaction in Logic Programming. MIT Press. ISBN 978-0-262-08181-8.
- Rashidi, Hassan.; Tsang, Edward. (2012). "Novel constraints satisfaction models for optimization problems in container terminals". Journal of Applied Mathematical Modelling. 37 (6): 3601–34. doi:10.1016/j.apm.2012.07.042.
