c++ - 广度优先搜索修剪和内存泄漏 C++

Question

我正在做一个项目，需要我解决一个你不能左转的迷宫。该程序运行良好，但输入非常大的情况除外。

我的一般策略是让图中迷宫中的每个点都有 4 个节点，分别对应上、下、左和右，其中每个节点都有一条边直向右，直线的权重为 0 和右权重为 1。边在我的代码中表示为一个对象，并且有一个指向目标节点及其起始节点的指针。

为了找到最佳路径(右转最少的路径)，我使用了带有双端队列的广度优先搜索。我使用双端队列能够将权重为 1 的节点推到后面，将权重为 0 的节点推到前面。但是，我在搜索期间分配了少量内存并且没有在任何地方清理它，这可能导致我的程序在非常大的迷宫输入中失败。

这是代码(特别是用于检查 BFS 中节点相邻边缘的 for 循环):

    //t is a node object in the graph that has been popped out of the deque

    //loop that checks each adjacent node from t (adj is a vector of edges)
    for(unsigned int i = 0; i < t.adj.size(); i++)
    {
        if(!t.adj[i].used)
        {
            if(!t.adj[i].dest->visited)
            {
                //Memory leak location
                t.adj[i].dest->prev = new node(t);

                t.adj[i].used = true;

                //weight of an edge is 1 if it's a right turn, 0 otherwise
                if(t.adj[i].weight == 1) 
                {
                    //put the heavier nodes on the end of the queue
                    nodes.push_back(t.adj[i].dest);
                }
                //0-weight nodes on the top
                else nodes.push_front(t.adj[i].dest);                
            }

        }

我一直在尝试找出如何更好地修剪搜索以及如何在我绝对不再需要这些节点时释放此分配。但是我需要一些指导来思考这个问题。让我知道是否需要额外的代码。

谢谢。

编辑:节点和边缘类(请原谅我无视标准类设计原则，只是快速将它们放在一起):

class node
{
public:
    node();
    node(Direction d, int r, int c, NodeType t);
    ~node(); //empty definition
    node(const node* n);
    node(const node& n);
    node& operator=(const node& n);
    node& operator=(const node* n);

    void addAdj(node* a, int w);
    void printAdj() const;
    string direction() const;

    void print() const;
    bool operator<(const node& n) const;


    int distance; //from start
    bool visited;
    node* prev;
    vector<Edge> adj;
    Direction dir;
    int row, col;
    NodeType type;
};
///////////////////////
struct Edge
{

    Edge();
    Edge(node* o, node* d, int c);

    node* org;
    node* dest;
    int weight;
    bool used;

};

Answer 1

如果 node 接受一个指向 t 的指针(这样你就不需要 t 类型的完整定义(node?) 用于 node::adj[]::dest::prev 的声明并按值获取 node(而不是动态分配)对于 t.adj[i].dest->prev?

这将确保您不会泄漏内存，因为您没有动态分配任何东西。缺点是一旦 t 超出范围，您需要确保没有通过 dest::prev 引用 t。

在这种情况下，您将更改行

t.adj[i].dest->prev = new node(t);

到

t.adj[i].dest->prev = node(&t);

您将需要一个特殊值来表示无效的 prev(之前为 NULL)。也许使用 node(NULL)？

备选方案:使用共享指针(如果您不使用 C++11，则 BOOST 提供一个选择)以确保在所有引用都消失时自动释放。您将必须确保您不会永远保留循环引用，以防止“僵尸”节点(不会再次使用的节点，但由于仍有对它们的引用而无法解除分配)的释放