1
$\begingroup$

By this possibly good attempt to explain this, the "uniformity" in the Uniform cost search is actually the uniformity of the heuristic function.

Is this explanation correct ? If yes, then don't all un-informed cost searches (like BFS, DFS, etc) have no heurstic and thus, be called as "uniform cost searches" ?

$\endgroup$
1
$\begingroup$

Truth to be told, I am not completely sure about my answer, so take it with a grain of salt:

Uniform Cost Search is just a variant of Best-First Search. Among other variants, take Breadth-First Search where $f(n)$ equals $d(n)$, its depth. This actually means that nodes are not treated uniformly since different paths to the same node might result very easily in different depths ---with different costs if the costs of the operators are different among them. Much the same happens with Depth-First Search where nodes are distinguished by the path that led to them.

What makes Uniform-Cost Search a uniform search is that nodes are distinguished just by $g(n)$ so that all paths that lead to a particular node n are considered to be equivalent (and they are indeed when seeking the optimal solution), with the first one (the one with the optimal value) being expanded, and all the others being discarded. In this regard, I would consider a number of Best-First Search variants, uniform such as $A^*$ where nodes are uniformly treated according to $f(n)=g(n)+h(n)$ with $h(n)$ being an admissible estimate.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.