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*和dijkstra 算法。请注意，最后 2 个也适用于加权图。所有这些都可以在达到一定深度时终止，就像在 IDDFS 中达到一定深度时终止 DFS 一样。

于 2012-06-03T17:33:27.130 回答