제약 만족 문제

이 글은 검증을 위해 추가 인용문이 필요합니다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선하는 데 도움을 주십시오. 조달되지 않은 자재는 제거될 수 있습니다.출처 : '제약만족 문제'– 뉴스 · 신문 · 서적 · 학자 · JSTOR (2014년 11월) (이 템플릿 메시지 삭제 방법 및 삭제 시기 확인)

CSP(Constraint Satfaction Problems)는 상태가 여러 제약 또는 제한을 충족해야 하는 객체 집합으로 정의된 수학적 질문입니다.CSP는 변수에 대한 유한 제약의 동질적인 집합으로서 문제 내의 실체를 나타내며, 이는 제약 만족 방법에 의해 해결된다.CSP는 인공 지능과 운영 연구 모두에서 연구의 대상이다. CSP의 공식화의 규칙성은 관련이 없어 보이는 많은 가족의 문제를 분석하고 해결하기 위한 공통 기반을 제공하기 때문이다.CSP는 종종 매우 복잡하기 때문에 합리적인 시간 내에 발견적 검색과 조합적 검색 방법을 조합해야 합니다.제약 프로그래밍(CP)은 ^[1][2]이러한 문제를 해결하는 데 특히 초점을 맞춘 연구 분야입니다.또한 부울 만족도 문제(SAT), 만족도 모듈로 이론(SMT), 혼합 정수 프로그래밍(MIP) 및 응답 세트 프로그래밍(ASP)은 모두 제약 만족도 문제의 특정 형식의 해결에 초점을 맞춘 연구 분야이다.

제약조건 만족 문제로 모델링할 수 있는 문제의 예는 다음과 같습니다.

• 유형 추론^[3][4]
• 여덟 개의 여왕 퍼즐
• 지도 색칠 문제
• 최대 절단 문제^[5]
• 스도쿠, 크로스워드, 후토시키, 가쿠로(크로스섬), 저림, 히다토 등 많은 논리 퍼즐

CP, ASP, Boolean SAT 및 SMT 솔버의 튜토리얼과 함께 제공되는 경우가 많습니다.일반적인 경우, 제약 문제는 훨씬 더 어려울 수 있으며 이러한 단순한 시스템 중 일부에서는 표현되지 않을 수 있습니다.「실생활」의 예에는, ^[6][7]자동 계획, 어휘의 명확화,^{[8][9] [10]}음악학^[11], 제품 구성,^[12] 자원 할당등이 있습니다.

CSP에 대한 솔루션의 존재는 의사결정 문제로 볼 수 있습니다.이는 해결책을 찾거나 철저한 검색 후 해결책을 찾지 못하는 방법으로 결정할 수 있습니다(확실한 알고리즘은 일반적으로 충분히 작은 문제에 대해 완전한 결론에 도달하는 경우가 많습니다).경우에 따라서는 CSP가 다른 수학적 추론 프로세스를 통해 사전에 해결책을 가지고 있는 것으로 알려져 있을 수 있습니다.

형식적 정의

