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完全な定義は必要ありません。tnodenode::adj[]::dest::prevnodet.adj[i].dest->prev

これにより、動的に何も割り当てていないため、メモリリークが発生しなくなります。t欠点は、 via dest::prevonceへの参照tが範囲外であることを確認する必要があることです。

この場合、行を変更します

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 に答える