how does a best first search decide on equal distance nodes?

Question

am working on this assignment but am confused on which node will the best first search move next. using Manhattan distance, I found that all the nodes which are directly connected to the starting node have the same distance. my question is that since it is s BFS and am supposed to use Manhattan distance as evaluation function. how will the BFS decide which node to explore next.

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);
}

For Best-first search,

1. You would use a heuristic function that best estimates the distance to goal from current node. For Manhattan distance, that function could be: Math.abs(goal.row - current.row) + Math.abs(goal.col - current.col). Here you take the different between the row values and column values of node you are currently processing and your goal node and add their absolute values together.

2. You would then have a priority queue in which you add the neighbors along with heuristic cost to get to them.

3. You would remove the least costing node from the priority queue based on the heuristic value and explore each of its neighbors and calculate heuristic cost to get to those nodes and push to the priority queue and so on until you reach the end node.

If the estimated distances of nodes are equal, then either node you choose will produce the correct result. Best First Search doesn't guarantee the shortest path. But to answer your question, you don't need to have a tie breaker if they have the same cost, just remove from priority queue, whatever gets removed is still correct. If you need the shortest path, then look into A-Star algorithm.

P.S. for further clarification, ask in the comments, you shouldn't create an answer to ask another question/clarification.