스튜어드 러셀의 인공지능을 읽어보자(21) :제약 만족 문제1

https://startagainbornagain.tistory.com/127

스튜어드 러셀의 인공지능을 읽어보자(20) : 대항 검색7

 

제약 만족 문제

  저번에는 상태들의 공간을 검색해서 문제를 풀 수 있다는 착안을 살펴보았습니다. 그런 상태들 특정 영역에 국한된 발견법적 함수로 평가하고, 해당 상태가 목표 상태와 부합하는지 판정하면서 상태 공간을 검색합니다. 그런데 검색 알고리즘의 관점에서 각 상태는 더 분해 할 수 없다는 뜻에서 원자적입니다. 즉, 상태는 내부 구조가 드러나지 않는 일종의 블랙박스입니다.

이번 장에서는 광범위한 무제들을 좀 더 효율적으로 푸는 방법 하나를 서술합니다. 이번 장의 방법에서는 각 상태의 분해된 표현(factored representation)을 사용합니다. 즉, 하나의 상태는 여러 변수의 집합으로 표현되며, 각 변수는 각자 하나의 값을 가집니다. 모든 변수의 값이 해당 변수에 가해진 모든 제약(constraint, 구속조건)을 만족하면 문제가 풀린 것입니다. 이런 식으로 서술하는 문제를 가리켜 제약 만족 문제(constraint satisfaction problem, CSP)라고 부릅니다. CSP 검색 알고리즘들은 상태의 구조를 활용하며, 복잡한 문제라도 문제에 고유한 발견법적 함수에 의존하지 않고 범용 발견법적 함수를 이용해서 해답을 구합니다. 주된 착안은, 제약들을 위반하는 변수, 값, 조합을 식별함으로써 검색 공간의 커다란 부분을 단번에 제거한다는 것입니다.

 

이번시간에는 CSP를 위주로 설명합니다. 내일 CSP에 대해 더 공부해보도록 하겠습니다.