Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It only takes a minute to sign up.
Sign up to join this community
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.)
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.
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.
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):
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:
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:
