javascript - A星算法: Slow Implementation

Question

我正在研究 A-Star 算法在 JavaScript 中的实现。它可以工作，但是需要花费大量时间在两个非常接近的点之间创建路径:(1,1) 到 (6,6) 需要几秒钟。我想知道我的算法犯了哪些错误以及如何解决这些错误。

我的代码:

Node.prototype.genNeighbours = function() {
    var right = new Node(this.x + 1, this.y);
    var left = new Node(this.x - 1, this.y);
    var top = new Node(this.x, this.y + 1);
    var bottom = new Node(this.x, this.y - 1);
    this.neighbours = [right, left, top, bottom];
}

AStar.prototype.getSmallestNode = function(openarr) {
    var comp = 0;
    for(var i = 0; i < openarr.length; i++) {
        if(openarr[i].f < openarr[comp].f) comp = i
    }
    return comp;
}

AStar.prototype.calculateRoute = function(start, dest, arr){
var open = new Array();
var closed = new Array();

start.g = 0;
start.h = this.manhattanDistance(start.x, dest.x, start.y, dest.y);
start.f = start.h;
start.genNeighbours();
open.push(start);
while(open.length > 0) {
    var currentNode = null;
    this.getSmallestNode(open);
    currentNode = open[0];
    if(this.equals(currentNode,dest)) return currentNode;
    currentNode.genNeighbours();
    var iOfCurr = open.indexOf(currentNode);
    open.splice(iOfCurr, 1);
    closed.push(currentNode);
    for(var i = 0; i < currentNode.neighbours.length; i++) {
        var neighbour = currentNode.neighbours[i];
        if(neighbour == null) continue;
        var newG = currentNode.g + 1;
        if(newG < neighbour.g) {
            var iOfNeigh = open.indexOf(neighbour);
            var iiOfNeigh = closed.indexOf(neighbour);
            open.splice(iOfNeigh, 1);
            closed.splice(iiOfNeigh,1);
        }
        if(open.indexOf(neighbour) == -1 && closed.indexOf(neighbour) == -1) {
            neighbour.g = newG;
            neighbour.h = this.manhattanDistance(neighbour.x, dest.x, neighbour.y, dest.y);
            neighbour.f = neighbour.g + neighbour.h;
            neighbour.parent = currentNode;
            open.push(neighbour);
        }
    }

}
}

编辑:我现在已经解决了这个问题。这是因为我只是调用:open.sort();它没有按节点的“f”值对节点进行排序。我编写了一个自定义函数，现在算法运行得很快。

Answer 1

我发现的一些错误:

• 您的一组开放节点没有以任何方式构建，因此检索距离最小的节点很容易。通常的选择是使用优先级队列，但按排序顺序插入新节点(而不是 open.push(neighbour))就足够了(首先)。
• 在您的 getSmallestNode 函数中，您可以在索引 1 处开始循环
• 您正在调用 getSmallestNode()，但根本不使用其结果。您每次只需要 currentNode = open[0]; (然后甚至搜索它的位置来拼接它!它是 0!)。对于队列，它只是 currentNode = open.shift()。

但是，最重要的事情(可能会出错)是您的 getNeighbors() 函数。每次调用时，它都会创建全新节点对象 - 以前闻所未闻的节点对象，并且您的算法(或其封闭集)不知道这些对象。它们可能与其他节点在网格中处于相同的位置，但它们是不同的对象(通过引用进行比较，而不是通过相似性进行比较)。这意味着indexOf将永远在闭合数组中找到那些新的邻居，并且它们将被一遍又一遍地处理。我不会尝试计算此实现的复杂性，但我猜它甚至比指数还要糟糕。

通常，A* 算法在已经存在的图上执行。 OOP getNeighbors 函数将返回对现有节点对象的引用，而不是创建具有相同坐标的新节点对象。如果需要动态生成图形，则需要一个查找结构(二维数组？)来存储和检索已生成的节点。