제약 조건 프로그래밍

제약 프로그래밍(CP)^[1]은 인공지능, 컴퓨터 과학, 운영 연구 등 광범위한 기술을 활용하여 조합 문제를 해결하기 위한 패러다임입니다.제약조건 프로그래밍에서 사용자는 일련의 의사결정 변수에 대해 실현 가능한 해결책에 대한 제약을 선언적으로 진술한다.제약조건은 실행할 단계 또는 일련의 단계를 지정하는 것이 아니라 찾을 수 있는 솔루션의 속성을 지정하는 점에서 명령형 프로그래밍 언어의 일반적인 기본조건과 다릅니다.사용자는 제약조건과 더불어 이러한 제약조건을 해결하기 위한 방법도 지정해야 합니다.이는 일반적으로 시간순 역추적 및 제약조건 전파와 같은 표준 방법을 사용하지만 문제별 분기 경험적 접근법처럼 맞춤형 코드를 사용할 수 있습니다.

제약조건 프로그래밍은 제약조건을 논리 프로그램에 포함시키는 제약조건 논리 프로그래밍의 형태로 표현될 수 있습니다.이 논리 프로그래밍의 변종은 1987년에 Prolog II에서 도입된 특정 클래스의 제약을 확장한 Jaffar와 Lassez에 ^[2]기인합니다.제약 로직 프로그래밍의 첫 번째 구현은 Prolog III, CLP(R) 및 CHIP였습니다.

논리 프로그래밍 대신 기능 프로그래밍, 용어 다시 쓰기 및 명령 언어와 제약 조건을 혼합할 수 있습니다.제약 조건을 지원하는 내장 프로그래밍 언어로는 Oz(기능 프로그래밍) 및 Kaleidoscope(임페셔널 프로그래밍)가 있습니다.대부분의 제약조건은 기존 명령어를 위한 별도의 라이브러리인 제약조건 해결 툴킷을 통해 명령어로 구현된다.

제약 로직 프로그래밍

제약 조건 프로그래밍은 호스트 언어에 제약 조건이 포함된 것입니다.처음 사용된 호스트 언어는 논리 프로그래밍 언어였기 때문에 처음에는 구속 로직 프로그래밍이라고 불렸습니다.두 패러다임은 논리 변수 및 역추적과 같은 많은 중요한 기능을 공유합니다.오늘날 대부분의 프롤로그 구현에는 제약 로직 프로그래밍을 위한 하나 이상의 라이브러리가 포함되어 있습니다.

이 둘의 차이는 주로 세상을 모델링하는 스타일과 접근법에 있다.논리 프로그램으로 쓰는 것이 더 자연스럽고(따라서 더 간단한) 문제가 있는 반면 제약 프로그램으로 쓰는 것이 더 자연스러운 문제도 있습니다.

제약조건 프로그래밍 접근법은 다수의 제약조건이 동시에 충족되는 세계의 상태를 검색하는 것입니다.문제는 일반적으로 알려지지 않은 많은 변수를 포함하는 세계의 상태로 기술됩니다.제약 조건 프로그램은 모든 변수의 값을 검색합니다.

TCC(Temporal Concurrent Constraint Programming)와 비결정론적 Temporary Constraint Programming(MJV)은 시간을 처리할 수 있는 제약 프로그래밍의 변형입니다.

제약 만족 문제

제약 조건은 여러 변수 간의 관계이며, 이러한 변수가 동시에 취할 수 있는 값을 제한합니다.

