8
$\begingroup$

The name of Uniform-cost search in computer science is not instinctive since what part of it being "uniform" is not clear to me. Apparently uniformity is not about the cost of each edge - most of the examples handle edges with various costs. Can someone explain? Thank you.

(Hope this question is appropriate here. FAQ page at Theoretical Computer Science - Stack Exchange, a research level CS community, indicates that theoretical CS question can be asked here.)

$\endgroup$
2
  • $\begingroup$ RE cstheory FAQ: Well, ComputerScience.SE has gone beta! You can join and post your question there! $\endgroup$
    – user2468
    Mar 7, 2012 at 19:28
  • $\begingroup$ @J.D. thanks, I just got a notification too. For this particular question I've already made myself satisfied. $\endgroup$
    – IsaacS
    Mar 8, 2012 at 1:17

3 Answers 3

3
$\begingroup$

The article "Artificial Intelligence - Uniform Cost Search (UCS)" by Siddharth Agrawal (http://algorithmicthoughts.wordpress.com/2012/12/15/artificial-intelligence-uniform-cost-searchucs/) claims that the reason why it is called uniform cost search is because at any given point in time, the priority queue is filled with path costs that are mostly uniform. From the article:

"The elements in the priority queue have almost the same costs at a given time, and thus the name Uniform Cost Search. It may seem as if the elements don’t have almost the same costs ... but when applied on a much larger graph it is certainly so."

This may be a feasible explanation. The costs in the priority queue for DFS will range from nothing all the way to the cost of reaching the deepest node. If we consider BFS on a weighted graph, it is certainly possible to have paths of greatly varying costs, even though we only have two levels of depth OPEN at a time.

Cost and heuristic are two separate measurements (a heuristic is supposed to be an estimate of the cost), so it doesn't seem that it would make sense to call it "uniform cost" if the word uniform was referring to the heuristic.

$\endgroup$
1
$\begingroup$

Trying to answer to my own question. Correct me if wrong.

I think I need to think about 2 types of concept in search so-called un-informed and informed search, and (here I'm skipping much explanation about fundamentals though) Uniformed Search (don't get confused) can be considered as "uninformed" version of A* search, i.e. return of heuristic function is equal to zero. This zero informed cost might have us call it as uniformed.

This naming is not really intuitive, because the reason it's called as uninformed is based on the heuristic function's cost, not on the path-cost which is the main comparison criteria when you talk about un-informed search.

$\endgroup$
2
  • $\begingroup$ @templatetypedef That's the OP answering his/her own question! $\endgroup$
    – user2468
    Mar 7, 2012 at 19:29
  • $\begingroup$ Great question! Possibly the correct answer! Does this mean that uniform cost search is called "uniform" as it has a "uniform heuristic" ? By that notion, all un-informed searches like BFS, DFS, etc are also uniform searches ? Is it correct to say that ? $\endgroup$
    – Garfield
    Oct 14, 2012 at 19:35
1
$\begingroup$

I believe it is probably because of the way UCS proceeds. An easy way to visualize the progression of UCS is to draw contours in the state space similar to the contours found in topographical maps, except that instead of them representing the points of equal elevation, they represent the "region" in which the path cost is always lower than some particular value. Here is an example of such a contour map (taken from Alan Blair's lecture):

A state space representation of the Map of Romania problem from Russell & Norvig where the contour lines showing how UCS would progress in it can be clearly seen

In UCS, the search contours progress uniformly as a circle. For example, if at some point you expanded a node with a path-cost of R1, then UCS would only move to expanding nodes with cost greater than R1 if all the nodes with path-costs lesser then or equal to R1 have already been expanded. After expanding all such nodes, UCS will, for example, expand a node with a cost of R2, where R2 > R1, and then, again, before expanding any node with a cost greater than R2, UCS will first expand all the nodes with a cost lesser than or equal to R2. So, you can imagine the search as progressing in the form of uniform, circular contours of radii R1 and R2:

The red circle in the center is the root node

This is probably why, I believe, this is called "Uniform" Cost Search. For contrast, the search contours of A* search are generally not uniform. For example:

A state space representation of the Map of Romania problem from Russell & Norvig where the contour lines show the progress of A* search

$\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.