algorithm - A* 找到第二条最短路径

Question

我正在尝试使用 A* 寻路算法实现第 2 条，最好是第 n 条最短路径。我已经实现了最短路径:

while(open.length > 0) {
    max = worldSize;
    min = -1;
    for(i in open) {
        if(open[i].f < max) {
            max = open[i].f;
            min = i;
        }
    }

    node = open.splice(min, 1)[0];
    if(node.value === nodeEnd.value) {
        path = closed[closed.push(node)-1];
        do {
            result.push({x: path.x, y:path.y});
        } while(path = path.parent);
            open = closed = astar = [];
        result.reverse();
    } else {
        neighbors = findNeighbors(node.x, node.y);
        for(i = 0; i < neighbors.length; ++i) {
            path = newNode(node, neighbors[i]);
            if(!astar[path.value]) {
                path.g = node.g + manhattanDistance(neighbors[i], node);
                path.f = path.g + manhattanDistance(neighbors[i], nodeEnd);
                open.push(path);
                astar[path.value] = true;
            }

        }
        closed.push(node);
    }   
}

我能做什么？我在这方面的经验为零，甚至不完全理解算法(目前仍在研究)。谢谢。

Answer 1

所以这个问题一般来说是NP难的。由于您只需要第二条最短路径，因此可以轻松完成。基本上，给定最短路径，您可以通过获取原始图并从最短路径中删除一条边来生成一组图。所以如果你有一条长度为 N 的最短路径，在图 G(E,N) 上，你最终会得到 G(E-1,V) 的 N 个图。现在你在这些图的每一个上运行 A*，最短的是你的第二个最短路径，因为它是与原始最短路径至少有一条边不同的最短路径。

这也说明了为什么它在实践中是 NP 难的。如果我想要第三条最短路径，我必须按照以下过程只从两条最短路径中的每条路径中删除一条边，这样的对的数量呈指数增长。 N->N^2->N^3 等