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星)寻路算法，例如Wikipedia上所述:

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.

据我了解(大部分来自Wikipedia文章)，需要在打开的列表上进行的操作如下:

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分数作为排序标准
• 因此，将节点添加到这种数据结构是有问题的:如何最佳地检查是否存在不存在具有相似坐标集(但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.

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

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

对堆的任何更新都可以将自身更新(这需要堆知道哈希表，因此这是侵入性的，而不仅仅是两个现成实现的包装器)与更新次数一样的哈希表同步(每个O(1)，显然)是堆中移动的项目数，当然，只有 log n 个项目才能移动以进行插入，remove-min或update-key.哈希表在堆中找到要更新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屋！