폭력 적 인 예술: 역 추적 알고리즘

나의 약서: 동방 미 희
1. 역 추적 알고리즘 과 DFS
역 추적 알고리즘 은 폭력 적 인 해석 의 하나 로 한 문제 의 모든 해석 이나 임 의 해 를 체계적으로 검색 할 수 있다.그것 은 가능 한 모든 해 를 심도 있 는 검색 을 통 해 재 귀적 으로 옮 겨 다 닌 다.해 공간의 한 가 지 를 옮 겨 다 닐 때 현재 분기 가 조건 에 만족 하지 않 는 다 면 이전 단계 로 돌아 가 다른 가 지 를 시도 합 니 다.이런 이전 단계 로 되 돌아 가 는 방식 은 바로 '역 추적' 이 고 분기 의 해석 여 부 를 판단 하 는 것 이 바로 '가지치기' 이다.만약 당신 이 초보 라면, 역 추적 의 정 의 를 보고, 당신 은 기 대 를 가지 고 있 습 니까? 아니면 마음 이 심란 합 니까?사실 역 추적 법 은 알고리즘 학습 의 입문 으로 프로그래머 가 알고리즘 을 배 웠 는 지 평가 하고 그 가 역 추적 을 쓸 수 있 는 지 없 는 지 를 보면 된다.따라서 역 추적 알고리즘 은 각종 필기시험 과 면접 에 자주 등장 한다. 검색 문제 에 직면 했 을 때 역 추적 법 이 하나 또 하나의 순환 for 이 아 닌 역 추적 법 을 쓰 면 면접 관 들 도 당신 의 코드 가 수려 하 다 고 느 낄 것 이다.역 추적 알고리즘 의 기 초 는 깊이 우선 검색 (DFS) 입 니 다. 이 검색 은 한 가지 에 깊이 들 어가 이 가 지 를 옮 겨 다 닐 때 까지 다른 가 지 를 시도 합 니 다.DFS 의 위조 코드 는 다음 과 같 습 니 다. visited[i] 배열 은 i 점 에 방 문 했 는 지 여 부 를 대표 합 니 다.

void dfs(int v) {
    visited[v] = true;
    for (v      w) {
        if (!visited[w])
            dfs(w);
    }
}

역 추적 알고리즘 은 DFS 과정 에서 반환 조건 과 가 지 를 넣 은 것 입 니 다. 다음은 Leetcode 의 진 제 를 통 해 한 걸음 한 걸음 이해 하 겠 습 니 다.
2. Leetcode 는 진 제 를 거 슬러 올라간다.
1. 구 해 부분 집합
Leetcode 주소: 78. 부분 집합 제목 의 뜻 은 간단 합 니 다. n 길이 의 중복 숫자 가 포함 되 지 않 은 시퀀스 를 주 고 이 시퀀스 의 모든 부분 집합 을 되 돌려 줍 니 다.이 서열 에 중복 숫자 가 포함 되 어 있 지 않 은 이상 부분 집합 의 개 수 는 2 ^ n (부분 집합 을 구 할 때 모든 요 소 를 선택 하거나 두 가지 조작 을 선택 하지 않 기 때 문) 이 고 알고리즘 의 시간 복잡 도 는 O (2 ^ n) 입 니 다.그렇다면 이 두 가지 조작 을 선택 하고 선택 하지 않 는 것 은 어떻게 프로그램 에 나타 날 수 있 습 니까?예 를 들 어 현재 의 서열 이 [1, 2, 3] 이 라 고 가정 하면 우 리 는 요소 1 을 하위 집중 에 추가 하고 나머지 서열 [2, 3] 의 모든 부분 집합 을 구 할 수 있다.우 리 는 또한 요소 1 을 서브 집중 에 추가 하지 않 고 [2, 3] 의 모든 부분 집합 을 구 할 수 있다.이것 은 분명히 재 귀적 인 과정 이다. i 번 째 요 소 를 선택 한 후에 결 과 를 저장 하고 나머지 요 소 를 선택 하 는 것 이다.모든 요 소 를 선택 한 후에 얻 은 결 과 는 키 집합 입 니 다.

