A*，开放列表的最佳数据结构是什么? [英] A*, what's the best data structure for the open list?

问题描述

免责声明:我真的相信这不是类似问题的重复.我读过这些，他们(大部分)推荐使用堆或优先级队列.我的问题更多是我不明白在这种情况下它们会如何工作".

Disclaimer: I really believe that this is not a duplicate of similar questions. I've read those, and they (mostly) recommend using a heap or a priority queue. My question is more of the "I don't understand how those would work in this case" kind.

简而言之:

我指的是典型的 A*(A 星)寻路算法，如(例如)维基百科所述:

I'm referring to the typical A* (A-star) pathfinding algorithm, as described (for example) on Wikipedia:

https://en.wikipedia.org/wiki/A*_search_algorithm

更具体地说，我想知道什么是最好的数据结构(可以是一个众所周知的数据结构，也可以是这些结构的组合)，这样您就不会在任何操作上获得 O(n) 性能算法需要在打开列表上做的事情.

More specifically, I'm wondering about what's the best data structure (which can be a single well known data structure, or a combination of those) to use so that you never have O(n) performance on any of the operations that the algorithm requires to do on the open list.

据我了解(大部分来自维基百科的文章)，需要对open list进行的操作如下:

As far as I understand (mostly from the Wikipedia article), the operations needed to be done on the open list are as follows:

此列表中的元素必须是具有以下属性的 Node 实例:

The elements in this list need to be Node instances with the following properties:

• 位置(或坐标).为了便于论证，假设这是一个从 0 到 64516 范围内的正整数(我将我的 A* 区域大小限制为 254x254，这意味着任何一组坐标都可以在 16 位上进行位编码)
• F 分数.这是正浮点值.

鉴于这些，操作是:

• 向打开列表添加一个节点:如果存在具有相同位置(坐标)的节点(但可能具有不同的 F 分数)，则替换它.
• 从开放列表中检索(并删除)具有最低 F 分数的节点
• (检查是否存在并)从列表中检索给定位置(坐标)的节点

据我所知，对打开列表使用堆或优先队列的问题是:

As far as I can see, the problem with using a Heap or Priority Queue for the open list are:

• 这些数据结构将使用 F-score 作为排序标准
• 因此，向这种数据结构添加节点是有问题的:您如何以最佳方式检查具有相似坐标集(但 F 分数不同)的节点是否已经存在.此外，即使您以某种方式能够进行此检查，如果您确实找到了这样一个节点，但它不在堆/队列的顶部，如何以最佳方式删除它，以便堆/队列保持其正确的顺序
• 此外，根据节点的位置检查节点是否存在并删除它不是最佳的，甚至是不可能的:如果我们使用优先队列，我们​​必须检查其中的每个节点，如果找到则删除相应的节点.对于一个堆，如果需要这样的移除，我想所有剩余的元素都需要被提取并重新插入，这样堆仍然是一个堆.
• 当我们想要删除具有最低 F 分数的节点时，唯一剩余的操作是这样的数据结构是好的.在这种情况下，操作将是 O(Log(n)).

此外，如果我们制作自定义数据结构，例如使用哈希表(以位置为键)和优先队列的数据结构，我们仍然会有一些操作需要对其中任何一个进行次优处理:为了保持它们同步(两者都应该有相同的节点)，对于给定的操作，该操作在其中一个数据结构上总是次优的:按位置添加或删除节点在 Hashtable 上会很快，但在 Priority 上会很慢队列.删除 F 值最低的节点在优先级队列上会很快，但在哈希表上会很慢.

Also, if we make a custom data structure, such as one that uses a Hashtable (with position as key) and a Priority Queue, we would still have some operations that require suboptimal processing on either of these: In order to keep them in sync (both should have the same nodes in them), for a given operation, that operation will always be subomtimal on one of the data structures: adding or removing a node by position would be fast on the Hashtable but slow on the Priority Queue. Removing the node with the lowest F score would be fast on the Priority Queue but slow on the Hashtable.

我所做的是为使用它们的位置作为键的节点创建一个自定义哈希表，它还跟踪具有最低 F 分数的当前节点.添加新节点时，它会检查其 F 分数是否低于当前存储的最低 F 分数节点，如果是，则替换它.当您想要删除节点时(无论是按位置还是最低的 F 得分)，此数据结构的问题就出现了.在这种情况下，为了更新保存当前最低 F 分数节点的字段，我需要遍历所有剩余的节点，以找到现在哪个节点的 F 分数最低.

What I've done is make a custom Hashtable for the nodes that uses their position as key, that also keeps track of the current node with the lowest F score. When adding a new node, it checks if its F score is lower than the currently stored lowest F score node, and if so, it replaces it. The problem with this data structure comes when you want to remove a node (whether by position or the lowest F scored one). In this case, in order to update the field holding the current lowest F score node, I need to iterate through all the remaining node in order to find which one has the lowest F score now.

所以我的问题是:有没有更好的方法来存储这些?

So my question is: is there a better way to store these ?

推荐答案

您可以将哈希表和堆结合起来，而不会出现慢速操作.

You can combine the hash table and the heap without slow operations showing up.

将哈希表的位置映射到堆中的索引而不是节点.

Have the hash table map position to index in the heap instead of node.

对堆的任何更新都可以将其自身(这需要堆知道哈希表，因此这是侵入性的，而不仅仅是两个现成实现的包装)同步到具有尽可能多的更新的哈希表(每个 O(1)，显然) 作为在堆中移动的项目数，当然只有 log n 项目可以移动以进行插入、删除最小或更新键.哈希表找到节点(在堆中)以更新 A* 的父更新/G 更改步骤的键，这样也很快.

Any update to the heap can sync itself (which requires the heap to know about the hash table, so this is invasive and not just a wrapper around two off-the-shelf implementations) to the hash table with as many updates (each O(1), obviously) as the number of items that move in the heap, of course only log n items can move for an insertion, remove-min or update-key. The hash table finds the node (in the heap) to update the key of for the parent-updating/G-changing step of A* so that's fast too.

这篇关于A*，开放列表的最佳数据结构是什么?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！