问：

我正在为尖峰时刻（游戏）编写一个 A* 算法，以便学习基础知识。为此，我编写了一个名为 的类，该类的实例也充当 A* 搜索的“节点”。Board

为了使算法起作用，我将 （） 可能的移动生成为新移动，并将它们作为子项（命名为 ）。generate_moves()Boardstd::priority_queuechildren

出于某种原因，当我决定从 mycontainer 中获取 时，它指向其父项 （） 的指针（之前在生成过程中分配）变成了指向自身的指针。Boardstd::priority_queue childrentop()Board* parent

1. 缩写功能：generate_moves()

"for each possible move do"
...
Board newBoard = Board();
...
newBoard.parent = this; // I understand 'this' to always point towards the function caller.
children.push(newBoard); // Priority queue of the current board
...

下图显示了从 root 进行单个节点扩展后函数（以 root 身份调用）中的调试过程，同时抓取第一个“子节点”： 在 top（） 之前 如您所见，优先级队列中的每个元素都有根父节点，其自己的父节点是“nullptr”（这是正确的，根节点没有父节点）。a_star()Boardopen

自定义分数比较类 比较优先级队列正如你所看到的，一切都已经搞砸了。从第一次比较开始，每个子项上的父项指针现在都指向自身，而不是 。parentnullptr

after top（） （板 currNode）在优先级队列退出后，该节点现在被搞砸了，有一个自引用的父节点。top()

after top（） （priority_queue打开）优先级队列中的每个优先级队列也是如此，有一个自引用的父级。Boardopen

我已经涉足这个问题很长时间了。任何帮助将不胜感激。如果您需要任何其他背景信息，请告诉我。

我试过：

• 替换为我自己的类型，但我最终处理了“const”必需值的问题，为此我最终创建了基本相同的类。priority_queue
• 将父指针作为构造函数参数提供。什么都没改变。
• 我没有使用 OPEN priority_queue的副本进行一些需要弹出的比较（我不想对原始节点这样做），我还尝试弹出原始节点，然后将节点推回，因为“复制”位可能是问题。什么都没改变。
• 我将比较功能从比较参考值 （） 更改为正常值 （），因为在比较过程中似乎发生了问题。什么都没改变。Board&Board

编辑：这是我对“最小可重复示例”的尝试。由于使用 rand（） 来简化某些函数，不确定是否一致，但它展示了完全相同的问题：

#pragma once
#include <iostream>
#include <bitset>
#include <vector>
#include <queue>
#include <stdexcept>

using namespace std;

class SimplifiedBoard {
public:
    bitset<36> board;
    class Compare {
    public:
        bool operator() (SimplifiedBoard& a, SimplifiedBoard& b) {
            return (a.fscore < b.fscore);
        }
    };
    int fscore;
    priority_queue<SimplifiedBoard, vector<SimplifiedBoard>, Compare> children;
    SimplifiedBoard* parent;

    SimplifiedBoard() {
        fscore = 0;
        parent = nullptr;
    }

    // Move generator
    void generateMoves() {
        int arbitraryChildren = 5;
        for (int i = 0; i < arbitraryChildren; i++) {
            SimplifiedBoard newBoard = SimplifiedBoard();
            newBoard.fscore = (int)rand() / 100;
            // Assign parent to child
            newBoard.parent = this;
            // Add new child
            children.push(newBoard);
        }
    }

    // A*
    vector<SimplifiedBoard> aStar(SimplifiedBoard& start) {
        priority_queue<SimplifiedBoard, vector<SimplifiedBoard>, Compare> open = {};
        vector<SimplifiedBoard> closed = {};
        start.fscore = 0;
        start.parent = nullptr;
        open.push(start);

        // Loop
        while (!open.empty()) {
            // ***BUG HAPPENS here (2nd cycle, after root node has been expanded and closed)****
            SimplifiedBoard currNode = open.top(); open.pop();
            if (currNode.parent != nullptr &&
                currNode.parent->parent != nullptr &&
                currNode.parent == currNode.parent->parent) {
                cout << "Self-referential bug!" << endl;
            }
            // *** Here, in 2nd cycle, currNode.parent suddenly references a node which references itself ***
            
            // Child generation. f,g,h scores and 'parent' assigned inside function
            currNode.generateMoves();

            // For each child check OPEN/CLOSE and and see if I add to OPEN
            auto childrenCopy = currNode.children;
            for (int i = 0; i < (int)currNode.children.size(); i++) {
                bool isWorse = false;
                SimplifiedBoard currChildNode = childrenCopy.top(); childrenCopy.pop();

                // Victory?
                if (currChildNode.isVictory()) {
                    closed.push_back(currChildNode);
                    // Path reconstruction
                    vector<SimplifiedBoard> path = {};
                    SimplifiedBoard currPathNode = currChildNode;
                    // Ciclo child->parent
                    while (currPathNode.parent != nullptr) {
                        path.push_back(currPathNode);
                        currPathNode = *currPathNode.parent;
                    }
                    // Insert root
                    path.push_back(currPathNode);
                    // Return path
                    return path;
                }
                // OPEN
                auto openCopy = open;
                for (int j = 0; j < (int)open.size(); j++) {
                    SimplifiedBoard currOpenNode = openCopy.top(); openCopy.pop();
                    if (currChildNode.fscore <= currOpenNode.fscore) {
                        isWorse = true; break;
                    }
                }
                if (isWorse) { continue; }

                // CLOSED
                for (int j = 0; j < (int)closed.size(); j++) {
                    ;
                    if (currChildNode.fscore <= closed[j].fscore) {
                        isWorse = true; break;
                    }
                }
                if (isWorse) { continue; }

                //
                open.push(currChildNode);
            }
            // Close the node
            closed.push_back(currNode);
        }
        // return empty if can't find goal
        return vector<SimplifiedBoard>();
    }

    // Check victory
    bool isVictory() {
        if ((int)rand() % 50 == 5) { return true; }
        else { return false; }
    }
};

int main() {
    // Debug_example
    srand((int)time(NULL));
    SimplifiedBoard b = SimplifiedBoard();
    cout << "If it gets stuck the bug is happening:" << endl;
    vector<SimplifiedBoard> res = b.aStar(b);
    for (int i = 0; i < (int)res.size(); i++) {
        cout << res[i].fscore << endl;
    }
}