하이브리드 알고리즘(기존 만족도)

이 글에는 여러 가지 문제가 있다. 이 문제를 개선하거나 대화 페이지에서 토의하십시오. (이러한 템플릿 메시지를 제거하는 방법 및 시기 알아보기) 이 글은 주제를 잘 모르는 사람들에게 불충분한 맥락을 제공한다. 독자에게 더 많은 맥락을 제공하여 기사를 개선할 수 있도록 도와주십시오. (2012년 6월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기) 이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "하이브리드 알고리즘" 제약 만족도 – 뉴스 · 신문 · 책 · 학자 · JSTOR (2012년 6월) (이 템플릿 메시지 제거 방법과 시기 학습) 이 글에는 참고문헌, 관련 독서 또는 외부 링크 목록이 수록되어 있으나 인라인 인용구가 부족하여 출처가 불분명하다. 좀 더 정밀한 인용구를 도입하여 이 기사를 개선할 수 있도록 도와주십시오. (2012년 6월) (이 템플릿 메시지를 제거하는 방법과 시기 알아보기) (이 템플릿 메시지를 제거하는 방법 및 시기 알아보기)

제약조건 만족도에서, 하이브리드 알고리즘은 두 가지 방법의 조합에 의해 제약조건 만족 문제를 해결하는데, 예를 들어 가변 조건화(backtracking, backjumping 등)와 제약조건 추론(arc 일관성, 가변 제거 등)이 그것이다.

하이브리드 알고리즘은 서로 다른 방법의 좋은 속성을 그들이 효율적으로 해결할 수 있는 문제에 적용함으로써 이용한다. 예를 들어, 검색은 문제가 많은 해결책을 가지고 있을 때 효율적인 반면, 추론은 과도하게 제약된 문제의 만족도를 증명하는 데 효과적이다.

사이클 컷셋 추론/검색 알고리즘

이 하이브리드 알고리즘은 변수 집합에 대한 검색 실행과 다른 변수들에 대한 추론에 기초한다. 특히, 역추적 또는 다른 형태의 검색은 여러 변수에 걸쳐 실행된다. 이러한 변수에 대한 일관된 부분 할당을 발견할 때마다, 이 부분 할당을 확장하여 솔루션을 구성할 수 있는지 여부를 확인하기 위해 나머지 변수에 대해 추론을 실행한다.

어떤 종류의 문제에는 효율적이고 완전한 추론 알고리즘이 존재한다. 예를 들어 원시 그래프나 이중 그래프가 나무나 숲인 문제는 다항식 시간에 해결할 수 있다. 이는 검색에 의해 평가된 변수의 선택에 영향을 미친다. 실제로 변수를 평가한 후에는 그래프에서 효과적으로 제거할 수 있으므로 변수의 값과 관련된 모든 제약조건을 제한할 수 있다. 또는 평가된 변수를 각 제약조건에 하나씩, 단일 값 도메인을 갖는 여러 개별 변수로 대체할 수 있다.

이 혼합 알고리즘은 검색 변수를 선택해서 중복되거나 삭제하는 것이 문제를 추론에 의해 효율적으로 해결할 수 있는 것으로 바꾼다면 효율적이다. 특히 이러한 변수들이 문제의 그래프의 사이클 컷셋을 형성한다면, 추론은 그래프가 나무인 문제나 더 일반적으로 숲인 문제를 해결해야 하기 때문에 효율적이다. 그러한 알고리즘은 다음과 같다.

모든 변수에 대한 일관된 부분 할당이 발견될 때 컷셋 변수에 대한 문제 실행 검색 그래프의 사이클 컷셋을 찾고, 컷셋의 각 변수를 각 제약조건에 대한 새 변수로 교체하고, 이러한 새로운 변수의 도메인을 부분 할당 해결의 이전 변수 값으로 설정한다. 추론을 이용한 문제 

이 알고리즘의 효율성은 두 가지 대조적인 요소에 따라 달라진다. 반면 컷셋이 작을수록 검색으로 해결해야 할 부문제점은 작다. 나무에서 추론이 효율적이기 때문에 검색은 효율성에 가장 큰 영향을 미치는 부분이다. 반면 미니멀한 사이즈의 컷셋을 찾는 것은 어려운 문제다. 그 결과 최소 사이클 대신 소형 사이클 컷셋을 사용할 수 있다.

