0

IDDFS アルゴリズムは、隣接行列を使用してグラフの最短経路を見つけます。ソリューションの深さを示しています (これは、開始点から終了点までのポイントの量であると理解しています)。
これらのポイントを配列で取得したいと思います。

例:
解が深さ 5 で見つかったとしましょう。そのため、点を持つ配列が必要です: {0,2,3,4,6}。
深さ 3: 配列 {1,2,3}。

C++ のアルゴリズムは次のとおり
です。

int DLS(int node, int goal, int depth,int adj[9][9])
{
    int i,x;

    if ( depth >= 0 )
    {
        if ( node == goal )
            return node;

        for(i=0;i<nodes;i++)
        {
            if(adj[node][i] == 1)
            {
                child = i;
                x = DLS(child, goal, depth-1,adj);

                if(x == goal)
                    return goal;
            }
        }
    }
    return 0;
}

int IDDFS(int root,int goal,int adj[9][9])
{
    depth = 0;
    solution = 0;
    while(solution <= 0 && depth < nodes)
    {
        solution = DLS(root, goal, depth,adj);
        depth++;
    }
    if(depth  == nodes)
        return inf;

    return depth-1;
}

int main()
{
    int i,u,v,source,goal;

int adj[9][9] = {{0,1,0,1,0,0,0,0,0},
       {1,0,1,0,1,0,0,0,0},
       {0,1,0,0,0,1,0,0,0},
       {1,0,0,0,1,0,1,0,0},
       {0,1,0,1,0,1,0,1,0},
       {0,0,1,0,1,0,0,0,1},
       {0,0,0,1,0,0,0,1,0},
       {0,0,0,0,1,0,1,0,1},
       {0,0,0,0,0,1,0,1,0}
    };

    nodes=9;
    edges=12;

    source=0;
    goal=8;

    depth = IDDFS(source,goal,adj);

    if(depth == inf)printf("No solution Exist\n");
    else printf("Solution Found in depth limit ( %d ).\n",depth);

    system("PAUSE");
    return 0;
}

他のパス検索アルゴリズムの代わりに IDDFS を使用している理由は、正確な長さのパスを検索するために深さを指定された数に変更したいからです (ただし、それが機能するかどうかはわかりません)。

隣接行列を使用して指定された長さのパスを見つけるための他のアルゴリズムを誰かが提案する場合は、それについて教えてください。

4

1 に答える 1

1

パスファインディング アルゴリズムから取得した実際のパスを取得するという考え方は、キーが頂点であり、値がキーを発見するために使用される頂点であるようなものを使用することです (ソースはキーではないか、値map:V->Vを持つキーにはなりません)。null、どの頂点からも発見されていないため)。

パスファインディング アルゴリズムは、実行中にこのマップを変更し、完了すると、ターゲットからソースに至るまで、テーブルから繰り返し読み取ることでパスを取得できます。逆の順序でパスを取得できます。 .

DFSでは(key,value)、新しい頂点 ( ) を発見するたびにペアを挿入しますkey。keyがすでにマップ内のキーで ある場合は、このブランチをスキップする必要があることに注意してください。
特定のパスの探索を終了し、頂点を「閉じる」場合は、リストから削除する必要がありますが、アルゴリズムを最適化してこの部分をスキップできる場合があります (分岐係数が小さくなります)。

IDDFS は実際には DFS を反復的に実行しているため、同じロジックに従うだけで、新しい DFS 反復を作成するたびに、古いマップをクリアして、新しいマップを最初から開始できます。

他の経路探索アルゴリズムは、BFS、A*、およびダイクストラのアルゴリズムです。最後の 2 つは加重グラフにも適合することに注意してください。これらはすべて、IDDFS で特定の深度に達すると DFS が終了するのと同じように、特定の深度に到達すると終了する可能性があります。

于 2012-06-03T17:33:27.130 に答える