高级搜索算法

高级搜索算法超越了基本的DFS和BFS，包括A*搜索、双向搜索和迭代加深等专门技术。这些算法对于高效解决复杂的路径查找和优化问题至关重要。

A*搜索算法

A*搜索使用启发式函数引导搜索朝向目标，结合了Dijkstra算法的优点和有信息搜索策略。

A*搜索实现

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

struct Point {
    int x, y;
    
    Point(int x = 0, int y = 0) : x(x), y(y) {}
    
    bool operator==(const Point& other) const {
        return x == other.x && y == other.y;
    }
    
    // 曼哈顿距离启发式
    int manhattanDistance(const Point& other) const {
        return abs(x - other.x) + abs(y - other.y);
    }
    
    // 欧几里得距离启发式
    double euclideanDistance(const Point& other) const {
        return sqrt((x - other.x) * (x - other.x) + (y - other.y) * (y - other.y));
    }
};

// Point的哈希函数
struct PointHash {
    size_t operator()(const Point& p) const {
        return hash<int>()(p.x) ^ (hash<int>()(p.y) << 1);
    }
};

struct AStarNode {
    Point pos;
    int gCost; // 从起点的代价
    int hCost; // 到目标的启发式代价
    Point parent;
    
    AStarNode(Point p, int g, int h, Point par) 
        : pos(p), gCost(g), hCost(h), parent(par) {}
    
    int fCost() const { return gCost + hCost; }
    
    bool operator>(const AStarNode& other) const {
        return fCost() > other.fCost();
    }
};

class AStar {
private:
    vector<vector<int>> grid;
    int rows, cols;
    vector<Point> directions = {{0,1}, {1,0}, {0,-1}, {-1,0}, 
                               {1,1}, {1,-1}, {-1,1}, {-1,-1}}; // 8方向
    
public:
    AStar(vector<vector<int>>& g) : grid(g), rows(g.size()), cols(g[0].size()) {}
    
    bool isValid(const Point& p) {
        return p.x >= 0 && p.x < rows && p.y >= 0 && p.y < cols && grid[p.x][p.y] == 0;
    }
    
    int getMoveCost(const Point& from, const Point& to) {
        // 对角线移动代价更高
        if (abs(from.x - to.x) + abs(from.y - to.y) == 2) {
            return 14; // 约为sqrt(2) * 10
        }
        return 10;
    }
    
    vector<Point> findPath(Point start, Point goal) {
        priority_queue<AStarNode, vector<AStarNode>, greater<AStarNode>> openSet;
        unordered_map<Point, int, PointHash> gScore;
        unordered_map<Point, Point, PointHash> cameFrom;
        
        openSet.push(AStarNode(start, 0, start.manhattanDistance(goal), Point(-1, -1)));
        gScore[start] = 0;
        
        while (!openSet.empty()) {
            AStarNode current = openSet.top();
            openSet.pop();
            
            if (current.pos == goal) {
                // 重构路径
                vector<Point> path;
                Point curr = goal;
                while (!(curr.x == -1 && curr.y == -1)) {
                    path.push_back(curr);
                    curr = cameFrom[curr];
                }
                reverse(path.begin(), path.end());
                return path;
            }
            
            // 如果已经找到更好的路径则跳过
            if (gScore.count(current.pos) && current.gCost > gScore[current.pos]) {
                continue;
            }
            
            for (const Point& dir : directions) {
                Point neighbor(current.pos.x + dir.x, current.pos.y + dir.y);
                
                if (!isValid(neighbor)) continue;
                
                int tentativeG = current.gCost + getMoveCost(current.pos, neighbor);
                
                if (!gScore.count(neighbor) || tentativeG < gScore[neighbor]) {
                    gScore[neighbor] = tentativeG;
                    cameFrom[neighbor] = current.pos;
                    
                    int hCost = neighbor.manhattanDistance(goal);
                    openSet.push(AStarNode(neighbor, tentativeG, hCost, current.pos));
                }
            }
        }
        
        return {}; // 未找到路径
    }
    