검색 실행 시간을 줄일 수 있는 또 다른 대안은 추론 부분에 더 많은 부담을 주는 것이다. 특히 문제 그래프가 숲이 아니라 작은 유도폭의 그래프라 하더라도 추론은 비교적 효율적일 수 있다. 이것은 사이클 컷셋이 아니지만 일단 제거되면 문제를 일부 값 $[\displaystyle b}$에 의해 너비가 경계를 이루도록 유도하는 변수 집합에 대해 검색을 수행함으로써 이용할 수 있다$.$^{[clarification needed]} 이러한 변수 집합을 문제의 $b{\displaystyle }$ ${\displaystyle b}$ -컷셋이라고$$ 한다.

일련의 변수가 제거된 후 그래프의 유도 폭을 조정 유도폭이라고 한다. 따라서 $b{\displaystyle }$ ${\displaystyle b}$ 컷셋에$$ 대해 조정된 유도 폭은 항상 $b{\displaystyle }$ ${\displaystyle b}$이며$,$ 최소 크기 $b{\displaystyle }$ ${\displaystyle$ b$}$ -컷셋을$$ 찾는 것은 일반적으로 어렵다. 그러나 변수의 고정 순서에 따라 $최소{\displaystyle }$ 크기가 아닌 b ${\displaystyle b}$ -컷셋을$$ 쉽게 찾을 수 있다. 특히, 그러한 컷셋은 변수의 특정 순서에$$ $따라{\displaystyle }$ b$${\$displaystyle b}$로 경계된 폭의 그래프를 남긴다.

이러한 컷셋을 찾기 위한 알고리즘은 고려된 변수의 순서에 따라 문제의 유도 그래프를 찾는 절차를 모방하여 진행한다(이 절차는 순서의 마지막 노드에서 첫 번째 노드로 진행되며, 모든 노드의 연결되지 않은 부모 쌍 사이에 엣지가 추가된다). 이 절차에서 $b{\displaystyle }$ ${\displaystyle b}$개 이상의 부모를$$ 가진 노드를 찾거나 만들 때마다 노드는 그래프에서 제거되고 컷셋에 추가된다. 정의상 결과 그래프는 $b{\displaystyle }$ ${\displaystyle b}$보다 큰 폭의 노드를 포함하지 않으며$,$ 따라서 제거된 노드 $집합$은 b ${\displaystyle b}$ -cutset이다$$.

이 알고리즘을 사용하는 대안은 검색을 통해 변수를 평가하도록 하되, 각 단계에서 나머지 그래프가 포리스트인지 확인하고, 이 경우 추론을 실행하는 것이다. 즉, 초기에 변수 집합을 찾아 검색 중에만 사용하는 대신 알고리즘은 정기 검색으로 시작한다. 각 단계에서 할당된 변수가 $문제$의 b ${\displaystyle b}$컷셋을$$ 형성하면 추론을 실행하여 만족도를 확인한다. 이는 주어진 노드 집합이 $고정{\displaystyle }$ b ${\displaystyle b}$에 $대한{\displaystyle }$ b ${\displaystyle b}$ 컷셋인지$$ 확인하는 것은 다항식 문제이기$$ 때문에 가능하다.

트리 분해 하이브리드 알고리즘

또 다른 하이브리드 검색/추론 알고리즘은 트리 분해에 대해 작용한다. 일반적으로 제약조건 만족 문제는 먼저 나무 분해를 만든 다음 전문 알고리즘을 사용하여 해결할 수 있다.

그러한 알고리즘 중 하나는 먼저 노드 사이에 제약조건을 전파한 다음 각 노드의 하위 문제를 해결하는 것에 기초한다. 이 전파는 결합한 노드에 대한 노드의 제약조건의 영향을 나타내는 새로운 제약조건을 만드는 것으로 구성된다. 더 정확히 말하면, 두 개의 노드가 결합되면 변수를 공유한다. 첫 번째 노드의 제약조건에 따라 이러한 변수의 평가가 허용되면 첫 번째 노드가 두 번째 노드의 변수에 어떻게 영향을 미치는지 알 수 있다. 알고리즘은 이러한 평가에 의해 충족되는 제약조건을 만들고 이 새로운 제약조건을 두 번째 노드에 통합함으로써 작동한다.

모든 제약조건이 잎에서 뿌리로, 그리고 다시 뿌리로 전파되었을 때, 모든 노드는 그것과 관련된 모든 제약조건을 포함한다. 따라서 이 문제는 각 노드에서 해결할 수 있다.

노드 내에서 전파되는 새로운 제약조건을 생성하기 위한 가변 제거와 각 개별 노드에 대한 검색 알고리즘(백트랙팅, 백점핑, 로컬 검색 등)을 사용하여 하이브리드 접근방식을 취할 수 있다.

참조

• Dechter, Rina (2003). Constraint Processing. Morgan Kaufmann. ISBN 1-55860-890-7.