// nums         
vector<vector<int> > subsets(vector<int>& nums) {
    vector<vector<int> > result; //        
    vector<int> path; //            
    search(0, nums, path, result); //   0       
    return result;
}

// idx      nums[idx]
void search(int idx, vector<int>& nums, vector<int>& path, vector<vector<int> >& result) {
    //          ，        
    if (idx >= nums.size()) {
        result.push_back(path);
        return; //        
    }
    //   nums[idx] 
    path.push_back(nums[idx]);
    search(idx + 1, nums, path, result);
    //    nums[idx] 
    path.pop_back();
    search(idx + 1, nums, path, result);
}

2. 전체 정렬
Leetcode 주소: 46. 전체 배열 문 제 는 중복 되 지 않 은 숫자의 순 서 를 정 하고 가능 한 모든 배열 을 되 돌려 줍 니 다.위의 문제 풀이 부분 집합 은 모든 요소 에 대해 하위 집중 에 추가 할 지 여 부 를 선택 하 는 것 입 니 다. 전체 배열 은 추가 되 지 않 은 요 소 를 현재 배열 에 추가 하 는 것 을 선택 하 는 것 입 니 다.어떤 요소 가 선택 되 었 는 지 판단 하려 면 하나의 bool visited[i] 배열 이 i 요소 가 배열 에 추가 되 었 는 지 판단 해 야 합 니 다.
예 를 들 어 구 해 [1, 2, 3] 의 전체 배열 은 다음 과 같다. ① 1 을 1 위 에 추가 하고 이때 1 이 방문 되 었 으 면 visited[1]=true 그 후의 요 소 는 [2, 3] 에서 만 선택 할 수 있 고 최종 적 으로 1 위 에 있 는 모든 배열 [1, 2, 3] 과 [1, 3, 2] 가 형성 된다.② 이때 1 위 에 있 는 모든 상황 을 옮 겨 다 니 며 1 의 방문 상 태 를 방문 하지 않 은 것, 즉 visited[1]=false 으로 되 돌려 야 한다.이렇게 한 후에 다른 수 를 1 위 에 놓 았 을 때 도 1 을 선택 하여 뒤 를 따 를 수 있다.③ 1 위 에 2 를 추가 하고 [1, 3] 의 전체 배열 을 따라간다.

vector<vector<int> > permute(vector<int>& nums) {
    vector<vector<int> > result;
    vector<int> cur;
    int size = nums.size();
    //   nums  ，     
    if (size == 0)
        return result;
    // visited                   
    bool* visited = new bool[size];
    for (int i = 0; i < size; ++i)
        visited[i] = false;
    dfs(0, result, cur, nums, visited);
    return result;
}

// index       index        
void dfs(int index, vector<vector<int> >& result, vector<int> cur, vector<int>& nums, bool* visited) {
    if (index >= nums.size()) {
        result.push_back(cur);
        return;
    }
    for (int i = 0; i < nums.size(); ++i) {
        //                
        if (!visited[i]) {
            //            
            cur.push_back(nums[i]);
            visited[i] = true;
            dfs(index + 1, result, cur, nums, visited);
            //     
            cur.pop_back();
            visited[i] = false;
        }
    }
}

3. 조합 총화
Leetcode 주소: 39. 중복 요소 가 없 는 배열 candidates 과 목표 수 target 를 조합 하여 candidates 의 모든 숫자 와 target 의 조합 을 찾 아 냅 니 다.candidates 중의 숫자 는 무제 한 중복 으로 선택 할 수 있다.이 문제 에서 배열 의 요 소 는 중복 선택 할 수 있 기 때문에 특정한 숫자 가 방문 되 었 는 지 판단 할 필요 가 없다.여러 차례 에 걸 쳐 visited[] 를 그룹 에 추가 하 는 것 이 확실 하 다 면 candidates[i] 을 다음 라운드 재 귀적 인 새로운 target-candidates[i] 으로 할 수 있 고, 새로운 target 이 0 이 라면 이전 조합 은 하나의 풀이 다.0 보다 작 으 면 현재 분기 가 성립 되 지 않 고 이전 단계 로 되 돌아 갑 니 다.0 이상 이면 조합 에 숫자 를 추가 할 수 있 습 니 다.

