Java A*（A星）算法优化
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/21161416/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
A* (A star) algorithm optimization
提问by Bartosz Wygl?dacz
I'm a student and me and my team have to make a simulation of student's behaviour in a campus (like making "groups of friends") walking etc. For finding path that student has to go, I used A* algorithm (as I found out that its one of fastest path-finding algorithms). Unfortunately our simulation doesn't run fluently (it takes like 1-2 sec between successive iterations). I wanted to optimize the algorithm but I don't have any idea what I can do more. Can you guys help me out and share with me information if its possible to optimize my A* algorithm? Here goes code:
我是一名学生，我和我的团队必须模拟学生在校园中的行为（例如结交“朋友小组”）步行等。为了找到学生必须走的路，我使用了 A* 算法（因为我发现它是最快的寻路算法之一）。不幸的是，我们的模拟运行不流畅（在连续迭代之间需要 1-2 秒）。我想优化算法，但我不知道我还能做些什么。如果有可能优化我的 A* 算法，你们能帮助我并与我分享信息吗？代码如下：
public LinkedList<Field> getPath(Field start, Field exit) {
LinkedList<Field> foundPath = new LinkedList<Field>();
LinkedList<Field> opensList= new LinkedList<Field>();
LinkedList<Field> closedList= new LinkedList<Field>();
Hashtable<Field, Integer> gscore = new Hashtable<Field, Integer>();
Hashtable<Field, Field> cameFrom = new Hashtable<Field, Field>();
Field x = new Field();
gscore.put(start, 0);
opensList.add(start);
while(!opensList.isEmpty()){
int min = -1;
//searching for minimal F score
for(Field f : opensList){
if(min==-1){
min = gscore.get(f)+getH(f,exit);
x = f;
}else{
int currf = gscore.get(f)+getH(f,exit);
if(min > currf){
min = currf;
x = f;
}
}
}
if(x == exit){
//path reconstruction
Field curr = exit;
while(curr != start){
foundPath.addFirst(curr);
curr = cameFrom.get(curr);
}
return foundPath;
}
opensList.remove(x);
closedList.add(x);
for(Field y : x.getNeighbourhood()){
if(!(y.getType()==FieldTypes.PAVEMENT ||y.getType() == FieldTypes.GRASS) || closedList.contains(y) || !(y.getStudent()==null))
{
continue;
}
int tentGScore = gscore.get(x) + getDist(x,y);
boolean distIsBetter = false;
if(!opensList.contains(y)){
opensList.add(y);
distIsBetter = true;
}else if(tentGScore < gscore.get(y)){
distIsBetter = true;
}
if(distIsBetter){
cameFrom.put(y, x);
gscore.put(y, tentGScore);
}
}
}
return foundPath;
}
private int getH(Field start, Field end){
int x;
int y;
x = start.getX()-end.getX();
y = start.getY() - end.getY();
if(x<0){
x = x* (-1);
}
if(y<0){
y = y * (-1);
}
return x+y;
}
private int getDist(Field start, Field end){
int ret = 0;
if(end.getType() == FieldTypes.PAVEMENT){
ret = 8;
}else if(start.getX() == end.getX() || start.getY() == end.getY()){
ret = 10;
}else{
ret = 14;
}
return ret;
}
//EDIT
//编辑
This is what i got from jProfiler:
这是我从 jProfiler 得到的：
So getH is a bottlneck yes? Maybe remembering H score of field would be a good idea?
所以 getH 是一个瓶颈，是吗？也许记住领域的 H 分数会是一个好主意？
采纳答案by harold
A linked list is not a good data structure for the open set. You have to find the node with the smallest F from it, you can either search through the list in O(n) or insert in sorted position in O(n), either way it's O(n). With a heap it's only O(log n). Updating the G score would remain O(n) (since you have to find the node first), unless you also added a HashTable from nodes to indexes in the heap.
链表对于开放集来说不是一个好的数据结构。您必须从中找到 F 最小的节点，您可以在 O(n) 中搜索列表或在 O(n) 中的排序位置插入，无论哪种方式都是 O(n)。对于堆，它只是 O(log n)。更新 G 分数将保持 O(n)（因为您必须首先找到节点），除非您还添加了从节点到堆索引的 HashTable。
A linked list is also not a good data structure for the closed set, where you need fast "Contains", which is O(n) in a linked list. You should use a HashSet for that.
对于闭集来说，链表也不是一个好的数据结构，在那里你需要快速的“包含”，这是链表中的 O(n)。您应该为此使用 HashSet。
回答by Igor S.
- Find bottlenecks of your implementation using profiler . ex. jprofiler is easy to use
- Use threads in areas where algorithm can run simultaneously.
- Profile your JavaVM to run faster. Allocate more RAM
- 使用 profiler 查找实现的瓶颈。前任。jprofiler 易于使用
- 在算法可以同时运行的区域使用线程。
- 配置您的 JavaVM 以更快地运行。 分配更多内存
回答by Chriss
You can optimize the problem by using a different algorithm, the following page illustrates and compares many different aglorihms and heuristics:
您可以使用不同的算法优化问题，以下页面说明并比较了许多不同的算法和启发式：
- A*
- IDA*
- Djikstra
- JumpPoint
- ...
- 一种*
- 国际开发协会*
- 吉克斯特拉
- 跳跃点
- ...
回答by JakubT
a) As mentioned, you should use a heap in A* - either a basic binary heap or a pairing heap which should be theoretically faster.
a) 如前所述，您应该在 A* 中使用堆 - 基本的二元堆或理论上应该更快的配对堆。
b) In larger maps, it always happens that you need some time for the algorithm to run (i.e., when you request a path, it will simply have to take some time). What can be done is to use some local navigation algorithm (e.g., "run directly to the target") while the path computes.
b) 在较大的地图中，您总是需要一些时间来运行算法（即，当您请求路径时，它只需要花费一些时间）。可以做的是在计算路径时使用一些本地导航算法（例如，“直接运行到目标”）。
c) If you have reasonable amount of locations (e.g., in a navmesh) and some time at the start of your code, why not to use Floyd-Warshall's algorithm? Using that, you can the information where to go next in O(1).
c) 如果您有合理数量的位置（例如，在导航网格中）并且在您的代码开始时有一些时间，为什么不使用 Floyd-Warshall 算法？使用它，您可以获得 O(1) 中下一步的信息。
回答by Vikram Bhat
From your implementation it seems that you are using naive A* algorithm. Use following way:-
从您的实现来看，您似乎正在使用天真的 A* 算法。使用以下方式：-
A* is algorithm which is implemented using priority queue similar to BFS.
Heuristic function is evaluated at each node to define its fitness to be selected as next node to be visited.
As new node is visited its neighboring unvisited nodes are added into queue with its heuristic values as keys.
Do this till every heuristic value in the queue is less than(or greater) calculated value of goal state.
A*是使用类似于BFS的优先级队列实现的算法。
启发式函数在每个节点上进行评估，以定义其适合度被选为下一个要访问的节点。
随着新节点被访问，它的相邻未访问节点被添加到队列中，并将其启发式值作为键。
这样做直到队列中的每个启发式值都小于（或大于）目标状态的计算值。
回答by D.R.Bendanillo
I built a new pathfinding algorithm. called Fast* or Fastaer, It is a BFS like A* but is faster and efficient than A*, the accuracy is 90% A*. please see this link for info and demo.
我构建了一个新的寻路算法。称为 Fast* 或 Fastaer，它是一种类似于 A* 的 BFS，但比 A* 更快更高效，准确率为 90% A*。请参阅此链接以获取信息和演示。
https://drbendanilloportfolio.wordpress.com/2015/08/14/fastaer-pathfinder/
https://drbendanilloportfolio.wordpress.com/2015/08/14/fastaer-pathfinder/
It has a fast greedy line tracer, to make path straighter. The demo file has it all. Check Task manager when using the demo for performance metrics. So far upon building this the profiler results of this has maximum surviving generation of 4 and low to nil GC time.
它有一个快速贪婪的线跟踪器，使路径更直。演示文件包含所有内容。使用演示时检查任务管理器以获取性能指标。到目前为止，在构建此分析器的结果中，最大幸存代为 4，GC 时间低至零。
