교환성 알고리즘

컴퓨터 과학에서 교환성 알고리즘은 제약 만족 문제(CSP)를 보다 효율적으로 해결하기 위해 사용되는 기술입니다.CSP는 변수로 표현되는 객체가 변수 값의 제약을 받는 수학적인 문제입니다.CSP의 목표는 제약조건과 일치하는 변수에 값을 할당하는 것입니다.CSP의 2개의 변수 A와 B를 서로 교환할 수 있는 경우(즉, A는 B로, B는 A로 교환) 문제의 성질 또는 해결 방법을 변경하지 않고 A와 B는 교환 가능한 변수입니다.교환 가능한 변수는 CSP의 대칭성을 나타내며, 이 대칭성을 이용함으로써 CSP 문제에 대한 해결책의 탐색 공간을 줄일 수 있습니다.예를 들어 A=1 및 B=2의 용액을 시험한 경우, 교환 대칭에 의해 B=1 및 A=2의 용액을 조사할 필요가 없다.

제약 만족 문제에서의 교환성 및 교환성 알고리즘의 개념은 1991년 ^[1]^[2]유진 프로이더에 의해 처음 도입되었다.교환성 알고리즘은 역추적 검색 알고리즘의 검색 공간을 줄여 NP-완전 CSP ^[3]문제의 효율성을 향상시킵니다.

정의들

완전 교환 가능: 변수 값 av가치와 완전히 교환할 수 있습니다.bv = a가 포함된 모든 솔루션이 다음과 같은 경우에만 솔루션을 유지할 수 있습니다.b대신하다a그 ^[2]반대도 마찬가지입니다.

인근 지역 교환 가능: 변수 값 av네이버가 값 b와 교환 가능한 것은 모든 제약조건이 있는 경우뿐입니다.vv = a와 호환되는 값은 v = ^[2]b와 정확히 호환되는 값입니다.

완전 대체 가능: 변수 값 av가치로 충분히 대체할 수 있다bv = a가 포함된 모든 솔루션이 다음과 같은 경우에만 솔루션을 유지할 수 있습니다.b를 대신합니다(단, 반드시 그 ^[2]반대일 필요는 없습니다).

동적으로 교환 가능: 변수 값 av를 위해 동적으로 교환할 수 있습니다.bA에 의해 유발되는 하위 문제에서 변수 할당이 완전히 호환 가능한 경우에만 변수 할당 집합 A와 관련하여.^[2]

유사 코드

근린 교환성 알고리즘

CSP에서 네이버 호환 가능한 값을 찾습니다.각 변수에 대해 반복합니다.

다음을 통해 식별 트리 구축:

각 값 v:에 대해 반복합니다.

각 인접 변수 W에 대해 반복합니다.

v:와 일치하는 각 값에 대해 반복합니다.

있으면^[2] 이동시키고 없으면 W에 해당하는 식별 트리의 노드로 구성합니다.

K-교환성 알고리즘

이 알고리즘을 사용하여 제약 조건 만족 문제에 대한 해결책을 명시적으로 찾을 수 있습니다.알고리즘은 다음 시간 동안 실행할 수도 있습니다.k프리프로세서로서 순서를 실시해, 이후의 백트랙 검색을 간소화합니다.

CSP에서 k-교환 가능한 값을 찾습니다.각 변수에 대해 반복합니다.

다음을 통해 식별 트리 구축:

각 값 v:에 대해 반복합니다.

변수의 각 (k - 1)-tuple에 대해 반복

각 (k - 1)-태플 값에 대해 반복합니다.w와 함께v유발되는 하위 문제에 대한 해결책을 구성하다W:

있으면^[2] 이동시키고 없으면 W에 해당하는 식별 트리의 노드로 구성합니다.

복잡도 분석

