A星算法：实施缓慢

Question

我正在 javascript 中实现 A-Star 算法。它可以工作，但是在两个非常靠近的点之间创建路径需要花费大量时间：(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 节点集没有以任何方式构建，因此很容易检索距离最小的节点。通常的选择是使用优先级队列，但按排序顺序插入新节点（而不是 open.push(neighbour)）就足够了（一开始）。
在您的 getSmallestNode 函数中，您可以在索引 1
您正在调用 getSmallestNode()，但根本没有使用其结果。每次只取currentNode = open[0];（然后还要找位置拼接！是0！）。使用队列，它只是 currentNode = open.shift().

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

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

A星算法：实施缓慢

A-Star Algorithm: Slow Implementation

javascript

a-star