Question

根据这一理论执行A*算法:

create the open list of nodes, initially containing only our starting node
   create the closed list of nodes, initially empty
   while (we have not reached our goal) {
       consider the best node in the open list (the node with the lowest f value)
       if (this node is the goal) {
           then we re done
       }
       else {
           move the current node to the closed list and consider all of its neighbors
           for (each neighbor) {
               if (this neighbor is in the closed list and our current g value is lower) {
                   update the neighbor with the new, lower, g value 
                   change the neighbor s parent to our current node
               }
               else if (this neighbor is in the open list and our current g value is lower) {
                   update the neighbor with the new, lower, g value 
                   change the neighbor s parent to our current node
               }
               else this neighbor is not in either the open or closed list {
                   add the neighbor to the open list and set its g value
               }
           }
       }
   }

现在有两个优先事项公开名单和封闭名单的询问。

在从开放名单到封闭名单之后,如果邻国也被列入封闭名单并从事上述行动,就必须建立其邻国,相互核对。问题只能是 pe头,与产生邻国相比。我也能够接触到 que子的其余部分,以便进行比较。

我的问题是:

how can i compare the neighbours to the nodes in the closed list. Or should i use a different data structure for the closed list?

感谢

Answer 1

优先程度主要的不利之处是,它只是保证“什么是第一个要素”,对任何其他要素没有任何保障[除非是“先是”的,否则],因此,找到一个要素是一种权宜之计。

You can use a TreeSet to store your states, and then finding the elements will be done in O(logn) time, instead the O(n) PriorityQueue offers. You can use the first() method to get the first [lowest] element. To modify an element, you will need first to remove the original [will probably require an additional HashMap:State->value to store the current value] and then to insert the new node, with its modified value
Note that you will probably have to rewrite equals() for your nodes.

还注意到: 虽然这两条均为<代码>O(logn),但每一条在<代码>TreeSet上的运行通常较慢,在<代码>Priority Queue上的等值则比较低,因此,如果你的问题没有需要重新说明,这一解决办法实际上可能较慢。然而,在一般情况下,由于缩短了寻求时间,预计这一选择会更快。

Answer 2

Store a value on each node that indicates if it is in the open list, closed list, or no list, then you don t have to go through the lists to see if it is or not.

而正如其他人所指出的,你可能从执行自己的肥皂中取得最佳成果,因为 j的实施显然缺乏在 no子上更新关键价值的能力。

Answer 3

What is the structure of your search space? If it s a path though a grid, you can use a grid to find a node "by positions". To update the F cost of the "potentially re-parented node" that is on the open-list you need operations that Java s standard PriorityQueue class does not support (namely UpdateKey, and the nodes have to know their index in the heap so UpdateKey can find them), so you d have to roll your own heap (which is relatively easy).

友情链接