정의: 유한 도메인(또는 CSP)에서의 제약 조건 만족 문제는 트리플렛 $({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$ $)({\mathcal {X}),$ {\ $mathcal {D},$ {\ $mathcal {C}})$ 에 $({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$ 의해 정의됩니다.

${\mathcal {X}}=\{x_{1},\dots ,x_{n}\}$ ${\mathcal {X}}=\{x_{1},\dots ,x_{n}\}$ { ${\mathcal {X}}=\{x_{1},\dots ,x_{n}\}$ , ${\mathcal {X}}=\{x_{1},\dots ,x_{n}\}$ , x ${\mathcal {X}}=\{x_{1},\dots ,x_{n}\}$ $}$ { $displaystyle$ { $mathcal$ { ${\mathcal {X}}=\{x_{1},\dots ,x_{n}\}$ X } = \ { $x$ _ { $1}$ , \ $dots$ , x _ { n $}$ }는 ${\mathcal {X}}=\{x_{1},\dots ,x_{n}\}$ 문제의 변수 세트입니다.
${\mathcal {D}}=\{{\mathcal {D}}_{1},\dots ,{\mathcal {D}}_{n}\}$ ${\mathcal {D}}=\{{\mathcal {D}}_{1},\dots ,{\mathcal {D}}_{n}\}$ { ${\mathcal {D}}=\{{\mathcal {D}}_{1},\dots ,{\mathcal {D}}_{n}\}$ 1 , ${\mathcal {D}}=\{{\mathcal {D}}_{1},\dots ,{\mathcal {D}}_{n}\}$ , ${\mathcal {D}}=\{{\mathcal {D}}_{1},\dots ,{\mathcal {D}}_{n}\}$ ${\mathcal {D}}=\{{\mathcal {D}}_{1},\dots ,{\mathcal {D}}_{n}\}$ $}$ { $displaystyle$ { d } = \ { \ $mathcal { D$ } } ${\mathcal {D}}=\{{\mathcal {D}}_{1},\dots ,{\mathcal {D}}_{n}\}$ _ { } \ $dots$ , { \ $mathcal$ { $D } _$ { $n$ $k\in [1;n]$ } _ { n } \ dots ${\mathcal {D}}=\{{\mathcal {D}}_{1},\dots ,{\mathcal {D}}_{n}\}$ , 즉, $x_{k}\in {\mathcal {D}}_{k}$ $k\in [1;n]$ [ $1$ ; $style k ]$ 에 $k\in [1;n]$ $x_{k}\in {\mathcal {D}}_{k}$ 변수의 도메인 집합입니다.
${\mathcal {C}}=\{C_{1},\dots ,C_{m}\}$ ${\mathcal {C}}=\{C_{1},\dots ,C_{m}\}$ { ${\mathcal {C}}=\{C_{1},\dots ,C_{m}\}$ , ${\mathcal {C}}=\{C_{1},\dots ,C_{m}\}$ , ${\mathcal {C}}=\{C_{1},\dots ,C_{m}\}$ m $}$ { $displaystyle$ \ $mathcal$ { ${\mathcal {C}}=\{C_{1},\dots ,C_{m}\}$ C } = \ { $C$ _ { $1$ , \ $dots$ , $C$ _ { $m$ } }는 ${\mathcal {C}}=\{C_{1},\dots ,C_{m}\}$ 제약 조건의 집합입니다.제약 $C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})$ $C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})$ i $C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})$ ( $C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})$ i , $C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})$ ) { $displaystyle$ C _ { i } $= set$ ${\mathcal {X}}_{i}=\{x_{i_{1}},\dots ,x_{i_{k}}\}$ $i$ ${\mathcal {X}}_{i}=\{x_{i_{1}},\dots ,x_{i_{k}}\}$ { \ $mathcal$ { $R$ } } _ { ${\mathcal {X}}_{i}=\{x_{i_{1}},\dots ,x_{i_{k}}\}$ } { \ ${\mathcal {X}}_{i}=\{x_{i_{1}},\dots ,x_{i_{k}}\}$ { R ${\mathcal {X}}_{i}=\{x_{i_{1}},\dots ,x_{i_{k}}\}$ $_$ { ${\mathcal {X}}_{i}=\{x_{i_{1}},\dots ,x_{i_{k}}\}$ $C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})$ } ${\mathcal {X}}_{i}=\{x_{i_{1}},\dots ,x_{i_{k}}\}$ } { $displaystyle$ \ $mathcal { X} =$ { $i$ } } { i } { 1 } { i } { i } { i } { i } ${\mathcal {R}}_{i}\subset {\mathcal {D}}_{i_{1}}\times \dots \times {\mathcal {D}}_{i_{k}}$ {\ $displaystyle {R}_{i}\subset {mathcal$ { $D}_{1}\$ times \ $dots$ \times $\mathcal$ ${D$ $}_{i_{k$ $Xi\$ style 변수에 ${\mathcal {R}}_{i}\subset {\mathcal {D}}_{i_{1}}\times \dots \times {\mathcal {D}}_{i_{k}}$ 대해 $동시$ 에 허용되는 값 $집합$ 을 정의합니다.

제약에는 다음 세 가지 범주가 있습니다.

확장 제약 조건: 제약 조건을 충족하는 값 집합을 열거함으로써 제약 조건을 정의합니다.
산술적 제약조건: 제약조건은 산술식으로 정의됩니다.즉, < $<,>,\leq ,\geq ,=,\neq ,...$ , $<,>,\leq ,\geq ,=,\neq ,...$ , " , " , " , " , $<,>,\leq ,\geq ,=,\neq ,...$ , $<,>,\leq ,\geq ,=,\neq ,...$ " $<,>,\leq ,\geq ,=,\neq ,...$ , " $<,>,\leq ,\geq ,=,\neq ,...$ . " $.\display$ style < , > , \ $leq$ , \ $geq$ , = , \ $neq$ , . " $<,>,\leq ,\geq ,=,\neq ,...$ " 를 사용합니다. $<,>,\leq ,\geq ,=,\neq ,...$ ;
논리적 제약조건: 제약조건은 명시적 의미(AllDifferent, AtMost 등)로 정의됩니다.

정의 — $P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$ P $P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$ ( $P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$ , $P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$ , $C$ ) { $displaystyle$ P = ( X , D , $P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$ ${\mathcal {A}}$ ) , { \ $mathcal$ { D } , { \ $mathcal { C$ } 의 할당(또는 모델 $)$ 은 ${\mathcal {A}}$ A ${\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})$ ( $X$ ) style ${\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})$ )에 $P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$ 의해 정의됩니다. $al {A}}}}}}.$ 여기서 ${\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})$ :