네이버 호환 알고리즘의 경우 각 루프에 바인드된 최악의 경우를 할당합니다.다음으로 변수에 대해 최대 d값을 갖는 n개의 변수에 대해 $O(nd(n-l)*d)=O(n^{2}d^{2})$ d ) $O(nd(n-l)*d)=O(n^{2}d^{2})$ O $O(nd(n-l)*d)=O(n^{2}d^{2})$ $O(nd(n-l)*d)=O(n^{2}d^{2})$ = O( $ndisplaystyle$ O $(n-l)*d= O(n^{2}d^{2})$ 의 $O(nd(n-l)*d)=O(n^{2}d^{2})$ 경계가 있습니다.

$O(n^{k-1})$ 로 $(k-1)$ $(k-1)$ $)$ ( $k-1$ $O(n^{k-1})$ ( $k-1$ $)$ (k-1) ( $k-1)$ (k-1 $)$ (k-1) (k-1 $))$ (k-1 $(k-1)$ ) ( $(k-1)$ ) ( $d^{k-1}$ ) (k-1 $d^{k-1}$ ( $k-1$ $)$ (k-1) ( $(k-1)$ ( $k-1$ ) (k-1) (k-1 $(k-1)$ ) (k-1) (k-1) ( $)$ (k-1) (k-1) (k-1) (k-1) (k-1) (k-1) (k-1) (k-1) (k-1) ( $k-1$ ) (k-1) (k-1) (k-1) (k-1) (k-1 $)$ ( $k$ $O(ndn^{k-l}d^{k-1})=O(n^{k}d^{k})$ $O(ndn^{k-l}d^{k-1})=O(n^{k}d^{k})$ k $O(ndn^{k-l}d^{k-1})=O(n^{k}d^{k})$ - $O(ndn^{k-l}d^{k-1})=O(n^{k}d^{k})$ d $O(ndn^{k-l}d^{k-1})=O(n^{k}d^{k})$ - $O(ndn^{k-l}d^{k-1})=O(n^{k}d^{k})$ ) $O(ndn^{k-l}d^{k-1})=O(n^{k}d^{k})$ ( n $O(ndn^{k-l}d^{k-1})=O(n^{k}d^{k})$ $O(ndn^{k-l}d^{k-1})=O(n^{k}d^{k})$ k $O(ndn^{k-l}d^{k-1})=O(n^{k}d^{k})$ ){ $displaystyle O$ ( ndn ^ { $k$ - l }d^ { k - 1 } $O(ndn^{k-l}d^{k-1})=O(n^{k}d^{k})$ = $O(ndn^{k-l}d^{k-1})=O(n^{k}d^{k})$ O ( n^ { $k }d^$ { k } $O(ndn^{k-l}d^{k-1})=O(n^{k}d^{k})$

예

상호 교환성 알고리즘 예제.

이 그림에서는 가장자리에 의해 결합된 두 개의 정점이 동일한 색을 가지지 않도록 색상을 정점으로 하는 단순한 그래프 색칠 예를 보여 줍니다.각 정점에서 사용 가능한 색상이 표시됩니다.노란색, 녹색, 갈색, 빨간색, 파란색, 분홍색은 정점을 나타냅니다.Y정의상 완전히 호환됩니다.예를 들어, 용액 주황색 X(X를 주황색)에서 녹색을 갈색으로 대체하면 녹색 Y가 다른 해를 생성합니다.

적용들

컴퓨터 사이언스에서는 교환성 알고리즘이 인공지능, 그래프 색칠 문제, 추상 프레임 워크 및 솔루션 적응 ^[2]^[4]^[5]^[6]분야에서 광범위하게 사용되어 왔습니다.^[7]^[8]^[9]

레퍼런스

^ Belaid Benhamou 및 Mohamed Reda Saidi "비균등 이진 제약 네트워크에서의 우위에 의한 추론", Laboratoire des Sciences de l'Information et Systmes(LSIS), Centre de Mathématiques et d'Informatique, 프랑스.
^ ^a ^b ^c ^d ^e ^f ^g ^h 프로이드, E.C:제약 만족 문제에서 교환 가능한 값 제거.인: CA 애너하임 AAAI-91의 대리점(1991) 227~233
^ Asef Chmeiss와 Lakhdar Sais "CSP의 인근 지역 대체 가능성에 대하여", Artrois, France 대학, 그리고 그 사이에, 당신은 알게 되었습니다.
^ Haselbock, A.: 제약 만족 문제에서의 상호 교환성 활용.제13회 IJCAI(1993) 282~287호 대리
^ Weigel, R., Faltings, B:제약 조건 만족도 문제를 컴파일하고 있습니다.인공지능 115(1999) 257–289
^ 츄이리, B.Y.: 리소스 할당을 위한 추상화 방법.박사논문, EPFL 박사논문 제1292호(1994)
^ Weigel, R., Faltings, B:구성 문제에서 케이스 적응을 위한 교환 가능성.AAAI98 다모달 추론에 관한 봄 심포지엄의 진행에 있어서, 스탠포드, CA, TR SS-98-04. (1998)
^ Neagu, N., Faltings, B:케이스 적응을 위한 교환성 이용.제4차 ICBR01호(2001)의 대리인
^ Steven Prestwich, Cork 제약조건 계산센터, University College, Cork, Ireland 컴퓨터 과학부, SAT 인코딩에 의한 완전 동적 대체 가능성

[1] Belaid Benhamou 및 Mohamed Reda Saidi "비균등 이진 제약 네트워크에서의 우위에 의한 추론", Laboratoire des Sciences de l'Information et Systmes(LSIS), Centre de Mathématiques et d'Informatique, 프랑스.

[main-2] ^ ^a ^b ^c ^d ^e ^f ^g ^h 프로이드, E.C:제약 만족 문제에서 교환 가능한 값 제거.인: CA 애너하임 AAAI-91의 대리점(1991) 227~233

[3] Asef Chmeiss와 Lakhdar Sais "CSP의 인근 지역 대체 가능성에 대하여", Artrois, France 대학, 그리고 그 사이에, 당신은 알게 되었습니다.

[4] Haselbock, A.: 제약 만족 문제에서의 상호 교환성 활용.제13회 IJCAI(1993) 282~287호 대리

[5] Weigel, R., Faltings, B:제약 조건 만족도 문제를 컴파일하고 있습니다.인공지능 115(1999) 257–289

[6] 츄이리, B.Y.: 리소스 할당을 위한 추상화 방법.박사논문, EPFL 박사논문 제1292호(1994)

[7] Weigel, R., Faltings, B:구성 문제에서 케이스 적응을 위한 교환 가능성.AAAI98 다모달 추론에 관한 봄 심포지엄의 진행에 있어서, 스탠포드, CA, TR SS-98-04. (1998)

[8] Neagu, N., Faltings, B:케이스 적응을 위한 교환성 이용.제4차 ICBR01호(2001)의 대리인

[9] Steven Prestwich, Cork 제약조건 계산센터, University College, Cork, Ireland 컴퓨터 과학부, SAT 인코딩에 의한 완전 동적 대체 가능성

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

Search