1

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

我的总体策略是在图中将迷宫中的每个点设置为 4 个节点，分别对应于 UP、DOWN、LEFT 和 RIGHT，其中每个节点都有一条直线和向右的边，其中直线的权重为 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;

};

4

1 回答 1

1

如果node需要一个指向的指针t（因此您不需要t' 类型的完整定义（node？）对于node::adj[]::dest::prev' 的声明并按node值获取（而不是动态分配它）对于t.adj[i].dest->prev？

这将确保您不会泄漏内存，因为您没有动态分配任何东西。缺点是您需要确保没有对tvia dest::prevoncet的引用超出范围。

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

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

至

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

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

替代方案：使用共享指针（如果您不使用 C++11，BOOST 会提供一个选择）以确保在所有引用消失时自动解除分配。您必须确保不会永远保留循环引用，以防止释放“僵尸”节点（不会再次使用但无法释放的节点，因为仍然存在对它们的引用

于 2012-04-17T03:23:00.553 回答