[Study]Chapter 6, 제약 충족 문제
해당 포스트는 공부를 위해 개인적으로 정리한 내용으로 해당 도서에는 다양한 예시를 통해 좀 더 직관적인 이해가 가능합니다.
작성시 목차에 의존하지 말고 내가 직접 생각하면서 정리하기! 만약 목차대로 작성한다면 그냥 “깜지”랑 다를게 없지 않은가?
Artificial Intelligence : A Modern Approach 4th Edition
해당 챕터에서는 상태를 작은 블랙박스 이상의 것으로 취급하면 새로운 검색 방법들을 만들어 낼 수 있고 문제의 구조를 더 깊이 이해할 수 있음을 배운다.
Chapter 6. 제약 충족 문제.
검색 알고리즘의 관점에서 각 상태는 원자적이다. 즉, 상태는 더 이상 분할할 수 없는 어떤 것이고, 내부 구조가 드러나지 않ㄹ는 일종의 블랙박스에 해당한다.
이번 장에서는 각 상태의 분해된 표현\(_{factored-representation}\)을 이용해서 그런 블랙박스를 열어본다. 분해된 표현에서 하나의 상태는 여러 변수의 집합이고, 각 변수는 각자 하나의 값을 가진다. 모든 변수의 값이 해당 변수에 가해진 모든 제약\(_{constraint}\)을 충족하면 문제가 풀린 것이다. 이런 식으로 서술하는 문제를 가리켜 제약 충족 문제\(_{constraint-satisfaction-problem;CSP}\)라고 부른다.
제약 충족문제의 정의
제약 충족 문제는 아래와 같은 세 구성요소로 이루어진다.
Figure : 6-1
CSP에서 값들을 변수들로 배정하는 연산 , 즉 \(\{X_i=v_i\}\)이 관여한다. CSP의 해답은 일관 배정이자 완전 배정이다. 어떤 제약도 위반하지 않는 배정을 일관배정이라 부르고, 모든 변수에 값이 배정된 것을 완전 배정이라고 부른다.
문제를 CSP로 형시고하하는 이유는 무엇인가? 주어진 문젤를 손쉽게 형식화 가능하고, 빠르고 효율적인 해결기들이 개발되어있고, 검색 공간의 커다란 부분을 빠르게 제거 가능하다.
전체 작업은 여러 과제로 구성되며, 각 과제를 변수로 모형화할 수 있다. 각 변수의 값은 과제를 시작하는 시간을 뜻하는 정수라고 하자.
\[T_1 + d_1 \leq T_2\]\(_{T_1}\)이 반드시 \(_{T_2}\) 이전에 수행되어야하고 완료에 걸리는 시간이 \(_{d_1}\)이하여야 한다는 개별 과제 사이의 선행 관계 제약\(_{precedence-constraint}\)을 위와 같이 표현하였다.
Figure L 6-2
또한, 위와 같이 작업자가 네 명이지만, Nuts 라는 도구를 공유하는 경우를 처리하려면 시간이 겹치지 않아야 한다는 논리합 제약\(_{disjunctive-constraint}\)이 필요하다.
가장 간단한 종류의 CSP는 변수들이 이산적이고 그 정의역이 유한한 경우이다. 정수 변수들에 대한 선형 제약에 대해서는 튼ㄱ별한 해법 알고리즘을디 존재한다. 선형 제약은 각 변수가 선형으로만 나타나는 제약을 말한다.
일반적인 비선형 제약을 푸는 알고리즘은 존재하지 않음(결정불가능)을 증명하는 것이 가능하다. 연속적 정의역 CSP들 중 가장 알려진 부류는 선형 계획법 문제로 시간 복잡도는 변수 개수에 대해 다항식적이다.
CSP에 나타날 수 있는 벼수들의 종류를 조사하는 것 외에, 제약들의 종류를 살펴보는 것도 도움이 된다. 일례로 변수가 가질 수 있는 값을 제한하는 단항 제약\(_{unary-constraint}\)나 이항 제약의 더 고차의 제약들도 서술 할 수있다.
임의의 개수의 변수들이 관여하는 제약을 전역 제약이라고 부른다. 복면산\(_{cryptarithmetic}\) 퍼즐에도 전역 제약이 존재하는데, 이러한 제약들을 아래와 같이 하나의 제약 초그래프\(_{constraint-hypergraph}\)로 표현할 수 있다.
Figure3 : (a)복면산 퍼즐로 각 글자는 서로 다른 숫자를 나타내고 각 글자를 특정 숫자로 치환하는 것 (b)복면산 퍼즐의 초그래프로 모두 다르다는 제약(최상단 상자)과 각 자리의 덧셈 제약들이 표시되어 있다.
지금까지의 제약은 해당 규칙을 위반하면 해답이 될 수 없는 절대적인 제약들이지만 현실의 CSP들에는 어떤 해답을 더 선호할 것인지를 나타내는 선호 제약\(_{preference-constraint}\)이 있는 것도 많다. 선호 제약이 있는 제약 충족 문제를 최적화 검색 방법들을 이용하여 제약 최적화 문제\(_{constrained-optimization-problem;COP}\)라 부른다.
제약 전파 CSP의 추론
CSP알고리즘은 새 변수 배정을 선택함으로써 후행자들을 생성할 수도 있고, 제약 전파라고 부르는 특정 종류의 추론을 수행할 수 도있다. 제약전파란 제약들을 이용해서 한 변수가 가질 수 있는 값들의 개수를 줄이고, 이에 기반하여 다른 변수의 적법한 값들을 줄이는 과정을 반복하다 보면 다음 변수 배정을 할때 선택지가 줄어들 것이라는 착안이 깔려 있다.
핵심 개념은 국소 일관성으로 각 변수를 그래프의 노드로 간주하고 각 이항 제약을 간선으로 간주할 때(Figure3의 b), 그래프의 각 부분에서 국소 일관성을 강제하는 과정을 반복하다 보면 그래프 전반에서 일관성 없는 값들이 제거된다.
- 노드 일관성 : 정의역의 모든 값이 단항제약들을 충족할때
- 호 일관성 : 정의역의 모든 값이 이항제약들을 충족할때
- ex) AC-3알고리즘 : 대기열에서 임의의 호(X1, X2)를 뽑아 호일관적이게 만들고, 변하지 않는다면 다음 호로 넘어간다. 변수 개수 n; 각 변수의 정의역 개수 d; 이항 제약이 c개라 가정하면 한 호의 일관성을 강제하는데 필요한 시간은 \(_{O(d^2)}\)이므로, 최악의 경우의 총 시간은 \(_{O(cd^3)}\)이다.
- 경로 일관성 : 세 변수 쌍에서 추론한 암묵적 제약을 이용해서 이항 제약들을 좀 더 강하게 만든다.
- k-일관성 : k-1개의 변수들로 이루어진 임의의 집합과 임의의 일관적 배정에 대해, 임의의 k번쨰 변수에 일관적인 값을 배정할 수 있다면 k-일관적이다.
- ex)1-일관성은 노드 일관성, 2-일관성은 호 일관성 등으로 나아갈 수 있다.
일반적으로 제약 충족 문제는 NP-완전이지만 최악의 경우 시간 복잡도와 공간 복잡도가 n에 지수적이다.
전역 제약
전역 제약은 임의의 개수의 변수들이 관여하는 제약을 뜻한다. 이는 실제 문제에 자주 등장하며, 예를들어 모든 변수가 반드시 값이 달라야 한다는 제약의 비일관성을 점검하는 간단한 방법은 제약의 변수들중 정의역이 한원소집합인 것들을 모두 제거하고, 나머지 변수들의 정의역에서 그 변수들의 값들을 모두 제거를 반복한다. 이 과정에서 공집합 정의역이 나타나거나 정의역 값들의 개수가 변수 개수보다 적어지면, 제약의 비일관성이 검출되는 방법이 있다.
더 고차 제약으로 자원 제약이 있으며 커다란 자원 제약 문제에서는 정의역을 상계와 하계로 표현하고 경계 전파 기법으로 줄여나가는 방식이 있따.
CSP를 위한 역추적 검색
제약 전파 과정을 마친 후에도 가능한 값이 여러 개인 변수들이 남아있을 때가 있다. 이런 경우 해답을 검색해야한다. CSP의 핵심적인 성질인 주어진 동작들을 적용하는 순서가 최종 결과에 영향을 미치지 않는 성질인 가환성\(_{commutativity; 교환성}\)을 이용하면 검색트리의 잎을 줄일 수 있다.
Backtracking-SEARCH는 검색 도중 한 상태의 표현 하나만 유지하며, 매번 새 표현을 생성하는 대신 그표현을 수정한다는 점을주목해야한다.
Figure 4 :
제3장의 정보 없는 검색 알고리즘은 영역 특화\(_{domain-specific}\) 발견적 함수를 지정해야 개선가능헀지만, 역추적 검색은 CSP의 분해된 표현의 장점을 취하는 영역 ㅗㄱ립 발견적 함수로 개선할 수 있다. 다음과 같은 네가지 질문으로 나누어 살표보자.
- 어떤 변수를 배정하는가? SELECT-UNASSIGNED-VARIABLE 그리고 어떤 순서로 시도하는가?
- 가장 간단한 전략은 정적 순서로 변수들을 그냥 차례로 선택하거나 무작위 선택이지만 ‘적법한’값이 가장 적은 변수부터 선택한다는 직관적인 착안으로 최소 잔여 값\(_{minimut-remaining-values;MRV}\)발견법등이 있고, 차수발견법, 최소제약값 등이 있다.핵심은 문제의 해답을 하나만 구하면 되어 해답의 일부일 가능성이 가장 큰 값을 먼저 조사하는 것이 합당하다. 해답 하나가 아니라 모든 해답을 나열해야 한다면 값 순서 결정은 중요하지 않다.
- 각 단계에서 어떤 추론을 수행할 것인가? INFERECNE
- 추론은 검색 도중에 더욱 강력한 효과를 낼 수 있다. 변수의 값을 선택하는 시점에서는 항상 그 이웃 변수들의 정의역을 줄일 새로운 기회가 생긴다. 간단한 형태로는 순방향 점검으로 변수 X에 값을 배정할떄마다 변수에 대한 호 일관성을 강제한다. 정보를 전파함으로써, 변수들에 대한 분기가 완전히 제거되어 정의역이 하나의 값으로 줄었으며 부분 배정이 문제의 제약들에 비일관적임을 검출하여 알고리즘은 즉시 역추적을 수행한다.
- 필요하다면 BACKTRACK을 한 단계 이상 실행가능한가?
- 검색의 한 분기가 실패했을 때 한은 일은 아주 간단하다. 이전 변수로 돌아가서 다른 값을 시도하는 것. 이를 연대순 역추적이라고 부른다.좀 더 지능적인 접근방식은 문제를 해결할 수 있을 만한 변수로 책임이 있는 변수로 돌아가는 것으로 역도약\(_{backjumping}\)방법은 그러한 충돌 집합에 있는 가장 최근 배정으로 돌아간다. 역도약은 한정의역의 모든 ㅏㅄ이 현재 배정과 충돌할 떄 일어난다. 그러나 순방향 점검은 사건을 검출하고, 검색이 그런 노드로 도달하는 일을 방지한다. 사실 역도약에 의해 잘라나가는 모든 가지는 순방향 점검에 의해서도 잘려나감이 증명가능해 단순한 역도약은 순방향 점검 검색과 중복이다.
- 검색의 부분 결과를 저자ㅣㅇ하고 재활용 할 수 있는가?
- 제약 학습은 충돌 집합 중 문제를 일으킨 최소한의 변수들의 집합을 찾는다. 그러한 변수 집합과 해당 값들의 조합을 가리켜 무익이라고 부른다. 이러한 조합을 찾았ㄷ마ㅕㄴ 개별적인 캐시에 추가함으로써 기록해 둔다. 순방향 점검이나 역도약은 이러한 무익 조합들을 유용하게 사용할 수 있는데 제약 학습은 현대적인 CSP해결기들이 복잡한 문제를 효율적으로 푸는 데 쓰이는 가장 중요한 기법의 하나이다.
csp를 위한 국소 검색
국소 갬색 알고리즘은 완전한 상태 형식화를 사용한다. 즉, 각 상태는 모든 변수에 값을 배정하며, 검색은 한 번에 변수 하나의 값을 변경한다.가장 자명한 접근방식은 다른 변수와의 충돌이 최소과 되는 값을 선택하는 최소 충돌발견법이 있다. 이러한 방법은 여러 csp에 대해 기막히게 효과적이다. 최소 충돌의 실행 시간은 대체로 문제의 크기에 독립적이다 심지어 백만 퀸 문제를 평균 50단계로 푼다.
왜 줄푸는지 대충 말하자면, 해답들이 상태 공간 전반에 조밀하게 분포되어 있다는 ㅓㅅ이다. 대체로, 최소 충돌 발견법 하에서의 csp의 지형에는 일련의 대지들이 존재하고 이를 탈출하게 하는 데에는 횡이동을 허용하는 대지 검색이 도움이 된다. 대지 안에서의 탐색 방향을 결정하는 데에는 터부 검색이라는 기법이 유용하다. 제약 가중이라고 하는 또 다른 기법은 검색이 중요한 제약들에 집중하게 만들려 한다. 각 제약에 가중치를 부여하여 대지들에 지형지물을 추가함으로써 현재 상태로부터의 개선이 반드시 일어나게하고 시간이 지남에 따라 어려운 제약들에 점점 더 큰 가중치를 배정함으로써 일종의 학습이 일어난다.
또 다른 이점은, 문제가 동적으로 변하는 온라인 환경에도 사용할 수 있다는 것이다.
문제의 구조
제약 그래프의 형태로 표현된 문제의 구조를 활용해서 해답을 빠르게 찾아내는 방법들을 조사한다.
방대한 규모으ㅟ 실제 세계를 다루려면, 문제를 여러 부분 문제들로 분해해야 그나마 풀 희망이 생긴다. 지도 채색 문제의 제약그래프를 보면 독립적인 부분 문제임이 자명하다.
Figure 5 :
이러한 독립성은 제약 그래프에서 연결된 구성요소들을 찾아보면 쉽게 확인할 수 있따. 각 구성요소는 각 부분 문제 CSP에 해당한다. 이것이 왜 중요할까? CSP를 부분문제로 분할하면 최악의 경우의 시간이 우주의 나이에서 1초 미만으로 줄어든다.
따라서, 완전히 독립적인 부분 문제들이 바람직하지만, 그런 부분 문제들은 드물다. 다행히 쉽게 풀 수 있는 또 다른 성격의 그래프 구조가 존재하는데 사실상 하나의 트리이다. 임의의 트리구조 CSP는 변수 개수에 선형인 시간으로 풀 수 있다는 점으로 핵심은 방향 호 일관성 이라는 새로운 일관성 개념을 도입하는 것이다. 트리의 뿌리에서 임의의 변수를 선택하고, 각 변수가 트리에서 자신의 부모 다음에 나타난다는 조건을 충족하는 변수들의 순서 관계를 선택한다., 그런 순서 관계를 위상 정렬\(_{topological-sort}\)이라고 부른다. 부모에서 자식으로의 모든 간선은 호일관적이므로 유효한 값이 남아 역추적이 필요하지 않음을 뜻해 변수들을 따라 직선으로 움직이면 된다. 이런 트리보다 더 일반적인 제약 그래프를 어떤 방식으로든 트리로 축약하는 문제로 노드를 제거하는 방식과 노드들을 합치는 방식들이 있따.
절단 집합 조건화
트리를 축약하는 접근방식중 하나로 나머지 변수들이 트리를 형성하도록 일부 변수들에 값을 배정하는 것이다.이렇게 주어진 CSP의 변수들 중, 제약 그래프에서 제거한다면 제약 그래프가 트리로 변하는 변수들을 찾았을때 그러한 변수들의 집합을 순환 절단 집합이라고 부른다.
Figure 6 :
가장 작은 순환 절단 집합을 찾는 것은 NP-hard 문제이나, 효율적인 근사 알고리즘들이 알려져 있으며 이러한 접근방식을 통칭해서 절단 집합 조건화라 부른다.
트리 분해
두번쨰 접근방식으로 트리 분해를 구축한다.
Figure 7 :
모든 변수가 적어도 하나의 트리 노드에 있어야 하며 제약으로 연결된 두 변수는 적어도 하나의 트리 노드에 함께 있어야 하고, 한 변수가 트리의 두 노드에 있다면 그 두 노드를 연결하는 경로의 모든 노드에 그 변수가 있어야 한다는 필수 조건을 충족해야한다.
처음 두 조건은 모든 변수와 제약이 트리 분해로 표현됨을 보장하기 위한것이고 세번째 조건은 원래 문제의 각 변수의 값은 트리의 인접 노드에 있는 해당 변수들의 값과 같아야 한다는 점을 나타내기 위해서 필요하다.
일단 그래프를 트리로 축약하고 나면 TREE0CSP-SOLBER를 이용해 \(O(nd^2)\)의 시간으로 해답을 구할 수 있다. 그 어떤 트리 분해 문제도 해당 시간안에 풀 수 있따. 즉, 제약 그래프의 트리 너비가 유계인 CSP는 다항식 시간으로 풀 수 있다. 안타깝게도, 트리 너비가 최소인 분해를 찾는 것인 NP-hard의 문제이다.
값 대칭성
그런데 변수의 값들에도, 또는 제약 관계들 자체에도 중요한 구조가 있을 수 있다. 예예를들어 세지역에 세 가지 색을 배정하는 방법은 3!=6이다. 색 이름들을 순열치환해서 얻을 수 있는 d!개의 해답이 존재하면 이를 값 대칭성이라고 부르는데, 대칭성 파괴 제약을 도입하여 검색 공간을 줄일 수 있다.