소 급 법의 일반적인 방법.
7323 단어 방법.
소 급 법의 일반적인 절차 와 기술
역 추적 법 으로 관련 문 제 를 해결 하 는 과정 에서 보통 나 무 를 세우 면서 이 나 무 를 옮 겨 다 닌 다.역 추적 법 에서 우 리 는 일반적으로 비 재 귀 방법 을 채택 한다.다음은 역 추적 법의 비 재 귀 알고리즘 에 대한 일반적인 절 차 를 제시 합 니 다.
역 추적 법 으로 문 제 를 해결 하 는 것, 즉 상태 공간 나 무 를 옮 겨 다 니 는 과정 에서 비 재 귀 방법 을 사용 하면 우 리 는 보통 스 택 의 데이터 구 조 를 사용 해 야 한다.이때 스 택 으로 옮 겨 다 니 고 있 는 나무의 결 점 을 표시 할 수 있 을 뿐만 아니 라 아이의 결 점 과 역 추적 과정 을 편리 하 게 표시 할 수 있다.
문제 의 해결 공간
문제 의 벡터: 역 추적 법 은 한 문제 의 풀이 가 n 원 식 (x1, x2,..., xn) 의 형식 으로 나타 나 기 를 바란다.
현 구속: 분량 xi 에 대한 수치 제한.
암시 적 제약: 문제 의 해 를 만족 시 키 기 위해 서로 다른 분량 간 에 가 하 는 제약.
해 공간: 문제 의 인 스 턴 스 에 대해 벡터 가 명시 적 제약 조건 을 만족 시 키 는 모든 다 중 그룹 은 이 인 스 턴 스 의 해 공간 을 구성 합 니 다.
주의: 같은 문 제 는 여러 가지 로 표시 할 수 있 습 니 다. 어떤 표현 방법 은 더욱 간단 하고 표시 할 상태 공간 이 더 작 습 니 다 (저장량 이 적 고 검색 방법 이 간단 합 니 다).
예: 거 슬러 올 라 가 는 일반적인 방법, 코드 는 다음 과 같다.
void BackTrack(n){
// 。 X(1:n) ，
// 。 X(l),…,X(k-l) ，T(X(l), …,
//X(k-1)) X(k) 。 B(X(l),…,X(k))
// X(k) 。
int k，n ；int X[n]；
k=1；
while(k>0) {
if( X(k) X(k)∈T(X[l],…,X[k-1] and
B(X[1],…,X[k])=True) {
if((X[1],…,X[k]) ) {
print(X[1],…,X[k]) }；//if
++k； //
else {--k；} //
}；//if
}；
}// BackTrack메모: 집합 T () 는 벡터 를 푸 는 첫 번 째 분량 X (1) 의 모든 가능 한 값 을 제공 하고, 벡터 를 푸 는 것 은 한계 함수 B1 (X (1) 을 진짜 X (1) 의 값 으로 합 니 다.또 주의해 야 할 것 은 이 요소 들 이 어떻게 깊이 우선 방식 으로 생 성 되 는 지 하 는 것 이다.k 값 이 증가 함 에 따라 벡터 의 각 분량 이 계속 생 성 되 고 해 를 찾 거나 검사 되 지 않 은 X (k) 가 남지 않 을 때 까지 생 성 됩 니 다.k 값 이 줄 어 들 때 알고리즘 은 이전에 남 았 을 수도 있 고 검증 되 지 않 았 을 수도 있 는 요 소 를 다시 시작 해 야 합 니 다.따라서 이 요소 X (k) 를 특정한 순서에 따라 생 성 할 수 있 도록 키 알고리즘 을 만들어 야 한다.하나만 풀 려 면 print 뒤에 return 문 구 를 설정 할 수 있 습 니 다.
예 를 들 어 재 귀 역 추적 알고리즘, 코드 는 다음 과 같다.
void RBackTrack(k) {
// 。 ，
// X(1:n) k-1 X(1)，…，X(k-1)
int n，X[n]； //
for( X[k]|X[k]∈T(X[1],…,X[k-1]) and
B(X[1],…,X[k]=true) {
if(X[1],…,X[k]) )
{print(X[1],…,X[k])；}//if
RBackTrack(k+1)；
}；
}//RBackTrack벡터 풀이 (x1,..., xn) 는 전체 배열 X (1: n) 로 처리 합 니 다.이 원 그룹의 k 번 째 위치 에서 B 를 만족 시 키 는 모든 요소 가 하나씩 생 성 되 고 현재 벡터 (X (l),..., X (k - 1) 에 연결 되 며, 매번 X (k) 는 하나의 해 를 찾 았 는 지 여 부 를 판단 하 는 검 사 를 첨부 해 야 합 니 다.그래서 이 알고리즘 은 재 귀적 으로 호출 되 었 다.for 순환 을 종료 할 때 X (k) 값 이 남아 있 지 않 습 니 다. 이 층 의 재 귀 를 끝내 고 지난번 에 완료 되 지 않 은 호출 을 계속 합 니 다.지적 하고 자 하 는 것 은 k 가 n 보다 클 때 T (X (1),..., X (k - 1) 가 빈 집합 을 되 돌려 주기 때문에 for 순환 에 들 어가 지 않 는 다 는 것 이다.또 이 프로그램 이 모든 해 를 출력 하고 해 를 구성 하 는 원 그룹의 크기 는 가 변 적 이라는 점 을 지적 했다.하나만 풀 려 면 첫 번 째 성공 상황 을 가리 키 기 위해 로 고 를 매개 변수 로 추가 할 수 있 습 니 다.
효율 평가 위 에서 제시 한 두 개의 역 추적 프로그램의 효율 은 주로 다음 과 같은 네 가지 요소 에 달 려 있다. ① 다음 X (k) 를 생 성 하 는 시간;② 명시 적 제약 조건 을 만족 시 키 는 X (k) 의 수량;③ 한계 함수 Bi 의 계산 시간;④ 모든 i 에 대해 Bi 의 X (k) 수 를 만족시킨다.
예 를 들 어 역 추적 법의 효율 을 평가 할 때 알고리즘 은 다음 과 같다.
void Estimate() {
//
m = l；r = 1；k = 1；
while(1) {
T[k]={X[k]|X[k]∈T(X[1],…,X[k-1]) and Bk(X[1],…,X[k])}
if(Size(T[k])=0) break；
r* = Size(T[k])；
m += r；
X[k]=Choose(T[k])；
++k；
}；//while
return m；
}//Estimate알고리즘 Estimate 를 조금 만 수정 하면 더욱 정확 한 결점 추정 수 를 얻 을 수 있 습 니 다.이것 은 하나의 for 순환 문 구 를 추가 하고 여러 개의 서로 다른 랜 덤 경로 (보통 20 개 를 취 할 수 있 음) 를 선택 하여 각 경로 의 평가 치 를 구 한 후에 평균 치 를 취하 면 됩 니 다.
좋은 웹페이지 즐겨찾기
