2. 탐색과 최적화 - 제약조건 만족 문제

제약조건 만족 문제

: 주어진 제약조건을 만족하는 조합 해를 찾는 문제

 

 

1) 백트래킹 탐색

• 깊이 우선 탐색으로 변수에 허용되는 값을 하나씩 대입
• 만족하는 것이 없으면 이전 단계로 돌아가서 다른 값을 대입

 

2) 제약 조건 전파

: 인접 변수 간의 제약 조건에 따라 각 변수에 허용될 수 없는 값들을 
제거하는 방식