2`层级（A※、BFS)

A*

• 最短路径问题：在指定区域内，找到A到B的多条可行路径中，最短路径
• 尝试用其他解决方案：
  • 深度优先搜索：由于找到一条可行路径并不一定是最短路径，因此要遍历所有路径，这样非常耗时，如果要保存所有可行路径结果，还要大量的存储空间
  • 广度优先搜索：不断往外扩展搜索，时间上最坏情况要遍历所有节点，空间上要大量存储，因为不知道哪个路径可行，都要存储
• 对于已知终点位置来说，其实没必要遍历所有节点和记录所有情况
• Dijkstra：和bfs相似也是向外扩展，但对于每个节点的4个子节点代价不同，代价为距离起点的移动距离，并非像bfs使用queue，而是改用priority_queue，先从代价最小的节点开始扩展，能保证找到最短路径
• 最佳优先搜索：和Dijkstra相比，代价改为距离终点的移动距离，并且仅会从代价最小的节点开始扩展，而非像Dijkstra一样保留所有路径，这样可以非常快的找到终点，但是如果中间有障碍物，可能找到错误的结果（非最短路径）

A*

• 
• 思想：从代价最小的节点开始扩展
• 代价：
  • gn是距离起点的代价
  • hn距离终点的估算代价（对于起点开始到达此位置付出的代价，由已经历的路径可以计算，但我们还不知道距离终点的代价，启发函数）
  • 两者相加为fn节点代价
• 启发函数:
  • 控制算法的速度和精确度
    • 如果hn == 0，则退化成了Dijkstra算法
    • hn <= g(n)，能保证找到最短路径, hn值越小，算法越慢
    • hn == g(n)，能保证找到最短路径,算法很快
    • hn > g(n)，不能保证找到最短路径, 算法很快
    • 当hn比g(n)大很多，则退化成了最佳优先搜索
  • 在某些情况，不一定期望找到最短路径，而希望以更快的速度，找到一条可行路径即可，因此A*算法很灵活

  • 对于网格图，常见的启发函数：

    function heuristic(node) =
      dx = abs(node.x - goal.x)
      dy = abs(node.y - goal.y)
      return D * (dx + dy)
    function heuristic(node) =
      dx = abs(node.x - goal.x)
      dy = abs(node.y - goal.y)
      return D * (dx + dy) + (D2 - 2 * D) * min(dx, dy)
    function heuristic(node) =
      dx = abs(node.x - goal.x)
      dy = abs(node.y - goal.y)
      return D * sqrt(dx * dx + dy * dy)
    

    展开

    • 曼哈顿距离、只允许朝上下左右四个方向移动, D是固定常数
    • 对角距离、允许朝八个方向移动（对角代价更大），D2是对角移动代价：sqrt(2) * D
    • 欧几里得距离、允许朝任何方向移动,两个节点连接向量的模长

steps：

• 确立搜索区域，
• 简化搜索区域：划分网格 / 节点（可以用vector< vector< Node*»存储，每个节点有可走（非障碍物），不可走（障碍物）两种情况）
• 开始搜索算法:
  • 每次选取优先级最高（值最小）的节点
  • 两个集合open_set和close_set，表示待遍历的节点，与已遍历的节点，其他未遍历的不在两个集合中

#include <vector>
#include <queue>
#include <unordered_set>
#include <cmath>
#include <algorithm>

// 定义节点结构
struct Node {
    int x, y;
    float g, h, f;
    Node* parent;
    bool isWalkable;

    Node(int x, int y, bool walkable = true) 
        : x(x), y(y), g(0), h(0), f(0), parent(nullptr), isWalkable(walkable) {}

    // 重载比较运算符
    bool operator<(const Node& other) const {
        return f > other.f; // 最小堆
    }
};

// 节点指针比较器，用于优先队列
struct NodeCompare {
    bool operator()(Node* a, Node* b) {
        return a->f > b->f; // 最小堆
    }
};

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

// 节点哈希函数，用于unordered_set
struct NodeHash {
    std::size_t operator()(Node* node) const {
        return std::hash<int>()(node->x) ^ (std::hash<int>()(node->y) << 1);
    }
};

// 节点相等比较
struct NodeEqual {
    bool operator()(Node* a, Node* b) const {
        return a->x == b->x && a->y == b->y;
    }
};

class AStar {
private:
    std::vector<std::vector<Node>> grid; // 网格地图

public:
    AStar(int width, int height) {
        grid.resize(height, std::vector<Node>(width, Node(0, 0)));
        // 初始化网格
        for (int y = 0; y < height; y++) {
            for (int x = 0; x < width; x++) {
                grid[y][x] = Node(x, y, true);
            }
        }
    }

    // 设置节点是否可走
    void setWalkable(int x, int y, bool walkable) {
        if (x >= 0 && x < grid[0].size() && y >= 0 && y < grid.size()) {
            grid[y][x].isWalkable = walkable;
        }
    }

    // 获取邻居节点
    std::vector<Node*> getNeighbors(Node* node) {
        std::vector<Node*> neighbors;
        int x = node->x, y = node->y;
        int width = grid[0].size(), height = grid.size();

        // 四个方向：上、右、下、左
        int dx[] = {0, 1, 0, -1};
        int dy[] = {-1, 0, 1, 0};

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

            if (nx >= 0 && nx < width && ny >= 0 && ny < height) {
                Node* neighbor = &grid[ny][nx];
                if (neighbor->isWalkable) {
                    neighbors.push_back(neighbor);
                }
            }
        }
        return neighbors;
    }

    // A*算法实现
    std::vector<Node*> findPath(Node* start, Node* goal) {
        // 使用优先队列（最小堆）
        std::priority_queue<Node*, std::vector<Node*>, NodeCompare> openSet;
        
        // 使用unordered_set记录访问过的节点
        std::unordered_set<Node*, NodeHash, NodeEqual> closedSet;

        // 初始化起点
        start->g = 0;
        start->h = manhattanDistance(start->x, start->y, goal->x, goal->y);
        start->f = start->g + start->h;
        start->parent = nullptr;

        openSet.push(start);

        while (!openSet.empty()) {
            // 获取f值最小的节点
            Node* current = openSet.top();
            openSet.pop();

            // 到达目标
            if (current->x == goal->x && current->y == goal->y) {
                return reconstructPath(current);
            }

            // 加入已访问集合
            closedSet.insert(current);

            // 检查邻居
            for (Node* neighbor : getNeighbors(current)) {
                // 跳过已访问节点
                if (closedSet.find(neighbor) != closedSet.end()) {
                    continue;
                }

                // 计算新的g值
                float tentativeG = current->g + 1; // 假设每个移动代价为1

                // 检查是否找到更优路径
                bool foundBetter = false;
                if (tentativeG < neighbor->g || neighbor->g == 0) {
                    neighbor->parent = current;
                    neighbor->g = tentativeG;
                    neighbor->h = manhattanDistance(neighbor->x, neighbor->y, goal->x, goal->y);
                    neighbor->f = neighbor->g + neighbor->h;
                    foundBetter = true;
                }

                // 如果找到更优路径，加入开放集合
                // 注意：这里简化处理，实际应该检查是否已在开放集合中
                if (foundBetter) {
                    openSet.push(neighbor);
                }
            }
        }

        // 未找到路径
        return {};
    }

private:
    // 重建路径
    std::vector<Node*> reconstructPath(Node* end) {
        std::vector<Node*> path;
        Node* current = end;

        while (current != nullptr) {
            path.push_back(current);
            current = current->parent;
        }

        std::reverse(path.begin(), path.end());
        return path;
    }
};

// 使用示例
int main() {
    // 创建10x10的地图
    AStar astar(10, 10);

    // 设置障碍物
    astar.setWalkable(3, 3, false);
    astar.setWalkable(3, 4, false);
    astar.setWalkable(3, 5, false);

    // 获取起点和终点
    Node* start = &astar.grid[1][1];  // (1,1)
    Node* goal = &astar.grid[8][8];   // (8,8)

    // 寻找路径
    std::vector<Node*> path = astar.findPath(start, goal);

    // 输出路径
    if (!path.empty()) {
        std::cout << "找到路径：" << std::endl;
        for (Node* node : path) {
            std::cout << "(" << node->x << "," << node->y << ") ";
        }
        std::cout << std::endl;
    } else {
        std::cout << "未找到路径" << std::endl;
    }

    return 0;
}

展开

• 节点
  • 属性：位置，是否可走（非障碍物），代价，父节点指针（用于path追踪）
  • 构造：
  • 重载比较运算符，根据代价
• 工具
  • 重载相等运算符，根据节点位置
  • 启发函数
• Astart
  • 数据：网格（二维，宽高节点数量）
  • 网格生成器：new出来所有节点，并初始可走
  • 找到邻居（所有可行的）：循环4个方向，如果没有到达边界/不是障碍物/没有被访问过
  • 路径追踪：根据parent指针向起点回溯，用数组存储，最后反转结果
  • 搜索算法：
    • openSet优先队列（不同于bfs的队列）
    • closedSet无序集合，记录是否访问过
    • 将start加入到openSet
    • while，pq不为空
      • 取出top，并从openSet pop，加入到closedSet
      • 当找到end，路径追踪，并返回结果
      • 找到所有邻居，并循环，计算代价，如果邻居代价g>当前节点代价g，则加入openSet
• main
  • 网格生成
  • 设置障碍物
  • 搜索算法
  • 打印输出路径

bfs

• 广度优先搜索
• 数据结构：队列
• 二维矩阵图/四连通图：（和树层级遍历差不多）
  • 首先将当前位置加入到队列
  • while队列不为空，遍历当前队列每个节点，每次弹出
  • 如果找到结果就停止
  • 对每个节点，遍历4个方向节点，如果未超过边界/未被访问过，就加入到队列
• 适用场景：找最短路径（当首次找到目标，能保证找到的是最短路径（找到的是深度最少的路径））