免责声明：我真的相信这不是类似问题的重复。我读过这些内容，他们（大多数）建议使用堆或优先级队列。我的问题更多的是“我不明白这些在这种情况下如何运作”。
简而言之：
我指的是典型的 A*（A-star）寻路算法，如维基百科上所述（例如）：
https://en.wikipedia.org/wiki/A*_search_algorithm https://en.wikipedia.org/wiki/A*_search_algorithm
更具体地说，我想知道使用什么是最好的数据结构（可以是单个众所周知的数据结构，或它们的组合），这样您就不会在算法的任何操作上获得 O(n) 性能要求在开放清单上做。
据我了解（主要来自维基百科文章），需要对打开列表进行的操作如下：
此列表中的元素必须是具有以下属性的 Node 实例：
- 位置（或坐标）。为了便于讨论，假设这是一个值范围为 0 到 64516 的正整数（我将 A* 区域大小限制为 254x254，这意味着任何坐标集都可以在 16 位上进行位编码）
- F 分数。这是正浮点值。
鉴于这些，操作是：
- 将节点添加到打开列表中：如果存在具有相同位置（坐标）的节点（但可能具有不同的 F 分数），则替换它。
- 从打开列表中检索（并删除）F 分数最低的节点
- （检查是否存在并）从列表中检索给定位置（坐标）的节点
据我所知，使用堆或优先级队列作为打开列表的问题是：
- 这些数据结构将使用F-score作为排序标准
- 因此，向这种数据结构添加节点是有问题的：如何最佳地检查具有相似坐标集（但 F 分数不同）的节点是否已存在。此外，即使您能够以某种方式进行此检查，如果您确实找到了这样的节点，但它不在堆/队列的顶部，如何以最佳方式删除它以使堆/队列保持其正确的顺序
- 此外，检查是否存在并根据位置删除节点并不是最佳的，甚至是不可能的：如果我们使用优先级队列，我们必须检查其中的每个节点，如果找到则删除相应的节点。对于堆来说，如果需要这样的删除，我想所有剩余的元素都需要被提取并重新插入，以便堆仍然是堆。
- 这种数据结构唯一有效的剩余操作是当我们想要删除 F 分数最低的节点时。在这种情况下，运算时间复杂度为 O(Log(n))。
此外，如果我们创建一个自定义数据结构，例如使用哈希表（以位置为键）和优先级队列的数据结构，我们仍然会有一些操作需要对其中任何一个进行次优处理：为了使它们保持同步（两者都应该具有相同的节点），对于给定的操作，该操作在其中一种数据结构上总是次优的：按位置添加或删除节点在哈希表上会很快，但在优先级队列上会很慢。删除 F 分数最低的节点在优先级队列上会很快，但在哈希表上会很慢。
我所做的是为使用其位置作为键的节点创建一个自定义哈希表，该哈希表还跟踪具有最低 F 分数的当前节点。添加新节点时，它会检查其 F 分数是否低于当前存储的最低 F 分数节点，如果是，则替换它。当您想要删除一个节点（无论是按位置还是按 F 得分最低的节点）时，此数据结构就会出现问题。在这种情况下，为了更新保存当前最低 F 分数节点的字段，我需要迭代所有剩余节点，以找到现在哪一个具有最低 F 分数。
所以我的问题是：有没有更好的方法来存储这些？
您可以将哈希表和堆结合起来，而不会出现缓慢的操作。
将哈希表映射位置到堆中的索引而不是节点。
对堆的任何更新都可以将自身（这需要堆了解哈希表，因此这是侵入性的，而不仅仅是两个现成实现的包装器）同步到哈希表，并具有尽可能多的更新（每个 O( 1），显然）作为堆中移动的项目数，当然只是log n项目可以因插入、删除最小或更新键而移动。哈希表找到节点（在堆中）来更新 A* 的父更新/G 更改步骤的键，因此速度也很快。
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
