A *算法:关闭列表包含太多元素/太大 [英] A* Algorithm: closed list contains too many elements / too large
本文介绍了A *算法:关闭列表包含太多元素/太大的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!
问题描述
我目前正在用JavaScript实现A *算法。但是,我遇到了一个问题:我的closedList似乎太大了。以下是输出的屏幕截图:
I'm currently implementing the A* algorithm in JavaScript. However, I've ran into a problem: My closedList seems way too large. Here is a screenshot of the output:
什么可能导致这个问题?我的启发式计算是错误的吗?
What could cause this problem? Is my heuristic calculation wrong?
Node.prototype.getHeuristic = function(pos0, pos1)
{
// Manhatten Distance
var horizontalDistance = Math.abs(pos1.x - pos0.x);
var verticalDistance = Math.abs(pos1.y - pos0.y);
return horizontalDistance + verticalDistance;
}
或者我在这个方法中理解/实现了什么错误?:
Or did I understand/implement something wrong in this method?:
PathFinder.prototype.findPath = function()
{
var start = new Date().getTime();
var openList = [];
var closedList = [];
var startNode = this.startNode;
var grid = this.grid;
var endNode = this.finishNode;
openList.push(startNode);
while (openList.length > 0)
{
var lowInd = 0;
for(var i = 0; i < openList.length; i++) {
if (openList[i].f < openList[lowInd].f)
{
lowInd = i;
}
}
var currentNode = openList[lowInd];
if (currentNode.x == endNode.x && currentNode.y == endNode.y)
{
var curr = currentNode;
var ret = [];
while (curr.parent)
{
ret.push(curr);
curr.type = NODES.PATH;
curr = curr.parent;
}
this.finishNode.type = NODES.FINISH;
this.printGrid();
console.log("Total Operations: " + this.operations);
var end = new Date().getTime();
var time = end - start;
console.log('Execution time: ' + time + "ms");
return true;
}
openList.splice(lowInd, 1);
closedList.push(currentNode);
if (currentNode.type != NODES.START)
{
currentNode.type = NODES.CLOSED;
}
var neighbors = currentNode.getNeighbors(this.grid);
for (var indexNeighbors = 0; indexNeighbors < neighbors.length; indexNeighbors++)
{
var neighbor = neighbors[indexNeighbors];
if (this.findNodeInArray(closedList, neighbor) || neighbor.isWall())
{
continue;
}
var gValue = currentNode.g + 1;
var isGvalueLowest = false;
if (!this.findNodeInArray(openList, neighbor))
{
isGvalueLowest = true;
neighbor.h = neighbor.getHeuristic(neighbor, endNode);
openList.push(neighbor);
}
else if (gValue < neighbor.g)
{
isGvalueLowest = true;
}
if (isGvalueLowest)
{
neighbor.parent = currentNode;
neighbor.g = gValue;
neighbor.f = neighbor.g + neighbor.h;
neighbor.type = NODES.MARKED;
console.log(neighbor);
this.operations++;
}
}
}
}
如果您想查看代码的更多部分,请告诉我。感谢您的帮助,谢谢。
If you want to see more parts of the code, just tell me. I appreciate any help, thank you.
推荐答案
您需要断开与端点的联系。
(不破坏与端点的联系)
(与端点断开关系)
(带障碍物的示例)
这篇关于A *算法:关闭列表包含太多元素/太大的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!
查看全文