[인공지능] 과제하다 어려워서 정리 하는 용어정리_ CSP,AC3,휴리스틱,MRV, LCV,MAC

안녕하세요. 우당탕탕 개발일지입니다.  BFS, DFS는 코드트리에서 학습했는데요. CSP문제는 코드트리에 없어서 블로그랑 용어 검색하면서 공부하고 있습니다. 아핫.. 다들 이렇게 공부하는게 맞걸까요.. 어렵네요 ㅎㅎ

 

1.AC3 알고리즘 (= AC-3)

: arc-Consistency 3  : 제약 충돌문제 (CSP) 에서 사용되는 알고리즘 

 

두 변수 X, Y에 대해, X의 도메인에 있는 모든 값에 대해 Y의 도메인에 제약을 만족하는 값이 반드시 존재해야 한다는 의미다.

예를 들어, 제약이 X≠Y 라면, X의 어떤 값에도 Y에서 다른 값이 존재해야 함. 

 

2. CSP(Constraint Satisfaction Problem)
: 변수들에 값을 할당하되, 주어진 모든 제약 조건을 만족하는 해를 찾는 문제 유형.

• 변수: 할당해야 하는 대상. 
• 도메인: 각 변수에 할당할 수 있는 값들의 집합.
• 제약 : 변수들 간에 반드시 지켜야 하는 조건.

 

3. 변수의 도메인

: 변수가 가질 수 있는 값들의 목록 (정답후보)

 

4. 휴리스틱 알고리즘.

: 최적의 해를 반드시 보장하지는 않지만 제한된 시간내에  충분히 좋은 해답을 빠르게 찾기 위해 경험적 규칙이나 직관적인 방법을 사용하는 알고리즘이다.  (CSP에서의 휴리스틱 기법: MRV, LCV, Degree) 

 

5.MRV, LCV, MAC

이름	적용단계	원리	요약
MRV	변수 선택	도메인에 남은 값이 가장 적은 변수 선택, 실패를 빠르게 감지(fail first)	가능한 값이 적은 변수를 먼저 선택해 탐색 효율화
LCV	값 선택	제약을 가장 적게 주는 값을 선택, 경우의 수를 최대화(fail last)	이후 변수의 도메인을 가장 적게 제한하는 값을 우선 선택
MAC	제약 전파 (일관성)	변수 할당 시마다 Arc Consistency유지, 도메인 불필요 값 미리 제거	할당된 변수와 연결된 모든 변수 쌍에 대해 도메인에서 불필요한 값 반복적으로 제거