vector<vector<int> > combinationSum(vector<int>& candidates, int target) {
    vector<vector<int> > result;
    vector<int> path; //          
    sort(candidates.begin(), candidates.end()); //   
    search(0, result, candidates, path, target);
    return result;
}

void search(int idx, vector<vector<int> >& result, vector<int>& candidates, 
            vector<int>& path, int target) {
    if (target == 0) {
        result.push_back(path);
        return;
    }
    if (target < 0) {
        return;
    }
    //          
    for (int i = idx; i < candidates.size(); ++i) {
        path.push_back(candidates[i]);
        //         ，                 
        search(i, result, candidates, path, target - candidates[i]);
        //        ，for      
        path.pop_back();
    }
}

상기 프로그램 은 재 귀 시 판단 target 이 0 보다 작 는 지 여 부 를 통 해 현재 분기 가 풀 리 지 않 았 는 지 확인 합 니 다. 이러한 '가지치기' 방식 은 너무 거 칠 지 않 습 니 다.이 프로그램 을 OJ 에 넣 고 실행 하면 통과 할 수 있 지만 실행 시간 이 약 28% 에 불과 한 상황 에서 최적화 하 는 방법 이 있 을 것 이다.자세히 살 펴 보 니 target 는 작은 것 에서 큰 것 으로 순 위 를 매 겼 고 candidates 이 라면 target-candidates[i] < 0 모두 0 보다 작 았 다.따라서 target-candidates[i + 1], target-candidates[i + 2]...... 함 수 는 이렇게 최적화 할 수 있다.

void search(int idx, vector<vector<int> >& result, vector<int>& candidates, 
            vector<int>& path, int target) {
    if (target == 0) {
        result.push_back(path);
        return;
    }
    for (int i = idx; i < candidates.size(); ++i) {
        if (target - candidates[i] < 0) {
            break;
        } else {
            path.push_back(candidates[i]);
            search(i, result, candidates, path, target - candidates[i]);
            path.pop_back();
        }
    }
}

최 적 화 된 후에 코드 의 운행 시간 은 98% 이상 의 프로그램 을 격 파 했 는데 정말 세부 적 인 것 이 성 패 를 결정 한다.
4. 조합 총화 변형
Leetcode 주소: 40. 조합 총화 II 라 는 문 제 는 이전 문제 와 많은 차이 가 있 습 니 다. 하 나 는 숫자 가 중복 되 고 다른 하 나 는 숫자 마다 한 번 만 가 져 갈 수 있 습 니 다.지난 문제 풀이 search() 를 search(i, result...) 로 바 꾸 면 된다 고 생각한다 면 틀 렸 다.이렇게 만 수정 하면 search(i + 1, result...) [1, 1, 3] 과 candidates 가 4 인 상황 에서 결과 에 두 개의 [1, 3] 가 나 오기 때문에 중복 결 과 를 삭제 해 야 한다.set 를 사용 하 는 것 은 방법 이지 만 효율 이 낮 습 니 다. 우 리 는 외부 에서 반복 되 는 숫자 를 뛰 어 넘 어 중복 해 를 뛰 어 넘 는 효 과 를 얻 을 수 있 습 니 다.

vector<vector<int> > combinationSum2(vector<int>& candidates, int target) {
    vector<vector<int> > result;
    vector<int> path;
    sort(candidates.begin(), candidates.end());
    search(0, result, path, candidates, target);
    return result;
}

void search(int idx, vector<vector<int> >& result, vector<int>& path, 
            vector<int>& candidates, int target) {
    if (target == 0) {
        result.push_back(path);
        return;
    }
    for (int i = idx; i < candidates.size(); ++i) {
        if (i > idx && candidates[i] == candidates[i - 1])
            continue;
        if (target - candidates[i] < 0) {
            break;
        } else {
            path.push_back(candidates[i]);
            search(i + 1, result, path, candidates, target - candidates[i]);
            path.pop_back();
        }
    }
}

