제약 만족도 이중 문제

이중 문제는 원래 문제의 각 제약을 변수로 표현하는 제약 만족 문제의 재구성이다.이중 문제에는 이진 제약 조건만 포함되므로 이러한 문제에 맞게 조정된 알고리즘으로 해결할 수 있습니다.제약 조건 만족 문제의 결합 그래프와 결합 트리는 이중 문제 또는 이중 문제를 나타내는 그래프이며 이중 제약 조건을 제거하여 얻은 문제를 나타냅니다.

이중 문제

제약 조건 만족 문제의 이중 문제에는 원래 문제의 각 제약 조건에 대한 변수가 포함됩니다.그 도메인과 제약조건은 원래 문제와 동등하게 적용되도록 구축되어 있습니다.특히 이중문제의 변수 도메인은 대응하는 원래의 제약을 만족시키는 각 태플에 대해 하나의 요소를 포함한다.이와 같이 듀얼 변수는 대응하는 원래 제약조건이 대응하는 태플에 의해 충족되는 경우에만 값을 얻을 수 있습니다.

이중 문제의 제약 조건 때문에 두 개의 이중 변수가 호환되지 않는 두 개의 튜플에 해당하는 값을 취할 수 없습니다.이러한 제약 조건이 없으면 한 이중 변수는 $튜플{\displaystyle }$ x ${\displaystyle =1}$, y ${\displaystyle =}$ $({displaystyle$ x$=1,y=2)$에 해당하는 값을 취하는 반면, 다른 이중 변수는$$y ${\displaystyle =}$ ${\displaystyle 3}$, ${\displaystyle \mathrm{z}}$ $=$ 1({$displaystyle$y$=3,z=$1$\})$에 다른 값을 할당하는 ${\displaystyle \mathrm{y}}$ =${\displaystyle }$3, z=1$}$에 $해당$하는 값을 가질 수 있습니다.

