C++搜索问题

C++ 中的搜索算法是指在数据结构或图中寻找某些特定元素或满足条件的路径的算法。搜索算法广泛应用于问题求解、路径规划、数据检索等领域。常见的搜索算法可以分为两大类：

1. 无权搜索算法：如深度优先搜索（DFS）、广度优先搜索（BFS）。
2. 启发式搜索算法：如A算法、双向搜索、IDA算法等。

1. 深度优先搜索（DFS）

特点

• DFS 是一种递归或栈实现的搜索策略，从起点出发尽可能深入，然后再回溯继续探索未访问的路径。
• 时间复杂度：O(V+E)O(V + E)O(V+E)（V是节点数，E是边数）。
• 适用场景：路径搜索、连通性检测、拓扑排序等。

实现方式

递归版 DFS

#include <iostream>
#include <vector>
using namespace std;

void dfs(int node, vector<vector<int>>& graph, vector<bool>& visited) {
    visited[node] = true;
    cout << "访问节点: " << node << endl;

    for (int neighbor : graph[node]) {
        if (!visited[neighbor]) {
            dfs(neighbor, graph, visited);
        }
    }
}

int main() {
    int n = 5; // 节点数
    vector<vector<int>> graph(n);

    // 构建无向图
    graph[0] = {1, 2};
    graph[1] = {0, 3};
    graph[2] = {0, 4};
    graph[3] = {1};
    graph[4] = {2};

    vector<bool> visited(n, false);
    dfs(0, graph, visited); // 从节点 0 开始搜索
    return 0;
}

非递归版 DFS

使用显式栈来模拟递归调用栈。

#include <iostream>
#include <vector>
#include <stack>
using namespace std;

void dfs_iterative(int start, vector<vector<int>>& graph, vector<bool>& visited) {
    stack<int> s;
    s.push(start);

    while (!s.empty()) {
        int node = s.top();
        s.pop();

        if (!visited[node]) {
            visited[node] = true;
            cout << "访问节点: " << node << endl;

            for (int neighbor : graph[node]) {
                if (!visited[neighbor]) {
                    s.push(neighbor);
                }
            }
        }
    }
}

int main() {
    int n = 5;
    vector<vector<int>> graph(n);
    graph[0] = {1, 2};
    graph[1] = {0, 3};
    graph[2] = {0, 4};
    graph[3] = {1};
    graph[4] = {2};

    vector<bool> visited(n, false);
    dfs_iterative(0, graph, visited);
    return 0;
}

2. 广度优先搜索（BFS）

特点

• BFS 是一种层次搜索策略，先访问所有距离起点最近的节点，然后逐层向外扩展。
• 时间复杂度：O(V+E)O(V + E)O(V+E)。
• 适用场景：最短路径（无权图）、连通性检测等。

实现方式

使用队列实现 BFS。

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

void bfs(int start, vector<vector<int>>& graph) {
    int n = graph.size();
    vector<bool> visited(n, false);
    queue<int> q;

    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int node = q.front();
        q.pop();

        cout << "访问节点: " << node << endl;

        for (int neighbor : graph[node]) {
            if (!visited[neighbor]) {
                visited[neighbor] = true;
                q.push(neighbor);
            }
        }
    }
}

int main() {
    int n = 5;
    vector<vector<int>> graph(n);
    graph[0] = {1, 2};
    graph[1] = {0, 3};
    graph[2] = {0, 4};
    graph[3] = {1};
    graph[4] = {2};

    bfs(0, graph);
    return 0;
}

3. A*搜索算法

特点

• A* 是一种启发式搜索算法，结合了广度优先搜索和Dijkstra算法的优点。
• f(n) = g(n) + h(n)：
  • g(n)g(n)g(n)：起点到当前节点的实际代价。
  • h(n)h(n)h(n)：当前节点到目标节点的估算代价（启发式函数）。
• 时间复杂度：根据启发式函数的设计，通常优于普通BFS和Dijkstra。

实现方式

#include <iostream>
#include <vector>
#include <queue>
#include <cmath>
using namespace std;

struct Node {
    int x, y, cost, heuristic;
    bool operator>(const Node& other) const {
        return (cost + heuristic) > (other.cost + other.heuristic);
    }
};

int heuristic(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2); // 曼哈顿距离
}

void a_star(vector<vector<int>>& grid, pair<int, int> start, pair<int, int> goal) {
    int rows = grid.size();
    int cols = grid[0].size();
    vector<vector<int>> cost(rows, vector<int>(cols, INT_MAX));
    priority_queue<Node, vector<Node>, greater<Node>> pq;

    int dx[] = {0, 1, 0, -1};
    int dy[] = {1, 0, -1, 0};

    pq.push({start.first, start.second, 0, heuristic(start.first, start.second, goal.first, goal.second)});
    cost[start.first][start.second] = 0;

    while (!pq.empty()) {
        Node current = pq.top();
        pq.pop();

        if (current.x == goal.first && current.y == goal.second) {
            cout << "到达目标点，总代价为: " << current.cost << endl;
            return;
        }

        for (int i = 0; i < 4; ++i) {
            int nx = current.x + dx[i];
            int ny = current.y + dy[i];

            if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && grid[nx][ny] == 0) {
                int new_cost = current.cost + 1;
                if (new_cost < cost[nx][ny]) {
                    cost[nx][ny] = new_cost;
                    pq.push({nx, ny, new_cost, heuristic(nx, ny, goal.first, goal.second)});
                }
            }
        }
    }

    cout << "无法到达目标点" << endl;
}

int main() {
    vector<vector<int>> grid = {
        {0, 0, 0, 0},
        {0, 1, 1, 0},
        {0, 0, 0, 0},
        {0, 1, 0, 0}
    };
    pair<int, int> start = {0, 0};
    pair<int, int> goal = {3, 3};

    a_star(grid, start, goal);
    return 0;
}

4. 双向搜索

特点 

• 双向搜索同时从起点和目标节点进行搜索，缩小搜索范围，适用于无向图。

总结

1. 无权图搜索：DFS（深度优先搜索）、BFS（广度优先搜索）。
2. 权重图搜索：A*算法、Dijkstra算法、Bellman-Ford算法。
3. 全局搜索：Floyd-Warshall、Johnson算法。

C++ 强大的 STL（如 vector、priority_queue）可以有效实现这些算法，使得代码简洁高效。在实际应用中，选择合适的搜索算法和优化技巧是关键。