algorithm - 最佳首次搜索如何决定等距离节点？

Question

我正在处理这个任务，但我对接下来最好的第一个搜索移动哪个节点感到困惑。使用曼哈顿距离，我发现所有直接连接到起始节点的节点具有相同的距离。我的问题是，因为它是 BFS 并且应该使用曼哈顿距离作为评估函数。BFS 将如何决定接下来要探索的节点。

标签： algorithmsearchmanhattan

Answer 1

const getHeuristic = (row, col) => {
    return Math.abs(end.row - row) + Math.abs(end.col - col);
};

const NEIGHBORS = [
    [-1, 0],
    [0, 1],
    [1, 0],
    [0, -1],
];

const visitNeighbors = (node) => {
    let { row, col } = node;
    NEIGHBORS.forEach((neighbor) => {
        let r = row + neighbor[0];
        let c = col + neighbor[1];
        if (checkIndexes(matrix, r, c)) {
            //check to see if the neighbors of this node don't cause out of bounds issues. Like edge nodes.
            let cost = getHeuristic(r, c);
            pQueue.insert({ row: r, col: c, cost });
        }
    });
};

let begin = {
        row: start.row,
        col: start.col,
        cost: 0,
    };

pQueue.insert(begin);

while (pQueue.size() > 0) {
    let cell = pQueue.pop();
    if (isEquals(cell, end)) {
        //handle when end is found. If you want to trace the path, the use a map to keep track of the parent node when you explore its children.
return;
    }
    visitNeighbors(cell);
}

对于最佳优先搜索，

1. 您将使用一个启发式函数来最好地估计从当前节点到目标的距离。对于曼哈顿距离，该函数可能是：Math.abs(goal.row - current.row) + Math.abs(goal.col - current.col). 在这里，您获取当前正在处理的节点和目标节点的行值和列值之间的差异，并将它们的绝对值相加。

2. 然后，您将有一个优先队列，您可以在其中添加邻居以及到达它们的启发式成本。

3. 您将根据启发式值从优先级队列中删除成本最低的节点，并探索其每个邻居并计算启发式成本以到达这些节点并推送到优先级队列等等，直到您到达结束节点。

如果节点的估计距离相等，那么您选择的任何一个节点都会产生正确的结果。最佳优先搜索不保证最短路径。但是要回答您的问题，如果它们具有相同的成本，则不需要有决胜局，只需从优先级队列中删除即可，无论删除的内容仍然是正确的。如果您需要最短路径，请查看 A-Star 算法。

PS为了进一步澄清，在评论中提问，你不应该创建一个答案来提出另一个问题/澄清。