$X$ A ${\mathcal {X_{\mathcal {A}}}}\subset {\mathcal {X}}$ X ({style ${X_{\mathcal {A}}})\subset$ {{ $mathcal {X}})$ 는 ${\mathcal {X_{\mathcal {A}}}}\subset {\mathcal {X}}$ 변수의 서브셋입니다.
${\mathcal {V_{\mathcal {A}}}}=\{v_{{\mathcal {A}}_{1}},\dots ,v_{{\mathcal {A}}_{k}}\}\in \{{\mathcal {D}}_{{\mathcal {A}}_{1}},\dots ,{\mathcal {D}}_{{\mathcal {A}}_{k}}\}$ A ${\mathcal {V_{\mathcal {A}}}}=\{v_{{\mathcal {A}}_{1}},\dots ,v_{{\mathcal {A}}_{k}}\}\in \{{\mathcal {D}}_{{\mathcal {A}}_{1}},\dots ,{\mathcal {D}}_{{\mathcal {A}}_{k}}\}$ { ${\mathcal {V_{\mathcal {A}}}}=\{v_{{\mathcal {A}}_{1}},\dots ,v_{{\mathcal {A}}_{k}}\}\in \{{\mathcal {D}}_{{\mathcal {A}}_{1}},\dots ,{\mathcal {D}}_{{\mathcal {A}}_{k}}\}$ A ${\mathcal {V_{\mathcal {A}}}}=\{v_{{\mathcal {A}}_{1}},\dots ,v_{{\mathcal {A}}_{k}}\}\in \{{\mathcal {D}}_{{\mathcal {A}}_{1}},\dots ,{\mathcal {D}}_{{\mathcal {A}}_{k}}\}$ , ${\mathcal {V_{\mathcal {A}}}}=\{v_{{\mathcal {A}}_{1}},\dots ,v_{{\mathcal {A}}_{k}}\}\in \{{\mathcal {D}}_{{\mathcal {A}}_{1}},\dots ,{\mathcal {D}}_{{\mathcal {A}}_{k}}\}$ , v ${\mathcal {V_{\mathcal {A}}}}=\{v_{{\mathcal {A}}_{1}},\dots ,v_{{\mathcal {A}}_{k}}\}\in \{{\mathcal {D}}_{{\mathcal {A}}_{1}},\dots ,{\mathcal {D}}_{{\mathcal {A}}_{k}}\}$ ${\mathcal {V_{\mathcal {A}}}}=\{v_{{\mathcal {A}}_{1}},\dots ,v_{{\mathcal {A}}_{k}}\}\in \{{\mathcal {D}}_{{\mathcal {A}}_{1}},\dots ,{\mathcal {D}}_{{\mathcal {A}}_{k}}\}$ ${\mathcal {V_{\mathcal {A}}}}=\{v_{{\mathcal {A}}_{1}},\dots ,v_{{\mathcal {A}}_{k}}\}\in \{{\mathcal {D}}_{{\mathcal {A}}_{1}},\dots ,{\mathcal {D}}_{{\mathcal {A}}_{k}}\}$ ${\mathcal {V_{\mathcal {A}}}}=\{v_{{\mathcal {A}}_{1}},\dots ,v_{{\mathcal {A}}_{k}}\}\in \{{\mathcal {D}}_{{\mathcal {A}}_{1}},\dots ,{\mathcal {D}}_{{\mathcal {A}}_{k}}\}$ { ${\mathcal {V_{\mathcal {A}}}}=\{v_{{\mathcal {A}}_{1}},\dots ,v_{{\mathcal {A}}_{k}}\}\in \{{\mathcal {D}}_{{\mathcal {A}}_{1}},\dots ,{\mathcal {D}}_{{\mathcal {A}}_{k}}\}$ ${\mathcal {V_{\mathcal {A}}}}=\{v_{{\mathcal {A}}_{1}},\dots ,v_{{\mathcal {A}}_{k}}\}\in \{{\mathcal {D}}_{{\mathcal {A}}_{1}},\dots ,{\mathcal {D}}_{{\mathcal {A}}_{k}}\}$ 1 , ${\mathcal {V_{\mathcal {A}}}}=\{v_{{\mathcal {A}}_{1}},\dots ,v_{{\mathcal {A}}_{k}}\}\in \{{\mathcal {D}}_{{\mathcal {A}}_{1}},\dots ,{\mathcal {D}}_{{\mathcal {A}}_{k}}\}$ , ${\mathcal {V_{\mathcal {A}}}}=\{v_{{\mathcal {A}}_{1}},\dots ,v_{{\mathcal {A}}_{k}}\}\in \{{\mathcal {D}}_{{\mathcal {A}}_{1}},\dots ,{\mathcal {D}}_{{\mathcal {A}}_{k}}\}$ ${\mathcal {V_{\mathcal {A}}}}=\{v_{{\mathcal {A}}_{1}},\dots ,v_{{\mathcal {A}}_{k}}\}\in \{{\mathcal {D}}_{{\mathcal {A}}_{1}},\dots ,{\mathcal {D}}_{{\mathcal {A}}_{k}}\}$ ${\mathcal {V_{\mathcal {A}}}}=\{v_{{\mathcal {A}}_{1}},\dots ,v_{{\mathcal {A}}_{k}}\}\in \{{\mathcal {D}}_{{\mathcal {A}}_{1}},\dots ,{\mathcal {D}}_{{\mathcal {A}}_{k}}\}$ { $displaystyle$ { V _ { \ $mathcal$ { A } } = { $v$ _ { \ $mathcal$ { $A } }$ , \ $dots$ , v _ { \ $mathcal$ { $A$ } } $}$ } 。할당된 변수

할당은 도메인에서 값에 변수를 연관짓는 것입니다.부분 할당은 문제의 변수의 하위 집합이 할당된 경우입니다.총 할당은 문제의 모든 변수가 할당된 경우입니다.

특성 - ${\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})$ ${\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})$ ( ${\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})$ A ${\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})$ , ${\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})$ A ${\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})$ ) { $displaystyle$ ${\mathcal {A}}=({\mathcal {X_{\mathcal {A}}}},{\mathcal {V_{\mathcal {A}}}})$ { x _ { \ $mathcal$ { $A }$ } , { \ $mathcal$ { $A$ } } } { \ $mathcal$ { A } } } } $P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$ P $P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$ $P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$ $P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$ , $P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$ ）、 $P=({\mathcal {X}},{\mathcal {D}},{\mathcal {C}})$ $=$ C $style 。$ $)($ ${\mathcal {X}}_{i}\subset {\mathcal {X_{\mathcal {A}}}}$ ${\mathcal {X}}_{i}\subset {\mathcal {X_{\mathcal {A}}}}$ ${\mathcal {X}}_{i}\subset {\mathcal {X_{\mathcal {A}}}}$ A ${\mathcal {X}}_{i}\subset {\mathcal {X_{\mathcal {A}}}}$ ( \ $display$ $style$ \ $mathcal$ { $X } _$ { $i$ } )와 ${\mathcal {X}}_{i}\subset {\mathcal {X_{\mathcal {A}}}}$ P $($ \ $displaystyle$ { $R } _$ { $i$ } )의 $C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})$ $P$ 제약조건(\displaystyle { $X } _$ { $i$ } \ $subset$ { \ $mathcal$ { $X$ _ { { A ${\mathcal {X}}_{i}\subset {\mathcal {X_{\mathcal {A}}}}$ ) )을 $($ ) 할당한다 $C_{i}=({\mathcal {X}}_{i},{\mathcal {R}}_{i})$ $i}$ 모든 $C_{i}$ ${\mathcal {V}}_{{\mathcal {A}}_{i}}=\{v_{i}\in {\mathcal {V}}_{\mathcal {A}}{\mbox{ tel que }}x_{i}\in {\mathcal {X}}_{i}\}$ V ${\mathcal {V}}_{{\mathcal {A}}_{i}}=\{v_{i}\in {\mathcal {V}}_{\mathcal {A}}{\mbox{ tel que }}x_{i}\in {\mathcal {X}}_{i}\}$ i ${\mathcal {V}}_{{\mathcal {A}}_{i}}=\{v_{i}\in {\mathcal {V}}_{\mathcal {A}}{\mbox{ tel que }}x_{i}\in {\mathcal {X}}_{i}\}$ { ${\mathcal {V}}_{{\mathcal {A}}_{i}}=\{v_{i}\in {\mathcal {V}}_{\mathcal {A}}{\mbox{ tel que }}x_{i}\in {\mathcal {X}}_{i}\}$ i ${\mathcal {V}}_{{\mathcal {A}}_{i}}=\{v_{i}\in {\mathcal {V}}_{\mathcal {A}}{\mbox{ tel que }}x_{i}\in {\mathcal {X}}_{i}\}$ V ${\mathcal {V}}_{{\mathcal {A}}_{i}}=\{v_{i}\in {\mathcal {V}}_{\mathcal {A}}{\mbox{ tel que }}x_{i}\in {\mathcal {X}}_{i}\}$ ${\mathcal {V}}_{{\mathcal {A}}_{i}}=\{v_{i}\in {\mathcal {V}}_{\mathcal {A}}{\mbox{ tel que }}x_{i}\in {\mathcal {X}}_{i}\}$ ${\mathcal {V}}_{{\mathcal {A}}_{i}}=\{v_{i}\in {\mathcal {V}}_{\mathcal {A}}{\mbox{ tel que }}x_{i}\in {\mathcal {X}}_{i}\}$ x ${\mathcal {V}}_{{\mathcal {A}}_{i}}=\{v_{i}\in {\mathcal {V}}_{\mathcal {A}}{\mbox{ tel que }}x_{i}\in {\mathcal {X}}_{i}\}$ X ${\mathcal {V}}_{{\mathcal {A}}_{i}}=\{v_{i}\in {\mathcal {V}}_{\mathcal {A}}{\mbox{ tel que }}x_{i}\in {\mathcal {X}}_{i}\}$ { $displaystyle$ { $mathcal { A } _$ { i } $=$ \ { $v$ _ { i ${\mathcal {V}}_{{\mathcal {A}}_{i}}=\{v_{i}\in {\mathcal {V}}_{\mathcal {A}}{\mbox{ tel que }}x_{i}\in {\mathcal {X}}_{i}\}$ } $in$ { $mathcal$ { V } $_$ { A } = { \ $mathcal$ { A } { A } { mathcal { A } } { i } } { mox } { i } $box$ {\ x ${\mathcal {V}}_{{\mathcal {A}}_{i}}=\{v_{i}\in {\mathcal {V}}_{\mathcal {A}}{\mbox{ tel que }}x_{i}\in {\mathcal {X}}_{i}\}$ x x i x }} X i } }} X }} X }} $}}$ }gs ${\mathcal {R}}_{i}$ $($ 스타일) { $mathcal {R}_{i$

정의: CSP의 솔루션은 문제의 모든 제약을 충족하는 총 할당입니다.

CSP의 솔루션을 검색하는 동안 사용자는 다음을 원할 수 있습니다.

해결 방법 찾기(모든 제약 조건 준수);
문제의 모든 해결 방법을 찾는다.
문제가 만족스럽지 않다는 것을 증명합니다.

제약 조건 최적화 문제

제약 최적화 문제(COP)는 목적 함수와 관련된 제약 만족 문제입니다.

최소(최대화) COP에 대한 최적의 솔루션은 목표 함수의 값을 최소(최대화)하는 솔루션입니다.

CSP의 솔루션을 검색하는 동안 사용자는 다음을 원할 수 있습니다.

해결 방법 찾기(모든 제약 조건 준수);

목표와 관련하여 최적의 솔루션을 찾는다.
가장 잘 발견된 솔루션의 최적성을 입증한다.
문제가 만족스럽지 않다는 것을 증명합니다.

섭동 대 정제 모델

제약 조건 기반 프로그래밍 언어는 다음 두 가지 방법 ^[3]중 하나를 따릅니다.

미세화 모델: 문제의 변수는 처음에는 할당되지 않으며, 각 변수는 범위 또는 영역에 포함된 값을 포함할 수 있다고 가정합니다.계산이 진행됨에 따라 변수 영역의 값이 다른 변수의 가능한 값과 호환되지 않는 것으로 나타나면 변수마다 하나의 값이 발견될 때까지 플루닝됩니다.
섭동 모형: 문제의 변수에 단일 초기 값이 할당됩니다.다른 시간에 하나 이상의 변수가 섭동(이전 값의 변경)을 수신하고 시스템은 섭동과 일치하는 다른 변수에 새로운 값을 할당하려고 변화를 전파합니다.

제약 조건 만족 문제에서 제약 조건 전파는 정제 모델의 전형적인 예이며, 스프레드시트는 섭동 모델의 전형적인 예이다.

정제 모형은 변수를 단일 값으로 제한하지 않기 때문에 더 일반적이며 동일한 문제에 대한 여러 가지 솔루션으로 이어질 수 있습니다.그러나, 섭동 모델은 혼합 명령 제약 객체 지향 ^[4]언어를 사용하는 프로그래머에게 더 직관적이다.

도메인

제약 조건 프로그래밍에 사용되는 제약 조건은 일반적으로 일부 특정 도메인에 걸쳐 있습니다.제약 조건 프로그래밍에 자주 사용되는 도메인은 다음과 같습니다.

true/false 제약 조건만 적용되는 부울 도메인(SAT 문제)
정수 도메인, 합리적 도메인
인터벌 도메인, 특히 스케줄링 문제의 경우
선형 함수만 기술 및 분석되는 선형 영역(비선형 문제에 대한 접근법이 존재하지만)
제약이 유한 집합에 걸쳐 정의되는 유한 도메인
위의 두 개 이상의 도메인이 포함된 혼합 도메인

유한 도메인은 제약 조건 프로그래밍에서 가장 성공적인 도메인 중 하나입니다.(운영 조사와 같은) 일부 영역에서는 제약 프로그래밍이 종종 유한 도메인에 대한 제약 프로그래밍으로 식별됩니다.

제약 전파

국소 일관성 조건은 변수 또는 제약 조건의 하위 집합의 일관성과 관련된 제약 조건 만족 문제의 속성입니다.검색 공간을 줄이고 문제를 쉽게 해결하기 위해 사용할 수 있습니다.노드 일관성, 아크 일관성, 경로 일관성 등 다양한 종류의 로컬 일관성 조건이 활용됩니다.

모든 로컬 일관성 조건은 솔루션을 변경하지 않고 문제를 변경하는 변환을 통해 적용할 수 있습니다.이러한 변환을 제약 ^[5]전파라고 합니다.제약 조건 전파는 변수의 도메인을 줄이거나, 제약 조건을 강화하거나, 새로운 변수를 만드는 방식으로 작동합니다.따라서 검색 공간이 줄어들어 일부 알고리즘으로 문제를 쉽게 해결할 수 있습니다.제약 전파는 불만족성 검사기로도 사용될 수 있으며, 일반적으로 불완전하지만 일부 특정 경우에는 완전하다.

제약 해결

제약 조건 만족 문제를 해결하기 위한 알고리즘 기법에는 백트랙 검색, 로컬 검색 및 동적 프로그래밍의 ^[1]세 가지가 있습니다.

역추적 검색

역추적 검색은 일부 계산 문제, 특히 제약 만족 문제에 대한 모든(또는 일부) 솔루션을 찾기 위한 일반적인 알고리즘으로, 솔루션에 대한 후보를 점진적으로 구축하고 후보가 유효한 솔루션에 대해 완료할 수 없다고 판단되는 즉시 후보("백트랙")를 포기합니다.

로컬 검색

로컬 검색은 문제의 해결책을 찾는 불완전한 방법입니다.이는 모든 제약 조건이 충족될 때까지 변수 할당을 반복적으로 개선하는 것을 기반으로 합니다.특히 로컬 검색 알고리즘은 일반적으로 각 단계에서 할당 변수 값을 수정합니다.새 할당은 할당 공간에서 이전 할당과 비슷하므로 로컬 검색이라는 이름을 사용합니다.

동적 프로그래밍

동적 프로그래밍은 수학적 최적화 방법이자 컴퓨터 프로그래밍 방법입니다.복잡한 문제를 재귀적으로 더 단순한 하위 문제로 분해하여 단순화하는 것을 말합니다.일부 의사결정 문제는 이러한 방식으로 분리할 수 없지만, 여러 시점에 걸친 결정은 종종 반복적으로 분리됩니다.마찬가지로 컴퓨터 공학에서도 문제를 하위 문제로 나누어 반복적으로 하위 문제에 대한 최적의 해결책을 찾아냄으로써 문제를 최적으로 해결할 수 있다면, 그것은 최적의 하위 구조를 가지고 있다고 할 수 있다.

예

한정된 도메인에 걸쳐 제약조건을 표현하는 구문은 호스트 언어에 따라 달라집니다.다음은 구속 로직 프로그래밍에서 고전적인 알파벳 퍼즐 SEND+MORE=MONY를 해결하는 프롤로그 프로그램입니다.

% 이 코드는 환경 제공 시스템을 사용하여 YAP와 SWI-Prolog 모두에서 작동합니다. % CLPFD 제약 해결사 라이브러리.작동하려면 약간의 수정이 필요할 수 있습니다. 다른 프롤로그 환경 또는 기타 제약 해결사 사용률(%) :- use_module(도서관(clpfd)). 송신하다(숫자) :-    숫자 = [S,E,N,D,M,O,R,Y],   변수 생성률(%)    숫자 인스톨 0..9,                도메인에 대한 변수 연결 비율(%)    S #\= 0,                        % 제약 조건: S는 0과 달라야 합니다.    M #\= 0,    모두 다른(숫자),          % 모든 요소가 다른 값을 가져야 합니다.                 1000*S + 100*E + 10*N + D     기타 제약사항(%)               + 1000*M + 100*O + 10*R + E    #= 10000*M + 1000*O + 100*N + 10*E + Y,    라벨.(숫자).                  % 검색 시작

해석자는 퍼즐의 각 글자에 대해 변수를 만듭니다.오퍼레이터ins는 이러한 변수의 도메인을 지정하기 위해 사용되며 값 집합 {0,1,2,3, ...,9}에 걸쳐 있습니다.제약 사항S#\=0그리고.M#\=0이 두 변수가 값 0을 취할 수 없음을 의미합니다.인터프리터는 이들 제약조건을 평가할 때 값 0을 삭제함으로써 이들 두 변수의 도메인을 줄입니다.그러면 제약이 있습니다.all_different(Digits)도메인이 줄어들지 않기 때문에 단순히 저장됩니다.마지막 제약 조건은 각 문자가 해당 숫자로 대체될 때 "SEND+MORE=MONEY"가 유지되도록 문자에 할당된 숫자가 지정되어야 합니다.이 제약 조건으로부터, 해결사는 M=1을 추론합니다. 변수 M을 포함하는 모든 저장된 제약 조건이 각성됩니다. 이 경우, 제약 조건 전파는all_different제약조건은 나머지 모든 변수의 도메인에서 값 1을 삭제합니다.제약 전파는 모든 도메인을 단일 값으로 줄임으로써 문제를 해결할 수 있습니다.또한 도메인이 빈 집합으로 줄임으로써 문제가 해결되지 않음을 증명할 수 있습니다.또한 만족도 또는 불만족도를 증명하지 않고 종료될 수도 있습니다.레이블 리터럴은 실제로 솔루션을 검색하는 데 사용됩니다.

「」를 참조해 주세요.

레퍼런스

^ ^a ^b Rossi, Francesca; Beek, Peter van; Walsh, Toby (2006-08-18). Handbook of Constraint Programming. Elsevier. ISBN 9780080463803.
^ Jaffar, Joxan, 그리고 J-L. Lassez."제한 로직 프로그래밍"제14회 프로그래밍 언어의 원리에 관한 ACM SIGACT-SIGPLAN 심포지엄의 진행.ACM, 1987.
^ Mayoh, Brian; Tyugu, Enn; Penjam, Jaan (1993). Constraint Programming. Springer Science+Business Media. p. 76. ISBN 9783642859830.
^ Lopez, G., Freeman-Benson, B. 및 Borning, A.(1994년, 1월).만화경: 제약조건 명령형 프로그래밍 언어입니다.제약 조건 프로그래밍(313-329페이지)에 있습니다.스프링거 베를린 하이델베르크입니다
^ Bessiere, Christian (2006), "Constraint Propagation", Handbook of Constraint Programming, Foundations of Artificial Intelligence, vol. 2, Elsevier, pp. 29–83, doi:10.1016/s1574-6526(06)80007-6, ISBN 9780444527264

외부 링크

제약조건 프로그래밍을 위한 협회
CP 회의 시리즈
구속조건 프로그래밍 가이드
아카이브 중인 모차르트 프로그래밍 시스템(2012년 12월 5일 아카이브), Oz 기반의 자유 소프트웨어(X11 스타일)
보관소의 코르크 제약 조건 계산 센터(2013년 1월 7일 보관)
글로벌 제약 조건 카탈로그

[:0-1] Rossi, Francesca; Beek, Peter van; Walsh, Toby (2006-08-18). Handbook of Constraint Programming. Elsevier. ISBN 9780080463803.

[2] Jaffar, Joxan, 그리고 J-L. Lassez."제한 로직 프로그래밍"제14회 프로그래밍 언어의 원리에 관한 ACM SIGACT-SIGPLAN 심포지엄의 진행.ACM, 1987.

[3] Mayoh, Brian; Tyugu, Enn; Penjam, Jaan (1993). Constraint Programming. Springer Science+Business Media. p. 76. ISBN 9783642859830.

[4] Lopez, G., Freeman-Benson, B. 및 Borning, A.(1994년, 1월).만화경: 제약조건 명령형 프로그래밍 언어입니다.제약 조건 프로그래밍(313-329페이지)에 있습니다.스프링거 베를린 하이델베르크입니다

[5] Bessiere, Christian (2006), "Constraint Propagation", Handbook of Constraint Programming, Foundations of Artificial Intelligence, vol. 2, Elsevier, pp. 29–83, doi:10.1016/s1574-6526(06)80007-6, ISBN 9780444527264

[1]

[2]

[3]

[4]

[5]

v t 프로그래밍 언어의 종류
패러다임	배우 기반 어레이 애스펙트 지향 클래스 베이스 연결형 동시 데이터 흐름 선언적 차별화 가능 도메인 고유의 역학 난해한 이벤트 주도형 확장 가능 기능하다 필수 논리 매크로 메타프로그래밍 오브젝트 베이스 객체 지향 파이프라인 절차 프로토타입 기반 사색적인 규칙 기반 스크립트 작성 스택 지향 동기 촉각 템플릿
레벨	어셈블리 컴파일 완료 통역 완료 기계. 저레벨 개략적인 매우 높은 레벨
시대	첫번째 둘째 셋째 넷째 다섯 번째의
관련된	Non-English-based 시각.

Search

제약 조건 프로그래밍

네임스페이스

더

목차

제약 로직 프로그래밍

제약 만족 문제

제약 조건 최적화 문제

섭동 대 정제 모델

도메인

제약 전파

제약 해결

역추적 검색

로컬 검색

동적 프로그래밍

예

「」를 참조해 주세요.

레퍼런스

외부 링크

Search

제약 조건 프로그래밍

제약 로직 프로그래밍

제약 만족 문제

제약 조건 최적화 문제

섭동 대 정제 모델

도메인

제약 전파

제약 해결

역추적 검색

로컬 검색

동적 프로그래밍

예

「 」를 참조해 주세요.

레퍼런스

외부 링크

「」를 참조해 주세요.