A* 迭代算法 c++

A* 迭代算法是 A* 算法的一种变体，它可以在不知道最优解路径代价的情况下，逐步增加 A* 搜索的深度，直到找到最优解为止。以下是 A* 迭代算法的 C++ 实现：

#include <iostream>
#include <vector>
#include <queue>
#include <limits>
#include <cmath>

using namespace std;

// 定义节点类
class Node {
public:
    int x, y;       // 节点的坐标
    double g, h;    // g 和 h 值
    Node *parent;   // 父节点
    Node(int _x, int _y) : x(_x), y(_y), g(0), h(0), parent(nullptr) {}
};

// 定义比较运算符，用于优先队列
struct CompareNode {
    bool operator()(Node *n1, Node *n2) {
        return n1->g + n1->h > n2->g + n2->h;
    }
};

// 定义 A* 算法的迭代版
Node* AStarIterative(vector<vector<int>>& grid, int start_x, int start_y, int end_x, int end_y, double w) {
    int max_depth = 100;    // 最大深度
    Node *result = nullptr; // 存储最优解
    for (int depth = 0; depth <= max_depth; depth++) {
        priority_queue<Node*, vector<Node*>, CompareNode> open_list; // 优先队列
        open_list.push(new Node(start_x, start_y)); // 将起点节点加入 open_list
        vector<vector<bool>> closed_list(grid.size(), vector<bool>(grid[0].size(), false)); // 标记是否已经探索过
        bool found = false; // 是否找到最优解
        while (!open_list.empty()) {
            Node* current = open_list.top(); // 取出 open_list 中 f 值最小的节点
            open_list.pop();
            if (current->x == end_x && current->y == end_y) { // 到达终点
                result = current;
                found = true;
                break;
            }
            if (closed_list[current->x][current->y]) { // 已经探索过该节点
                continue;
            }
            closed_list[current->x][current->y] = true; // 标记探索过该节点
            for (int dx = -1; dx <= 1; dx++) { // 遍历当前节点周围的节点
                for (int dy = -1; dy <= 1; dy++) {
                    if (dx == 0 && dy == 0) { // 不考虑当前节点本身
                        continue;
                    }
                    int new_x = current->x + dx;
                    int new_y = current->y + dy;
                    if (new_x < 0 || new_x >= grid.size() || new_y < 0 || new_y >= grid[0].size()) { // 节点越界
                        continue;
                    }
                    if (grid[new_x][new_y] == 1) { // 节点被占用
                        continue;
                    }
                    double new_g = current->g + sqrt(dx * dx + dy * dy); // 计算新节点的 g 值
                    double new_h = w * sqrt(pow(end_x - new_x, 2) + pow(end_y - new_y, 2)); // 计算新节点的 h 值
                    Node* neighbor = new Node(new_x, new_y);
                    neighbor->g = new_g;
                    neighbor->h = new_h;
                    neighbor->parent = current;
                    open_list.push(neighbor); // 将新节点加入 open_list
                }
            }
        }
        if (found) { // 找到了最优解
            break;
        }
    }
    return result; // 返回最优解
}

// 打印路径
void printPath(Node* end_node) {
    vector<Node*> path;
    Node* current = end_node;
    while (current != nullptr) {
        path.push_back(current);
        current = current->parent;
    }
    for (int i = path.size() - 1; i >= 0; i--) {
        cout << "(" << path[i]->x << ", " << path[i]->y << ")";
        if (i != 0) {
            cout << " -> ";
        }
    }
    cout << endl;
}

int main() {
    vector<vector<int>> grid = {
        {0, 0, 0, 0, 0},
        {0, 1, 0, 1, 0},
        {0, 1, 0, 0, 0},
        {0, 1, 1, 1, 0},
        {0, 0, 0, 0, 0},
    };
    Node* end_node = AStarIterative(grid, 0, 0, 4, 4, 1.2);
    if (end_node != nullptr) {
        printPath(end_node);
    } else {
        cout << "No path found!" << endl;
    }
    return 0;
}

在上述代码中，AStarIterative函数是 A* 迭代算法的实现，它接收一个二维矩阵grid表示地图，起点的x坐标start_x和y坐标start_y，终点的x坐标end_x和y坐标end_y，以及一个权重参数w。在 A* 迭代算法中，我们需要设置一个最大深度max_depth，表示最大搜索深度。在每次迭代中，我们都会增加搜索深度，直到找到最优解或者达到最大深度为止。

AStarIterative函数首先创建一个优先队列open_list，用于存储待扩展的节点。然后将起点节点加入open_list中。接下来创建一个二维矩阵closed_list，用于标记哪些节点已经探索过。在每次循环中，我们取出open_list中f值最小的节点，并将其从open_list中删除。如果该节点是终点，说明找到了最优解，我们将该节点返回。否则，我们标记该节点已经被探索过，并遍历其周围的节点。对于每个周围的节点，如果它已经被探索过或者被占用，我们就跳过它。否则，我们计算该节点的g值和h值，并将其加入open_list中。在计算g值时，我们使用欧几里得距离公式，计算h值时，我们使用权重参数w来调整估价函数的权重。

最后，我们在main函数中调用AStarIterative函数，并打印最优解的路径。