我正在尝试在迷宫上实现 Floyd-Warshall 算法来计算从一个点到迷宫内所有其他点的距离。出于某种原因，当我使用k等于列和行之间最大值的 a 时，我得到的答案不正确。
k有没有办法用一个对于给定迷宫的所有长度都正确的值来解决这个问题？
换句话说，有没有办法将 Floyd-Warshall 算法用于非 n×n 矩阵？也就是说，对于 am×n 矩阵 where m!= n?
问问题
1653 次
4 回答
1
不。
您似乎对 Floyd-Warshall 算法中矩阵的用途感到困惑：对于迷宫中的两个位置 i,j，矩阵 A[i,j] 存储边 i -> j 的权重（如果没有边缘）。列和行都表示位置，对于非方阵来说是没有意义的。
如果您有一个大小为 M x N 的矩形迷宫，并且所有可能的地方都是可能的，那么 Floyd-Warshall 算法需要 (M*N) x (M*N) 矩阵。假设您只能朝 4 个方向前进，这确实是在浪费空间。
如果您想要一个 顶点的最短路径，请使用 Dijkstra 算法，它要快得多。如果边缘没有重量，更好的是，使用普通的 BFS。
于 2011-12-19T19:57:21.457 回答
1
如果迷宫属于狭窄通道类型（这很常见，并且可能是这里的情况），那么为每个单元格设置一个顶点是没有意义的，因为它会添加绝对不必要的顶点，而每条路径的成本都是相同的（未加权） .
为图形建模的正确方法是为每个交点（而不是角）分配一个顶点。IE。如果在任何时候选择在 3 或 4 个方向之间放置一个顶点。如果您只能前进或后退，则不要分配顶点。
即使对于大型迷宫，这也会产生相当紧凑的顶点数量。
接下来，一对顶点之间的路径的权重就是两个顶点之间的单独直接路径上的正方形数。这可以通过在顶点的最大四个方向中的每一个方向上并计算跳数来轻松计算。
因此，您从顶点和路径权重开始，我相信 Floyd-Warshall 将毫无问题地为您提供每对之间的最短路径长度。
矩阵将是 NxN（而不是 MxN 等）
编辑：此外，如果您的迷宫不是“狭窄通道”类型，并且您通常可以在所有四个方向上进行，那么使用 A*-search 或模拟退火或那组全局优化来代替 Floyd-Warshall 或图形算法算法。（A*-search 是我推荐的）
于 2011-12-19T20:10:14.790 回答
0
从Wikipedia article看来，似乎可以在非方阵上使用 Floyd-Warshall。我对算法的细节不够熟悉，无法解释如何解释，但我会继续研究它。
不过，根据我对迷宫的了解，我认为第一步是生成一个表示迷宫的图形，其中一个点的每个非墙“边缘”由 1 表示，每个墙由无穷大或一些非常大的数字表示.
于 2011-12-19T19:43:43.363 回答
0
我在这个算法中看不到你的问题的原因。据我所知，该算法在矩阵大小方面没有任何限制（注意：您可以使用任何图形！）。
维基百科的快速概览证实了我的猜测。
我只能认为您的实现或图形定义中可能存在错误。另外，你能有任何负循环吗？
于 2011-12-19T19:49:35.993 回答