搜索算法进阶：剪枝优化与启发式搜索
搜索算法的优化必要性
⚡ 搜索算法优化技巧
🎯 剪枝优化
- • 可行性剪枝
- • 最优性剪枝
- • 记忆化搜索
- • 效果：减少搜索空间
🔍 启发式搜索
- • A*算法
- • IDA*算法
- • 估价函数设计
- • 效果：优先搜索有希望的分支
⚙️ 双向搜索
- • 从起点和终点同时搜索
- • 相遇即找到答案
- • 时间复杂度开方
- • 效果：大幅减少搜索时间
在信息学竞赛中，搜索算法是解决问题的基础工具。但是，简单的暴力搜索往往会导致时间复杂度爆炸。通过剪枝优化和启发式搜索，我们可以将原本不可解的问题变得可解，将超时的程序变得高效。
搜索优化的主要方向
| 优化类型 | 原理 | 效果 | 适用场景 |
|---|---|---|---|
| 剪枝 | 提前终止无用分支 | 减少搜索空间 | 所有搜索问题 |
| 记忆化 | 保存已计算结果 | 避免重复计算 | 有重叠子问题 |
| 启发式 | 优先搜索更可能的方向 | 快速找到解 | 最优化问题 |
| 迭代加深 | 限制搜索深度 | 平衡时空复杂度 | 深度未知问题 |
| 双向搜索 | 从两端同时搜索 | 指数级优化 | 起点终点明确 |
剪枝技术详解
1. 可行性剪枝
当前状态已经不满足约束条件，继续搜索必然无解。
// N皇后问题的可行性剪枝
bool isValid(vector<int>& queens, int row, int col) {
for (int i = 0; i < row; i++) {
// 同列或对角线冲突
if (queens[i] == col ||
abs(queens[i] - col) == abs(i - row)) {
return false;
}
}
return true;
}
void solveNQueens(int n, int row, vector<int>& queens, int& count) {
if (row == n) {
count++;
return;
}
for (int col = 0; col < n; col++) {
if (isValid(queens, row, col)) { // 可行性剪枝
queens[row] = col;
solveNQueens(n, row + 1, queens, count);
}
}
}
2. 最优性剪枝
当前路径的代价已经超过已知最优解，继续搜索不会得到更优解。
// 旅行商问题的最优性剪枝
int minCost = INT_MAX;
void TSP(vector<vector<int>>& dist, vector<bool>& visited,
int curr, int count, int cost, int n) {
if (cost >= minCost) return; // 最优性剪枝
if (count == n) {
minCost = min(minCost, cost + dist[curr][0]);
return;
}
for (int next = 0; next < n; next++) {
if (!visited[next]) {
visited[next] = true;
TSP(dist, visited, next, count + 1,
cost + dist[curr][next], n);
visited[next] = false;
}
}
}
3. 上下界剪枝
估算当前状态能达到的最好和最坏情况，判断是否需要继续搜索。
// 01背包问题的上界剪枝
struct Item {
int weight, value;
double density;
};
// 计算上界（使用分数背包）
double upperBound(vector<Item>& items, int idx, int capacity, int currentValue) {
double bound = currentValue;
int totalWeight = 0;
for (int i = idx; i < items.size(); i++) {
if (totalWeight + items[i].weight <= capacity) {
totalWeight += items[i].weight;
bound += items[i].value;
} else {
bound += (capacity - totalWeight) * items[i].density;
break;
}
}
return bound;
}
int maxValue = 0;
void knapsack(vector<Item>& items, int idx, int capacity, int currentValue) {
if (idx == items.size() || capacity == 0) {
maxValue = max(maxValue, currentValue);
return;
}
// 上界剪枝
if (upperBound(items, idx, capacity, currentValue) <= maxValue) {
return;
}
// 选择当前物品
if (items[idx].weight <= capacity) {
knapsack(items, idx + 1, capacity - items[idx].weight,
currentValue + items[idx].value);
}
// 不选择当前物品
knapsack(items, idx + 1, capacity, currentValue);
}
4. 对称性剪枝
利用问题的对称性，避免搜索等价的状态。
// 数独求解的对称性剪枝
void solveSudoku(vector<vector<int>>& board) {
// 找到空格最少的位置（最少选择剪枝）
int minChoices = 10;
int targetRow = -1, targetCol = -1;
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
if (board[i][j] == 0) {
int choices = countValidNumbers(board, i, j);
if (choices < minChoices) {
minChoices = choices;
targetRow = i;
targetCol = j;
}
}
}
}
if (targetRow == -1) return; // 已完成
// 优先尝试出现次数少的数字（对称性剪枝）
vector<pair<int, int>> candidates;
for (int num = 1; num <= 9; num++) {
if (isValid(board, targetRow, targetCol, num)) {
candidates.push_back({countOccurrences(board, num), num});
}
}
sort(candidates.begin(), candidates.end());
for (auto& p : candidates) {
board[targetRow][targetCol] = p.second;
solveSudoku(board);
if (isSolved(board)) return;
board[targetRow][targetCol] = 0;
}
}
启发式搜索算法
A*算法
A*算法是最著名的启发式搜索算法，通过评估函数f(n) = g(n) + h(n)来指导搜索方向。
struct Node {
int x, y;
int g, h, f; // g:实际代价, h:启发代价, f:总代价
bool operator<(const Node& other) const {
return f > other.f; // 小顶堆
}
};
// 曼哈顿距离作为启发函数
int heuristic(int x1, int y1, int x2, int y2) {
return abs(x1 - x2) + abs(y1 - y2);
}
int AStar(vector<vector<int>>& grid, int sx, int sy, int ex, int ey) {
int n = grid.size(), m = grid[0].size();
vector<vector<int>> dist(n, vector<int>(m, INT_MAX));
priority_queue<Node> pq;
dist[sx][sy] = 0;
pq.push({sx, sy, 0, heuristic(sx, sy, ex, ey), heuristic(sx, sy, ex, ey)});
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
while (!pq.empty()) {
Node curr = pq.top();
pq.pop();
if (curr.x == ex && curr.y == ey) {
return curr.g;
}
if (curr.g > dist[curr.x][curr.y]) continue;
for (int i = 0; i < 4; i++) {
int nx = curr.x + dx[i];
int ny = curr.y + dy[i];
if (nx >= 0 && nx < n && ny >= 0 && ny < m && grid[nx][ny] == 0) {
int newG = curr.g + 1;
if (newG < dist[nx][ny]) {
dist[nx][ny] = newG;
int newH = heuristic(nx, ny, ex, ey);
pq.push({nx, ny, newG, newH, newG + newH});
}
}
}
}
return -1;
}
IDA*算法（迭代加深A*）
// 15数码问题的IDA*解法
int manhattanDistance(vector<vector<int>>& board) {
int dist = 0;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (board[i][j] != 0) {
int targetX = (board[i][j] - 1) / 4;
int targetY = (board[i][j] - 1) % 4;
dist += abs(i - targetX) + abs(j - targetY);
}
}
}
return dist;
}
bool dfs(vector<vector<int>>& board, int depth, int maxDepth,
int lastMove, int& nextBound) {
int h = manhattanDistance(board);
if (depth + h > maxDepth) {
nextBound = min(nextBound, depth + h);
return false;
}
if (h == 0) return true; // 找到解
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};
int opposite[] = {2, 3, 0, 1}; // 相反方向
// 找到空格位置
int ex, ey;
for (int i = 0; i < 4; i++) {
for (int j = 0; j < 4; j++) {
if (board[i][j] == 0) {
ex = i; ey = j;
break;
}
}
}
for (int dir = 0; dir < 4; dir++) {
if (dir == opposite[lastMove]) continue; // 避免回退
int nx = ex + dx[dir];
int ny = ey + dy[dir];
if (nx >= 0 && nx < 4 && ny >= 0 && ny < 4) {
swap(board[ex][ey], board[nx][ny]);
if (dfs(board, depth + 1, maxDepth, dir, nextBound)) {
return true;
}
swap(board[ex][ey], board[nx][ny]);
}
}
return false;
}
int IDAStar(vector<vector<int>>& board) {
int bound = manhattanDistance(board);
while (bound < 100) { // 设置上限
int nextBound = INT_MAX;
if (dfs(board, 0, bound, -1, nextBound)) {
return bound;
}
bound = nextBound;
}
return -1;
}
双向搜索
从起点和终点同时搜索，当两个搜索相遇时找到解。
// 单词接龙的双向BFS
int ladderLength(string beginWord, string endWord, vector<string>& wordList) {
unordered_set<string> dict(wordList.begin(), wordList.end());
if (!dict.count(endWord)) return 0;
unordered_set<string> beginSet, endSet;
beginSet.insert(beginWord);
endSet.insert(endWord);
int step = 1;
while (!beginSet.empty() && !endSet.empty()) {
// 优化：总是扩展较小的集合
if (beginSet.size() > endSet.size()) {
swap(beginSet, endSet);
}
unordered_set<string> nextSet;
for (string word : beginSet) {
for (int i = 0; i < word.length(); i++) {
char old = word[i];
for (char c = a; c <= z; c++) {
if (c == old) continue;
word[i] = c;
if (endSet.count(word)) {
return step + 1; // 相遇
}
if (dict.count(word)) {
nextSet.insert(word);
dict.erase(word);
}
}
word[i] = old;
}
}
beginSet = nextSet;
step++;
}
return 0;
}
记忆化搜索
// 数位DP的记忆化搜索
int dp[20][2][2]; // [位数][是否有界][是否有前导零]
int dfs(string& num, int pos, bool limit, bool lead, int target) {
if (pos == num.length()) return 1;
if (!limit && !lead && dp[pos][0][0] != -1) {
return dp[pos][0][0];
}
int maxDigit = limit ? (num[pos] - 0) : 9;
int res = 0;
for (int digit = 0; digit <= maxDigit; digit++) {
if (digit == target && !lead) continue; // 不能出现target
res += dfs(num, pos + 1,
limit && (digit == maxDigit),
lead && (digit == 0),
target);
}
if (!limit && !lead) {
dp[pos][0][0] = res;
}
return res;
}
int countNumbers(int n, int target) {
string num = to_string(n);
memset(dp, -1, sizeof(dp));
return dfs(num, 0, true, true, target);
}
搜索优化技巧汇总
优化技巧对比
| 技巧 | 原理 | 实现难度 | 优化效果 |
|---|---|---|---|
| 预排序 | 优先搜索更可能的分支 | 简单 | 中等 |
| 位运算优化 | 用位表示状态 | 中等 | 显著 |
| 哈希判重 | 快速判断重复状态 | 简单 | 显著 |
| 最优化剪枝 | 及时放弃无用分支 | 中等 | 显著 |
| 估价函数 | 启发式指导 | 困难 | 极大 |
经典问题的搜索优化
八皇后问题的优化演进
// 版本1：朴素回溯 O(n^n)
// 版本2：可行性剪枝 O(n!)
// 版本3：位运算优化
void solveNQueens(int n, int row, int cols, int diag1, int diag2, int& count) {
if (row == n) {
count++;
return;
}
int availablePositions = ((1 << n) - 1) & (~(cols | diag1 | diag2));
while (availablePositions) {
int position = availablePositions & (-availablePositions);
availablePositions -= position;
solveNQueens(n, row + 1,
cols | position,
(diag1 | position) << 1,
(diag2 | position) >> 1,
count);
}
}
练习题推荐
剪枝优化题目
| 题目 | 主要技巧 | 难度 |
|---|---|---|
| 数独求解 | 可行性剪枝 | ★★☆ |
| 装载问题 | 最优性剪枝 | ★★☆ |
| 图着色 | 对称性剪枝 | ★★★ |
| 旅行商问题 | 上下界剪枝 | ★★★ |
启发式搜索题目
| 题目 | 算法 | 难度 |
|---|---|---|
| 八数码 | A* | ★★★ |
| 迷宫最短路 | A* | ★★☆ |
| 15数码 | IDA* | ★★★★ |
| K短路 | A*变形 | ★★★★ |
总结
搜索算法的优化是信息学竞赛的重要技能，掌握搜索优化需要：
- 理解原理：知道各种优化技术的本质
- 识别时机：判断何时使用哪种优化
- 组合使用：多种优化技术结合
- 经验积累：通过练习培养直觉
- 创新思维：针对具体问题设计优化
记住，搜索优化的本质是”不做无用功”。通过剪枝减少搜索空间，通过启发式选择更好的搜索方向，通过记忆化避免重复计算。掌握这些技术，你将能够解决更复杂的搜索问题！
Views: 0
答复