What are the differences between the uniform-cost search (UCS) and greedy best-first search (GBFS) algorithms? How would you convert a UCS into a GBFS?
$\begingroup$
$\endgroup$
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
0
In the case of UCS, the evaluation function (that is, the function that is used to select the next node to expand) is $f(n) = g(n)$, where $g(n)$ is the cost of the path from the initial node to $n$, while in the case of the greedy BFS it is $f(n) = h(n)$, where $h(n)$ is the heuristic function that estimates the cost of the path from $n$ to the goal node. In other words, in the case of UCS, nodes are expanded only using the experience (in the form of $g(n)$), while, in the case of GBFS, nodes are expanded only using the estimate of the cost to the goal. Note that, in both cases, the node that is chosen to be expanded is the one with the smallest $f(n)$ value.