代码之家 › 专栏 › 技术社区 › user1559625

奈特最短路径图数据结构与算法

search-tree chess shortest-path data-structures algorithm

0

user1559625 · 技术社区 · 12 年前

我对上一篇Stack Overflow文章有一个问题@ Knight's Shortest Path on Chessboard

我理解关于“好吧,这是一个图形问题,它的稀疏矩阵是这样的”的回答:

(a1,b3)=1,
(a1,c2)=1,
  .....

其描述现有的边缘。然而,我仍然不知道这个图的数据结构应该是什么样子(它是邻接矩阵吗?上面称为“稀疏矩阵”,还是其他什么?),这样Dijkstra的算法就可以很容易地使用它。

从算法描述来看,如果图数据结构是一组顶点,并且具有可用的相邻顶点信息,则看起来很方便。但我们如何做到这一点呢?

如何为该图写出示例数据结构?我正在寻求了解如何将其方便地与Dijkstra的算法联系起来。

2 回复 | 直到 4 年前

1

2

amit 12 年前

图是非常稀疏的(64个顶点,每个顶点最多有8条边),因此邻接矩阵是浪费的IMO。

更好的结构是 adjacency list 以下为:

v1->v2,v3,v4,v5
v2->v1,...
...

这个想法确实是为了 Set<Vertex> ,以及 Vertex 键入以具有领域以下为: List<Vertex> neighbors ,它将包含顶点的所有相邻顶点。

在这种情况下,不需要一些额外的权重信息,因为图是未加权的。

此外- Dijkstra的算法是多余的 在这里。同样,图是未加权的,因此找到最短路径的更简单(编程和理解)、更快(运行时)的算法是 BFS 对于未加权的图。

2

0

user555045 12 年前

由于只有64个瓦片,您可以方便地将邻接矩阵放入64个整数的数组中,每个整数64位。当然,它很稀疏,但也很小,所以如果它存在的话(指针与单个比特相比相当大),浪费也会很小。

从位向量中提取索引列表在稀疏时也特别容易,但是 你根本不需要 -您可以让前面是一个位向量队列,而“已访问”集可以是一个单独的位向量。

编辑:好吧,如果你使用这个技巧,实际上你可能仍然需要它,但它仍然只需要一些快速操作,如位扫描和 x &= x -1 。