    void printPath(const vector<Point>& path) {
        if (path.empty()) {
            cout << "未找到路径！" << endl;
            return;
        }
        
        vector<vector<char>> display(rows, vector<char>(cols, '.'));
        
        // 标记障碍物
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 1) display[i][j] = '#';
            }
        }
        
        // 标记路径
        for (int i = 0; i < path.size(); i++) {
            if (i == 0) display[path[i].x][path[i].y] = 'S'; // 起点
            else if (i == path.size() - 1) display[path[i].x][path[i].y] = 'G'; // 终点
            else display[path[i].x][path[i].y] = '*';
        }
        
        // 打印网格
        for (const auto& row : display) {
            for (char c : row) {
                cout << c << " ";
            }
            cout << endl;
        }
        
        cout << "路径长度: " << path.size() << endl;
    }
};

int main() {
    // 创建带障碍物的网格（1=障碍物，0=空闲）
    vector<vector<int>> grid = {
        {0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
        {0, 0, 0, 0, 0, 0, 0, 0, 0, 0}
    };
    
    AStar astar(grid);
    Point start(0, 0);
    Point goal(9, 9);
    
    cout << "使用A*搜索从(0,0)到(9,9)找路径:" << endl;
    cout << "图例: S=起点, G=终点, *=路径, #=障碍物, .=空闲" << endl << endl;
    
    vector<Point> path = astar.findPath(start, goal);
    astar.printPath(path);
    
    return 0;
}

A*搜索使用f(n) = g(n) + h(n)，其中g(n)是从起点的实际代价，h(n)是到目标的启发式估计。当启发式函数是可接受的（从不高估）时，算法保证最优路径。

双向搜索

双向搜索从起点和终点同时运行两个搜索，在中间相遇以指数级减少搜索空间。

双向BFS实现

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

class BidirectionalBFS {
private:
    vector<vector<int>> graph;
    int n;
    
public:
    BidirectionalBFS(vector<vector<int>>& g) : graph(g), n(g.size()) {}
    
    vector<int> findPath(int start, int goal) {
        if (start == goal) return {start};
        
        // 正向和反向搜索的两个队列
        queue<int> forwardQueue, backwardQueue;
        unordered_set<int> forwardVisited, backwardVisited;
        unordered_map<int, int> forwardParent, backwardParent;
        
        forwardQueue.push(start);
        backwardQueue.push(goal);
        forwardVisited.insert(start);
        backwardVisited.insert(goal);
        forwardParent[start] = -1;
        backwardParent[goal] = -1;
        
        while (!forwardQueue.empty() || !backwardQueue.empty()) {
            // 扩展正向搜索
            if (!forwardQueue.empty()) {
                int meetingPoint = expandLevel(forwardQueue, forwardVisited, backwardVisited, 
                                             forwardParent, true);
                if (meetingPoint != -1) {
                    return constructPath(meetingPoint, forwardParent, backwardParent);
                }
            }
            
            // 扩展反向搜索
            if (!backwardQueue.empty()) {
                int meetingPoint = expandLevel(backwardQueue, backwardVisited, forwardVisited, 
                                             backwardParent, false);
                if (meetingPoint != -1) {
                    return constructPath(meetingPoint, forwardParent, backwardParent);
                }
            }
        }
        
        return {}; // 未找到路径
    }
    
private:
    int expandLevel(queue<int>& q, unordered_set<int>& visited, 
                   unordered_set<int>& otherVisited, unordered_map<int, int>& parent, 
                   bool isForward) {
        int levelSize = q.size();
        
        for (int i = 0; i < levelSize; i++) {
            int current = q.front();
            q.pop();
            
            for (int neighbor : graph[current]) {
                if (otherVisited.count(neighbor)) {
                    // 找到交集！
                    parent[neighbor] = current;
                    return neighbor;
                }
                
                if (!visited.count(neighbor)) {
                    visited.insert(neighbor);
                    parent[neighbor] = current;
                    q.push(neighbor);
                }
            }
        }
        
        return -1; // 在此层未找到交集
    }
    
    vector<int> constructPath(int meetingPoint, unordered_map<int, int>& forwardParent, 
                             unordered_map<int, int>& backwardParent) {
        vector<int> path;
        
        // 构建从起点到交汇点的路径
        vector<int> forwardPath;
        int current = meetingPoint;
        while (current != -1) {
            forwardPath.push_back(current);
            current = forwardParent[current];
        }
        reverse(forwardPath.begin(), forwardPath.end());
        
        // 构建从交汇点到终点的路径
        vector<int> backwardPath;
        current = backwardParent[meetingPoint];
        while (current != -1) {
            backwardPath.push_back(current);
            current = backwardParent[current];
        }
        
        // 合并路径
        path = forwardPath;
        path.insert(path.end(), backwardPath.begin(), backwardPath.end());
        
        return path;
    }
};

// 迭代加深DFS
class IterativeDeepeningDFS {
private:
    vector<vector<int>> graph;
    int n;
    
public:
    IterativeDeepeningDFS(vector<vector<int>>& g) : graph(g), n(g.size()) {}
    
    vector<int> findPath(int start, int goal, int maxDepth = 20) {
        for (int depth = 0; depth <= maxDepth; depth++) {
            vector<bool> visited(n, false);
            vector<int> path;
            
            if (dfsLimited(start, goal, depth, visited, path)) {
                return path;
            }
        }
        
        return {}; // 在深度限制内未找到路径
    }
    
private:
    bool dfsLimited(int current, int goal, int depth, vector<bool>& visited, vector<int>& path) {
        path.push_back(current);
        
        if (current == goal) {
            return true;
        }
        
        if (depth == 0) {
            path.pop_back();
            return false;
        }
        
        visited[current] = true;
        
        for (int neighbor : graph[current]) {
            if (!visited[neighbor]) {
                if (dfsLimited(neighbor, goal, depth - 1, visited, path)) {
                    return true;
                }
            }
        }
        
        visited[current] = false;
        path.pop_back();
        return false;
    }
};

int main() {
    // 创建示例图
    vector<vector<int>> graph = {
        {1, 2},       // 0 -> 1, 2
        {0, 3, 4},    // 1 -> 0, 3, 4
        {0, 5, 6},    // 2 -> 0, 5, 6
        {1, 7},       // 3 -> 1, 7
        {1, 7},       // 4 -> 1, 7
        {2, 8},       // 5 -> 2, 8
        {2, 8},       // 6 -> 2, 8
        {3, 4, 9},    // 7 -> 3, 4, 9
        {5, 6, 9},    // 8 -> 5, 6, 9
        {7, 8}        // 9 -> 7, 8
    };
    
    BidirectionalBFS bidiBFS(graph);
    IterativeDeepeningDFS iddfs(graph);
    
    int start = 0, goal = 9;
    
    // 测试双向BFS
    cout << "双向BFS从 " << start << " 到 " << goal << ": ";
    vector<int> bidiPath = bidiBFS.findPath(start, goal);
    if (!bidiPath.empty()) {
        for (int i = 0; i < bidiPath.size(); i++) {
            if (i > 0) cout << " -> ";
            cout << bidiPath[i];
        }
        cout << " (长度: " << bidiPath.size() << ")" << endl;
    } else {
        cout << "未找到路径" << endl;
    }
    
    // 测试迭代加深DFS
    cout << "迭代加深DFS从 " << start << " 到 " << goal << ": ";
    vector<int> iddfsPath = iddfs.findPath(start, goal);
    if (!iddfsPath.empty()) {
        for (int i = 0; i < iddfsPath.size(); i++) {
            if (i > 0) cout << " -> ";
            cout << iddfsPath[i];
        }
        cout << " (长度: " << iddfsPath.size() << ")" << endl;
    } else {
        cout << "未找到路径" << endl;
    }
    
    return 0;
}

双向搜索将时间复杂度从O(b^d)减少到O(b^(d/2))，其中b是分支因子，d是深度。迭代加深结合了DFS的空间效率和BFS的最优性。

关键要点

A*搜索使用启发式函数高效引导搜索，在可接受启发式下保证最优路径
双向搜索通过在中间相遇减少指数级搜索空间
迭代加深结合了DFS的内存效率和BFS的完整性与最优性
根据问题约束选择搜索算法：内存、最优性要求和启发式可用性