정식적으로는 제약조건 만족 문제는 ${\displaystyle \mathrm{트리플}}{\displaystyle X,}$ $,$ C로 정의됩니다(\$displaystyle \langle$ X,$D, C\rangle$

• ${\displaystyle {}_{}}$ ${\displaystyle =}$ { ${\displaystyle {X\mathrm{}}_{}}$1 , ${\displaystyle ...}$ , X ${\displaystyle n_{}}$ $}$ { $displaystyle$ X = \ { $X$_ {$1$ , \$ldots$, $X$_ { $n$} } a$$, 。
• ${\displaystyle D}$ ${\displaystyle =}$ { ${\displaystyle {D\mathrm{}}_{}}$1 , ${\displaystyle ...}$ , ${\displaystyle {}_{}}$ ${\displaystyle n_{}}$ $}$ { $displaystyle$ D = \ { $D$_ { { 1 , $\ldots$ , D _ { n$$} } d$$ 、 , of of of of 。
• ${\displaystyle C}$ ${\displaystyle =}$ { ${\displaystyle {C\mathrm{}}_{}}$1 , ${\displaystyle ...}$ , ${\displaystyle C_{}}$ m $}$ { $displaystyle$ C = \ { C _ {$1$ , \$ldots$, $C$_ { $m$} } a$$ 、 제약사항 세트입니다.

각 $변수{\displaystyle {}_{}}$ $({$})는$$ 공백이 아닌 $도메인{\displaystyle {}_{}}$ $({$의 값을 취할 수 있습니다.각 $제약조건{\displaystyle {}_{}}$ ${\displaystyle {Cj}_{}c}$C { $displaystyle C_{j}\in$ C$}$는 쌍${\displaystyle {tj}_{}}$ ${\displaystyle {Rj}_{}}$ \$display$style$t_{$j} {\$lle$} {j} {$rangle$ } {J} } } }입니다.는 k$(\displaystyle$ k$)$ $변수$의 $서브셋이며{\displaystyle {}_{}}$, $(\$})는$$ $도메인{\displaystyle {}_{}}$ $(\$의 대응하는 서브셋에 $대한{\displaystyle }$k(\$displaystyle$ k$}-$ary 관계입니다.변수 평가는 변수의 서브셋에서 대응하는 서브셋에 대한 특정 값 집합으로의 함수입니다.의 도메인입니다.$변수{\displaystyle {}_{}}$ ${\displaystyle {tj}_{}}${\$displaystyle t_{$j$$}에 할당된 ${\displaystyle {값}_{}}$이 R$$j {$displaystyle R_{$j$\}\}$ 관계를 $충족$하는 경우 $평가{\displaystyle }$ v ${\displaystyle$$$v$}$는 제약 조건 ${\displaystyle {}_{}}{\displaystyle }$t$j$, ${\displaystyle R_{}}$j${\$ {$j}$를 충족합니다.

어떤 제약 조건도 위반하지 않는 한 평가는 일관됩니다.평가는 모든 변수를 포함하는 경우 완료됩니다.평가는 일관되고 완전하다면 해결책이다. 이러한 평가는 제약조건 만족 문제를 해결한다고 한다.

솔루션

유한 도메인의 제약 조건 만족 문제는 일반적으로 검색 형식을 사용하여 해결됩니다.가장 많이 사용되는 기술은 백트랙킹, 제약조건 전파 및 로컬 검색의 변형입니다.이러한 기술은 VLNS 방법과 같이 종종 결합되며, 현재 연구는 선형 프로그래밍과 ^[14]같은 다른 기술을 포함합니다.

백트랙킹은 재귀 알고리즘입니다.변수의 부분 할당을 유지합니다.처음에는 모든 변수가 할당 해제됩니다.각 단계에서 변수가 선택되고 가능한 모든 값이 차례로 할당됩니다.각 값에 대해 부분 할당과 제약조건의 일관성이 체크되고 일관성이 있는 경우 재귀 호출이 실행됩니다.모든 값이 시행되면 알고리즘은 역추적합니다.이 기본 역추적 알고리즘에서 일관성은 변수가 모두 할당된 모든 제약 조건을 만족시키는 것으로 정의됩니다.백트랙에는 몇 가지 종류가 있습니다.백마킹은 일관성 확인의 효율성을 향상시킵니다.백점프를 사용하면 경우에 따라 "여러 변수"를 백트래킹하여 검색의 일부를 저장할 수 있습니다.제약 조건 학습은 나중에 검색의 일부를 피하는 데 사용할 수 있는 새로운 제약 조건을 추론하고 저장합니다.예측은 또한 변수 또는 값 선택의 효과를 예측하기 위해 역추적에서 종종 사용되며, 따라서 때로는 하위 문제가 언제 충족되거나 만족스럽지 못한지를 미리 판단합니다.

제약 조건 전파 기술은 제약 조건 만족 문제를 수정하기 위해 사용되는 방법입니다.보다 정확하게는 변수 그룹 및/또는 제약 조건의 일관성과 관련된 조건인 로컬 일관성의 형태를 적용하는 방법이다.제약 전파에는 다양한 용도가 있습니다.첫째, 그것은 문제를 동등하지만 보통 해결하기가 더 쉬운 문제로 바꾼다.둘째, 문제의 만족도와 불만족도를 증명할 수 있습니다.이것은 일반적으로 발생하는 것을 보증하는 것은 아닙니다.다만, 반드시, 제약 전파의 일부나 특정 종류의 문제에 대해서 발생합니다.로컬 일관성의 가장 잘 알려져 사용되고 있는 형태는 아크 일관성, 하이퍼 아크 일관성 및 경로 일관성입니다.가장 일반적인 제약 전파 방식은 AC-3 알고리즘으로 아크 일관성을 적용합니다.

로컬 검색 방법은 불완전한 만족도 알고리즘입니다.그들은 문제의 해결책을 찾을 수 있지만, 문제가 만족스럽더라도 실패할 수 있습니다.이들은 변수에 대한 완전한 할당을 반복적으로 개선함으로써 작동합니다.각 단계에서 이 할당에 의해 충족되는 제약조건의 수를 증가시키기 위해 소수의 변수 값이 변경됩니다.min-conflicts 알고리즘은 CSP 고유의 로컬 검색 알고리즘으로, 이 원칙에 근거하고 있습니다.실제로 로컬 검색은 이러한 변경사항이 랜덤 선택 사항의 영향을 받는 경우에도 잘 작동하는 것으로 보입니다.검색과 로컬 검색의 통합이 개발되어 하이브리드 알고리즘이 도입되었습니다.

이론적인 측면

의사결정 문제

CSP는 계산 복잡도 이론과 유한 모델 이론에서도 연구된다.중요한 문제는 각 관계 집합에 대해 해당 집합에서 선택된 관계만 사용하여 나타낼 수 있는 모든 CSP 집합이 P인지 NP-완전인지 여부입니다.만약 그러한 이분법 정리가 참이라면, CSP는 NP-중간 문제를 회피하는 NP의 가장 큰 알려진 부분 집합 중 하나를 제공한다. 그 존재는 모든 이용 가능한 관계가 부울 연산자일 때, 즉, 크기 2에 대한 경우를 처리하는 가정 하에 래드너의 정리에 의해 증명되었다.섀퍼의 이분법 정리는 최근에 더 큰 부류의 ^[15]관계들로 일반화되었다.

다루기 쉬운 것으로 알려진 CSP의 대부분의 클래스는 제약의 하이퍼그래프가 나무 너비에 경계를 두거나(및 제약 관계의 집합에는 제한이 없음), 또는 제약 조건이 임의의 형태를 가지지만 제약 관계의 집합에는 본질적으로 비단일 다형성이^{[clarification needed]} 존재하는 클래스입니다.

모든 CSP는 접속 쿼리 억제 ^[16]문제로 간주할 수도 있습니다.

기능상의 문제

기능 클래스 FP와 #P 사이에도 같은 상황이 존재합니다.라드너의 정리를 일반화하면 FP # #P인 한 FP도 #P-완전도 문제가 없다.의사결정 사례와 마찬가지로 #CSP의 문제는 일련의 관계에 의해 정의됩니다.각 문제는 부울 공식을 입력으로 사용하며 작업은 만족스러운 할당 수를 계산하는 것입니다.이는 더 큰 도메인 크기를 사용하여 각각의 만족스러운 할당에 가중치를 부여하고 이러한 가중치의 합계를 계산함으로써 더욱 일반화할 수 있다.복잡한 가중치 부여 #CSP 문제는 모두 FP ^[17]또는 #P-hard에 있는 것으로 알려져 있습니다.

변종

제약 만족 문제의 고전적 모델은 정적, 유연하지 않은 제약의 모델을 정의합니다.이 경직된 모델은 문제를 ^[18]쉽게 표현하기 어려운 단점입니다.모델을 다양한 문제에 적응시키기 위해 기본 CSP 정의의 몇 가지 수정이 제안되었습니다.

동적 CSP

동적 CSP^[19](DCSP)는 일반적으로 고려해야 할 제약 조건이 ^[20]환경에 따라 진화하기 때문에 문제의 원래 공식이 어떤 식으로든 변경될 때 유용합니다.DCSP는 스태틱 CSP의 시퀀스로 간주되며, 각 CSP는 변수와 제약조건을 추가(제한) 또는 삭제(완화)할 수 있는 앞의 CSP의 변환입니다.문제의 초기 공식에서 발견된 정보를 사용하여 다음 정보를 구체화할 수 있습니다.해결 방법은 정보가 전송되는 방식에 따라 분류할 수 있습니다.

• Oracles: 시퀀스에서 이전 CSP에 대해 발견된 솔루션은 현재 CSP의 해결을 처음부터 안내하기 위한 휴리스틱으로 사용됩니다.
• 로컬 복구: 각 CSP는 이전 CSP의 부분 솔루션에서 시작하여 로컬 검색으로 일관되지 않은 제약 조건을 복구합니다.
• 제약사항 기록: 검색의 각 단계에서 새로운 제약사항이 정의되어 일관성 없는 의사결정 그룹의 학습을 나타냅니다.이러한 제약은 새로운 CSP 문제로 이어집니다.

유연한 CSP

기존의 CSP는 제약조건을 엄격히 취급합니다.즉, 제약조건은 반드시 필요한 것(각 솔루션이 모든 것을 만족시킬 필요가 있다)과 유연성이 없는 것(완전히 만족해야 한다, 그렇지 않으면 완전히 위반된다)을 의미합니다.유연한 CSP는 이러한 전제 조건을 완화하고 제약 조건을 부분적으로 완화하며 솔루션이 모든 조건을 준수하지 않도록 합니다.이는 선호 기반 계획의 선호도와 유사합니다.유연한 CSP에는 다음과 같은 종류가 있습니다.

• MAX-CSP: 다수의 제약조건을 위반할 수 있으며 솔루션의 품질은 충족된 제약조건의 수에 따라 측정됩니다.
• Weighted CSP: 사전 정의된 프리퍼런스에 따라 각 제약 위반에 가중치가 부여되는 MAX-CSP.따라서 더 많은 무게로 구속조건을 만족시키는 것이 선호된다.
• 퍼지 CSP 모델 제약조건은 제약조건의 만족도가 변수 값의 연속 함수인 퍼지 관계로서 완전 만족에서 완전 위반으로 변화한다.

분산형 CSP

DCSP에서는^[21] 각 제약 변수는 별도의 지리적 위치를 갖는 것으로 간주됩니다.변수 간의 정보 교환에는 강력한 제약이 가해져 제약 만족 문제를 해결하기 위해 완전히 분산된 알고리즘을 사용해야 한다.

「 」를 참조해 주세요.

• 제약 조건 합성 그래프
• 제약 조건 프로그래밍
• 선언적 프로그래밍
• 제한 최적화(COP)
• 분산 제약 조건 최적화
• 그래프 동형사상
• 독특한 게임 추측
• WCSP(Weighted Constraint Satfaction) 문제

레퍼런스

추가 정보

• YouTube의 제약 만족도에 대한 빠른 소개
• Steven Minton; Andy Philips; Mark D. Johnston; Philip Laird (1993). "Minimizing Conflicts: A Heuristic Repair Method for Constraint-Satisfaction and Scheduling Problems". Journal of Artificial Intelligence Research. 58 (1–3): 161–205. CiteSeerX 10.1.1.308.6637. doi:10.1016/0004-3702(92)90007-k.
• Tsang, Edward (1993). Foundations of Constraint Satisfaction. Academic Press. ISBN 0-12-701610-4
• Chen, Hubie (December 2009). "A Rendezvous of Logic, Complexity, and Algebra". ACM Computing Surveys. 42 (1): 1–32. arXiv:cs/0611018. doi:10.1145/1592451.1592453. S2CID 11975818.
• Dechter, Rina (2003). Constraint processing. Morgan Kaufmann. ISBN 1-55860-890-7
• Apt, Krzysztof (2003). Principles of constraint programming. Cambridge University Press. ISBN 9780521825832. ISBN 0-521-82583-0
• Lecoutre, Christophe (2009). Constraint Networks: Techniques and Algorithms. ISTE/Wiley. ISBN 978-1-84821-106-3
• 토마스 페더, 제약 만족: 개인적인 관점, 원고.
• 제약 아카이브
• RB 모델의 강제 충족 가능한 CSP 벤치마크
• 벤치마크 – CSP 인스턴스의 XML 표현
• XCSP3 – CSP 인스턴스를 나타내도록 설계된 XML 기반 형식
• 제약 전파 – 이론 및 구현 문제에 대한 적절한 조사를 제공하는 Guido Tack의 논문