algorithm - 使用 IDDFS 创建路径数组

Question

我的 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 而不是其他寻路算法的原因是我想将深度更改为指定的数字以搜索精确长度的路径(但我不确定这是否可行)。

---

如果有人建议使用邻接矩阵查找指定长度路径的其他算法，请告诉我。

Answer 1

从寻路算法中获取实际路径的想法是使用 map:V->V 这样键是一个顶点，值是用于发现路径的顶点键(源不是键，也不是具有 null 值的键，因为它不是从任何顶点发现的)。

寻路算法将在运行时修改此 map ，当它完成时 - 您可以通过迭代地从表中读取来获取您的路径 - 从目标开始 - 一直到源 - 然后您获得您的路径以相反的顺序。

在DFS :每次发现新顶点(即key)时，都插入(key,value) 对。请注意，如果 key 已经是映射中的键 - 您应该跳过此分支。
一旦你完成探索某条路径，并“关闭”一个顶点，你需要将它从列表中取出，但是 - 有时你可以优化算法并跳过这部分(它会使分支因子更小)。

由于 IDDFS 实际上是迭代地进行 DFS，因此您可以遵循相同的逻辑，每次进行新的 DFS 迭代时 - 为了获得更高的深度，您可以清除旧 map ，并从头开始新 map 。

其他寻路算法是BFS , A*和 dijkstra's algorithm .请注意，最后 2 个也适用于加权图。所有这些都可以在达到一定深度时终止，就像在 IDDFS 中达到一定深度时终止 DFS 一样。