我有一个Town类，用于表示图中的节点，如下所示：

class Town{public:    Town();public:    Town* _parent;    int _name;    int _row;    int _column;    State _state;    vector<Town*> _neighbors;};

我有一个Map类，它包含一个二维的Town向量，并且基本上构建了我的随机图。

class Map{public:    Map(const int elements, const int size, const int seed);public:     vector <vector<Town> > _map;    vector <Town*> _towns;    vector <vector<int> > _adjacency;    vector <vector<double> > _mDistance;    vector <Line> _edges;    const int _elements;    const int _size;    Town* _start;    Town* _exit;};

然后我的AI类接收一个Map对象，并根据算法解决它，目前我正在实现Astar算法。

class AI{private:    struct TownWithCost    {        Town town;        double cost;    };    struct OrderByTotalCost    {        bool operator()(TownWithCost lfs, TownWithCost rhs)        {            return lfs.cost > rhs.cost;        }    };public:    AI(Map map);private:    bool AStar(Town* town);    double GetTotalCost(Town town);public:    bool _success;private:    Map _map;};

这是我的Astar实现：

bool AI::AStar(Town* town){    AI::OrderByTotalCost comparator;    vector<TownWithCost> priorityQueue;    TownWithCost currentTown = { *town, 0 };    Town temp = currentTown.town;    priorityQueue.push_back(currentTown);    SetEnvironment(temp, State::visited);    while (!priorityQueue.empty())    {        currentTown = priorityQueue.front();        Town temp = currentTown.town;        priorityQueue.erase(priorityQueue.begin());        SetEnvironment(temp, State::visited);        PrintEnvironment();        if (temp._name == _map._exit->_name)        {            return true;        }        vector <Town*> neighbors = town->_neighbors;        for each (Town* neighbor in neighbors)        {            Town tempNeighbor = *neighbor;            if (tempNeighbor._state == State::town)            {                tempNeighbor._parent = &temp;                TownWithCost neighborWithCost = { tempNeighbor, GetTotalCost(tempNeighbor) };                priorityQueue.push_back(neighborWithCost);            }        }        make_heap(priorityQueue.begin(), priorityQueue.end(), comparator);    }    return false;}

你可能会注意到，我还没有实现查看priorityQueue中是否已经存在一个Town并比较成本以决定保留哪一个，但我计划在解决当前问题后实现这一点。

我的问题是，我不希望priorityQueue中包含指针。我试图创建临时变量来复制Town及其来自特定路径的成本。

假设我从Town 9开始。

9的邻居是0、7、8、3，具体来说，第一次循环时的priorityQueue看起来像这样：

然后我将3作为我的currentTown，并检查它的邻居。

当我第二次到达Town temp = currentTown.town;这行时，priorityQueue中每个元素的父节点都被设置为3。我明白为什么会发生这种情况，但我不知道如何防止这种情况发生。

我基本上需要priorityQueue存储相同的Town（不是相同的内存地址），但有不同的父节点和不同的成本（我已经通过TownWithCost结构处理了单独的成本）。所以总的来说，每次都需要创建副本。

例如，我可以直接从9到达0，总成本为81，但我也可以通过3到达0（9 -> 3 -> 0），总成本为50。我希望能够区分这两者。

我如何在priorityQueue中区分它们，以及我如何避免重置父节点，或者换句话说，我如何在每次循环运行时为Town temp分配另一块内存，以便每次都有不同的临时变量？

如果你有其他更适合新手的方法，请随时提出。

回答：

你以值的方式传递Map的实例，而这个类没有复制构造函数或赋值运算符。当这个类被浅拷贝（如memcpy）时，vector实例在被销毁时（多次）会导致崩溃。

尝试使用指针或引用。也会更快。