Menu
When searching in a tree, my understanding of uniform cost search is that for a given node A, having child nodes B,C,D with associated costs of (10, 5, 7), my algorithm will choose C, as it has a lower cost. After expanding C, I see nodes E, F, G with costs of (40, 50, 60). It will choose 40, as it has the minimum value from both 3.
Now, isn't it just the same as doing a Greedy-Search, where you always choose what seems to be the best action?
Also, when defining costs from going from certain nodes to others, should we consider the whole cost from the beginning of the tree to the current node, or just the cost itself from going from node n to node n'?
Thanks
356
Uniform-cost search (UCS) expands the node with lowest path cost (i.e. with the lowest g(n)), whereas best-first search (BFS) expand the node with closest to the goal. UCS cannot deal with a heuristic function, whereas BFS can deal with a heuristic function.
UCS uses the evaluation function f(n)=g(n), where g(n) is the length of the path from the starting node to n, whereas A* uses the evaluation function f(n)=g(n)+h(n), where g(n) means the same thing as in UCS and h(n), called the "heuristic" function, is an estimate of the distance from n to the goal node.
2 Answers. It is true that both the methods have a list of expanded nodes but Best-first search tries to minimize the expanded nodes using both the path cost and heuristic function. Uniform-cost search is uninformed search whereas Best-first search is informed search.
Greedy best-first search expands nodes with minimal h(n). It is not optimal, but is often efficient. A* search expands nodes with minimal f(n)=g(n)+h(n).
Nope. Your understanding isn't quite right.
The next node to be visited in case of uniform-cost-search would be D, as that has the lowest total cost from the root (7, as opposed to 40+5=45).
Greedy Search doesn't go back up the tree - it picks the lowest value and commits to that. Uniform-Cost will pick the lowest total cost from the entire tree.
141
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
