2. 搜索
[[ACM技能树]]
- 四个关键点
- 开始状态
- 结束状态
- 状态空间
- 结束函数
2.1 深度优先搜索
- 定义
- 深度优先搜索（Depth-First Search，简称DFS）是一种用于遍历或搜索树或图的算法。在深度优先搜索中，我们从一个节点开始，尽可能深地搜索树的分支，直到找到目标或者不能再深入为止，然后回溯并搜索其他分支。
- 深度优先搜索的关键特性是它生成了一种特殊类型的树结构，称为探索树（spanning tree），这棵树包含了所有被访问过的节点和边。
- 深度优先搜索通常使用栈来实现，可以是显式的栈（在编程中显式创建一个栈数据结构）或隐式的栈（通过递归调用时的系统调用栈）。
- 基本思想
- 选择一个起始节点：从树或图的某个节点开始。
- 探索尽可能深的分支：沿着树或图的边，从上到下（或从左到右）探索节点，直到到达没有未探索的邻居的节点。
- 回溯：当无法继续深入时，回溯到上一个节点，并探索其他未访问的分支。
- 重复：重复上述过程，直到所有节点都被访问过。
- 应用场景
- 树和图的遍历：用于访问树或图中的所有节点。
- 路径寻找：在迷宫或网络中寻找从一个节点到另一个节点的路径。
- 拓扑排序：对有向无环图（DAG）的顶点进行排序。
- 解决数独：在解决数独问题时尝试不同的数字填入空格。
- 字符串的排列：生成一个字符串的所有排列。
- 深度优先搜索的示例：图的遍历
- 题解
#include <iostream>
#include <vector>
#include <stack>
// 图的表示，使用邻接表
std::vector<std::vector<int>> adj;
// 深度优先搜索函数
void DFS(int v, std::vector<bool>& visited) {
visited[v] = true;
std::cout << v << " ";
// 遍历v的所有邻接节点
for (int u : adj[v]) {
if (!visited[u]) {
DFS(u, visited);
}
}
}
int main() {
// 创建一个图
adj = {
{2, 3},
{1, 4},
{1, 5},
{2},
{1},
{2}
};
// 图的顶点数
int n = 5;
// 标记所有顶点为未访问
std::vector<bool> visited(n + 1, false);
// 从顶点1开始深度优先搜索
DFS(1, visited);
return 0;
}
2.2 广度优先搜索
-
定义
- 广度优先搜索（Breadth-First Search，简称BFS）是一种遍历或搜索树或图的算法，它从一个节点开始，先访问所有邻近的节点（即深度为1的节点），然后再逐层向外扩展，访问每个邻近节点的邻近节点（即深度为2的节点），依此类推。BFS通常使用队列来实现。
- 广度优先搜索的关键特性是它能够找到从起点到目标节点的最短路径，如果目标节点是图中的某个节点的话。
-
广度优先搜索的基本思想是：
- 选择一个起始节点：从树或图的某个节点开始。
- 逐层探索：首先访问起始节点的所有邻接节点，然后对于每个邻接节点，访问它们的邻接节点，但排除已经访问过的节点。
- 使用队列：新发现的节点被加入到队列的末尾，而队列的前端始终是下一个要访问的节点。
- 重复：重复上述过程，直到队列为空，即所有可达的节点都被访问过。
-
广度优先搜索的应用场景：
- 最短路径寻找：在未加权图中找到两点间的最短路径。
- 社交网络分析：确定个体之间的联系距离。
- 网络广播：如何通过最少的中继站将信息传播到整个网络。
- A*搜索算法：在图形平面上，有多个节点的路径中，为每个节点定义了一个“成本”，在移动时成本最低的路径。
- 解决迷宫问题：找到从起点到终点的最短路径。
-
广度优先搜索的示例：图的遍历
-
题解
#include <iostream>
#include <vector>
#include <queue>
// 图的表示，使用邻接表
std::vector<std::vector<int>> adj;
// 广度优先搜索函数
void BFS(int start) {
std::vector<bool> visited(adj.size(), false); // 记录访问状态
std::queue<int> q; // 用来存储待访问的节点
// 标记起始节点为已访问并入队
visited[start] = true;
q.push(start);
while (!q.empty()) {
int v = q.front();
q.pop();
std::cout << v << " "; // 访问节点
// 遍历v的所有邻接节点
for (int u : adj[v]) {
if (!visited[u]) {
visited[u] = true;
q.push(u); // 邻接节点入队
}
}
}
}
int main() {
// 创建一个图
adj = {
{2, 3},
{1, 4},
{1, 5},
{2},
{1},
{2}
};
// 图的顶点数
int n = 5;
// 从顶点1开始广度优先搜索
BFS(1);
return 0;
}
2.3 双向搜索
-
定义
- 双向搜索是一种用于图或树结构中搜索路径的算法，它从两个方向开始搜索：一个是从起始节点向目标方向，另一个是从目标节点向起始方向。当两个方向的搜索在图中的某一点相遇时，就找到了一条路径。这种方法特别适用于寻找两个节点之间的最短路径，尤其是当图中的边没有权重或者所有边的权重相同时。
-
双向搜索的关键思想是：
- 两个方向：同时从起始节点和目标节点开始搜索。
- 交替扩展：在两个方向上交替扩展节点，直到两个方向的搜索相遇。
- 相遇即完成：一旦两个方向的搜索在图中的某个节点相遇，就找到了一条路径，搜索结束。
-
双向搜索通常用于解决以下问题：
- 最短路径问题：在无权图中寻找两个节点之间的最短路径。
- 图的连通性问题：确定图中两个节点是否连通。
- 迷宫问题：在迷宫中找到从起点到终点的路径。
-
双向搜索的步骤：
- 初始化：在起始节点和目标节点分别标记已访问，并创建两个开放列表（或队列）。
- 扩展节点：从起始节点和目标节点同时开始，扩展邻接节点，并将它们添加到相应的开放列表中。
- 检查相遇：在每次扩展后，检查两个开放列表是否有共同的节点，如果有，则搜索结束。
- 更新路径：当两个方向的搜索相遇时，可以通过回溯已访问的节点来重建路径。
-
双向搜索的示例：寻找最短路径
#include <iostream>
#include <vector>
#include <queue>
// 图的表示，使用邻接表
std::vector<std::vector<int>> adj;
// 双向搜索函数
std::vector<int> bidirectionalSearch(int start, int end) {
std::vector<bool> visited1(adj.size(), false);
std::vector<bool> visited2(adj.size(), false);
std::queue<int> q1;
std::queue<int> q2;
visited1[start] = true;
q1.push(start);
visited2[end] = true;
q2.push(end);
while (!q1.empty() && !q2.empty()) {
int node1 = q1.front();
q1.pop();
int node2 = q2.front();
q2.pop();
// 检查是否相遇
if (node1 == node2) {
return {node1}; // 找到路径，返回节点
}
// 扩展节点
for (int neighbor : adj[node1]) {
if (!visited1[neighbor]) {
visited1[neighbor] = true;
q1.push(neighbor);
}
}
for (int neighbor : adj[node2]) {
if (!visited2[neighbor]) {
visited2[neighbor] = true;
q2.push(neighbor);
}
}
}
return {}; // 没有找到路径
}
int main() {
// 创建一个图
adj = {
{2, 3},
{1, 4},
{1, 5},
{2},
{1},
{2}
};
// 从顶点1开始，到顶点5结束的双向搜索
std::vector<int> path = bidirectionalSearch(1, 5);
if (!path.empty()) {
std::cout << "Path found: ";
for (int node : path) {
std::cout << node << " ";
}
std::cout << std::endl;
} else {
std::cout << "No path found." << std::endl;
}
return 0;
}
2.4 记忆化搜索
-
定义
- 记忆化搜索是一种编程技巧，主要用于优化搜索算法的性能，特别是在处理重叠子问题和重复计算时非常有效。这种方法通常与分治策略相结合，通过保存中间结果来避免对同一问题的多次重复计算，从而显著提高算法的效率。记忆化搜索的核心思想是在递归地解决问题时，对于某个特定的输入，如果之前已经计算过，则直接从记忆单元中读取结果，而不是重新计算。
-
记忆化搜索的基本步骤如下：
- 定义一个问题和一个解决方案的空间。
- 创建一个记忆单元，用于存储已解决的子问题的答案。
- 对于一个新的问题，首先检查记忆单元中是否存在该问题的解。如果有，直接返回该解。
- 如果记忆单元中没有该问题的解，则进行递归求解。在递归过程中，对于遇到的每一个子问题，都按照上述步骤进行检查和存储。
- 在得到最终解后，将其存入记忆单元，以便后续使用。
-
记忆化搜索的主要优点包括：
- 减少了重复计算，提高了算法的时间复杂度。
- 对于某些问题，可以使用自顶向下的递归方式来实现，使得代码更加直观和易于理解。
- 可以应用于多种问题，如动态规划、组合数学等。
-
记忆化搜索也有其局限性：
- 需要额外的空间来存储中间结果，这可能影响算法的空间复杂度。
- 对于某些问题，如果不合理地设计记忆单元，可能会出现大量的冗余存储，导致性能下降。
- 示例斐波那契数列问题
#include <iostream>
#include <vector>
#include <unordered_map>
// 使用哈希表作为记忆单元
std::unordered_map<int, long long> memo;
// 记忆化搜索函数
long long fibonacci(int n) {
// 检查记忆单元中是否已经计算过该值
if (memo.find(n) != memo.end()) {
return memo[n];
}
// 递归基
if (n == 0) return 0;
if (n == 1) return 1;
// 计算斐波那契数，并将结果存入记忆单元
memo[n] = fibonacci(n - 1) + fibonacci(n - 2);
// 返回计算结果
return memo[n];
}
int main() {
// 测试记忆化搜索的斐波那契数列计算
std::cout << "Fibonacci(10) = " << fibonacci(10) << std::endl; // 输出 55
std::cout << "Fibonacci(30) = " << fibonacci(30) << std::endl; // 输出 832040
return 0;
}
2.5 启发式搜索
-
定义
- 启发式搜索（Heuristic Search）是一种用于解决搜索问题的技术，特别是在图搜索中。它使用一个启发式函数来估计从当前节点到目标节点的距离，从而指导搜索过程朝着目标方向前进。启发式搜索算法中最知名的是A*（A星）算法。
-
启发式搜索的关键思想是：
- 启发式函数（Heuristic Function）：这个函数估计了从当前节点到目标节点的成本。它应该是乐观的，即永远不超过实际成本，但越准确越好。
- 优先选择：启发式搜索算法优先扩展那些具有最低估计总成本的节点，这个总成本通常由两部分组成：从起始节点到当前节点的实际成本（g(n)），以及从当前节点到目标节点的估计成本（h(n)）。
- 开放列表和关闭列表：开放列表（Open List）保存待检查的节点，关闭列表（Closed List）保存已经检查过的节点。
-
启发式搜索算法的步骤：
- 初始化：将起始节点加入开放列表，并设置起始节点的实际成本为0。
- 循环：当开放列表不为空时，执行以下步骤：
- 从开放列表中选择具有最低f(n) = g(n) + h(n)的节点。
- 如果选择的节点是目标节点，则搜索完成。
- 否则，将该节点加入关闭列表，并将它的邻接节点加入开放列表。
- 检查启发式函数：对于每个邻接节点，使用启发式函数估计其到目标节点的成本，并更新其实际成本和总估算成本。
-
启发式搜索算法的示例：A*算法
#include <iostream>
#include <vector>
#include <queue>
#include <map>
#include <limits>
using namespace std;
// 定义节点结构
struct Node {
int x, y; // 节点的坐标
double g; // 从起始节点到当前节点的成本
double h; // 从当前节点到目标节点的启发式估计成本
double f; // f(n) = g(n) + h(n)
Node *parent; // 父节点
Node(int x, int y, Node* parent = nullptr)
: x(x), y(y), parent(parent), g(0), h(0), f(0) {}
double getF() const {
return f = g + h;
}
};
// 比较函数，用于优先队列
struct CompareNode {
bool operator()(Node* a, Node* b) {
return a->getF() > b->getF();
}
};
// A*算法
vector<Node*> AStar(vector<vector<int>>& map, pair<int, int> start, pair<int, int> end) {
map[start.first][start.second] = 1; // 标记起始节点为已访问
priority_queue<Node*, vector<Node*>, CompareNode> openList;
map<Node*, double, greater<Node*>> cameFrom;
Node* current = new Node(start.first, start.second);
openList.push(current);
double gScore, hScore, tmpScore;
Node* neighbor;
while (!openList.empty()) {
current = openList.top();
openList.pop();
if (current->x == end.first && current->y == end.second) {
// 找到目标节点，重建路径
vector<Node*> path;
while (current) {
path.push_back(current);
current = current->parent;
}
reverse(path.begin(), path.end());
return path;
}
// 将当前节点加入关闭列表
map[current->x][current->y] = 2;
// 循环邻接节点
for (int dx : {-1, 0, 1}) {
for (int dy : {-1, 0, 1}) {
if (dx == 0 && dy == 0) continue;
int nx = current->x + dx, ny = current->y + dy;
if (nx >= 0 && nx < map.size() && ny >= 0 && ny < map[0].size() &&
map[nx][ny] != 3) { // 3表示障碍物
gScore = current->g + 1; // 简化成本计算
hScore = (nx - end.first) * (nx - end.first) +
(ny - end.second) * (ny - end.second); // 曼哈顿距离
tmpScore = gScore + hScore;
if (cameFrom.find(new Node(nx, ny)) == cameFrom.end() ||
cameFrom[new Node(nx, ny)] > tmpScore) {
cameFrom[new Node(nx, ny)] = tmpScore;
openList.push(new Node(nx, ny, current));
}
}
}
}
}
return {}; // 未找到路径
}
int main() {
vector<vector<int>> map = {
{0, 0, 0, 0, 1},
{1, 1, 0, 1, 1},
{0, 0, 0, 0, 0},
{0, 1, 1, 1, 0},
{0, 0, 0, 0, 0}
};
pair<int, int> start = {0, 0};
pair<int, int> end = {4, 4};
vector<Node*> path = AStar(map, start, end);
if (!path.empty()) {
cout << "Path found:\n";
for (Node* node : path) {
cout << "(" << node->x << ", " << node->y << ") -> ";
}
cout << "End" << endl;
} else {
cout << "No path found." << endl;
}
return 0;
}
- 在这个例子中，我们使用了一个二维数组
map来表示地图，其中0表示可通行区域，1表示障碍物，2表示已访问的节点。AStar函数实现了A*算法，使用优先队列openList来保存待检查的节点，并使用cameFrom映射来记录每个节点的父节点和成本。