보다 일반적으로 이중 문제의 제약 조건은 두 제약 조건이 공유하는 모든 변수에 동일한 값을 적용합니다.두 개의 이중 변수가 일부 변수를 공유하는 제약 조건에 해당하는 경우 이중 문제에는 두 변수 간의 제약 조건이 포함되어 모든 공유 변수의 동일성이 적용됩니다.

	이중 변수는 원래 문제의 제약 조건입니다.
	각 이중 변수의 도메인은 해당 원래 제약 조건의 튜플 집합입니다.
	이중 제약 조건은 이중 변수(원래 제약 조건)가 원래 변수의 동일한 값을 포함하는 값(원래 탭)을 갖도록 합니다. 이 예에서는 원래 $제약조건{\displaystyle {}_{}}$ $(\$과 $(\$$displaystyle$$C_{2$$\})$는 $y$를 공유합니다.듀얼 문제에서는 $변수{\displaystyle {}_{}}$ $(\$})과 ${\displaystyle {변수\mathrm{}}_{}}$ C2$(\$는 ${\displaystyle \mathrm{값}}({\displaystyle }$1$,$을 가질 수 있습니다$.$$$ 및${\displaystyle }$(${\displaystyle 2,}$1 $)(y$ ${\displaystyle =}$$({$$displaystyle$ y$=2$에서 값이 일치하므로 (2,$1)$ {$displaystyle$ (2,1$)}).$

이중 문제에서는 모든 제약조건이 2진수입니다.모두 두 개의 값, 즉 튜플이 하나 이상의 원래 변수에 일치하도록 강제합니다.

이중 그래프는 이중 문제에서 변수가 어떻게 구속되는지를 나타냅니다.더 정확히 말하면, 이중 그래프에는 각 이중 변수에 대한 노드와 변수 간의 모든 제약 조건에 대한 에지가 포함됩니다.또한 두 변수 사이의 모서리에는 이 두 이중 변수 간에 동일하게 적용되는 원래 변수에 의해 레이블이 지정됩니다.

듀얼 그래프는 원래 문제에서 직접 작성할 수 있습니다.각 제약조건의 정점과 변수를 공유하는 두 제약조건 사이의 모서리를 포함합니다. 이러한 모서리는 이러한 공유 변수에 의해 레이블이 지정됩니다.

이중 그래프두 제약 조건 사이의 가장자리는 공유 변수의 동일성을 강제하는 이중 제약 조건에 해당합니다.예를 들어 $(\$과 $(\$ C_${$$2})$ $사이$에 x${\displaystyle ,}$(\$displaystyle$ x$,y)$라는 라벨이 붙어 있는 ${\displaystyle {엣지}_{}}$는$C1$(\$displaystyle C_{$$1$})과$C2$(\$displaystyle C_$2}}) $사이$의 제약이 듀얼 문제에 포함되어 있음을 나타냅니다.h $on{\displaystyle }$x {\$displaystyle$ x$}$ 및$$$y{\displaystyle }$ {\$displaystyle$ y$\}.$

그래프 결합 및 트리 결합

이중 그래프에서는 일부 제약 조건이 필요하지 않을 수 있습니다.실제로 이중 제약조건은 원래 변수의 평등을 강제하며, 일부 제약조건은 평등의 이동성 때문에 중복될 수 있다.예를 들어 $(\$와 $(\$$displaystyle$ $C_{1})$이 라벨에$$y(\$displaystyle$ y$)$가 $포함$된 가장자리에 결합되어 있는 경우 $(\$과 $(\$$displaystyle$ $C_{3$도 3가지 듀얼 변수에서$y$의 평등이 보증됩니다.그 결과$,$ $C2(디스플레이$ 스타일$C_$${$$2{\displaystyle {}_{}}$$})$와$C3(디스플레이$ 스타일$C_{$3$$}) $사이$에 y($디스플레이$ 스타일 y$)$의 동일성을 강제하는 이중 구속이 필요하지 않으며, 존재하는 경우 제거할 수 있습니다.

$y의$$$동일성은 다른 이중 제약에 의해 강제되므로 $($디스플레이 $스타일 C_{2})$와 $($ C_${3})$ 사이의$$ $것$은 폐기할 수 있습니다.

이중 그래프에서 용장 에지를 제거하여 얻은 그래프를 결합 그래프라고 한다.만약 그것이 나무라면, 그것은 결합 나무라고 불립니다.제거된 모든 가장자리가 중복되므로 결합 그래프에서 이중 문제를 해결할 수 있습니다.차례로, 결합 그래프가 트리인 경우 비순환적 제약 만족 문제에 맞게 조정된 알고리즘을 사용하여 문제를 효율적으로 해결할 수 있다.

결합 트리가 있는 경우 다음 속성을 이용하여 결합 트리를 검색할 수 있습니다.듀얼 그래프에 결합 트리가 있는 경우 그래프의 최대 무게 스패닝 트리는 모두 결합 트리가 됩니다.가장자리에 대응하는 제약조건이 적용되는 변수 수에 따라 가중치가 부여되면 동일해집니다.결합 트리를 찾는 알고리즘(있는 경우)은 다음과 같이 진행됩니다.첫 번째 단계에서는 에지에 가중치가 할당됩니다.두 노드가$$n개의 $변수$를 $공유$하는 제약조건을 나타내는 경우 이들 노드를 결합하는 $에지$에 가중치$$n개(\$display n$가 할당됩니다.두 번째 단계에서는 최대 가중치 스패닝 트리가 검색됩니다.변수를 찾으면 변수의 필수 동일성을 적용하는지 여부를 확인합니다.이 경우 이 스패닝트리는 조인트리입니다

제약조건 만족 문제가 결합 트리를 가지고 있는지 여부를 알아내는 또 다른 방법은 이중 그래프 대신 문제의 원시 그래프를 사용한다.제약조건 만족 문제의 기본 그래프는 노드가 문제 변수이고 가장자리가 동일한 제약조건에 있는 두 변수의 존재를 나타내는 그래프입니다.다음과 같은 경우 문제의 조인 트리가 존재합니다.

1. 원시 그래프는 화음이다.
2. 원시 그래프의 모든 최대 집단 변수는 제약 조건의 범위이며, 그 반대도 마찬가지입니다. 이 속성을 적합성이라고 합니다.

다음으로 변수의 최대 카디널리티 순서를 사용하여 화음을 확인할 수 있습니다.위의 두 가지 조건이 충족되면 문제의 결합 트리를 찾기 위해 이러한 순서를 사용할 수도 있습니다.순서에 따라 가장 높은 변수로 제약조건을 정렬하면 결합트리를 생성하기 위한 알고리즘은 마지막에서 첫 번째 제약조건으로 진행되며, 각 단계에서 제약조건은 순서에서 선행하는 제약조건 중 최대수의 변수를 공유하는 제약조건에 접속된다.

내선번호

모든 제약 조건 만족 문제에 결합 트리가 있는 것은 아닙니다.단, 문제를 수정하여 결합 트리를 얻을 수 있습니다.조인 트리 클러스터링은 공동 트리를 취득하는 방식으로 문제를 수정하는 특정 방법입니다.이는 제약조건을 병합함으로써 이루어지며, 이는 일반적으로 문제의 크기를 증가시킵니다. 단, 결합 트리가 있는 모든 문제와 마찬가지로 결과적으로 발생하는 문제를 해결하는 것은 쉽습니다.

분해 방법에서는 결과적인 문제가 결합 트리를 갖는 방식으로 변수를 그룹화함으로써 결합 트리 클러스터링을 일반화합니다.분해 방법은 트리와 문제를 직접 관련짓습니다.이 트리의 노드는 원래 문제의 관련 변수 및/또는 제약 조건입니다.이 트리에 근거해 구속조건을 Marge 하는 것으로, 결합 트리를 가지는 문제를 발생시킬 수 있어 이 결합 트리는 분해 트리에서 간단하게 도출할 수 있다.또는 분해 트리에서 직접 바이너리 비순환 문제를 구축할 수 있습니다.

레퍼런스

• Dechter, Rina (2003). Constraint Processing. Morgan Kaufmann. ISBN 978-1-55860-890-0
• Downey, Rod; M. Fellows (1997). Parameterized complexity. Springer. ISBN 978-0-387-94883-6
• Georg Gottlob; Nicola Leone; Francesco Scarcello (2001). "Hypertree Decompositions: A Survey". MFCS 2001. pp. 37–57.^{[데드링크]}

「 」를 참조해 주세요.

• 숨겨진 변환