Python Algorithm Chapter3
Python Algorithm
제약 충족 문제
도메인이라는 범위의 값을 가진 변수가 제약 조건을 모두 충족하는 문제
1. 제약 충족 문제 프레임워크 구현하기
제약 조건은 Constraint 클래스로 정의
- 조건 변수
- 충족하는지 검사하는 매소드로 구성
CSP 클래스 : 제네릭을 사용하여 유연하게 처리
- 변수 : 변수 리스트
- 도메인 : 변수에 가능한 값 리스트 매핑하는 딕셔너리
-
제약 조건 컬렉션 : 각 변수에 제약조건(Constraint 클래스) 리스트 매핑된 딕셔너리
__init__(): 딕셔너리 타입의 제약 조건 생성add_constraint(): 모든 변수 제약조건 확인, 각 제약 조건 매핑에 자신을 추가
변수에 도메인이 없거나 존재하지 않은 변수에 제약 조건 있는 경우 예외 발생
consistent(): 주어진 변수에 대한 모든 제약 조건 확인backtracking_search(): 백트래킹 기법 사용(깊이 우선 탐색과 유사) 검색에서 벽에 부딪혔을 때 마지막 결정 지점으로 돌아가 다른 경로 선택
2. 호주 지도 색칠 문제
호주 지도의 분할된 지역을 색칠하는데 인접한 지역에 같은 색을 칠할수 없다.
- 변수 : 호주의 7개 지역
- 도메인 : 색상 3가지
- 제약 조건 : 인접한 지역에 같은 색을 칠할 수 없다. (이진 제약조건 공유)
3. 여덟 퀸 문제
여덟개의 퀸을 서로 위협하지 않는 위치에 위치시키는 문제
- 변수 : 퀸의 열
- 도메인 : 행
- 제약 조건 : 두 퀸이 같은 줄에 있거나 대각선에 있으면 안된다.
(같은 대각선에 있다는 것은 행과 열의 차이가 같다는 것)
4. 단어 검색
행, 열, 대각선에서 특정 단어 찾는 문제 (단어 중복x)
- 변수 : 단어
- 도메인 : 단어의 위치 (모든 문자의 가능한 위치 리스트의 리스트)
- 제약 조건 : 한 단어의 위치가 다른 단어의 위치와 동일한지 확인한다.(리스트를 셋으로 바꿔서 길이 비교하여 줄어들었으면 중복이 있다는 것을 파악)
5. SEND+MORE=MONEY
문자로 표현된 수식에서 각 문자가 나타내는 숫자를 알아내는 문제
무작위로 컴퓨터가 값을 대입하고 다음을 확인해본다.
- 여러 문자에서 중복된 숫자가 없는 지 확인
- 모든 문자에 할당 되었는지 확인
- 수식에 할당된 숫자가 올바른지 확인
마지막으로 모든 문자가 아직 할당되지 않은 경우 True를 반환한다. 이는 부분적인 답이 계속해서 계산되도록 보장하기 위한 것이다. 라는 말을 이해 못했다.
6. 회로판 레이아웃
회로판에 여러 다양한 사각형 모양의 칩을 장착하는 제약 충족 문제