I am reading [AI: A Modern Approach][1]. 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 best-first search is a *priority queue*, i.e., ordering nodes by the function **f(n)**. If we set the **f(n)** as 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 at the worst case is the root node, indicating initial state). In this way, each time a new node is chosen for expanding (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 algorithm? Is measuring cost of paths to new nodes computationally feasible? Can this be a practical algorithm?


  [1]: http://aima.cs.berkeley.edu/index.html