A*，open list最好的数据结构是什么？
A*, what's the best data structure for the open list?
免责声明：我真的相信这不是类似问题的重复。我读过那些，他们（大部分）建议使用堆或优先队列。我的问题更多是 "I don't understand how those would work in this case" 类的。
简而言之：
我指的是典型的 A*（A 星）寻路算法，如维基百科上（例如）所述：
https://en.wikipedia.org/wiki/A*_search_algorithm
更具体地说，我想知道最好的数据结构是什么（它可以是一个众所周知的数据结构，也可以是它们的组合），这样你就不会在任何方面都有 O(n) 的性能算法需要在open list上做的操作。
据我了解（大部分来自维基百科文章），open list需要做的操作如下：
此列表中的元素需要是具有以下属性的 Node 实例：
- 位置（或坐标）。为了论证，假设这是一个正整数，范围从 0 到 64516（我将我的 A* 区域大小限制为 254x254，这意味着任何一组坐标都可以在 16 位上进行位编码）
- F 分。这是正浮点值。
鉴于这些，操作是：
- 将节点添加到开放列表：如果存在具有相同位置（坐标）的节点（但可能具有不同的 F 分数），则替换它。
- 从开放列表中检索（并删除）F 分数最低的节点
- （检查是否存在并）从列表中检索给定位置（坐标）的节点
据我所知，对打开列表使用堆或优先队列的问题是：
- 这些数据结构将使用 F-score 作为排序标准
- 因此，向这种数据结构中添加一个节点是有问题的：如何以最佳方式检查具有相似坐标集（但 F 分数不同）的节点是否已经存在。此外，即使您以某种方式能够进行此检查，如果您确实找到了这样一个节点，但它不在 Heap/Queue 的顶部，您如何最佳地删除它使得 Heap/Queue保持正确的顺序
- 此外，检查节点是否存在并根据其位置删除节点不是最优的，甚至是不可能的：如果我们使用优先队列，我们必须检查其中的每个节点，如果找到则删除相应的节点。对于一个堆，如果需要这样的移除，我想是要把所有剩下的元素都抽出来重新插入，这样堆还是堆。
- 唯一适合这种数据结构的操作是当我们想要删除 F 分数最低的节点时。在这种情况下，操作将是 O(Log(n)).
此外，如果我们制作自定义数据结构，例如使用哈希表（以位置作为键）和优先级队列的数据结构，我们仍然会有一些操作需要对其中任何一个进行次优处理：为了为了使它们保持同步（两者都应该有相同的节点），对于给定的操作，该操作在其中一个数据结构上总是次优的：按位置添加或删除节点在哈希表上会很快但在哈希表上会很慢优先队列。删除具有最低 F 分数的节点在优先级队列上会很快，但在哈希表上会很慢。
我所做的是为使用它们的位置作为键的节点创建一个自定义哈希表，它还跟踪具有最低 F 分数的当前节点。在添加新节点时，它会检查其 F 分数是否低于当前存储的最低 F 分数节点，如果是，则将其替换。当您想要删除一个节点时（无论是按位置还是按 F 得分最低的节点），此数据结构就会出现问题。在这种情况下，为了更新保存当前最低 F 分数节点的字段，我需要遍历所有剩余的节点，以便找到现在哪个节点的 F 分数最低。
所以我的问题是：有没有更好的方法来存储这些？
您可以组合散列 table 和堆，而不会出现缓慢的操作。
将散列 table 映射位置到 堆中的索引 而不是节点。
对堆的任何更新都可以自行同步（这需要堆知道散列 table，因此这是侵入式的，而不仅仅是两个现成实现的包装器）到散列table 与堆中移动的项目数一样多的更新（显然每个 O(1)），当然只有 log n 项目可以移动以进行插入、删除-min 或更新-钥匙。散列 table 找到节点（在堆中）以更新 A* 的 parent-updating/G-changing 步骤的密钥，所以这也很快。
免责声明：我真的相信这不是类似问题的重复。我读过那些，他们（大部分）建议使用堆或优先队列。我的问题更多是 "I don't understand how those would work in this case" 类的。
简而言之：
我指的是典型的 A*（A 星）寻路算法，如维基百科上（例如）所述：
https://en.wikipedia.org/wiki/A*_search_algorithm
更具体地说，我想知道最好的数据结构是什么（它可以是一个众所周知的数据结构，也可以是它们的组合），这样你就不会在任何方面都有 O(n) 的性能算法需要在open list上做的操作。
据我了解（大部分来自维基百科文章），open list需要做的操作如下：
此列表中的元素需要是具有以下属性的 Node 实例：
- 位置（或坐标）。为了论证，假设这是一个正整数，范围从 0 到 64516（我将我的 A* 区域大小限制为 254x254，这意味着任何一组坐标都可以在 16 位上进行位编码）
- F 分。这是正浮点值。
鉴于这些，操作是：
- 将节点添加到开放列表：如果存在具有相同位置（坐标）的节点（但可能具有不同的 F 分数），则替换它。
- 从开放列表中检索（并删除）F 分数最低的节点
- （检查是否存在并）从列表中检索给定位置（坐标）的节点
据我所知，对打开列表使用堆或优先队列的问题是：
- 这些数据结构将使用 F-score 作为排序标准
- 因此，向这种数据结构中添加一个节点是有问题的：如何以最佳方式检查具有相似坐标集（但 F 分数不同）的节点是否已经存在。此外，即使您以某种方式能够进行此检查，如果您确实找到了这样一个节点，但它不在 Heap/Queue 的顶部，您如何最佳地删除它使得 Heap/Queue保持正确的顺序
- 此外，检查节点是否存在并根据其位置删除节点不是最优的，甚至是不可能的：如果我们使用优先队列，我们必须检查其中的每个节点，如果找到则删除相应的节点。对于一个堆，如果需要这样的移除，我想是要把所有剩下的元素都抽出来重新插入，这样堆还是堆。
- 唯一适合这种数据结构的操作是当我们想要删除 F 分数最低的节点时。在这种情况下，操作将是 O(Log(n)).
此外，如果我们制作自定义数据结构，例如使用哈希表（以位置作为键）和优先级队列的数据结构，我们仍然会有一些操作需要对其中任何一个进行次优处理：为了为了使它们保持同步（两者都应该有相同的节点），对于给定的操作，该操作在其中一个数据结构上总是次优的：按位置添加或删除节点在哈希表上会很快但在哈希表上会很慢优先队列。删除具有最低 F 分数的节点在优先级队列上会很快，但在哈希表上会很慢。
我所做的是为使用它们的位置作为键的节点创建一个自定义哈希表，它还跟踪具有最低 F 分数的当前节点。在添加新节点时，它会检查其 F 分数是否低于当前存储的最低 F 分数节点，如果是，则将其替换。当您想要删除一个节点时（无论是按位置还是按 F 得分最低的节点），此数据结构就会出现问题。在这种情况下，为了更新保存当前最低 F 分数节点的字段，我需要遍历所有剩余的节点，以便找到现在哪个节点的 F 分数最低。
所以我的问题是：有没有更好的方法来存储这些？
您可以组合散列 table 和堆，而不会出现缓慢的操作。
将散列 table 映射位置到 堆中的索引 而不是节点。
对堆的任何更新都可以自行同步（这需要堆知道散列 table，因此这是侵入式的，而不仅仅是两个现成实现的包装器）到散列table 与堆中移动的项目数一样多的更新（显然每个 O(1)），当然只有 log n 项目可以移动以进行插入、删除-min 或更新-钥匙。散列 table 找到节点（在堆中）以更新 A* 的 parent-updating/G-changing 步骤的密钥，所以这也很快。