I am reading Artificial Intelligence: A Modern Approach.
In Chapter 3, Section 3.3.1, The best-first search algorithm is introduced. We learn that in each iteration, this algorithm chooses which node to expand based on minimizing an evaluation function, $f(n)$, for new nodes. And if the expanded nodes are either not already reached, or they generate a less costly path to a reached state, they will be added to the frontier. So, the kind of queue used in the best-first search is a priority queue, i.e., ordering nodes by the function $f(n)$. If we set the $f(n)$ as the depth of the nodes, the queue type will be changed to FIFO (first-in-first-out), which is used in the breadth-first search algorithm.
Therefore, we can change the nature of algorithms using the $f(n)$ function.
I am wondering what would happen if we set $f(n)$ as the cost of the paths taken from the common parent node of new nodes to each new node $n$. Since new nodes might stem from different previous nodes, we might have to measure the cost of these nodes' path all the way back till we find a common parent of them (which, in the worst case, is the root node, indicating the initial state). In this way, each time a new node is chosen for expansion (using $f(n)$), and each time an expanded node is chosen for joining the frontier (using cost function), the choice is taken by the similar criterion since $f(n)$ and the cost function is now identical.
What would be the nature of such an algorithm? Is measuring the cost of paths to new nodes computationally feasible? Can this be a practical algorithm?
I read later sections and realized that the Dijkstra’s algorithm (uniform-cost search) is so similar to what I had in mind. However, it sets the evaluation function as the cost of the path from the root to the current node. I proposed grouping new nodes by their common parent and compare the cost of nodes within a certain group first. Then, after selecting out best nodes in each group, form a new group based on the selected nodes' new common parent, and do this until we reach the root node, when we will have the last group and comparing costs within that group will find the optimal node for us.
Would the algorithm I have in mind have any advantage over Dijkstra's algorithm?
