A-Star算法:慢实现

Question

我正在用javascript实现am算法.但是，它需要很长时间才能在两个非常接近的点之间创建一条路径：(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-function将返回对现有节点对象的引用，而不是创建具有相同坐标的新节点对象。如果需要动态生成图形，则需要一个查找结构(二维数组？)存储和检索已经生成的节点。