1
$\begingroup$

I am reading AI: 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 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?

Edit: I read later sections and realized 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 to the Dijkstra's algorithm?

$\endgroup$
1
  • 1
    $\begingroup$ Hello. You can format your math symbols with latex/mathjax on this site, so I suggest you edit your post to do it to improve its clarity. $\endgroup$ – nbro Apr 23 at 11:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.