首页 书籍 深入浅出程序设计竞赛(进阶篇) 进阶搜索

状态剪枝是一种优化搜索算法的技巧，用于减少搜索空间和提高效率。它通过在搜索过程中排除某些状态，从而减少需要考虑的可能性，进而加速找到解或者达到更优解的过程。

# 可行性剪枝（Feasibility Pruning）：

可行性剪枝是指在搜索过程中，根据问题的特点，排除那些显然不满足问题约束条件的状态，以减少搜索空间。通过这种剪枝方式，可以提前排除掉不可能存在解的分支，从而减少计算量。

例如，在求解数独问题时，如果某个位置已经填入了一个数字，并且该数字与该位置所在的行、列或宫格中已经填入了相同的数字，则可以直接将该状态剪枝掉，因为这个状态不符合数独问题的规则。

下面是使用可行性剪枝的数独求解器的例子代码（C++）：

#include <iostream>
#include <vector>
using namespace std;
bool isValid(vector<vector<char>>& board, int row, int col, char num) {
    // Check if the number is already in the same row or column
    for (int i = 0; i < 9; i++) {
        if (board[row][i] == num || board[i][col] == num) {
            return false;
        }
    }
    // Check if the number is already in the same 3x3 box
    int startRow = (row / 3) * 3;
    int startCol = (col / 3) * 3;
    for (int i = startRow; i < startRow + 3; i++) {
        for (int j = startCol; j < startCol + 3; j++) {
            if (board[i][j] == num) {
                return false;
            }
        }
    }
    return true;
}
bool solveSudoku(vector<vector<char>>& board) {
    for (int row = 0; row < 9; row++) {
        for (int col = 0; col < 9; col++) {
            if (board[row][col] == '.') {
                for (char num = '1'; num <= '9'; num++) {
                    if (isValid(board, row, col, num)) {
                        board[row][col] = num;
                        if (solveSudoku(board)) {
                            return true;
                        }
                        board[row][col] = '.'; // Backtrack
                    }
                }
                return false; // No valid number found for this cell
            }
        }
    }
    return true; // All cells are filled
}
int main() {
    vector<vector<char>> board = {
        {'5', '3', '.', '.', '7', '.', '.', '.', '.'},
        {'6', '.', '.', '1', '9', '5', '.', '.', '.'},
        {'.', '9', '8', '.', '.', '.', '.', '6', '.'},
        {'8', '.', '.', '.', '6', '.', '.', '.', '3'},
        {'4', '.', '.', '8', '.', '3', '.', '.', '1'},
        {'7', '.', '.', '.', '2', '.', '.', '.', '6'},
        {'.', '6', '.', '.', '.', '.', '2', '8', '.'},
        {'.', '.', '.', '4', '1', '9', '.', '.', '5'},
        {'.', '.', '.', '.', '8', '.', '.', '7', '9'}
    };
    if (solveSudoku(board)) {
        cout << "Solution found:" << endl;
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                cout << board[i][j] << " ";
            }
            cout << endl;
        }
    } else {
        cout << "No solution exists." << endl;
    }
    return 0;
}
在数独求解器中， isValid  函数用于判断在某个位置填入某个数字是否满足数独的规则。在 solveSudoku  函数中，通过遍历每个空格并尝试填入 1 到 9 的数字，如果发现某个数字不符合数独规则，则进行剪枝。


# 最优性剪枝（Optimality Pruning）：


最优性剪枝是指在搜索过程中，如果已经找到了一个解或者当前搜索的状态已经不可能得到更优解时，可以直接剪枝掉该状态所在的分支，以提高搜索效率。


例如，在解决旅行商问题（TSP）时，如果当前已经搜索到的路径长度已经超过了一个已知最优解，则可以直接将该状态剪枝掉。


下面是使用最优性剪枝的旅行商问题求解算法的例子代码（C++）：


#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int tsp(vector<vector<int>>& graph, vector<bool>& visited, int currPos, int n, int count, int cost, int& ans) {
    if (count == n && graph[currPos][0] != 0) { // Reached all cities and there is a path back to the starting city
        ans = min(ans, cost + graph[currPos][0]);
        return ans;
    }
    for (int i = 0; i < n; i++) {
        if (!visited[i] && graph[currPos][i] != 0) {
            visited[i] = true;
            tsp(graph, visited, i, n, count + 1, cost + graph[currPos][i], ans);
            visited[i] = false;
        }
    }
    return ans;
}
int main() {
    int n = 4; // Number of cities
    vector<vector<int>> graph = {
        {0, 10, 15, 20},
        {10, 0, 35, 25},
        {15, 35, 0, 30},
        {20, 25, 30, 0}
    };
    vector<bool> visited(n, false);
    visited[0] = true; // Starting city
    int ans = INT_MAX;
    int minCost = tsp(graph, visited, 0, n, 1, 0, ans);
    cout << "Minimum cost: " << minCost << endl;
    return 0;
}
在旅行商问题的求解算法中， tsp  函数使用回溯法遍历每个城市，并计算路径长度。在每个城市的选择过程中，通过不断更新当前最小路径长度 ans ，如果当前路径长度已经超过 ans ，则进行剪枝操作。


# 卡时技巧


（Time Complexity Optimization）是指在搜索过程中，通过一些技巧或数据结构的优化来减少时间复杂度，以提高算法的效率。例如，使用动态规划、剪枝等方法来减少重复计算或排除不必要的搜索空间。具体的卡时技巧的选择和实现，取决于问题的特点和需求。


      

          
          
      

  


   


    

  
    
      
    
    更新于