0

我正在尝试使用弗洛伊德的算法来生成一个通过具有 98 个航点（位于每个迷宫顶点）的迷宫的最快路线矩阵。当算法运行时，它会填充两个矩阵 - 距离矩阵（两个节点之间的最佳距离）和路径矩阵（下一个节点要转到任意两个节点之间的最佳路径）。

距离矩阵使用我在之前代码中生成的邻接矩阵进行初始化。我还生成了一个数据结构，其中包含指向每个航路点的四个可能的相邻航路点的指针，但我没有在生成路径矩阵时使用此数据结构。

这是我的 C# 代码：

        // Initialize distance path matrix
        distanceMatrix = adjacencyMatrix;

        // Initialize path matrix
        int N = (WaypointList.Count);
        pathMatrix = new int[N, N];

        for (int i = 0; i < N; i++)
            for (int t = 0; t < N; t++)
                pathMatrix[i,t] = t;

        // Floyd-Warshall algorithm            
        for (int k = 0; k < N; ++k)
            for (int i = 0; i < N; ++i)
                for (int j = 0; j <= i; ++j)
                {
                    int currentCombo = distanceMatrix[i, k] + distanceMatrix[k, j];
                    if (currentCombo < distanceMatrix[i, j])
                    {                            
                        distanceMatrix[j, i] = distanceMatrix[i, j] = currentCombo;
                        pathMatrix[j, i] = pathMatrix[i, j] = k;
                    }
                }

我相信我计算路径矩阵不正确，因为使用此代码生成的路径矩阵的机器人在大多数情况下都失败了（因为路径矩阵告诉要穿过墙等）。

我已经盯着这段代码看了好几个小时，我对自己做错了什么感到困惑。如何生成正确的路径矩阵以用于我的迷宫导航代码？

4

1 回答 1

1

设置时pathMatrix[i, j] = k，您假设这意味着从节点到的路径将从i节点j开始k。但实际上，这意味着从i到的路径j将k在某个时刻经过，不一定在第一步。

你需要做的是以下，假设有一个路径 from ito j：

target = j
while there is no edge from i to target:
    target = pathMatrix[i, target]

This will set target to the next node to go to from i.

于 2012-12-17T12:08:50.610 回答