만약 당신 이 잠시 이해 할 수 없다 면, 종이 위 에서 코드 의 절 차 를 모 의 할 수 있 습 니 다.
황후
돌 이 켜 보면 8 황후 문 제 를 돌 이 킬 수 없다. 너무 전형 적 이기 때문이다. Leetcode 에 변종 N 황후 문제 가 있 으 니 끝까지 알 아 보 자.Leetcode 주소: 51. N 황후 체스 에서 황 후 는 같은 직선 과 같은 사선 의 바둑 알 을 공격 할 수 있 습 니 다.N * N 의 바둑판 에 N 개의 황 후 를 놓 아 서로 공격 하지 않 으 려 면 줄 마다, 열 마다, 사선 마다 황후 가 한 명 밖 에 없다 는 뜻 이다.다음 그림 은 8 황후 의 풀이 다.
N * N 의 바둑판 은 분명히 N 행 N 열 만 있 고 모든 줄 에 황후 가 있 습 니 다.그럼 이 바둑판 은 몇 개의 사선 이 있 습 니까?중학교 수학 에 서 는 정사 선과 반사 선 이 모두 2N - 1 개 라 고 알려 준다.그 중에서 정사 선의 사율 은 모두 1 이 고 반사 선의 사율 은 모두 - 1 이다.정사 선의 공식 은 target 이 고 반사 선의 공식 은 y = x + k1 이다.그 중에서 k1 과 k2 의 수 치 는 모두 2N - 1 가지 가 있 고 k1 마다 정사 선 을 확정 할 수 있 으 며 k2 마다 반사 선 을 확정 할 수 있다.그래서 두 개의 배열 을 사용 하면 모든 사선 이 한 황후 에 의 해 차지 되 었 는 지 확인 할 수 있 습 니 다.(상기 경사 율 은 표준 좌표계 에 있 는 것 으로 2 차원 배열 의 좌표계 가 그렇지 않다.) 현재 y = -x + k2 황 후 를 배치 해 야 한다 고 가정 하면 (i, j) 대표 하 는 행 과 i 대표 하 는 열 은 차지 하지 않 아야 하고 j 과 i - j 대표 하 는 두 개의 사선 도 차지 하지 않 아야 한다.공간 을 절약 하기 위해 우 리 는 1 차원 배열 i + j 을 사용 하여 황후 의 배치 상황 을 저장 합 니 다. path[] 대표 path[i] = val 행 i 에는 황후 가 있 습 니 다.줄 마다 황후 가 있어 야 하기 때문에 줄 을 옮 겨 다 니 며 보관 할 수 있 습 니 다.

vector<vector<string> > solveNQueens(int n) {
    vector<vector<string> > result;
    // path[i] = val   i val      
    int* path = new int[n];
    //           
    bool* visited = new bool[n];
    for (int i = 0; i < n; ++i)
        visited[i] = false;
    //            
    bool* slash1 = new bool[2 * n];
    bool* slash2 = new bool[2 * n];
    for (int i = 0; i < 2 * n; ++i) {
        slash1[i] = false;
        slash2[i] = false;
    }
    search(0, result, path, n, visited, slash1, slash2);
    return result;
}

void search(int idx, vector<vector<string> >& result, int* path, int n, 
            bool* visited, bool* slash1, bool* slash2) {
    //           ，   
    if (idx >= n) {
        vector<string> tmp_result;
        for (int i = 0; i < n; ++i) {
            //    
            char* tmp = new char[n + 1];
            for (int j = 0; j < n; ++j) {
                if (path[i] == j)
                    tmp[j] = 'Q';
                else
                    tmp[j] = '.';
            }
            tmp[n] = '\0';
            string tmp_string(tmp);
            tmp_result.push_back(tmp_string);
        }
        result.push_back(tmp_result);
        return;
    }
    //           
    for (int i = 0; i < n; ++i) {
        if (!visited[i] && !slash1[idx + i] && !slash2[idx - i + n]) {
            //      ，           
            path[idx] = i;
            visited[i] = true;
            slash1[idx + i] = true;
            slash2[idx - i + n] = true;
            search(idx + 1, result, path, n, visited, slash1, slash2);
            //       ，    
            visited[i] = false;
            slash1[idx + i] = false;
            slash2[idx - i + n] = false;
        }
    }
}