해시넷
"역추적검색"의 두 판 사이의 차이
dlwldms1012 (토론 | 기여) |
dlwldms1012 (토론 | 기여) |
||
| 2번째 줄: | 2번째 줄: | ||
==개요== | ==개요== | ||
| − | 역추적검색은 제약조건 만족 문제를 해결하기 위해 조합 알고리즘 문제에 대해 가능한 모든 해를 나열하는 것이다. 제약조건 만족 문제는 완전한 해를 가진 문제이고, 요소들의 순서는 문제 되지 않는다. 그 문제는 값이 할당되어야 하는 일련의 변수들로 구성되며, 특별한 제약조건에 민감하다. 부분적인 조합을 시도해 보지 않아도 된다는 장점이 있으며, 조건을 만족할 경우 모든 경우의 수를 찾는 것보다 빠를 수 있다. 역추적검색이라는 용어는 1950년 미국의 수학자 [[데릭 레머]](Derrick Lehmer)에 의해 만들어졌다. 역추적검색은 맞는 답을 구할 때까지 모든 가능성을 | + | 역추적검색은 제약조건 만족 문제를 해결하기 위해 조합 알고리즘 문제에 대해 가능한 모든 해를 나열하는 것이다. 제약조건 만족 문제는 완전한 해를 가진 문제이고, 요소들의 순서는 문제 되지 않는다. 그 문제는 값이 할당되어야 하는 일련의 변수들로 구성되며, 특별한 제약조건에 민감하다. 부분적인 조합을 시도해 보지 않아도 된다는 장점이 있으며, 조건을 만족할 경우 모든 경우의 수를 찾는 것보다 빠를 수 있다. 역추적검색이라는 용어는 1950년 미국의 수학자 [[데릭 레머]](Derrick Lehmer)에 의해 만들어졌다. 역추적검색은 맞는 답을 구할 때까지 모든 가능성을 시도하며, 트리를 검사하기 위해 주로 깊이 우선 탐색을 사용한다. 탐색 도중 오답을 만나면 이전 분기점으로 돌아가고, 시도해 보지 않은 방법이 있으면 시도하고, 해결 방법이 없으면 더 이전 분기점으로 돌아간다. 모든 트리의 노드를 검사해도 답을 못 찾을 경우 이 문제의 해결 방법은 존재하지 않는 것이다. 역추적검색은 보통 각각의 인스턴스가 하나 이상의 변수를 가지고 모든 이용 가능한 값을 그 변수에 할당하는 재귀 함수 형태를 가지고, 계속되는 재귀 호출과 일치하는 값을 유지한다. 역추적검색은 깊이 우선 탐색과 유사하지만 공간 사용이 덜하며 딱 한 개의 최신 변수만 유지하고, 업데이트한다. 탐색 속도를 빠르게 하기 위해서 재귀 호출을 하기 전에 값이 선택될 때, 그 알고리즘은 할당되지 않은 영역과 다투지 못하도록 그 값을 제거하는 전방향 체크(forward checking)나 새로이 할당된 값이 어떤 다른 값을 배제하는지 보기 위해 모든 제약조건을 체크하는 제약전파(constraint propagation)를 사용한다. 넓이 우선 탐색의 경우 상대적으로 많은 메모리가 필요하기 때문에 일반적으로 깊이 우선 탐색을 통하여 구현한다. 역추적검색은 [[프롤로그]](Prolog) 같은 프로그램 언어에 사용되며, 텍스트 파싱(text parsing)에도 사용된다. 행위자 모델 개발에 쓰이는 [[인공지능]]에 적용하려는 움직임도 있었다. 역추적검색으로 해결할 수 있는 문제는 여덟 개의 퀸 퍼즐, 스도쿠, 십자말풀이 등이 있다. |
==휴리스틱== | ==휴리스틱== | ||
| − | 역추적검색을 빠르게 | + | 역추적검색을 빠르게 만들기 위해 몇몇 휴리스틱을 사용한다. 변수는 어떤 순서로도 처리할 수 있으므로 보통 효율적인 방법은 가장 한정된 조건을 먼저 시도하는 것이다. 이런 가지치기는 탐색 트리를 작게 해 최소의 비용으로 최대의 결과를 얻을 수 있다. 또, 어떤 값을 할당할 것인지 선택할 때 어떤 값이 최소 개수의 미래의 값들을 제약하는지 보는 전방향 체크를 사용한다. 전방향 체크는 해를 더 빨리 얻을 것 같은 값을 선택하는 것이다. 해결 방법이 가장 있을 것 같거나 가장 없을 것 같은 것을 찾아 탐색 트리를 작게 만든다. 섬세한 역추적검색은 분기 함수(bounding function)를 사용한다. 분기 함수는 해를 얻는 것이 가능한지 확인하기 위해 검사되는 문제에 만들어 모든 할당 단계에서 작동한다. 그래서 간단한 테스트를 통해 실패할 것 같은 부분적인 해를 찾아내 탐색 대상의 99%까지 제외하기도 한다. 분기 함수는 종종 지수적 탁샘공간인 모든 단계에서 작동하기 때문에, 계산하기 쉬워야 한다. 되돌릴 때 복구할 값들을 최소로 유지하기 위해 역추적검색은 변수 이력을 사용한다. 변수 이력은 변수 값이 바뀐 내역을 보관해, 분기점이 없을 때 값 변화에 대한 내역을 제거한다. 이는 분기점이 없는 조건을 하나의 연산으로 간주하고, 이와 관련된 값 변화를 지워서 구현한다. 변수 이력을 대체하는 방법은 변수에 마지막으로 값이 적용됐을 때의 타임 스탬프를 저장해 분기점의 타임 스탬프와 비교하는 것이다. 변수의 타임 스탬프보다 분기전의 타임 스탬프가 최근일 경우, 분기점으로 복귀했을 때 변수 값을 복구하지 않아도 된다. |
| − | == | + | ==유사 코드== |
| − | 다음은 | + | 다음은 역추적검색의 작동 방식을 표현한 유사 코드이다. |
| − | + | procedure bt(c) is | |
| − | + | if reject(P, c) then return | |
| − | + | if accept(P, c) then output(P, c) | |
| − | + | s ← first(P, c) | |
| − | + | while s ≠ NULL do | |
| − | + | bt(s) | |
| − | + | s ← next(P, s) | |
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
| − | |||
{{각주}} | {{각주}} | ||
==참고자료== | ==참고자료== | ||
| + | * 퇴각검색 위키백과 - https://ko.wikipedia.org/wiki/%ED%87%B4%EA%B0%81%EA%B2%80%EC%83%89 | ||
* 오현석, 〈[http://www.aistudy.com/heuristic/backtracking.htm Backtracking]〉, 《개인 블로그》 | * 오현석, 〈[http://www.aistudy.com/heuristic/backtracking.htm Backtracking]〉, 《개인 블로그》 | ||
* Jeong Dowon, 〈[https://medium.com/@jeongdowon/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-backtracking-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0-13492b18bfa1 (알고리즘) Backtracking 이해하기]〉, 《미디엄》 | * Jeong Dowon, 〈[https://medium.com/@jeongdowon/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-backtracking-%EC%9D%B4%ED%95%B4%ED%95%98%EA%B8%B0-13492b18bfa1 (알고리즘) Backtracking 이해하기]〉, 《미디엄》 | ||
2020년 7월 29일 (수) 10:38 판
역추적검색(Backtracking)은 제약조건 만족 문제(Constraint Satisfaction Problem)를 해결하기 위한 알고리즘이다. 역추적검색은 문제를 해결하기 위해 모든 해를 나열한다.
개요
역추적검색은 제약조건 만족 문제를 해결하기 위해 조합 알고리즘 문제에 대해 가능한 모든 해를 나열하는 것이다. 제약조건 만족 문제는 완전한 해를 가진 문제이고, 요소들의 순서는 문제 되지 않는다. 그 문제는 값이 할당되어야 하는 일련의 변수들로 구성되며, 특별한 제약조건에 민감하다. 부분적인 조합을 시도해 보지 않아도 된다는 장점이 있으며, 조건을 만족할 경우 모든 경우의 수를 찾는 것보다 빠를 수 있다. 역추적검색이라는 용어는 1950년 미국의 수학자 데릭 레머(Derrick Lehmer)에 의해 만들어졌다. 역추적검색은 맞는 답을 구할 때까지 모든 가능성을 시도하며, 트리를 검사하기 위해 주로 깊이 우선 탐색을 사용한다. 탐색 도중 오답을 만나면 이전 분기점으로 돌아가고, 시도해 보지 않은 방법이 있으면 시도하고, 해결 방법이 없으면 더 이전 분기점으로 돌아간다. 모든 트리의 노드를 검사해도 답을 못 찾을 경우 이 문제의 해결 방법은 존재하지 않는 것이다. 역추적검색은 보통 각각의 인스턴스가 하나 이상의 변수를 가지고 모든 이용 가능한 값을 그 변수에 할당하는 재귀 함수 형태를 가지고, 계속되는 재귀 호출과 일치하는 값을 유지한다. 역추적검색은 깊이 우선 탐색과 유사하지만 공간 사용이 덜하며 딱 한 개의 최신 변수만 유지하고, 업데이트한다. 탐색 속도를 빠르게 하기 위해서 재귀 호출을 하기 전에 값이 선택될 때, 그 알고리즘은 할당되지 않은 영역과 다투지 못하도록 그 값을 제거하는 전방향 체크(forward checking)나 새로이 할당된 값이 어떤 다른 값을 배제하는지 보기 위해 모든 제약조건을 체크하는 제약전파(constraint propagation)를 사용한다. 넓이 우선 탐색의 경우 상대적으로 많은 메모리가 필요하기 때문에 일반적으로 깊이 우선 탐색을 통하여 구현한다. 역추적검색은 프롤로그(Prolog) 같은 프로그램 언어에 사용되며, 텍스트 파싱(text parsing)에도 사용된다. 행위자 모델 개발에 쓰이는 인공지능에 적용하려는 움직임도 있었다. 역추적검색으로 해결할 수 있는 문제는 여덟 개의 퀸 퍼즐, 스도쿠, 십자말풀이 등이 있다.
휴리스틱
역추적검색을 빠르게 만들기 위해 몇몇 휴리스틱을 사용한다. 변수는 어떤 순서로도 처리할 수 있으므로 보통 효율적인 방법은 가장 한정된 조건을 먼저 시도하는 것이다. 이런 가지치기는 탐색 트리를 작게 해 최소의 비용으로 최대의 결과를 얻을 수 있다. 또, 어떤 값을 할당할 것인지 선택할 때 어떤 값이 최소 개수의 미래의 값들을 제약하는지 보는 전방향 체크를 사용한다. 전방향 체크는 해를 더 빨리 얻을 것 같은 값을 선택하는 것이다. 해결 방법이 가장 있을 것 같거나 가장 없을 것 같은 것을 찾아 탐색 트리를 작게 만든다. 섬세한 역추적검색은 분기 함수(bounding function)를 사용한다. 분기 함수는 해를 얻는 것이 가능한지 확인하기 위해 검사되는 문제에 만들어 모든 할당 단계에서 작동한다. 그래서 간단한 테스트를 통해 실패할 것 같은 부분적인 해를 찾아내 탐색 대상의 99%까지 제외하기도 한다. 분기 함수는 종종 지수적 탁샘공간인 모든 단계에서 작동하기 때문에, 계산하기 쉬워야 한다. 되돌릴 때 복구할 값들을 최소로 유지하기 위해 역추적검색은 변수 이력을 사용한다. 변수 이력은 변수 값이 바뀐 내역을 보관해, 분기점이 없을 때 값 변화에 대한 내역을 제거한다. 이는 분기점이 없는 조건을 하나의 연산으로 간주하고, 이와 관련된 값 변화를 지워서 구현한다. 변수 이력을 대체하는 방법은 변수에 마지막으로 값이 적용됐을 때의 타임 스탬프를 저장해 분기점의 타임 스탬프와 비교하는 것이다. 변수의 타임 스탬프보다 분기전의 타임 스탬프가 최근일 경우, 분기점으로 복귀했을 때 변수 값을 복구하지 않아도 된다.
유사 코드
다음은 역추적검색의 작동 방식을 표현한 유사 코드이다.
procedure bt(c) is
if reject(P, c) then return
if accept(P, c) then output(P, c)
s ← first(P, c)
while s ≠ NULL do
bt(s)
s ← next(P, s)
각주
참고자료
- 퇴각검색 위키백과 - https://ko.wikipedia.org/wiki/%ED%87%B4%EA%B0%81%EA%B2%80%EC%83%89
- 오현석, 〈Backtracking〉, 《개인 블로그》
- Jeong Dowon, 〈(알고리즘) Backtracking 이해하기〉, 《미디엄》
같이 보기
| ||||||||||||||||||||||||||||||||||
