如何存储优先级队列在执行 A* 搜索时遵循的完整路径

Question

我遇到了一个问题，我得到了用户输入的矩阵（行和列）。用户还将提供开始状态（行和列）和目标状态。作业是使用A*搜索找到从起始节点到目标节点的路径。

下面提供了示例矩阵，

0       0       0       0       0       0       0       0       0       0
0       0       0       1       1       0       0       0       0       G
0       0       0       1       1       0       0       0       1       1
0       0       0       0       0       0       0       0       0       0
0       1       1       0       0       0       0       0       0       1
0       0       0       0       0       0       0       0       1       0
0       0       0       0       0       1       1       0       0       0
0       0       0       0       0       1       1       0       0       0
0       1       0       1       0       1       1       0       0       0
0       1       0       1       0       1       1       0       0       0
0       0       0       0       0       0       0       0       0       0
S       0       0       0       0       0       0       0       0       0
0       1       0       0       0       1       1       0       0       0
0       0       0       0       0       1       1       0       0       0

其中“S”是起始状态，“G”是目标状态。 0 是您可以移动到的状态，1 是网格中的 障碍物 ，您不能移动到它们。允许 3 个操作。

向上一格（成本为 1）
右一格（成本为 3）
向右斜向上（成本为 2）

为了解决这个问题，我使用 曼哈顿的距离 作为我的启发式函数并计算了我所有状态的启发式值....它们看起来像这样（对于网格上面指定的）

10      9       8       7       6       5       4       3       2       1
9       8       7       6       5       4       3       2       1       0
10      9       8       7       6       5       4       3       2       1
11      10      9       8       7       6       5       4       3       2
12      11      10      9       8       7       6       5       4       3
13      12      11      10      9       8       7       6       5       4
14      13      12      11      10      9       8       7       6       5
15      14      13      12      11      10      9       8       7       6
16      15      14      13      12      11      10      9       8       7
17      16      15      14      13      12      11      10      9       8
18      17      16      15      14      13      12      11      10      9
19      18      17      16      15      14      13      12      11      10
20      19      18      17      16      15      14      13      12      11
21      20      19      18      17      16      15      14      13      12

现在，这是我的 A* 搜索代码

void A_search()
{
    priority_queue<node, vector<node>, CompareCost>q; // Priority Queue is used. 
    // node contains 4 elements... 1. "Heuristic" value, 2. Index row, 3. Index Col, 4. Actual Cost until this point
    q.push(node(heuristic[srow][scol], srow, scol, 0)); // srow, scol is start state. 0 is Actual Cost
    while (!q.empty())
    {
        node temp = q.top();
        path_cost = temp.cost; // path_cost is global variable, which stores actual cost until this point
        path[temp.i][temp.j] = true; // Boolean array, which tells the path followed so far. 
        q.pop();
        if (temp.i == grow && temp.j == gcol) // If goal state is found, we break out of the loop 
            break;
        if (temp.i > 0) // Checking for rows above the current state. 
        {
            if (arr[temp.i - 1][temp.j] != 1) // Checking if index above current state is obstacle or not 
            {
                q.push(node(heuristic[temp.i - 1][temp.j] + (temp.cost+1), temp.i - 1, temp.j, temp.cost + 1)); // pushing the above index into queue
            }
            if (temp.j - 1 < cols)
            {
                if (arr[temp.i - 1][temp.j + 1] != 1) // Diagonal Index checking 
                {
                    q.push(node(heuristic[temp.i - 1][temp.j + 1] + (temp.cost + 2), temp.i - 1, temp.j + 1, temp.cost + 2));
                }
            }
        }
        if (temp.j - 1 < cols) // Horizontal Index... Checking if column has exceeded the total cols or not
        {
            if (arr[temp.i][temp.j + 1] != 1) // Obstacle check for horizontal index
            {
                q.push(node(heuristic[temp.i][temp.j + 1] + (temp.cost + 3), temp.i, temp.j + 1, temp.cost + 3));
            }
        }
    }
}

这是我在运行这个算法之后得到的结果（请注意 # 代表程序采用的路径......我只是使用boolean 2D array 用于检查优先级队列正在访问哪些节点。仅对于这些索引，我正在打印 # 并且网格的其余部分仍然是相同）

0       0       0       0       0       #       #       #       #       #
#       #       #       1       1       #       #       #       #       G
#       #       #       1       1       #       #       #       1       1
#       #       0       #       #       #       #       #       0       0
#       1       1       #       #       #       #       0       0       1
#       #       #       #       #       #       #       0       1       0
#       #       #       #       #       1       1       0       0       0
#       #       #       #       0       1       1       0       0       0
#       1       #       1       0       1       1       0       0       0
#       1       #       1       0       1       1       0       0       0
#       #       0       0       0       0       0       0       0       0
S       0       0       0       0       0       0       0       0       0
0       1       0       0       0       1       1       0       0       0
0       0       0       0       0       1       1       0       0       0

Path Cost: 21

现在，从输出中可以明显看出，问题在于它存储了每个被访问的索引（因为所有索引的启发值差异非常小，这就是为什么几乎每个节点都被访问的原因。 . 然而，最终A*搜索找到了最佳路径，从“Path Cost: 21”可以看出，这是最优路径的实际成本)

考虑到路径成本，我相信我的算法是正确的，但我现在想要的是也存储最优路径的路径。为此，我想记录一条路径访问的所有索引（行和列）。

例如，我的路径从第 11 行，第 0 列

然后“最佳路径”转到，第 10 行，第 1 列 -> 当我将这些节点推入队列时，我也想存储“11、0”。这样，我就可以知道这个节点之前通过什么路径到达这个状态。

下面一样，然后会去，第 9 行，第 2 列 -> 因此，该节点还应在其中存储“11, 0”和“10, 1”，从而记录它到目前为止所走的路径。

这样下去，直到“目标”节点。但我似乎无法找到一种方法来实现这个东西，它可以跟踪每个节点所采用的所有路径。这样，我可以很容易地避免我面临的问题（我将简单地打印“目标节点”到达该点的路径，忽略所有不必要访问的其他节点）

任何人都可以帮我找到一个逻辑吗？

此外，需要说明的是，我的 class 节点 和 CompareCost 有这个实现，

class node
{
public:
    int i, j, heuristic, cost;
    node() { i = j = heuristic = cost = 0; }
    node(int heuristic, int i, int j, int cost) :i(i), j(j), heuristic(heuristic), cost(cost) {}
}; 
struct CompareCost {
    bool operator()(node const& p1, node const& p2)
    {
        return p1.heuristic > p2.heuristic;
    }
};

我猜我需要在我的“class 节点”中存储一些额外的东西，但我似乎无法弄清楚确切的东西。

Answer 1

像链接列表一样构建您的node：

class node
{
    public:
        int i, j, cost;
        node* next;
}

在class中添加显示完整路径的方法：

void ShowPath()
{
    Node* temp = this;

    do
    {
        if (temp != NULL)
        {
            std::cout << "(" << temp->i << ", " << temp->j << ")";
            temp = temp->next;
        }
    } while (temp != NULL);
}

最后，修改 A_search() 使其 return 成为新的 node 定义。然后，您可以在 return 值上调用 ShowPath()。

如何存储优先级队列在执行 A* 搜索时遵循的完整路径

How to store a complete path that a priority queue follows while performing A* search

c++

search

heuristics

graph

a-star